首页 > 代码库 > POJ 2777 Count Color
POJ 2777 Count Color
这题其实之前写过,应该算是线段树中比较简单的,不过自己还是被坑了很长时间,就是因为一个小小的错误,怎么找都找不到,哎,急哭了。
这题在找颜色种类的时候,因为最多只有30种颜色,所以可以用一个整型变量来存储,一个位代表一种颜色。这里就要考虑对位的处理了,具体见代码。
#include<cstdio> #include<cstring> const int N=100005; int L,T,O; struct board { int left,right,color; bool ischange; }node[N<<2]; void set_tree(int id,int l,int r) { node[id].left=l,node[id].right=r,node[id].color=1,node[id].ischange=false; if(l==r) return; int lson=id<<1,rson=lson+1,mid=(l+r)/2; set_tree(lson,l,mid); set_tree(rson,mid+1,r); } void update(int id,int l,int r,int c) { if(node[id].left==l&&node[id].right==r) { node[id].color=1<<(c-1); node[id].ischange=true; return; } int lson=id<<1,rson=lson+1,mid=(node[id].left+node[id].right)/2; if(node[id].ischange) { node[lson].ischange=true,node[rson].ischange=true; node[lson].color=node[id].color,node[rson].color=node[id].color; node[id].ischange=false; } if(r<=mid) update(lson,l,r,c); else if(l>mid) update(rson,l,r,c); else { update(lson,l,mid,c); update(rson,mid+1,r,c); } node[id].color=node[lson].color|node[rson].color; } void query(int id,int l,int r,int &ans) { if(node[id].ischange||(node[id].left==l&&node[id].right==r)) { ans|=node[id].color;//就是这里被坑了,我没有加或,而是直接赋值了,当时估计脑袋秀逗了。 return; } int lson=id<<1,rson=lson+1,mid=(node[id].left+node[id].right)/2; if(r<=mid) query(lson,l,r,ans); else if(l>mid) query(rson,l,r,ans); else { query(lson,l,mid,ans); query(rson,mid+1,r,ans); } } int main() { int a,b,c; char s[3]; while(scanf("%d%d%d",&L,&T,&O)!=EOF) { set_tree(1,1,L); for(int i=1;i<=O;i++) { scanf("%s",s); if(s[0]=='C') { scanf("%d%d%d",&a,&b,&c); if(a>b)//这里要比较a,b的大小 update(1,b,a,c); else update(1,a,b,c); } else { scanf("%d%d",&a,&b); int ans=0,cnt=0; if(a>b) query(1,b,a,ans); else query(1,a,b,ans); for(int i=0;i<T;i++) { int t=ans&1; if(t==1) cnt++; ans=ans>>1; } printf("%d\n",cnt); } } } return 0; }
POJ 2777 Count Color
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。