poj2106，POJ 2777 Count Color （線段樹區間修改 + 狀態壓縮）

題目鏈接：POJ 2777 Count Color

【題目大意】

poj2106。給你 n 塊板子， 編號1--n ， 板子的顏色最多30種， 初始時? 板子的顏色都是 1；

有兩種操作?

????????????? 1 。把給定區間的板子染成一種顏色

????????????? 2 。查詢給定區間有多少種不同的顏色

線段樹區間修改。

此題一看便是線段樹的區間修改問題 ， 然而對于統計有多少種不同顏色 ， 開始想用set 來操作， 后來發現用set每次查詢都要走到樹的葉子節點，并不能運用線段樹的高效率查詢。 后來學到了 二進制狀態壓縮的方法 。（又是狀態壓縮，我怎么沒想到捏！）

30種顏色 ，我們用二進制來存 ， 每一位對于一種顏色即可。

線段樹維護區間最大值？【源代碼】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define L(m) m<<1
#define R(m) m<<1|1
using namespace std;
const int maxn = 100000+5;
int ans =0 ;
struct node{int l,r,color;bool setv; //懶惰標記
}tree[maxn<<2];
void Build(int m,int l,int r){tree[m].l=l ; tree[m].r=r;if(tree[m].l==tree[m].r){tree[m].color=1;tree[m].setv = 0; //不要忘了賦初值return ;}int mid = (l+r)>>1;Build(L(m),l,mid);Build(R(m),mid+1,r);tree[m].color = tree[L(m)].color | tree[R(m)].color; //回溯，也可以寫maintain(m);
}
void pushdown(int m){if(tree[m].l==tree[m].r) return;if(tree[m].setv){int tmp = tree[m].color;tree[L(m)].color = tree[R(m)].color = tmp;tree[L(m)].setv= true;tree[R(m)].setv= true;tree[m].setv = false;}
}
void maintain(int m){tree[m].color = tree[L(m)].color | tree[R(m)].color;
}
void Update(int m,int l,int r,int x){if(tree[m].l>=l && tree[m].r<=r){tree[m].setv = true;tree[m].color = (1<<(x-1)); //存入2的幾次方return ;}pushdown(m);int mid = (tree[m].l+tree[m].r)>>1;if(mid>=l)Update(L(m),l,r,x);if(mid<r)Update(R(m),l,r,x);maintain(m);
}
void Query(int m,int l,int r){if( (tree[m].l >= l && tree[m].r <= r)){ans |=tree[m].color; //用 或 操作來實現顏色的累加return 	;}pushdown(m);int mid = (tree[m].l + tree[m].r)>>1;if(mid>=l)Query(L(m),l,r);if(mid<r)Query(R(m),l,r);
}
int main(){int n,m,t;scanf("%d%d%d",&n,&m,&t);Build(1,1,n);char cmd;int a,b,c;while(t--){scanf(" %c",&cmd);scanf("%d%d",&a,&b);if(a>b)swap(a,b);if(cmd=='C'){scanf("%d",&c);Update(1,a,b,c);}else{ans = 0;int count = 0;Query(1,a,b);for(int i=0;i<m;i++){if(ans & (1<<i)) //與每一個二進制位進行 與 操作 ， 相同說明有這個顏色count++;}printf("%d\n",count);}}return 0;
}