POJ 2777(线段树 位运算)

POJ 2777

题目大意

有一个长位L的区间,有T种颜色，进行O次操作，每次操作 (1≤n≤100000,1≤T≤30,1≤O≤100000)

每次操作有两种形式:

P A B C:将区间(A,B)染成颜色C

Q A B:询问区间(A,B)有多少种不同的颜色

每个点的初始颜色都是1

注意:A可能大于B

分析

线段树的区间更新

有两种信息，一个是区间维护的信息color表示某个区间有哪些颜色，还有一个信息是延迟标记信息lazy数组。

技巧

这道题可以用位运算来进行线段间的合并操作，就是用用一个32位int类型的col变量表示某个区间有哪些颜色

知道两个子节点有哪些颜色要求父亲节点有哪些颜色的时候通过按位或(|)进行合并.

代码

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> #include<map> #include<algorithm> #include<set> #include<stack> using namespace std; const int MAXN=100005; int n,s,m;//线段长度为n,一共有s种颜色,进行m种操作 int lazy[MAXN*4];//延迟标记 int col[MAXN*4]; void Init() { memset(lazy,0,sizeof(lazy)); } void Pushup(int rt)//rt的子节点已经更新好了，现在更新rt节点 { col[rt]=col[rt*2] | col[rt*2+1]; } void Build(int l,int r,int rt) { if(l==r) { col[rt]=2;//将颜色1也就是二进制1位染色 return ; } int m=(l+r)/2; Build(l,m,rt*2); Build(m+1,r,rt*2+1); Pushup(rt); } void Pushdown(int rt)//节点rt已经更新好了，将标记下推 { if(lazy[rt]!=0) { col[rt*2]=(1<<lazy[rt]); col[rt*2+1]=(1<<lazy[rt]); lazy[rt*2]=lazy[rt]; lazy[rt*2+1]=lazy[rt]; lazy[rt]=0; } } void Update(int L,int R,int x,int l,int r,int rt) { if(L<=l && r<=R) { col[rt]=(1<<x); lazy[rt]=x; return; } int m=(l+r)/2; Pushdown(rt); if(L<=m)Update(L,R,x,l,m,rt*2); if(R>m)Update(L,R,x,m+1,r,rt*2+1); Pushup(rt); } int Query(int L,int R,int l,int r,int rt) { if(L<=l && r<=R) { return col[rt]; } int color1,color2; int color_ans; color1=0; color2=0; int m=(l+r)/2; Pushdown(rt); if(L<=m)color1=Query(L,R,l,m,rt*2); if(R>m)color2=Query(L,R,m+1,r,rt*2+1); color_ans=color1 | color2; return color_ans; } void find_ans(int t) { int ans=0; while(t>0) { if(t%2==1)ans++; t=t/2; } cout<<ans<<endl; } int main() { char c; int L,R,x; int ans; int t; while(scanf("%d%d%d",&n,&s,&m)!=EOF) { Init(); Build(1,n,1); for(int i=1;i<=m;i++) { scanf("%c",&c); while(c==' '|| c=='\n')scanf("%c",&c); if(c=='C') { scanf("%d%d%d",&L,&R,&x); if(L>R){t=L;L=R;R=t;}//题目中可能有L>R的情况 Update(L,R,x,1,n,1); } else if(c=='P') { scanf("%d%d",&L,&R); if(L>R){t=L;L=R;R=t;}//题目中可能有L>R的情况 ans=Query(L,R,1,n,1); find_ans(ans); } } } return 0; } /* 6 7 4 C 1 6 2 P 1 5 C 4 2 7 P 6 1 */