poj 2777 线段树区间更新+位运算

题意：有一个长板子，分成多段，有两种操作，第一种是C给从a到b那段染一种颜色c，另一种是P询问a到b有多少种不同的颜色。
Sample Input
2 2 4 板长颜色数目询问数目
C 1 1 2
P 1 2
C 2 2 2
P 1 2
Sample Output
2
1

sum用二进制记录区间内颜色状态，col记录染上的颜色（其他颜色会被染上的颜色完全覆盖）

2015-07-23：专题复习

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define MOD 1000000007
 10 const int INF=0x3f3f3f3f;
 11 const double eps=1e-5;
 12 #define cl(a) memset(a,0,sizeof(a))
 13 #define ts printf("*****
");
 14 #define lson l,mid,rt<<1
 15 #define rson mid+1,r,rt<<1|1
 16 #define root 1,n,1
 17 #define mid ((l+r)>>1)
 18 const int MAXN=111111;
 19 int n,m,t,Min;
 20 int sum[MAXN<<2],col[MAXN<<2];
 21 void pushup(int rt)
 22 {
 23     sum[rt]=sum[rt<<1]|sum[rt<<1|1];
 24 }
 25 void pushdown(int rt)
 26 {
 27     if(col[rt]!=-1)
 28     {
 29         sum[rt<<1]=sum[rt<<1|1]=1<<(col[rt]-1);
 30         col[rt<<1]=col[rt<<1|1]=col[rt];
 31         col[rt]=-1;
 32     }
 33 }
 34 void build()
 35 {
 36     sum[1]=1;
 37     col[1]=1;
 38 }
 39 void update(int L,int R,int val,int l,int r,int rt)
 40 {
 41     if(L<=l&&r<=R)
 42     {
 43         sum[rt]=(1<<(val-1));
 44         col[rt]=val;
 45         return;
 46     }
 47     pushdown(rt);
 48     if(mid>=L)  update(L,R,val,lson);
 49     if(mid<R)   update(L,R,val,rson);
 50     pushup(rt);
 51 }
 52 int query(int L,int R,int l,int r,int rt)
 53 {
 54     if(L<=l&&r<=R)
 55     {
 56         return sum[rt];
 57     }
 58     pushdown(rt);
 59     int ans=0;
 60     if(mid>=L)  ans|=query(L,R,lson);
 61     if(mid<R)   ans|=query(L,R,rson);
 62     return ans;
 63 
 64 }
 65 int main()
 66 {
 67     int i,j,k;
 68     #ifndef ONLINE_JUDGE
 69     freopen("1.in","r",stdin);
 70     #endif
 71     int l,t,o,a,b,c;
 72     while(scanf("%d%d%d",&l,&t,&o)!=EOF)
 73     {
 74         n=l;
 75         build();
 76         char s[10];
 77         while(o--)
 78         {
 79             scanf("%s",&s);
 80             if(s[0]=='C')
 81             {
 82                 scanf("%d%d%d",&a,&b,&c);
 83                 if(a>b) swap(a,b);
 84                 update(a,b,c,root);
 85             }
 86             if(s[0]=='P')
 87             {
 88                 scanf("%d%d",&a,&b);
 89                 if(a>b) swap(a,b);
 90                 int tmp=query(a,b,root);
 91                 int ans=0;
 92                 while(tmp)
 93                 {
 94                     if(tmp&1)
 95                         ans++;
 96                     tmp>>=1;
 97                 }
 98                 printf("%d
",ans);
 99             }
100         }
101     }
102 }

View Code

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const int INF=0x3f3f3f3f;
11 const double eps=1e-5;
12 #define cl(a) memset(a,0,sizeof(a))
13 #define ts printf("*****
");
14 #define lson l,mid,rt<<1
15 #define rson mid+1,r,rt<<1|1
16 #define root 1,n,1
17 #define mid ((l+r)>>1)
18 const int MAXN=111111;
19 int n,m,t,Min;
20 int sum[MAXN<<2],col[MAXN<<2];
21 void pushup(int rt){
22     sum[rt]=sum[rt<<1]|sum[rt<<1|1];
23 }
24 void pushdown(int rt)
25 {
26     if(col[rt]!=-1)
27     {
28         sum[rt<<1]=sum[rt<<1|1]=1<<(col[rt]-1);
29         col[rt<<1]=col[rt<<1|1]=col[rt];
30         col[rt]=-1;
31     }
32 }
33 void build(){
34     sum[1]=1;
35     col[1]=1;
36 }
37 void update(int L,int R,int val,int l,int r,int rt)
38 {
39     if(l>=L&&r<=R)
40     {
41         col[rt]=val;
42         sum[rt]=(1<<(val-1));
43         return;
44     }
45     if(L>r||R<l)
46         return ;
47     pushdown(rt);
48     update(L,R,val,lson);
49     update(L,R,val,rson);
50     pushup(rt);
51 }
52 int query(int L,int R,int l,int r,int rt) {
53     if (l>=L&&r<=R){
54         return sum[rt];
55     }
56     if(L>r||R<l)
57        return 0;
58     pushdown(rt);
59     return query(L,R,lson)|query(L,R,rson);
60 }
61 int main()
62 {
63     int i,j,k;
64     #ifndef ONLINE_JUDGE
65     freopen("1.in","r",stdin);
66     #endif
67     int l,t,o,a,b,c;
68     while(scanf("%d%d%d",&l,&t,&o)!=EOF)
69     {
70         build();
71         n=l;
72         char s[10];
73         while(o--)
74         {
75             scanf("%s",&s);
76             if(s[0]=='C')
77             {
78                 scanf("%d%d%d",&a,&b,&c);
79                 if(a>b) swap(a,b);
80                 update(a,b,c,root);
81             }
82             if(s[0]=='P')
83             {
84                 scanf("%d%d",&a,&b);
85                 if(a>b) swap(a,b);
86                 int tmp=query(a,b,root);
87                 int ans=0;
88                 while(tmp)
89                 {
90                     if(tmp&1)
91                         ans++;
92                     tmp>>=1;
93                 }
94                 printf("%d
",ans);
95             }
96         }
97     }
98 }

poj 2777 线段树 区间更新+位运算

poj 2777 线段树区间更新+位运算