学步园

搞得好囧，想自己A，结果还是盗版货，而且郁闷了好久才见ac的，擦擦。。。

ps:

本来也想这么做的：每次染色的时候，并不更新到子节点，而是把信息上次的和目前的信息综合之后，再判断是否向下更新的，结果，采用基本做法，TLE到死........

#include<stdio.h><br /> #include<string.h><br /> #define max 100005<br /> struct node<br /> {<br /> int l,r;<br /> int color;<br /> }st[max*4];<br /> bool co[35];<br /> int L,T,O,ans;<br /> void create(int l,int r,int i)<br /> {<br /> st[i].color =1;<br /> st[i].l=l;st[i].r =r;<br /> if(st[i].l ==st[i].r )<br /> return ;<br /> int mid=(st[i].l+st[i].r)>>1;<br /> create(l,mid,i*2);<br /> create(mid+1,r,i*2+1);<br /> }<br /> void update(int l,int r,int col,int i)<br /> {<br /> if(st[i].color ==col)<br /> return ;<br /> if(l==st[i].l&&st[i].r==r)<br /> {<br /> st[i].color=col;<br /> return ;<br /> }<br /> if(st[i].color >0)<br /> {<br /> st[i<<1].color =st[i].color ;<br /> st[(i<<1)+1].color =st[i].color;<br /> st[i].color =-1;<br /> }<br /> int mid=(st[i].l+st[i].r)>>1;<br /> if(r<=mid)<br /> update(l,r,col,i*2);<br /> else if(l>mid)<br /> update(l,r,col,i*2+1);<br /> else<br /> {<br /> update(l,mid,col,i*2);<br /> update(mid+1,r,col,i*2+1);<br /> }<br /> }<br /> void search(int l,int r,int i)<br /> {<br /> if(st[i].color >0)<br /> {<br /> co[st[i].color ]=true;<br /> return ;<br /> }<br /> int mid=(st[i].l +st[i].r )>>1;<br /> if(r<=mid)<br /> search(l,r,i*2);<br /> else if(l>mid)<br /> search(l,r,i*2+1);<br /> else<br /> {<br /> search(l,mid,i*2);<br /> search(mid+1,r,i*2+1);<br /> }<br /> }<br /> int main()<br /> {<br /> int i,x,y,z,k;<br /> char c;<br /> scanf("%d%d%d",&L,&T,&O);<br /> create(1,L,1);<br /> for(i=0;i<O;i++)<br /> {<br /> getchar();<br /> scanf("%c",&c);<br /> if(c=='C')<br /> {<br /> scanf("%d%d%d",&x,&y,&z);<br /> if(x>y){k=x;x=y;y=k;}<br /> update(x,y,z,1);<br /> }<br /> else<br /> {<br /> ans=0;<br /> scanf("%d%d",&x,&y);<br /> if(x>y){k=x;x=y;y=k;}<br /> memset(co,false,sizeof(co));<br /> search(x,y,1);<br /> for(z=0;z<31;z++)<br /> if(co[z])<br /> ans++;<br /> printf("%d/n",ans);<br /> }<br /> }<br /> return 0;<br /> }