【YbtOJ#883】最大的割

题目

题目链接：https://www.ybtoj.com.cn/contest/118/problem/3

(nleq 500,m,Lleq 1000)。(L) 表示边权二进制下位数最大值。

思路

我们设一个点的点权为它所连接的边的边权异或和。这样一个割的异或和就与一个点集的点权异或和等价了。
我们需要知道任意时刻的线性基。由于线性基不好删除，考虑采用离线算法。事实上这道题有在线支持线性基删除的做法，没听懂 /kel。
因为每一个点的点权可以划分成若干个区间且每个区间的点权相同，所以我们可以把每一个点在不同时间的点权映射到线段树上。然后线段树分治，在每一层新开一个线性基，从父亲的线性基那里复制信息过来，然后再插入这个区间的点的点权。到达叶子节点后线性基查询最大值即可。
由于所有点划分成的区间总数是 (O(n+m)) 的，所以线性基用 bitset 时间可以优化到 (O(frac{mLlog n+m^2L}{omega}))。空间 (O(frac{mLlog m}{omega}))。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1010;
int n,m,last[N];
char ch[N];
bitset<N> sav,val[N];

struct Xor
{
	bitset<N> d[N];
	
	void ins(bitset<N> x)
	{
		for (int i=N-1;i>=0;i--)
			if (x[i])
			{
				if (!d[i][i]) { d[i]=x; return; }
				x^=d[i];
			}
	}
	
	void query()
	{
		bitset<N> res;
		for (int i=N-1;i>=0;i--)
			if (!res[i]) res^=d[i];
		int i=N-1;
		while (i && !res[i]) i--;
		for (;i>=0;i--) printf("%d",(int)res[i]);
		printf("
");
	}
}a[N];

struct SegTree
{
	vector<bitset<N> > b[N*4];
	
	void update(int x,int l,int r,int ql,int qr,int k)
	{
		if (ql>qr) return;
		if (ql<=l && qr>=r)
		{
			b[x].push_back(val[k]);
			return;
		}
		int mid=(l+r)>>1;
		if (ql<=mid) update(x*2,l,mid,ql,qr,k);
		if (qr>mid) update(x*2+1,mid+1,r,ql,qr,k);
	}
	
	void solve(int dep,int x,int l,int r)
	{
		for (int i=0;i<N;i++)
			a[dep].d[i]=a[dep-1].d[i];
		for (int i=0;i<b[x].size();i++)
			a[dep].ins(b[x][i]);
		if (l==r) { a[dep].query(); return; }
		int mid=(l+r)>>1;
		solve(dep+1,x*2,l,mid);
		solve(dep+1,x*2+1,mid+1,r);
	}
}seg;

int main()
{
	freopen("cut.in","r",stdin);
	freopen("cut.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) last[i]=1;
	for (int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d%s",&x,&y,ch);
		seg.update(1,1,m,last[x],i-1,x);
		seg.update(1,1,m,last[y],i-1,y);
		last[x]=last[y]=i;
		int len=strlen(ch);
		sav=0;
		for (int j=0;j<len;j++) sav[j]=ch[len-j-1]-48;
		val[x]^=sav; val[y]^=sav;
	}
	for (int i=1;i<=n;i++)
		seg.update(1,1,m,last[i],m,i);
	seg.solve(1,1,1,m);
	return 0;
}