| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
终于AC(附代码和注释)#include <iostream> #include <cstdio> #define N 400000+100 #define jh(x,y) x^=y^=x^=y/*这是两数交换*/ using namespace std; struct { int left; int right; int delta; int pained;//我用的是二进制来存储颜色信息 }tree[N]; int L, O, T; void pushdown(int p)//p点的delta需要向下传递,把下面的区间都染色 { if (tree[p].delta) { tree[p * 2].delta = tree[p * 2 + 1].delta = tree[p].delta; tree[p * 2].pained = tree[p * 2 + 1].pained = (1 << tree[p].delta); tree[p].delta = 0; } } int cou(int x)//计算颜色数 { int sum = 0; while (x) { if (x&1) ++sum; x >>= 1; } return sum; } void build(int p, int l, int r)//建树 { tree[p].pained = 2; tree[p].left = l; tree[p].right = r; if (l == r) return; int mid = (l + r) / 2; build(p * 2, l, mid); build(p * 2 + 1, mid + 1, r); } int getsum(int p, int l, int r)//得到l到r区间内的颜色状态 { if (tree[p].left == l && tree[p].right == r)return tree[p].pained;//直接返回该区间的颜色状态 pushdown(p);//向下更新 //底下就是线段树的基本操作了 int mid = (tree[p].left + tree[p].right) / 2; if (r <= mid)return getsum(2 * p, l, r); if (l>mid)return getsum(2 * p + 1, l, r); return getsum(2 * p, l, mid) | getsum(2 * p + 1, mid + 1, r);//左右区间的状态要合并 } void updata(int p, int l, int r, int data)//染色 { if (tree[p].left == l && tree[p].right == r)//找到区间的话直接染区间 { tree[p].pained = (1 << data); tree[p].delta = data;//记录下当前区间的颜色,为向下更新做准备 return; } pushdown(p);//向下更新 int mid = (tree[p].left + tree[p].right) / 2; if (r <= mid)updata(p * 2, l, r, data); else if (l>mid)updata(p * 2 + 1, l, r, data); else { updata(p * 2, l, mid, data); updata(p * 2 + 1, mid + 1, r, data); } tree[p].pained = tree[2 * p].pained | tree[2 * p + 1].pained; } int main(void) { scanf("%d%d%d", &L, &T, &O); build(1, 1, L); while (O--) { char s[2]; scanf("%s", s); if (*s == 'C') { int x, y, z; scanf("%d%d%d", &x, &y, &z); if (x>y)jh(x, y); updata(1, x, y, z); } else { int x, y; scanf("%d%d", &x, &y); if (x>y)jh(x, y); printf("%d\n", cou(getsum(1, x, y))); } } return 0; } /* 5 3 5 C 1 3 2 P 2 4 C 3 5 3 P 1 5 P 3 4 2 2 1 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator