题目：https://loj.ac/problem/2312
https://www.luogu.org/problemnew/show/P3733
原本以为要线段树分治+LCT，查了查发现环上的值直接是 dis[ u ] ^ dis[ v ] ^ w[ i ] 就行了（其中 u , v 是边的两端， i 是边的标号）。
再看一下题，发现一开始一定是连通的。所以剩下的就和 bzoj 4184 shallot 一样用线性基就行了。
因为有 1000 位，所以用 bitset 。
线性基求最大值原来不用判断 if( ( ans^b[ i ] ) > ans ) ans ^= b[ i ] ，直接看 ans 的这一位上是不是 0 就行了。
线段树的一个点不要用 vector 存 bitset ，存一下边的编号，然后每条边开 bitset 存一下自己就行了，能省出很多空间。
在线段树上 dfs 求答案的时候不要把一个线性基带在参数上，给每个点用 vector 记录一下它改了线性基的哪些位就行了，这样好像对栈空间更友好。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<bitset> #define ls Ls[cr] #define rs Rs[cr] #define pb push_back #define BT bitset<M> using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } int Mx(int a,int b){return a>b?a:b;} int Mn(int a,int b){return a<b?a:b;} const int N=505,M=1005; int n,m,hd[N],xnt,to[M],nxt[M],fa[N],dy[/*N*/M],mx; int tot,Ls[M<<1],Rs[M<<1]; char ch[M]; bool vis[/*N*/M]; BT dis[N],w[M],b[M],ew[M],tmp; vector<int> vt[M<<1],cg[M<<1]; struct Ed{int x,y; BT w;}ed[/*N*/M]; void cz(BT k,int cr) { for(int i=mx-1;i>=0;i--) { if(!k[i])continue; if(!b[i].any()){ b[i]=k;cg[cr].pb(i);break;} else k^=b[i]; } } void print() { tmp.reset(); for(int i=mx-1;i>=0;i--) if(!tmp[i])tmp^=b[i]; int st=mx-1; for(;st>0&&!tmp[st];st--); for(;st>=0;st--) putchar(tmp[st]+'0'); puts(""); } void rd1() { scanf("%s",ch); int len=strlen(ch); mx=Mx(mx,len); tmp.reset();// for(int i=0,j=len-1;i<len;i++,j--) tmp[i]=(ch[j]-'0'); } int fnd(int a){return fa[a]==a?a:fa[a]=fnd(fa[a]);} void add(int x,int y) { int u=fnd(x),v=fnd(y); if(u==v) { ed[++tot].x=x; ed[tot].y=y; ed[tot].w=tmp; } else { fa[u]=v; to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=tmp; to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;w[xnt]=tmp; } } void dfs(int cr,int fa) { for(int i=hd[cr],v;i;i=nxt[i]) if((v=to[i])!=fa) { dis[v]=dis[cr]^w[i]; dfs(v,cr); } } void build(int l,int r,int cr) { if(l==r)return; int mid=l+r>>1; ls=++tot; build(l,mid,ls); rs=++tot; build(mid+1,r,rs); } void ins(int l,int r,int cr,int L,int R,int k) { if(l>=L&&r<=R){vt[cr].pb(k);return;} int mid=l+r>>1; if(L<=mid)ins(l,mid,ls,L,R,k); if(mid<R)ins(mid+1,r,rs,L,R,k); } void dfs(int l,int r,int cr) { int sz=vt[cr].size(); for(int i=0;i<sz;i++)cz(ew[vt[cr][i]],cr); if(!ls)print(); else dfs(l,l+r>>1,ls), dfs((l+r>>1)+1,r,rs); sz=cg[cr].size(); for(int i=0;i<sz;i++)b[cg[cr][i]].reset(); } int main() { n=rdn();m=rdn();int Q=rdn(); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1,u,v;i<=m;i++) { u=rdn();v=rdn();rd1(); add(u,v); } dfs(1,0); int t2=tot; if(Q){ tot=1;build(1,Q,1);} for(int i=1,u;i<=t2;i++) { tmp=dis[ed[i].x]^dis[ed[i].y]^ed[i].w; cz(tmp,0); } int cnt=0; tot=0; for(int i=1,x;i<=Q;i++) { scanf("%s",ch); if(ch[0]=='A') { cnt++; dy[cnt]=i; ed[cnt].x=rdn();ed[cnt].y=rdn(); rd1(); ed[cnt].w=tmp; } else if(ch[1]=='a') { x=rdn(); ew[++tot]=dis[ed[x].x]^dis[ed[x].y]^ed[x].w; ins(1,Q,1,dy[x],i-1,tot); vis[x]=1; } else { x=rdn(); rd1(); ew[++tot]=dis[ed[x].x]^dis[ed[x].y]^ed[x].w; ins(1,Q,1,dy[x],i-1,tot); dy[x]=i; ed[x].w=tmp; } } for(int i=1;i<=cnt;i++) if(!vis[i]) { ew[++tot]=dis[ed[i].x]^dis[ed[i].y]^ed[i].w; ins(1,Q,1,dy[i],Q,tot); } print(); if(Q)dfs(1,Q,1); return 0; }