CodeForces 242E - XOR on Segment 二维线段树？

今天练习赛的题....又是线段树的变换..拿到题我就敲了个点更新区间查询的..果断超时...然后想到了可以将每个数与合表示成不进位的二进制数..这样就可以区间进行更新了..比赛的时候写搓了..刚重写了一遍过~~

为了表示每位的二进制数...线段树开成二维的...第一维老样子~记是树中哪个点..第二维记当前段之和的不进位二进制数...因为最多到10^5...也就是不会超过2^20...第二维开个20就够了....

区间更新如: 3 3 这段全xor 3...3+3的不进位二进制数为(2,2)...xor 3,3的二进制为(1,1)..将x二进制为1的改为len-原来的...那么(2-2,2-2)=0

2 4 这段全xor 3...2+4的不进位二进制数为(1,1,0).....将x二进制为1的改为len-原来的..那么(1,2-1,2-0)=(1,1,2)=2+2+4=8

不知道这货是不是叫二维线段树.....二维线段树应该是树中有树吧..也就是第一颗树的每个节点又是线段树....

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#define ll long long
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 100005
using namespace std;  
struct node
{
       int a[22];
};
int sum[MAXN<<2][22],col[MAXN<<2][22];
ll h[22];
void PushDown(int len,int now)
{
       int i; 
       for (i=0;i<20;i++) 
          if (col[now][i])
          {
                sum[now<<1][i]=(len-(len>>1))-sum[now<<1][i];
                sum[(now<<1)|1][i]=(len>>1)-sum[(now<<1)|1][i];
                col[now<<1][i]=1-col[now<<1][i];
                col[(now<<1)|1][i]=1-col[(now<<1)|1][i];
          }
       for (i=0;i<20;i++) col[now][i]=0;
       return;
}
void update(int L,int R,int x,int l,int r,int now)
{
       int i;
       if (L<=l && R>=r)
       {
               for (i=0;i<20;i++) 
                  if (x&(1<<i))
                  {
                         sum[now][i]=(r-l+1)-sum[now][i];
                         col[now][i]=1-col[now][i];   
                  }
               return;
       }   
       PushDown(r-l+1,now);
       int mid=(l+r)>>1;
       if (L<=mid) update(L,R,x,l,mid,now<<1);
       if (R>mid)  update(L,R,x,mid+1,r,(now<<1)|1); 
       for (i=0;i<20;i++) sum[now][i]=sum[now<<1][i]+sum[(now<<1)|1][i];
       return;
}
node query(int L,int R,int l,int r,int now)
{
       int i;
       node h;
       memset(h.a,0,sizeof(h.a));
       if (L<=l && R>=r)
       {
               for (i=0;i<20;i++) h.a[i]=sum[now][i];
               return h;
       }
       PushDown(r-l+1,now);
       int mid=(l+r)>>1; 
       if (L<=mid) 
       {
             node p=query(L,R,l,mid,now<<1); 
             for (i=0;i<20;i++) h.a[i]+=p.a[i];
       }
       if (R>mid)  
       {
             node p=query(L,R,mid+1,r,(now<<1)|1);
             for (i=0;i<20;i++) h.a[i]+=p.a[i];
       }
       return h;
}
int main()
{
       int i,n,m;  
       while (~scanf("%d",&n))
       { 
               memset(sum,0,sizeof(sum));
               memset(col,0,sizeof(col));
               for (i=1;i<=n;i++) 
               {
                      int x;
                      scanf("%d",&x);
                      update(i,i,x,1,n,1);
               }
               scanf("%d",&m);
               while (m--)
               {
                      int tp,l,r;
                      scanf("%d%d%d",&tp,&l,&r);
                      if (tp==1)
                      {
                            ll ans,x; 
                            node h=query(l,r,1,n,1);
                            ans=0,x=1;
                            for (i=0;i<20;i++)
                            {
                                   ans+=x*h.a[i];
                                   x*=2;
                            }
                            printf("%I64d\n",ans);                                                        
                      }else
                      {
                            int x;
                            scanf("%d",&x);
                            update(l,r,x,1,n,1);
                      }
               }
       }
       return 0;
}