学步园

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?

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)

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

A = [1 2 4 7]

SUM 0 2, result=1+2+4=7;

XOR 5 0 0, A=[4 2 4 7];

OR 6 0 3, A=[6 6 6 7];

SUM 0 2, result=6+6+6=18.

分析：逻辑运算都是按位运算的，所以一个数的不同位置进得按位运算都是互不影响的，而且每个数最多也就只有4位二进制位，所以可以看成四棵线段树，每个结点保存两个值：一个是当前区间内有多少个1，二是子结点是否需要进行XOR更新。

#include<stdio.h>
struct node
{
    int sum;//区间内1的个数，全1等价于当前区间数的第i位或运算，全0等价与运算（1&0=0,1&1=1,所以不用考虑位置与1相与）
    int XOR;//子节点是否需要异或
}tree[4][2*1000005];
int ans[1000005];
void builde(int l,int r,int k,int i)
{
    int m=(l+r)/2;

    tree[i][k].XOR=0;
    if(l==r)
    {
        if((1<<i)&ans[l])
            tree[i][k].sum=1;
        else tree[i][k].sum=0;
        return ;
    }

    builde(l,m,k*2,i);
    builde(m+1,r,k*2+1,i);

    tree[i][k].sum=tree[i][k*2].sum+tree[i][k*2+1].sum;
}

void set_childe(int l,int r,int k,int i)
{
    int flag=0,m;
    m=(l+r)/2;
    if(tree[i][k].sum==r-l+1)
    {
        flag=1;
        tree[i][k*2].sum=m-l+1;
        tree[i][k*2+1].sum=r-m;
    }
    else if(tree[i][k].sum==0)
        tree[i][k*2].sum=tree[i][k*2+1].sum=0,flag=1;

    if(tree[i][k].XOR)
    {
        if(!flag)//还没有跟据父节点更新时
        {
            tree[i][k*2].sum=(m-l+1)-tree[i][k*2].sum;
            tree[i][k*2+1].sum=(r-m)-tree[i][k*2+1].sum;
        }

       tree[i][k*2].XOR^=1;
       tree[i][k*2+1].XOR^=1;
    }
    tree[i][k].XOR=0;
}

void update_and(int l,int r,int k,int L,int R,int i)
{
    int m=(l+r)/2;
    if(L<=l&&r<=R)
    {
        tree[i][k].sum=0;
        return ;
    }
    set_childe(l,r,k,i);
    if(L<=m)
        update_and(l,m,k*2,L,R,i);
    if(m<R)
        update_and(m+1,r,k*2+1,L,R,i);
    tree[i][k].sum=tree[i][k*2].sum+tree[i][k*2+1].sum;
}

void update_or(int l,int r,int k,int L,int R,int i)
{
    int m=(l+r)/2;
    if(L<=l&&r<=R)
    {
        tree[i][k].sum=r-l+1;
        return ;
    }
    set_childe(l,r,k,i);
    if(L<=m)
        update_or(l,m,k*2,L,R,i);
    if(m<R)
        update_or(m+1,r,k*2+1,L,R,i);
    tree[i][k].sum=tree[i][k*2].sum+tree[i][k*2+1].sum;
}

void update_xor(int l,int r,int k,int L,int R,int i)
{
    int m=(l+r)/2;
    if(L<=l&&r<=R)
    {
        tree[i][k].sum=(r-l+1)-tree[i][k].sum;
        tree[i][k].XOR^=1;
        return ;
    }
    set_childe(l,r,k,i);
    if(L<=m)
        update_xor(l,m,k*2,L,R,i);
    if(m<R)
        update_xor(m+1,r,k*2+1,L,R,i);
    tree[i][k].sum=tree[i][k*2].sum+tree[i][k*2+1].sum;
}
int query(int l,int r,int k,int L,int R,int i)
{
    int m=(l+r)/2;
    if(L<=l&&r<=R)
    {
        return tree[i][k].sum;
    }
    set_childe(l,r,k,i);
    int sum=0;
    if(L<=m)
        sum+=query(l,m,k*2,L,R,i);
    if(m<R)
        sum+=query(m+1,r,k*2+1,L,R,i);
    return sum;
}

int main()
{
    int t,n,m,L,R,opn;
    char str[10];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        scanf("%d",&ans[i]);

        for(int i=0; i<4; i++)
        builde(1,n,1,i);

        while(m--)
        {
            scanf("%s",str);
            if(str[0]=='S')
            {
                scanf("%d%d",&L,&R);
                L++; R++;
                int sum=0,k;
                for(int i=0; i<4; i++)
                    sum+=query(1,n,1,L,R,i)*(1<<i);
                printf("%d\n",sum);
            }
            else
            {
                scanf("%d%d%d",&opn,&L,&R);
                L++; R++;
                for(int i=0;i<4;i++)
                if(str[0]=='A')
                {
                   if(!((1<<i)&opn)) update_and(1,n,1,L,R,i);
                }
                else if(str[0]=='O')
                {
                    if((1<<i)&opn) update_or(1,n,1,L,R,i);
                }
                else if((1<<i)&opn)
                    update_xor(1,n,1,L,R,i);
            }
        }
    }
}