題目鏈接： ?poj 2777 Count Color

題目大意： ?給出一塊長度為n的板，區間范圍[1,n]，和m種染料

? ? ? ? ? ? ? ? ? ? k次操作，C ?a ?b ?c 把區間[a,b]涂為c色，P ?a ?b 查詢區間[a,b]有多少種不同顏色

解題思路： ?很明顯的線段樹的區間插入和區間查詢，但是如何統計有多少不同的顏色呢？

? ? ? ? ? ? ? ? ? ? 如果每個結點數組來存儲顏色的種類，空間復雜度很高，而且查詢很慢

? ? ? ? ? ? ? ? ? ? 顏色最多只有30種，可以用位運算中的“按位或｜”

? ? ? ? ? ? ? ? ? ? 顏色也用二進制來處理，和存儲：

? ? ? ? ? ? ? ? ? ? 第一種顏色的二進制表示1

? ? ? ? ? ? ? ? ? ? 第二種顏色的二進制表示10

? ? ? ? ? ? ? ? ? ? 第三種顏色的二進制表示100

? ? ? ? ? ? ? ? ? ? 第四種顏色的二進制表示1000

? ? ? ? ? ? ? ? ? ? 如同一個區間出現第一種和第三種顏色，按位或運算之后得到 101

? ? ? ? ? ? ? ? ? ? 統計結果有多少個1，就說明區間有多少不同的顏色

? ? ? ? ? ? ? ? ? ? 線段樹每個結點存儲區間顏色的種類，結點＝左子樹｜右子樹

? ? ? ? ? ? ? ? ? ? 更多關于線段樹的解題報告可以看我博客 myzee.cn

代碼：

?

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 110000 #define MID(a,b) (a+b)>>1 #define L(a) a<<1 #define R(a) (a<<1|1) typedef struct{int left,right;int add,num; }Node; Node Tree[MAX<<2]; int Color[32]={0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824};//二進制表示第幾種顏色，如8表示第四種顏色：1000 int Lowbit(int x) //剔除x二進制中最后面一個1 {return x&(-x); }void Build(int t,int l,int r) //以1為根結點，建立[l,r]的線段樹 {Tree[t].left=l,Tree[t].right=r,Tree[t].add=0; //***if(l==r){Tree[t].num=1;return ;}int mid=MID(Tree[t].left,Tree[t].right);Build(L(t),l,mid);Build(R(t),mid+1,r);Tree[t].num=(Tree[L(t)].num|Tree[R(t)].num); }void Insert(int t,int l,int r,int m) //向區間[l,r]涂顏色 {if(Tree[t].left==l&&Tree[t].right==r){Tree[t].add=m;Tree[t].num=m;return ;}if(Tree[t].add!=0) //lazy標記{Tree[L(t)].num=Tree[t].add;Tree[R(t)].num=Tree[t].add;Tree[L(t)].add=Tree[t].add;Tree[R(t)].add=Tree[t].add;Tree[t].add=0;}int mid=MID(Tree[t].left,Tree[t].right);if(l>mid){Insert(R(t),l,r,m);}else if(r<=mid){Insert(L(t),l,r,m);}else{Insert(L(t),l,mid,m);Insert(R(t),mid+1,r,m);}Tree[t].num=(Tree[L(t)].num|Tree[R(t)].num); //*** }int Query(int t,int l,int r) {if(Tree[t].left==l&&Tree[t].right==r){return Tree[t].num;}if(Tree[t].add!=0) //區間插入的lazy思想{Tree[L(t)].num=Tree[t].add;Tree[R(t)].num=Tree[t].add;Tree[L(t)].add=Tree[t].add;Tree[R(t)].add=Tree[t].add;Tree[t].add=0;}int mid=MID(Tree[t].left,Tree[t].right);if(l>mid){return Query(R(t),l,r);}else if(r<=mid){return Query(L(t),l,r);}else{return Query(L(t),l,mid)|Query(R(t),mid+1,r); //***是｜，不是＋!!!}Tree[t].num=(Tree[L(t)].num|Tree[R(t)].num); }int main() {char ch;int n,col,q,i,k,a,b,c;int m;while(scanf("%d%d%d",&n,&col,&q)!=EOF){memset(Tree,0,sizeof(Tree)); //初始化Build(1,1,n); //建樹for(i=0;i<q;i++){getchar();scanf("%c",&ch);if(ch=='P'){scanf("%d%d",&a,&b);k=0;if(a>b)m=Query(1,b,a);elsem=Query(1,a,b);while(m>0) //計算查詢后的結果的二進制表示右多少個1{k++;m-=Lowbit(m);}printf("%d\n",k);}else{scanf("%d%d%d",&a,&b,&c);if(a>b)Insert(1,b,a,Color[c]);elseInsert(1,a,b,Color[c]);}}}return 0; }

?

注：原創文章，轉載請注明出處

?

?

總結

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

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