FZU 2105 (线段树)

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

For each test case and for each "SUM" operation, please output the result with a single line.

Sample Input

1 4 4 1 2 4 7 SUM 0 2 XOR 5 0 0 OR 6 0 3 SUM 0 2

Sample Output

7 18

题意不多说了。观察下a的值表示成二进制不会超过4位内存刚刚够。对每一位维护一下线段树就好了。

具体维护方法如下：

由于 : 1 & 0 = 0

0 & 0 =0 所以&0会改变区间值。

1& 1 =1

0&1=0 所以&1 区间值不变，可以忽略。

同理可以分析其他的操作。然后线段树lazy维护一下1的个数就好了。注意xor 和& or是互斥的，也就是说当标记了&或or时应把标记 xor清空。

  1 // by cao ni ma

  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 = +;

 10 typedef long long ll;

 11 int sum[][MAX<<];

 12 int col_or[][MAX<<],col_xor[][MAX<<];

 13 int A[MAX];

 14 void pushup(int o,int cur){

 15     sum[cur][o]=sum[cur][o<<]+sum[cur][o<<|];

 16 }

 17 

 18 void pushdown(int o,int cur,int m){

 19     if(col_or[cur][o]!=-){

 20         col_xor[cur][o<<]=col_xor[cur][o<<|]=;

 21         col_or[cur][o<<]=col_or[cur][o<<|]=col_or[cur][o];

 22         sum[cur][o<<]=(m-(m>>))*col_or[cur][o<<];

 23         sum[cur][o<<|]=(m>>)*col_or[cur][o<<|];

 24         col_or[cur][o]=-;

 25     }

 26     if(col_xor[cur][o]){

 27         col_xor[cur][o<<]^=,col_xor[cur][o<<|]^=;

 28         sum[cur][o<<]=((m-(m>>))-sum[cur][o<<]);

 29         sum[cur][o<<|]=((m>>)-sum[cur][o<<|]);

 30         col_xor[cur][o]=;

 31     }

 32 }

 33 

 34 void build(int L,int R,int o,int cur){

 35     col_or[cur][o]=-;

 36     col_xor[cur][o]=;

 37     if(L==R){

 38         sum[cur][o]=((A[L]&(<<cur))?:);

 39     }

 40     else{

 41         int mid=(L+R)>>;

 42         build(L,mid,o<<,cur);

 43         build(mid+,R,o<<|,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]=;

 51         col_or[cur][o]=v;

 52         sum[cur][o]=v*(R-L+);

 53         return ;

 54     }

 55     pushdown(o,cur,R-L+);

 56     int mid=(R+L)>>;

 57     if(ls<=mid) modify2(L,mid,o<<,ls,rs,v,cur);

 58     if(rs>mid) modify2(mid+,R,o<<|,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]!=-){

 66             col_or[cur][o]^=;

 67             sum[cur][o]=(R-L+)-sum[cur][o];

 68             return ;

 69         }

 70         else{

 71             col_xor[cur][o]^=;

 72             sum[cur][o]=(R-L+)-sum[cur][o];

 73             return ;

 74         }

 75     }

 76     pushdown(o,cur,R-L+);

 77     int mid=(R+L)>>;

 78     if(ls<=mid) modify1(L,mid,o<<,ls,rs,v,cur);

 79     if(rs>mid) modify1(mid+,R,o<<|,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+);

 86     int mid=(R+L)>>; int ans=;

 87     if(ls<=mid) ans+=Query(L,mid,o<<,ls,rs,cur);

 88     if(rs>mid) ans+=Query(mid+,R,o<<|,ls,rs,cur);

 89     return ans;

 90 }

 91 

 92 int main(){

 93     int n,m,cas,ls,rs,val;

 94     char op[];

 95     scanf("%d",&cas);

 96     while(cas--){

 97         scanf("%d %d",&n,&m);

 98         for(int i=;i<=n;i++) {

 99             scanf("%d",&A[i]);

         }

         for(int i=;i<;i++) {

             build(,n,,i);

         }

         for(int i=;i<m;i++) {

             scanf("%s",op);

             if(op[]=='S'){

                 scanf("%d %d",&ls,&rs);

                 ls++,rs++;

                 int ans=;

                 for(int i=;i<;i++) {

                     ans+=Query(,n,,ls,rs,i)*(<<i);

                 }

                 printf("%d\n",ans);

             }

             else if(op[]=='O'){

                 scanf("%d %d %d",&val,&ls,&rs);

                 rs++,ls++;

                 for(int i=;i<;i++) {

                     if(val&(<<i)){

                         modify2(,n,,ls,rs,,i);

                     }

                 }

             }

             else if(op[]=='A'){

                 scanf("%d %d %d",&val,&ls,&rs);

                 rs++,ls++;

                 for(int i=;i<;i++) {

                     if(!(val&(<<i))){

                        modify2(,n,,ls,rs,,i);

                     }

                 }

             }

             else{

                 scanf("%d %d %d",&val,&ls,&rs);

                 rs++,ls++;

                 for(int i=;i<;i++) {

                     if((val&(<<i))){

                          modify1(,n,,ls,rs,,i);

                     }

                 }

             }

         }

     }

     return ;

145 }

巴特西

FZU 2105 (线段树)

Problem Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章