Problem 2105 Digits Count
Problem Description
Given N integers A={A[0],A[1],...,A[N-1]}. Here we have some operations:
Operation 1: AND opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] AND opn (here "AND" is bitwise operation).
Operation 2: OR opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] OR opn (here "OR" is bitwise operation).
Operation 3: XOR opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] XOR opn (here "XOR" is bitwise operation).
Operation 4: SUM L R
We want to know the result of A[L]+A[L+1]+...+A[R].
Now can you solve this easy problem?
Input
The first line of the input contains an integer T, indicating the number of test cases. (T≤100)
Then T cases, for any case, the first line has two integers n and m (1≤n≤1,000,000, 1≤m≤100,000), indicating the number of elements in A and the number of operations.
Then one line follows n integers A[0], A[1], ..., A[n-1] (0≤A[i]<16,0≤i<n).
Then m lines, each line must be one of the 4 operations above. (0≤opn≤15)
Output
Sample Input
Sample Output
题意不多说了。 观察下a的值表示成二进制不会超过4位内存刚刚够。对每一位维护一下线段树就好了。
具体维护方法如下：
由于 : 1 & 0 = 0
0 & 0 =0 所以&0会改变区间值。
1& 1 =1
0&1=0 所以&1 区间值不变，可以忽略。
同理可以分析其他的操作。然后线段树lazy维护一下1的个数就好了。 注意xor 和& or是互斥的，也就是说当标记了&或or时应把标记 xor清空。
2 // hehe
3 #include <cstdio>
4 #include <cstring>
5 #include <algorithm>
6 #include <vector>
7 #include <queue>
8 using namespace std;
9 const int MAX = 1000000+5;
10 typedef long long ll;
11 int sum[4][MAX<<2];
12 int col_or[4][MAX<<2],col_xor[4][MAX<<2];
13 int A[MAX];
14 void pushup(int o,int cur){
15 sum[cur][o]=sum[cur][o<<1]+sum[cur][o<<1|1];
16 }
17
18 void pushdown(int o,int cur,int m){
19 if(col_or[cur][o]!=-1){
20 col_xor[cur][o<<1]=col_xor[cur][o<<1|1]=0;
21 col_or[cur][o<<1]=col_or[cur][o<<1|1]=col_or[cur][o];
22 sum[cur][o<<1]=(m-(m>>1))*col_or[cur][o<<1];
23 sum[cur][o<<1|1]=(m>>1)*col_or[cur][o<<1|1];
24 col_or[cur][o]=-1;
25 }
26 if(col_xor[cur][o]){
27 col_xor[cur][o<<1]^=1,col_xor[cur][o<<1|1]^=1;
28 sum[cur][o<<1]=((m-(m>>1))-sum[cur][o<<1]);
29 sum[cur][o<<1|1]=((m>>1)-sum[cur][o<<1|1]);
30 col_xor[cur][o]=0;
31 }
32 }
33
34 void build(int L,int R,int o,int cur){
35 col_or[cur][o]=-1;
36 col_xor[cur][o]=0;
37 if(L==R){
38 sum[cur][o]=((A[L]&(1<<cur))?1:0);
39 }
40 else{
41 int mid=(L+R)>>1;
42 build(L,mid,o<<1,cur);
43 build(mid+1,R,o<<1|1,cur);
44 pushup(o,cur);
45 }
46 }
47
48 void modify2(int L,int R,int o,int ls,int rs,int v,int cur){
49 if(ls<=L && rs>=R){
50 col_xor[cur][o]=0;
51 col_or[cur][o]=v;
52 sum[cur][o]=v*(R-L+1);
53 return ;
54 }
55 pushdown(o,cur,R-L+1);
56 int mid=(R+L)>>1;
57 if(ls<=mid) modify2(L,mid,o<<1,ls,rs,v,cur);
58 if(rs>mid) modify2(mid+1,R,o<<1|1,ls,rs,v,cur);
59 pushup(o,cur);
60
61 }
62
63 void modify1(int L,int R,int o,int ls,int rs,int v,int cur){
64 if(ls<=L && rs>=R){
65 if(col_or[cur][o]!=-1){
66 col_or[cur][o]^=1;
67 sum[cur][o]=(R-L+1)-sum[cur][o];
68 return ;
69 }
70 else{
71 col_xor[cur][o]^=1;
72 sum[cur][o]=(R-L+1)-sum[cur][o];
73 return ;
74 }
75 }
76 pushdown(o,cur,R-L+1);
77 int mid=(R+L)>>1;
78 if(ls<=mid) modify1(L,mid,o<<1,ls,rs,v,cur);
79 if(rs>mid) modify1(mid+1,R,o<<1|1,ls,rs,v,cur);
80 pushup(o,cur);
81 }
82
83 int Query(int L,int R,int o,int ls,int rs,int cur) {
84 if(ls<=L && rs>=R) return sum[cur][o];
85 pushdown(o,cur,R-L+1);
86 int mid=(R+L)>>1; int ans=0;
87 if(ls<=mid) ans+=Query(L,mid,o<<1,ls,rs,cur);
88 if(rs>mid) ans+=Query(mid+1,R,o<<1|1,ls,rs,cur);
89 return ans;
90 }
91
92 int main(){
93 int n,m,cas,ls,rs,val;
94 char op[6];
95 scanf("%d",&cas);
96 while(cas--){
97 scanf("%d %d",&n,&m);
98 for(int i=1;i<=n;i++) {
99 scanf("%d",&A[i]);
100 }
101 for(int i=0;i<4;i++) {
102 build(1,n,1,i);
103 }
104 for(int i=0;i<m;i++) {
105 scanf("%s",op);
106 if(op[0]=='S'){
107 scanf("%d %d",&ls,&rs);
108 ls++,rs++;
109 int ans=0;
110 for(int i=0;i<4;i++) {
111 ans+=Query(1,n,1,ls,rs,i)*(1<<i);
112 }
113 printf("%d ",ans);
114 }
115 else if(op[0]=='O'){
116 scanf("%d %d %d",&val,&ls,&rs);
117 rs++,ls++;
118 for(int i=0;i<4;i++) {
119 if(val&(1<<i)){
120 modify2(1,n,1,ls,rs,1,i);
121 }
122 }
123 }
124 else if(op[0]=='A'){
125 scanf("%d %d %d",&val,&ls,&rs);
126 rs++,ls++;
127 for(int i=0;i<4;i++) {
128 if(!(val&(1<<i))){
129 modify2(1,n,1,ls,rs,0,i);
130 }
131 }
132 }
133 else{
134 scanf("%d %d %d",&val,&ls,&rs);
135 rs++,ls++;
136 for(int i=0;i<4;i++) {
137 if((val&(1<<i))){
138 modify1(1,n,1,ls,rs,1,i);
139 }
140 }
141 }
142 }
143 }
144 return 0;
145 }