链接
线段树分治 (+) 线性基 (+) bitset。
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pb push_back
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=5e2+3,M=1e3+5;
struct hh{
int to,nxt;bitset<M>w;
}e[N<<1];
struct line{
int x,y,t;bitset<M>w;
}l[M];
int n,m,k,num,fa[N],fir[N],bo[M];
bitset<M>val[N],b[M];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL void add(int x,int y,bitset<M>&z){e[++num]=(hh){y,fir[x],z},fir[x]=num;}
int find(int x){return x^fa[x]?fa[x]=find(fa[x]):x;}
IL int ins(bitset<M>a){
for(int i=1000;~i;--i)
if(a[i]){
if(!b[i][i]){b[i]=a;return 1;}
else a^=b[i];
}
return 0;
}
IL void dele(bitset<M>a){
for(int i=1000;~i;--i)
if(a[i]){
a^=b[i];
if(a.none()){b[i].reset();return;}
}
}
IL void print(bitset<M>a){
int Max=1001;
while(Max&&!a[--Max]);
while(~Max) printf("%d",(int)a[Max--]);
printf("
");
}
IL void ask(){
bitset<M>a;a.reset();
for(int i=1000;~i;--i)
if(b[i][i]&&!a[i]) a^=b[i];
print(a);
}
void dfs(int u,int fa){
for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
if(v^fa) val[v]=val[u]^e[i].w,dfs(v,u);
}
struct segment{
vector<line>a[M<<2];
void mdy(int k,int l,int r,int ll,int rr,line &u){
if(l>=ll&&r<=rr){a[k].pb(u);return;}
int mid=l+r>>1;
if(ll<=mid) mdy(ls,l,mid,ll,rr,u);
if(rr>mid) mdy(rs,mid+1,r,ll,rr,u);
}
void solve(int k,int l,int r){
vector<int>bo;
for(int i=0;i<a[k].size();++i)
bo.pb(ins(val[a[k][i].x]^val[a[k][i].y]^a[k][i].w));
int mid=l+r>>1;
if(l==r) ask();
else solve(ls,l,mid),solve(rs,mid+1,r);
for(int i=a[k].size()-1;~i;--i)
if(bo[i]) dele(val[a[k][i].x]^val[a[k][i].y]^a[k][i].w);
}
}T;
int main()
{
int x,y,z;char s[M];
n=in(),m=in(),k=in();
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i){
x=in(),y=in(),scanf("%s",s);
int len=strlen(s);
for(int j=0;j<len;++j) l[i].w[len-j-1]=s[j]-'0';
l[i].x=x,l[i].y=y;
if(find(x)^find(y)) add(x,y,l[i].w),add(y,x,l[i].w),bo[i]=1,fa[find(x)]=y;
}
num=0,dfs(1,0);
for(int i=1;i<=m;++i) if(!bo[i]) ins(val[l[i].x]^val[l[i].y]^l[i].w);
ask();
for(int i=1;i<=k;++i){
scanf("%s",s+1),x=in();
if(s[1]=='A'){
l[++num].w.reset(),y=in(),scanf("%s",s);
int len=strlen(s);
for(int j=0;j<len;++j) l[num].w[len-j-1]=s[j]-'0';
l[num].x=x,l[num].y=y,l[num].t=i;
}
else if(s[2]=='a') T.mdy(1,1,k,l[x].t,i-1,l[x]),l[x].x=-1;
else{
T.mdy(1,1,k,l[x].t,i-1,l[x]);
scanf("%s",s);int len=strlen(s);l[x].w.reset();
for(int j=0;j<len;++j) l[x].w[len-j-1]=s[j]-'0';
l[x].t=i;
}
}
for(int i=1;i<=num;++i) if(l[i].x^-1) T.mdy(1,1,k,l[i].t,k,l[i]);
if(k) T.solve(1,1,k);
return 0;
}