|
|
  /**//*
 还是一个染色的覆盖问题，修改一个区段的颜色，查询一个区段有多少不同的颜色。
一开始用最原始的做法，修改，查询，TLE了，然后去上体育课，突然就想到一个优化，
由于颜色只有30种，所以可以把各种颜色的状态压缩到一个整数中，这样统计时就不用hash了
快了不少，哈哈！于是该线段树共有两个域，一个cover域，表明该区间下的颜色是单一的还是混合的，
还有一个计数域tree，该值表明该区间颜色的状态。
 */
 #include <iostream>
using namespace std;
int tree[1000010];
int cover[1000010];
int L, T, O;
int Build(int p, int l, int r)  {
  if(l == r) {
tree[p] = 1;
return 1;
 }
int mid = (l + r) / 2;
tree[2*p] = Build(2*p, l, mid);
tree[2*p+1] = Build(2*p+1, mid+1, r);
return tree[2*p] | tree[2*p+1];
}
int Update(int p, int a, int b, int l, int r, int color) {
if(cover[p] == color)
return tree[p];
if(a == l && r == b) {
cover[p] = color;
return ( 1<<(color-1) );
}
if(cover[p] >= 1) {
cover[ 2*p ] = cover[p];
cover[ 2*p+1 ] = cover[p];
tree[2*p] = tree[p];
tree[2*p+1] = tree[p];
cover[p] = -1;
}
int mid = (l + r) / 2;
if(b <= mid) {
tree[2*p] = Update(2*p, a, b, l, mid, color);
}else if(mid + 1 <= a) {
tree[2*p+1] = Update(2*p+1, a, b, mid+1, r, color);
}else {
tree[2*p] = Update(2*p, a, mid, l, mid, color);
tree[2*p+1] = Update(2*p+1, mid+1, b, mid+1, r, color);
}
return tree[2*p] | tree[2*p+1];
}
int Query(int p, int a, int b, int l, int r) {
if(cover[p] >= 1) {
return tree[p];
}
int mid = (l + r) / 2;
if(b <= mid) {
return Query(2*p, a, b, l, mid);
}else if(mid + 1 <= a){
return Query(2*p+1, a, b, mid+1, r);
}else {
int lef = Query(2*p, a, mid, l, mid);
int rig = Query(2*p+1, mid+1, b, mid+1, r);
return lef | rig;
}
}
int main() {
char str[10];
int x, y, z;
int coun, i;
while(scanf("%d %d %d", &L, &T, &O) != EOF) {
tree[1] = Build(1, 1, L);
for(i = 1; i <= 1000000; i++)
cover[i] = 1;
while(O --) {
scanf("%s", str);
if(str[0] == 'C') {
scanf("%d %d %d", &x, &y, &z);
if(x > y) {
int temp = x;
x = y;
y = temp;
}
tree[1] = Update(1, x, y, 1, L, z);
}else {
scanf("%d %d", &x, &y);
if(x > y) {
int temp = x;
x = y;
y = temp;
}
coun = 0;
int zty = Query(1, x, y, 1, L);
while(zty) {
if(zty & 1)
coun ++;
zty >>= 1;
}
printf("%d\n", coun);
}
}
}
}
|