經典傻逼題
Description
這是一道經典傻逼題，對經典題很熟悉的人也不要激動，希望大家不要傻逼。
考慮一張N個點的帶權無向圖，點的編号為1到N。 對于圖中的任意一個點集（可以為空或者全集），所有恰好有一個端點在這個點集中的邊組成的集合被稱為割。 一個割的權值被定義為所有在這個割上的邊的異或和。
一開始這張圖是空圖， 現在，考慮給這張無向圖不斷的加邊， 加入每條邊之後，你都要求出目前權值最大的割的權值， 注意加入的邊永遠都不會消失。
Input
輸入的第一行包括一個數ID表示資料編号， 如第一組資料中的ID = 1。注意樣例資料中的ID = 0。
接下來的第一行包括兩個整數N,M表示圖的點數和總共加的邊。
接下來M行，每行三個正整數x,y,w表示在點x和點y之間加入一條權值為w的邊。
注意x和y可能相同，兩條不同的邊也可能連接配接了同一對點。
此外， w将以二進制形式從高位向低位給出，比如， 6 = 110(2)，是以如果邊權為 6，那麼w将會是110。
1 ≤ N≤ 500， 1 ≤ M ≤ 1000， 0 ≤ L < 1000， 1 ≤ x,y≤ N
Output
輸出M行，按順序輸出每一條邊加入之後權值最大的割的權值。
同樣，你也要以二進制形式輸出，形式和輸入格式中描述的形式一樣。
Sample Input
0 3
6
1 2 1
1 2 1
3 3 111
1 3 101101
1 2 1011
2 3 111011
Sample Output
1 0 0
101101
101101
110000
HINT
前三條邊加入之後的答案較為顯然，考慮後三條邊，加入第六條邊之前， 考慮點集{1,2}，它對應的割隻有第四條邊， 是以答案就是第四條邊的權值。
考慮加入最後一條邊以後的情況，此時點集{1,2}對應的割變成了第四條邊和第六條邊組成的集合，權值也發生了相應的改變。
點集{2}對應的割是第五條邊和第六條邊組成的集合， 可以證明這就是權值最大的割，權值為1011(2) ⊕ 111011(2) =110000(2)
如果它是經典題，那麼咱就是shabi……
因為這麼經典的操作居然現在才第一次寫……
思路:
這個叫線段樹分治的東西，好像在哪裡見過……
而且好像當時被叫做時間線段樹……
首先考慮異或的性質。
可以發現，如果一條邊的兩個點選中，那麼這條邊将沒有貢獻。
于是如果咱們把邊權異或到這條邊的兩個點上，可以恰好使用選中的節點的點權異或和來描述所有滿足條件的邊的貢獻。
因為一旦一條邊的兩個點均被選中，那麼這個點的邊權就被異或運算消掉了。
那麼現在要求從所有點中選出一個子集使得點權異或和最大。
于是考慮線性基貪心，從高位向低位枚舉貪心，若答案異或上目前元素可以變大，那就異或目前元素，即可得到答案。
然而線性基很難茲瓷修改。
可以考慮針對高斯消元把原先的某一個點權的影響消去再重新插入。
然而貌似很難寫。
于是使用線段樹分治，用一棵線段樹描述一個時間軸。
對于每個點，它在整個操作過程中的權值變化可以按時間分成一些内部權值相同的小段。
對于每一段這樣的小段，線上段樹上對應時間區間打上目前權值的标記，代表在這一段的時間内這個點的權值是這一段的值。
最後dfs一遍整棵線段樹，每遇到一層節點就向線性基插入目前層的所有tag中的點權，同時每個節點的線性基均需繼承父親節點的資訊。
這樣遞歸到葉子結點時便可獲得葉子結點所代表的時間點處的線性基，此時可直接輸出答案。
于是就做完了~
#include<bits/stdc++.h>
using namespace std;
const int N=;
const int M=;
const int LEN=;
const int K=;
typedef bitset<LEN> bit;
#define mid ((l+r)>>1)
inline void read(bit &b)
{
static char s[LEN];
scanf("%s",s);
int len=strlen(s);
reverse(s,s+len);
b.reset();
for(int i=;i<len;i++)
b[i]=s[i]-'0';
}
inline void print(const bit &b)
{
int j;
for(j=K;~j;j--)
if(b[j])
break;
if(j<)putchar('0');
for(int i=j;i>=;i--)
putchar(b[i]?'1':'0');
putchar('\n');
}
struct basis
{
bit a[LEN];
basis()
{
for(int i=K;i>=;i--)
a[i].reset();
}
inline void add(bit x)
{
for(int i=K;i>=;i--)
if(x[i])
x^=a[i];
for(int i=K;i>=;i--)
if(x[i] && !a[i].any())
{
a[i]=x;
return;
}
}
inline void output()
{
bit ret;
for(int i=K;~i;i--)
if(a[i].any() && !ret[i])
ret^=a[i];
print(ret);
}
};
int n,m,lst[N];
bit lbit[N],tmp;
vector<bit> t[M<<];
inline void add(int x,int l,int r,int dl,int dr,const bit &b)
{
if(dl==l && r==dr)
{
t[x].push_back(b);
return;
}
if(dr<=mid)
add(x<<,l,mid,dl,dr,b);
else if(mid<dl)
add(x<<|,mid+,r,dl,dr,b);
else
{
add(x<<,l,mid,dl,mid,b);
add(x<<|,mid+,r,mid+,dr,b);
}
}
inline void dfs(int x,int l,int r,basis b)
{
for(int i=,e=t[x].size();i<e;i++)
b.add(t[x][i]);
if(l<r)
dfs(x<<,l,mid,b),dfs(x<<|,mid+,r,b);
else
b.output();
}
int main()
{
scanf("%*d%d%d",&n,&m);
for(int i=,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
read(tmp);
if(u==v)continue;
if(lst[u])
add(,,m,lst[u],i-,lbit[u]);
lst[u]=i;lbit[u]^=tmp;
if(lst[v])
add(,,m,lst[v],i-,lbit[v]);
lst[v]=i;lbit[v]^=tmp;
}
for(int i=;i<=n;i++)
if(lst[i]<=m && lst[i])
add(,,m,lst[i],m,lbit[i]);
dfs(,,m,basis());
return ;
}