自动搬运

查看原文

来自洛谷，原作者为

	xtx1092515503 Mathematics compares the most diverse phenomena, and discovers the secret analogies which unite them. @Joseph Fourier

搬运于2025-08-24 21:52:08，当前版本为作者最后更新于2020-07-21 09:02:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为什么大家写的都是线段树分治的呀，就没人写可删除线性基的吗，这可是少一个$\log$呢

首先，先介绍一下如何写可删除线性基。

不知道大家有没有用过LCT维护过动态图联通性呢？如果可以离线的话，我们可以在LCT上维护关于删除时间的最大生成树。当新加入一条边后，树上肯定成环，则只需要删掉环上删除时间最早的那条边即可。

没听懂没关系，反正这题也不用LCT，举这个例子只是类比一下而已

书归正传。如果我们要写可删除线性基的话，借鉴上面的思想，我们肯定希望在线性基中维护删除时间最晚的元素。

我们设$d_i$表示线性基中第$i$位的元素，$tms_i$表示该元素将在何时被删去。

按照贪心的思想，我们肯定希望越高位的线性基越晚删除——不然如果你到了时间，下面的能选而上面不能选，不是会令答案变小吗？

因此我们可以从上到下枚举每一位，能换就换，之后继续向下尝试替换。

这是尝试插入一个删除时间为$now$，值为$x$的一个bitset的代码：

void ins(int now,bi x){
//	print(x);
	for(int i=1000;i>=0;i--){
		if(!x[i])continue;
		if(tms[i]<now)swap(tms[i],now),swap(x,d[i]);
		if(!now)break;
		x^=d[i];
	}
}

有了插入代码，自然会有查询代码，查询$now$时刻的答案：

void ask(int now){
	bi res;
	for(int i=1000;i>=0;i--)if(tms[i]>now&&!res[i])res^=d[i];
	print(res);
}

这两者的复杂度都是$O(\dfrac{len^2}{w})$的，其中$len$是$01$串长度，而$w$是bitset常数。

那么这可删除线性基在本题中有什么应用呢？

不知道大家有没有做过[WC2011]最大XOR和路径啊，如果做过，就应该能看出来，任意一条从首都出发再回到首都的路径，$\operatorname{xor}$值能做出贡献的，只有环上的边，路径上的边因为来时异或一次走时再来一次，所以异或值就被消掉了。

因此我们仍然可以借鉴那题的思想，将所有的环搜出来扔进线性基中，找到线性基中的最大值即可。只需要保证每条边都会被包括在某个环中即可——线性基中进行的是异或过程，自然会保留出最优的一组解，不需要的边自然会被异或两次然后抵消掉。

我们可以设$dis_x$为$x$节点到一号节点的任意一条路径的异或值。则当我们插入一条边$x,y,z$时，只需要往线性基中加入$dis_x\operatorname{xor}dis_y\operatorname{xor}z$即可。

当然，这个操作是要离线下来的——不然你怎么知道新加入的边会在啥时候被删掉呢？

至于修改——你把它变成一次删除，一次加边即可。

当然，这里还可以给出一种在线做法（只不过多一个$\log$）：

对于插入线性基失败的某个数，记录它在插入过程中由哪些数异或起来得到了$0$。令一个集合$\mathbb{S}$表示这些数。

对于插入线性基成功的某个数，记录它在后来者的插入过程中，异或了哪些数。

当你插入一个数$x$时，维护上述集合。

当你删除一个数$x$时：

1. 如果它不在线性基中，直接删除。

2. 如果它在线性基中，且存在一个$\mathbb{S}$使得$x\in\mathbb{S}$，则删去$x$并用$\mathbb{S}$对应的那个数替代$x$即可——因为$\mathbb{S}$中所有数异或起来为$0$，故$\mathbb{S}$中任何数都可以替代$x$。在本次替代后，记得将$x$在其他集合中的所有出现，全都替换成替代的这个数。

3. 如果它在线性基中，且不存在一个$\mathbb{S}$使得$x\in\mathbb{S}$，则找到$\mathbb{T}_x$，并用$x$异或$\mathbb{T}_x$中所有数，即可消去$x$的影响。

但是，因为在线做法太恶心了，笔者还是选择了离线做法

丑的要命的代码：

#include<bits/stdc++.h>
using namespace std;
typedef bitset<1010> bi;
int n,m,q,tms[1010],ed[1010],cnt,tot,head[1010],op[1010],qwq,bkw[1010];
pair<int,int>nw[1010];
bi d[1010],dis[510],aft[1010];
struct node{
	int to,next;
	bi val;
}edge[1010];
string s;
bi read(){
	cin>>s;
	bi w(s);
	return w;
}
void ae(int u,int v){
	bi w=read();
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
	edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
void print(bi &x){
	bool stt=false;
	for(int i=999;i>=0;i--){
		if(x[i]||stt)putchar('0'+x[i]);
		if(x[i])stt=true;
	}
	if(!stt)putchar('0');
	putchar('\n');
}
void ins(int now,bi x){
//	print(x);
	for(int i=1000;i>=0;i--){
		if(!x[i])continue;
		if(tms[i]<now)swap(tms[i],now),swap(x,d[i]);
		if(!now)break;
		x^=d[i];
	}
}
bool vis[510];
void dfs(int x){
	for(int i=head[x];i!=-1;i=edge[i].next){
		if(vis[edge[i].to])ins(0x3f3f3f3f,dis[x]^dis[edge[i].to]^edge[i].val);
		else vis[edge[i].to]=true,dis[edge[i].to]=dis[x]^edge[i].val,dfs(edge[i].to);
	}
}
void ask(int now){
	bi res;
	for(int i=1000;i>=0;i--)if(tms[i]>now&&!res[i])res^=d[i];
	print(res);
}
int main(){
	cin>>n>>m>>q,memset(head,-1,sizeof(head)),qwq=q+1;
	for(int i=1,x,y;i<=m;i++)cin>>x>>y,ae(x,y);
	dfs(1);
	ask(0);
	for(int i=1,x,y;i<=q;i++){
		cin>>s;
		if(s[1]=='d')cin>>x>>y,op[i]=++tot,aft[tot]=(read()^dis[x]^dis[y]),nw[tot]=make_pair(x,y),bkw[tot]=tot;
		else if(s[1]=='h')cin>>x,ed[bkw[x]]=i,op[i]=--qwq,aft[qwq]=(dis[nw[x].first]^dis[nw[x].second]^read()),bkw[x]=qwq;
		else if(s[1]=='a')cin>>x,ed[bkw[x]]=i;
	}
	for(int i=1;i<=q;i++)if(!ed[i])ed[i]=0x3f3f3f3f;
	for(int i=1;i<=q;i++){
		if(op[i])ins(ed[op[i]],aft[op[i]]);
		ask(i);
	}
	return 0;
}