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