某天我觉得一切题目都是那么不可做，于是百度了一下“傻逼题”……

 

题目大意：对于图中的任意一个点集（可以为空或者全集），所有恰好有一个端点在这个点集中的边组成的集合被称为割。一个割的权值被定义为所有在这个割上的边的异或和。现在有一张一开始只有n个点的图，m次操作，每次加入一条边并询问当前最大的割的权值。（n<=500，m<=1000，边权用二进制表示，二进制数长度L<=1000）

思路：把选割看成把图分成两部分，“脚踏两只船”的边就是割，考虑选每个点的贡献，实际上就是使答案异或上连向这个点的所有边的异或和，这样每条边如果两端点都选或都不选贡献为0，只有一个选贡献就是这个边权。问题转化成n个数，一开始都是0，每次把其中两个异或上一个数，询问当前最大的子集异或和。考虑用线性基解决，由于线性基只支持插入，我们用线段树分治解决。暴力计算二进制数复杂度有点大，用bitset加速即可。总复杂度O(mlogm*L^2/32)。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;inline int read(){    int x;char c;    while((c=getchar())<'0'||c>'9');    for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0';    return x;}#define MN 500#define ML 1000bitset
         
           a[MN+5],w,z[ML+5],ans[ML+5];struct node{
   int l,r;vector
          
           
             > v;}t[ML*4+5];char s[ML+5];int l[MN+5];vector
            
              v[ML*4+5];void build(int k,int l,int r){ if((t[k].l=l)==(t[k].r=r))return; int mid=l+r>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r);}void ins(int k,int l,int r,bitset
             
              &x){ if(t[k].l==l&&t[k].r==r){t[k].v.push_back(x);return;} int mid=t[k].l+t[k].r>>1; if(r<=mid)ins(k<<1,l,r,x); else if(l>mid)ins(k<<1|1,l,r,x); else ins(k<<1,l,mid,x),ins(k<<1|1,mid+1,r,x);}void dfs(int x){ int i,j; for(i=0;i
              
               =0;--j)x=ans[i][j],printf("%d",x);puts(""); }}