sol
线性基+线段树分治傻题。
复杂度应该是(O((n+mlog n)frac{L^2}{omega}))？
code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
const int N = 1005;
#define ll bitset<N>
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
char s[N];
ll gl(){
scanf("%s",s);int len=strlen(s);ll x;x.reset();
for (int i=0;i<len;++i) x[len-i-1]=s[i]-'0';return x;
}
void po(ll x){
int i=N-1;while (!x[i]) --i;
while (~i) putchar(x[i]+'0'),--i;puts("");
}
int n,m,q,to[N],nxt[N],head[N],cnt,fa[N],tot,id,pos[N];
ll ww[N],dis[N];vector<int>v[N<<2];
struct edge{int u,v,l,r;ll w;}E[N<<1];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void link(int u,int v,ll w){
to[++cnt]=v;nxt[cnt]=head[u];ww[cnt]=w;head[u]=cnt;
to[++cnt]=u;nxt[cnt]=head[v];ww[cnt]=w;head[v]=cnt;
}
void dfs(int u,int f){
for (int e=head[u];e;e=nxt[e])
if (to[e]!=f) dis[to[e]]=dis[u]^ww[e],dfs(to[e],u);
}
void modify(int x,int l,int r,int ql,int qr,int i){
if (l>=ql&&r<=qr) {v[x].push_back(i);return;}
int mid=l+r>>1;
if (ql<=mid) modify(x<<1,l,mid,ql,qr,i);
if (qr>mid) modify(x<<1|1,mid+1,r,ql,qr,i);
}
struct xxj{
ll p[N];
void insert(ll x){
for (int i=N-1;~i;--i)
if (x[i]){
if (!p[i].any()) {p[i]=x;return;}
x^=p[i];
}
}
ll calc(){
ll x;x.reset();
for (int i=N-1;~i;--i)
if (!x[i]) x^=p[i];
return x;
}
}tmp;
void query(int x,int l,int r,xxj S){
for (auto i:v[x]) S.insert(dis[E[i].u]^dis[E[i].v]^E[i].w);
if (l==r) {po(S.calc());return;}int mid=l+r>>1;
query(x<<1,l,mid,S);query(x<<1|1,mid+1,r,S);
}
int main(){
n=gi();m=gi();q=gi();
for (int i=1;i<=n;++i) fa[i]=i;
for (int i=1;i<=m;++i){
int u=gi(),v=gi();ll w=gl();
if (find(u)^find(v)) link(u,v,w),fa[find(u)]=find(v);
else E[++tot]=(edge){u,v,0,q,w};
}
dfs(1,0);
for (int i=1;i<=q;++i){
scanf("%s",s);
if (s[0]=='A'){
int u=gi(),v=gi();ll w=gl();
E[++tot]=(edge){u,v,i,q,w};pos[++id]=tot;
}else if (s[1]=='h'){
int x=gi();ll w=gl();
E[pos[x]].r=i-1;E[++tot]=(edge){E[pos[x]].u,E[pos[x]].v,i,q,w};pos[x]=tot;
}else{
int x=gi();E[pos[x]].r=i-1;pos[x]=-1;
}
}
for (int i=1;i<=tot;++i) modify(1,0,q,E[i].l,E[i].r,i);
query(1,0,q,tmp);return 0;
}