Description：

定义无向图的割为一个点集与图中其他点的连边的异或和，每次加入一条权值为 $c$ 的边，询问这张图的最大割。

$1\leqslant n\leqslant 500,1\leqslant m\leqslant 1000,1\leqslant l\leqslant 1000$

Solution：

由于异或满足消去率，所以设 $v(i)$ 为与点 $i$ 相连的边的边权异或和，那么选出来一些点的 $v(i)$ 异或和就是割，因为在同一子集中的被消去了，所以只要求出每个点的 $v(i)$ 再加到线性基里求个异或最大值就行了，但是有加边操作，也就是说 $v(i)$ 会变，但是在两次修改之间是不动的，而线性基支持插入不支持删除，这启示我们可以用线段树分治，每次把一段区间内的 $v(i)$ 加到线段树的对应区间那里，最后 $dfs$ 整棵线段树维护一下从根到每个叶子的线性基最大值就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<bitset>

#include<cstring>

using namespace std;

int n,m;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

#define MAXL 1010

inline bitset<MAXL> readbit()

{

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	bitset<MAXL> s;

	while(isdigit(c))

	{

		s = s << 1;s[0] = c - '0';

		c = getchar();

	}

	return s;

}

void print(bitset<MAXL> k)

{

	bool tag = false;

	for(int i = MAXL - 1;i >= 0;--i)

	{

		if(k[i])tag = true;

		if(!k[i] && !tag)continue;

		if(k[i])putchar('1');

		else putchar('0');

	}

	if(!tag)putchar('0');

	puts("");

	return;

}

#define MAXN 510

#define MAXM 1010

bitset<MAXL> val[MAXN];

int last[MAXN];

struct node

{

	int lc,rc;

	vector< bitset<MAXL> > v;

}t[MAXM << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int L,int R,bitset<MAXL> s,int l,int r)

{

	if(R < 1)return;

	if(L <= l && r <= R)

	{

		t[rt].v.push_back(s);

		return;

	}

	if(L <= mid)add(t[rt].lc,L,R,s,l,mid);

	if(R > mid)add(t[rt].rc,L,R,s,mid + 1,r);

	return;

}

struct LinearBase

{

	bitset<MAXL> d[MAXL];

	LinearBase()

	{

		for(int i = 0;i < MAXL;++i)d[i].reset();

	}

	void insert(bitset<MAXL> k)

	{

		for(int i = MAXL - 1;i >= 0;--i)

		{

			if((k >> i)[0])

			{

				if(!d[i].any())

				{

					d[i] = k;

					return;

				}

				else

				{

					k ^= d[i];

				}

			}

		}

	}

	bitset<MAXL> query()

	{

		bitset<MAXL> res;

		for(int i = MAXL - 1;i >= 0;--i)

		{

			if(d[i].any() && !res[i])res ^= d[i];

		}

		return res;

	}

};

void pt(int rt,int l,int r,LinearBase k)

{

	for(vector< bitset<MAXL> >::iterator it = t[rt].v.begin();it != t[rt].v.end();++it)

	{

		k.insert(*it);

	}

	if(l == r)

	{

		print(k.query());

		return;

	}

	pt(t[rt].lc,l,mid,k);

	pt(t[rt].rc,mid + 1,r,k);

	return;

}

int main()

{

	read();n = read();m = read();

	build(root,1,m);

	int x,y;

	bitset<MAXL> s;

	for(int i = 1;i <= m;++i)

	{

		x = read();y = read();s = readbit();

		add(root,last[x] + 1,i - 1,val[x],1,m);

		add(root,last[y] + 1,i - 1,val[y],1,m);

		last[x] = last[y] = i - 1;

		val[x] ^= s;val[y] ^= s;

	}

	for(int i = 1;i <= n;++i)

	{

		add(root,last[i] + 1,m,val[i],1,m);

	}

	LinearBase lb;

	pt(root,1,m,lb);

	return 0;

}