Codeforces 587 E. Duff as a Queen

题目链接：http://codeforces.com/contest/587/problem/E
其实就是线段树维护区间线性基，合并的时候注意一下。复杂度${O(nlog^{3})}$
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 using namespace std;
  9 #define maxn 100100
 10 #define llg int
 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 12 llg n,m,Q;
 13 
 14 inline int getint()
 15 {
 16        int w=0,q=0; char c=getchar();
 17        while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
 18        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
 19 }
 20 
 21 struct XOR
 22 {
 23     llg bas[31],lazy,val;
 24     
 25     void init() {memset(bas,0,sizeof(bas)); lazy=val=0;}
 26 
 27     llg count() 
 28     {
 29         llg ans=0;
 30         for (llg i=0;i<=30;i++) if (bas[i]) ans++;
 31         return ans;
 32     }
 33 
 34     void add(llg x)
 35     {
 36         for (llg i=30;i>=0;i--)
 37             if ((x>>i)&1)
 38             {
 39                 if (bas[i]) x^=bas[i];
 40                 else {bas[i]=x; break;}
 41             }
 42     }
 43 
 44     XOR operator +(const XOR&a) const
 45     {
 46         XOR ans; ans.init();
 47         for (llg i=0;i<=30;i++) ans.add(bas[i]),ans.add(a.bas[i]);
 48         ans.add(a.val^val);
 49         ans.val=val;
 50         return ans;
 51     }
 52 }po[maxn*10],ans;
 53 
 54 void pushdown(llg o,llg l,llg r)
 55 {
 56     llg lc=o<<1,rc=o<<1|1;
 57     if (po[o].lazy)
 58     {
 59         po[lc].lazy^=po[o].lazy;
 60         po[rc].lazy^=po[o].lazy;
 61         po[lc].val^=po[o].lazy;
 62         po[rc].val^=po[o].lazy;
 63         po[o].lazy=0;
 64     }
 65 }
 66 
 67 void build(llg o,llg l,llg r)
 68 {
 69     po[o].init();
 70     if (l==r)
 71     {
 72         po[o].val=getint();
 73         return ;
 74     }
 75     llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;
 76     build(lc,l,mid);
 77     build(rc,mid+1,r);
 78     po[o]=po[lc]+po[rc];
 79 }
 80 
 81 void modify(llg o,llg l,llg r,llg L,llg R,llg d)
 82 {
 83     if (l>=L && r<=R)
 84     {
 85         po[o].lazy^=d;
 86         po[o].val^=d;
 87         return ;
 88     }
 89     pushdown(o,l,r);
 90     llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;
 91     if (L<=mid) modify(lc,l,mid,L,R,d);
 92     if (R>mid) modify(rc,mid+1,r,L,R,d);
 93     po[o]=po[lc]+po[rc];
 94 }
 95 
 96 void query(llg o,llg l,llg r,llg L,llg R)
 97 {
 98     if (l>=L && r<=R)
 99     {
100         ans=ans+po[o];
101         return ;
102     }
103     pushdown(o,l,r);
104     llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;
105     if (L<=mid) query(lc,l,mid,L,R);
106     if (R>mid) query(rc,mid+1,r,L,R);
107     po[o]=po[lc]+po[rc];
108 }
109 
110 int main()
111 {
112     yyj("xor");
113     cin>>n>>Q;
114     build(1,1,n);
115     while (Q--)
116     {
117         llg ty=getint(),l=getint(),r=getint();
118         if (ty==1)
119         {
120             llg d=getint();
121             modify(1,1,n,l,r,d);
122         }
123         else
124         {
125             ans.init();
126             query(1,1,n,l,r);
127             printf("%d
",(1<<ans.count()));
128         }
129     }
130     return 0;
131 }