cdoj 1259 线段树+bitset 区间更新/查询

Description

昊昊喜欢运动

他

现在有

昊昊把第
问昊昊第

Input

输入两个数

输入

输入一个数

输入

形如M l r x，表示昊昊把第
形如Q l r，表示昊昊想知道他第

Output

对于所有的Q操作，每一行输出一个数表示昊昊在第

Sample Input

5 3
1 2 3 2 3
4
Q 1 4
Q 2 4
M 5 5 2
Q 1 5

Sample Output

3
2
3

题意：中文题意

题解：线段树+bitset

bitset记录运动的种类 bitset的用法姿势涨

bitset<110> sum

(sum.reset() 全部置为0 )

(sum.count()计算为1的位数)

(sum[x]=1 第x位赋为1)

坑点：千万不要直接复制样例直接复制会很坑 orzzzz

getchar()的问题 re多次太菜了...

  1 /******************************
  2 code by drizzle
  3 blog: www.cnblogs.com/hsd-/
  4 ^ ^    ^ ^
  5  O      O
  6 ******************************/
  7 //#include<bits/stdc++.h>
  8 #include<iostream>
  9 #include<cstring>
 10 #include<cmath>
 11 #include<cstdio>
 12 #include<bitset>
 13 //#define ll long long
 14 #define mod 1000000007
 15 #define PI acos(-1.0)
 16 using namespace std;
 17 struct node
 18 {
 19     int l,r;
 20     int add;
 21     bitset<110> sum;
 22 } tree[2000005];
 23 int n,m;
 24 int exm;
 25 int l1,r1,x;
 26 int q;
 27 char judge;
 28 void buildtree(int root,int left,int right)
 29 {
 30     tree[root].l=left;
 31     tree[root].r=right;
 32     tree[root].add=0;
 33     if(left==right)
 34     {
 35         tree[root].sum.reset();
 36         scanf("%d",&exm);
 37         tree[root].sum[exm]=1;
 38         return ;
 39     }
 40     int mid=(left+right)>>1;
 41     buildtree(root<<1,left,mid);
 42     buildtree(root<<1|1,mid+1,right);
 43     tree[root].sum=tree[root<<1].sum|tree[root<<1|1].sum;//按位或得到新的运动种类
 44 }
 45 void pushdown(int root)
 46 {
 47     if(tree[root].add==0)
 48         return ;
 49     tree[root<<1].sum.reset();
 50     tree[root<<1|1].sum.reset();
 51     tree[root<<1].sum[tree[root].add]=1;
 52     tree[root<<1|1].sum[tree[root].add]=1;
 53     tree[root<<1].add=tree[root].add;//注意延迟标记也要往下传
 54     tree[root<<1|1].add=tree[root].add;
 55     tree[root].add=0;
 56 }
 57 void updata(int root,int left,int right,int c)
 58 {
 59     if(tree[root].l==left&&tree[root].r==right)
 60     {
 61         tree[root].sum.reset();//全部置零
 62         tree[root].add=c;
 63         tree[root].sum[c]=1;//整个区间只有c运动
 64         return ;
 65     }
 66     pushdown(root);//lazy 延迟标记
 67     int mid=(tree[root].l+tree[root].r)>>1;
 68     if(right<=mid)
 69         updata(root<<1,left,right,c);
 70     else
 71     {
 72         if(left>mid)
 73             updata(root<<1|1,left,right,c);
 74         else
 75         {
 76             updata(root<<1,left,mid,c);
 77             updata(root<<1|1,mid+1,right,c);
 78         }
 79     }
 80     tree[root].sum=tree[root<<1].sum|tree[root<<1|1].sum;
 81 }
 82 bitset<110> query(int root,int left,int right)
 83 {
 84     if(tree[root].l==left&&tree[root].r==right)
 85     {
 86         return  tree[root].sum;
 87     }
 88     pushdown(root);
 89     int mid=(tree[root].l+tree[root].r)>>1;
 90     if(right<=mid)
 91         return query(root<<1,left,right);
 92     else
 93     {
 94         if(left>mid)
 95             return query(root<<1|1,left,right);
 96         else
 97             return query(root<<1,left,mid)|query(root<<1|1,mid+1,right);
 98     }
 99 }
100 int main()
101 {
102     while(scanf("%d %d",&n,&m)!=EOF)
103     {
104         buildtree(1,1,n);
105         scanf("%d",&q);
106         getchar();
107         for(int i=1; i<=q; i++)
108         {
109             scanf("%c",&judge);
110             if(judge=='Q')
111             {
112                 scanf("%d %d",&l1,&r1);
113                 printf("%d
",query(1,l1,r1).count());
114             }
115             else
116             {
117                 scanf("%d %d %d",&l1,&r1,&x);
118                 updata(1,l1,r1,x);
119             }
120             getchar();//坑点
121         }
122     }
123     return 0;
124 }