|
|
  /**//*
 還是一個染色的覆蓋問題，修改一個區段的顏色，查詢一個區段有多少不同的顏色。
一開始用最原始的做法，修改，查詢，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);
}
}
}
}
|