求助!跪求巨佬查错!
查看原帖
求助!跪求巨佬查错!
72762
oxbby楼主2021/7/2 22:59
#include<bits/stdc++.h>

using namespace std;

const int maxN=200000+5;
const int maxQ=200000+5;

int lb[20][35],fa[maxN],W[maxN],sz[maxN];
int n,m,q;
struct Edge
{
	int u,v,w;
};

vector<Edge> E[maxQ<<2];
vector< pair<int, int> > Q[maxQ<<2],Del[maxQ<<2];
map< pair<int, int>, pair<int, int> > mp;

void insert(int d,int val)
{
	for (int i=29;i>=0;--i)
		if ((1<<i)&val)
		{
			if (lb[d][i]) val^=lb[d][i];
			else
			{
				lb[d][i]=val; return;
			}
		}
}

int query(int d,int val)
{
	for (int i=29;i>=0;--i)
	{
		if ((val^lb[d][i])<val) val^=lb[d][i];
		//if (!((val>>i)&1)) continue;
		//val^=lb[d][i];
	}
	return val;
}

int find(int u,int &w)
{
	if (fa[u]==u) return u;
	w^=W[u]; return find(fa[u],w);
}

void update(int u,int l,int r,int ul,int ur,Edge e)
{
	if (ul<=l && r<=ur)
	{
		E[u].push_back(e); return;
	}
	int m=(l+r)>>1;
	if (ul<=m) update(u<<1,l,m,ul,ur,e);
	if (m<ur) update(u<<1|1,m+1,r,ul,ur,e);
}

void update2(int u,int l,int r,int x,pair<int, int> e)
{
	if (l==r)
	{
		Q[u].push_back(e); return;
	}
	int m=(l+r)>>1;
	if (x<=m) update2(u<<1,l,m,x,e);
	else update2(u<<1|1,m+1,r,x,e);
}

void solve(int u,int l,int r,int d)
{
	//printf("%d %d %d %d\n",u,l,r,d);
	for (int i=0;i<=30;++i) lb[d][i]=lb[d-1][i];
	for (int i=0;i!=E[u].size();++i)
	{
		int x=E[u][i].u,y=E[u][i].v,w=E[u][i].w;
		x=find(x,w); y=find(y,w);
		if (x==y) insert(d,w);
		else
		{
			if (sz[x]>sz[y]) swap(x,y);
			fa[x]=y; sz[y]+=sz[x]; W[x]=w;
			Del[u].push_back(make_pair(x,y));
			//printf("link %d %d %d\n",x,y,W[x]);
		}
	}
	if (l==r)
	{
		for (int i=0;i!=Q[u].size();++i)
		{
			int x=Q[u][i].first,y=Q[u][i].second,w=0;
			x=find(x,w); y=find(y,w);
			printf("%d\n",query(d,w));
		}
		return;
	}
	int m=(l+r)>>1;
	solve(u<<1,l,m,d+1); solve(u<<1|1,m+1,r,d+1);
	for (int i=Del[u].size()-1;i>=0;--i)
	{
		int x=Del[u][i].first,y=Del[u][i].second;
		fa[x]=x; W[x]=0; sz[y]-=sz[x];
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i)
	{
		int u,v,w; scanf("%d%d%d",&u,&v,&w);
		if (u>v) swap(u,v);
		mp[make_pair(u,v)]=make_pair(w,1);
	}
	scanf("%d",&q);
	for (int u=1;u<=n;++u)
	{
		fa[u]=u; sz[u]=1;
	}
	for (int i=2;i<=q+1;++i)
	{
		int op,x,y,d; scanf("%d%d%d",&op,&x,&y);
		if (x>y) swap(x,y);
		if (op==1)
		{
			scanf("%d",&d);
			mp[make_pair(x,y)]=make_pair(d,i);
		}
		else if (op==2)
		{
			map< pair<int, int>, pair<int, int> >::iterator it=mp.find(make_pair(x,y));
			update(1,1,q+1,(*it).second.second,i-1,(Edge){x,y,(*it).second.first});
			//printf("e %d %d %d %d\n",x,y,(*it).second.second,i);
			mp.erase(it);
		}
		else update2(1,1,q+1,i,make_pair(x,y));
	}
	for (map< pair<int, int>, pair<int, int> >::iterator it=mp.begin();it!=mp.end();++it)
	{
		update(1,1,q+1,(*it).second.second,q+1,(Edge){(*it).first.first,(*it).first.second,(*it).second.first});
		//printf("e %d %d %d %d\n",(*it).first.first,(*it).first.second,(*it).second.second,q+1);
	}
	solve(1,1,q+1,1);
	return 0;
}
2021/7/2 22:59
加载中...