解題思路：這道題利用了線段樹+位運算的思想，由于顏色的種類只有30種，所以int可以存下來，所以我們在線段樹的節點里面加上status的狀態信息，表示這段區間內的顏色信息，而且我們可以知道，父節點的status是兩個兒子節點的status異或得到的，同時為了能夠提高查找效率，還要設置一個信息cover，cover=1表示這段區間只有一種顏色，cover=0表示有多種顏色被覆蓋了，所以在找到cover=1的節點時直接回溯（因為子節點都是一種顏色，不需要再去查找）。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100005; struct Segment {int l,r;int status;int cover; }tree[maxn<<2]; int n,color,m;void build(int rt,int l,int r) {tree[rt].l = l, tree[rt].r = r;tree[rt].status = tree[rt].cover = 1;if(l == r) return;int mid = (l + r) >> 1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r); }void update(int rt,int l,int r,int val) {if(l <= tree[rt].l && tree[rt].r <= r){tree[rt].status = 1 << (val - 1);tree[rt].cover = 1;return;}if(tree[rt].cover){tree[rt<<1].cover = tree[rt<<1|1].cover = tree[rt].cover;tree[rt<<1].status = tree[rt<<1|1].status = tree[rt].status;tree[rt].cover = 0;}int mid = (tree[rt].l + tree[rt].r) >> 1;if(mid >= l) update(rt<<1,l,r,val);if(mid < r) update(rt<<1|1,l,r,val);tree[rt].status = tree[rt<<1].status | tree[rt<<1|1].status;if(tree[rt<<1].cover && tree[rt<<1|1].cover && tree[rt<<1].status == tree[rt<<1|1].status)tree[rt].cover = 1; }int query(int rt,int l,int r) {if(l <= tree[rt].l && tree[rt].r <= r)return tree[rt].status;if(tree[rt].cover) return tree[rt].status;int mid = (tree[rt].l + tree[rt].r) >> 1;int ans = 0;if(l <= mid) ans |= query(rt<<1,l,r);if(mid < r) ans |= query(rt<<1|1,l,r);return ans; }int main() {char ch;int a,b,c;while(scanf("%d%d%d",&n,&color,&m)!=EOF){build(1,1,n);while(m--){getchar();scanf("%c",&ch);if(ch == 'C'){scanf("%d%d%d",&a,&b,&c);if(a > b) swap(a,b);update(1,a,b,c);}else{scanf("%d%d",&a,&b);if(a > b) swap(a,b);int ans = query(1,a,b),sum = 0;for(int i = 0; i < color; i++)if(ans & (1 << i))sum++;printf("%d\n",sum);}}}return 0; }

總結

以上是生活随笔為你收集整理的poj 2777(线段树+区间染色)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。