線分樹-ビット演算

FZU 2105  Digits Count
Time Limit:1000 MS     メモリLimit:262144 KB     64 bit IO Format:%I 64 d&%I 64 u
Practice
Description
Given N integers A={A[0],A[1],…,A[N-1].Here we have some operation:
Operation 1: AND opn L
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
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
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 R
We want to know the result of A[L]+A[L＋1]+…+A[R]
Now can you solive this easure proble?
Input
The first line of the input contains an integer T,indicating the number of test cases.(T≦100)
The n T cases、for any case、the first line has two integers n and m(1≦n≦1,000,000,000,1≦m≦100,000)、indicating the number of elemens in A and the number of operation.
The n one line follows n integers A[0],A[1],…,A[n-1](0≦A[i]<16,0≦i
The n mライン、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 reult 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=[1 2 4 7]
SUM 0 2,resuult=1+2+4=7
XOR 5 0,A=[4 2 4 7];
OR 6 0 3,A=[6 6 6 6 6 7];
SUM 0 2,resuult=6+6+6=18.
ac:

#include"algorithm"
#include"iostream"
#include"cstring"
#include"cstdlib"
#include"cstdio"
#include"string"
#include"vector"
#include"stack"
#include"queue"
#include"cmath"
#include"map"
using namespace std;
typedef long long LL ;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1   
#define FK(x) cout<>1);
        sum[rt<<1|1][i]=m>>1;
    }
    if(lazy[rt][i]==2) {     //     XOR  
        if(lazy[rt<<1][i]==INF) { //           ，   XOR  
            lazy[rt<<1][i]=2;
            sum[rt<<1][i]=m-(m>>1)-sum[rt<<1][i];
        } else if(lazy[rt<<1][i]==2) {  //     XOR  ，a^b^b==a       。
            lazy[rt<<1][i]=INF;
            sum[rt<<1][i]=m-(m>>1)-sum[rt<<1][i];
        } else {                  //           XOR         XOR  
            lazy[rt<<1][i]^=1;
            if(lazy[rt<<1][i]==0) sum[rt<<1][i]=0;
            else  sum[rt<<1][i]=m-(m>>1);
        }                        
//                                        
                 
        if(lazy[rt<<1|1][i]==INF) {
            lazy[rt<<1|1][i]=2;
            sum[rt<<1|1][i]=(m>>1)-sum[rt<<1|1][i];
        } else if(lazy[rt<<1|1][i]==2) {
            lazy[rt<<1|1][i]=INF;
            sum[rt<<1|1][i]=(m>>1)-sum[rt<<1|1][i];
        } else {
            lazy[rt<<1|1][i]^=1;
            if(lazy[rt<<1|1][i]==0) sum[rt<<1|1][i]=0;
            else sum[rt<<1|1][i]=(m>>1);
        }
    }
    lazy[rt][i]=INF; //  lazy  
}
 
void Build(int l,int r,int rt) {
    for(int i=0; i<4; i++) lazy[rt][i]=INF; //      
    if(r==l) {
        int temp;
        scanf("%d",&temp);
//      FK("temp=="<>1;
    Build(lson);
    Build(rson);
    for(int i=0; i<4; i++) PushUp(rt,i);
}
 
void UpData(int L,int R,int v,int i,int l,int r,int rt) {
    if(r<=R&&L<=l) {
        switch(v) {
            case 0:
                sum[rt][i]=0,lazy[rt][i]=v;
                //     AND  ，   0，   。
                break;
            case 1:
                sum[rt][i]=r-l+1,lazy[rt][i]=v;
                //     OR   ，   1，   。
                break;
            case 2:
                sum[rt][i]=r-l+1-sum[rt][i];
                if(lazy[rt][i]==2) lazy[rt][i]=INF;
                else if(lazy[rt][i]==INF) lazy[rt][i]=2;
                else lazy[rt][i]^=1;
                break;
            default:
                break;
        }
        return ;
    }
    PushDown(rt,r-l+1,i);
    int m=(r+l)>>1;
    if(L<=m)UpData(L,R,v,i,lson);
    if(R>m) UpData(L,R,v,i,rson);
    PushUp(rt,i);
}
 
int Query(int L,int R,int i,int l,int r,int rt) {
    if(L<=l&&r<=R) {
        return sum[rt][i];
//               。
    }
    int m=(r+l)>>1;
    int sum=0;
    PushDown(rt,r-l+1,i);
    if(L<=m)sum+=Query(L,R,i,lson);
    if(R>m) sum+=Query(L,R,i,rson);
    return sum;
}
 
int main() {
    int T;
    scanf("%d",&T);
    bigfor(T) {
        int n,m;
        scanf("%d%d",&n,&m);
        char op[5];
        Build(0,n-1,1);
//      FK("Build Success!");
        for(int i=0; i1,1->0【    】
                    for(int j=0; j<4; j++) {
                        int x=opn&(1<