早些日子为了学习线段树,在Du神牛的带领下,做了此题,入门好题也! poj2777 Count Color
此题是本人线段树第二题,前一道是TYVJ1039 忠诚2(一道动态RMQ问题)
输入区间长度L (1 <= L <= 100000),颜色数目 T (1 <= T <= 30) 和 指令数O (1 <= O <= 100000)
接下来O行C x y z 代表将[x,y]区间染成z色,P x y z 代表询问[x,y]有多少种颜色,起始各处颜色为1;
我第一眼看到”1 <= T <= 30″就格外激动为啥不是40呢？显然是为了小于32,所以显然可以用二进制每位表达一种颜色,颜色1是1(0x1)颜色10就是1024(0x400),在线段树里查询便可以获得这一段的几种颜色然后做一次OR操作便可得到所有颜色
我看到T的范围就马上想到到了Matrix67牛的一个位运算优化：位运算简介及实用技巧（二）：进阶篇(1) 中计算二进制中的1的个数的方法
|
1 2 3 4 5 6 7 8 |
inline int c1(int x){ x=(x & 0x55555555) + ((x >>1 ) & 0x55555555); x=(x & 0x33333333) + ((x >>2 ) & 0x33333333); x=(x & 0x0F0F0F0F) + ((x >>4 ) & 0x0F0F0F0F); x=(x & 0x00FF00FF) + ((x >>8 ) & 0x00FF00FF); x=(x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF); return x; } |
此方法可快速统计int型中1的个数
做这个题的时候曾经碰到个棘手的问题,WA了好几次,后来看了Du神牛的题解 ,发现代码出奇的相似,于是找不同之处,豁然开朗.
错误的代码详见poj2777里Discuss里Comzyh的”Wa的原因
这个问题的由来是这样的,架设有一段[1,10]的区间为红色,其子树为[1,5],[6,10]我么现在要对[5,7]染成蓝色,怎么做呢?
显然最终情况是[1,4][5,7][7,10]
我的原意是先染色[1,4] 然后染色[7,10] (下沉操作)然后染色[5,7]
后来看了Du神牛的题解,豁然开朗,原来直接将线段下沉到两个子节点即可,即先染色[1,5],在染色[6,10],再染色[5,7],我刚才的做法纯属闲的,我把右边那一段[7,10]染成当前要染的色而不是当前线段的颜色(今天又试了下改正了的,G++688ms,C++516,显然慢).
还是把错误代码贴一下吧,第23行Cover错了.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
void cover (int b,int e,int s,int c){ //printf("Cover from %4d to %4d in setment %4d (%4d,%4d)Colored %x\n",b,e,s,seg[s].b,seg[s].e,c); segment &ts=seg[s]; if (ts.b==b && ts.e==e){ ts.cd=1; ts.c =c; return ; } int mid=(ts.b + ts.e)>>1; if (ts.cd==1){ ts.cd=0; if (b>ts.b) if (b-1<=mid) cover(ts.b,b-1,s<<1,ts.c); else{ cover(ts.b,mid,s<<1,ts.c); cover(mid+1,b-1,(s<<1)+1,ts.c); } if (e<ts.e) if (e>=mid)//e+1>=mid+1 cover(e+1,ts.e,(s<<1)+1,ts.c); else {//能看到底下不是ts.c;这就是Wa的原因--Comzyh写本文时注 cover(e+1,mid,s<<1,c); cover(mid+1,ts.e,(s<<1)+1,c); } } ts.cd=0; if (e <= mid) cover(b,e,s<<1 ,c); else if (b>mid)//b>=mid+1 cover(b,e,(s<<1)+1,c); else{ cover(b ,mid,s<<1 ,c); cover(mid+1,e ,(s<<1)+1,c); } } |
哎,下面帖下我的G++547ms,C++438ms的代码,初学者,慢没法,另外严重怀疑poj的C++为什么比G++快这么多.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
/* Problem: 2777 User: comzyh Memory: 4312K Time: 407MS Language: C++ Result: Accepted */ #include <iostream> #include <cstdio> #include <stdlib.h> using namespace std; //#define ts seg[s] struct segment{ unsigned int b,e,cd;//begin,end,该线段仅有一种颜色?; long c;//二进制存储,从long long 改成 long 就407ms了 }; int L,T,O; segment seg[500000]; inline int c1(int x); void build(int b,int e,int s); void cover (int b,int e,int s,int c); int get(int b,int e,int s); int main(){ int i,j; char t; int b,e,c; scanf("%d%d%d",&L,&T,&O); build(1,L,1); for (i=1;i<=O;i++){ scanf ("\n%c",&t); if (t=='C'){ scanf ("%d%d%d",&b,&e,&c); if (b<e) cover(b,e,1,1<<(c-1)); else cover(e,b,1,1<<(c-1)); } else { scanf("%d %d",&b,&e); printf("%d\n",c1(get(b,e,1))); } } system("pause"); } inline int c1(int x){//从Matrix67那里学习的 x=(x & 0x55555555) + ((x >>1 ) & 0x55555555); x=(x & 0x33333333) + ((x >>2 ) & 0x33333333); x=(x & 0x0F0F0F0F) + ((x >>4 ) & 0x0F0F0F0F); x=(x & 0x00FF00FF) + ((x >>8 ) & 0x00FF00FF); x=(x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF); return x; } void build(int b,int e,int s){//建树 //printf("Build Tree from %4d to %4d in line %4d \n",b,e,s); seg[s].b=b; seg[s].e=e; seg[s].c=1; seg[s].cd=1; if (b != e){ int mid=(b+e)>>1; build(b ,mid,s<<1 ); build(mid+1,e ,(s<<1)+1); } } void cover (int b,int e,int s,int c){//覆盖,开始,结束,线段,颜色 //printf("Cover from %4d to %4d in setment %4d (%4d,%4d)Colored %x\n",b,e,s,seg[s].b,seg[s].e,c); segment &ts=seg[s];//当前线段的引用,下同 if (ts.b==b && ts.e==e){ ts.cd=1; ts.c =c; return ; } int mid=(ts.b + ts.e)>>1; if (ts.cd==1){ cover(ts.b ,mid ,s<<1 ,ts.c); cover(mid+1,ts.e,(s<<1)+1,ts.c); } ts.cd=0; if (e <= mid) cover(b,e,s<<1 ,c); else if (b>mid)//b>=mid+1 cover(b,e,(s<<1)+1,c); else{ cover(b ,mid,s<<1 ,c); cover(mid+1,e ,(s<<1)+1,c); } } int get(int b,int e,int s){//查询颜色 //printf("Get from %4d to %4d in segment %4d (%4d,%4d)\n",b,e,s,seg[s].b,seg[s].e); segment &ts=seg[s]; if (ts.cd==1)return ts.c; int mid=(ts.b+ts.e)>>1; if (e <= mid) return get(b,e,s<<1 ); else if (b>mid)//b>=mid+1 return get(b,e,(s<<1)+1); else{ return get(b ,mid,s<<1 ) | //这里就是统计颜色的OR get(mid+1,e ,(s<<1)+1); } } |
原创文章，转载请注明： 转载自Comzyh的博客
本文链接地址: POJ 2777 Count Color 线段树染色
2 replies on “POJ 2777 Count Color 线段树染色”