初见线段树分治
(对我来说可不是什么经典题=。=)
把时间轴建出来一棵线段树，然后在对应的区间上打标记，最后把整棵树DFS一遍，到叶节点输出答案即可
(把最终答案开成全局的了调了半天
#include<cstdio>
#include<bitset>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=;
int n,m,s,t1,t2,len,lst[N];
char str[M]; bitset<M> lbt[N],rd;
vector<bitset<M> > ve[*M];
struct a
{
bitset<M> bit[M];
void Set(bitset<M> bt)
{
for(int i=;~i;i--)
if(bt[i]) bt^=bit[i];
for(int i=;~i;i--)
if(bt[i]&&!bit[i].any())
{bit[i]=bt; break;}
}
void Output()
{
bitset<M> outp; outp.reset();
for(int i=;~i;i--)
if(!outp[i]&&bit[i].any())
outp^=bit[i];
bool b=false;
for(int i=;~i;i--)
if(outp[i])
{
b=true;
for(int j=i;~j;j--)
printf("%d",outp[j]?:);
break;
}
if(!b) printf(""); puts("");
}
}sb;
void Add(int nde,int l,int r,int ll,int rr,bitset<M> bt)
{
if(l>rr||r<ll)
return ;
else if(l>=ll&&r<=rr)
ve[nde].push_back(bt);
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+;
Add(ls,l,mid,ll,rr,bt),Add(rs,mid+,r,ll,rr,bt);
}
}
void Getans(int nde,int l,int r,a sb)
{
int siz=ve[nde].size();
for(int i=;i<siz;i++)
sb.Set(ve[nde][i]);
if(l==r)
sb.Output();
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+;
Getans(ls,l,mid,sb),Getans(rs,mid+,r,sb);
}
}
int main()
{
scanf("%d%d%d",&s,&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&t1,&t2);
scanf("%s",str),len=strlen(str);
if(t1!=t2)
{
rd.reset();
for(int j=;j<len;j++)
rd[j]=str[len-j-]-'';
if(lst[t1]) Add(,,m,lst[t1],i-,lbt[t1]);
if(lst[t2]) Add(,,m,lst[t2],i-,lbt[t2]);
lst[t1]=lst[t2]=i,lbt[t1]^=rd,lbt[t2]^=rd;
}
}
for(int i=;i<=n;i++)
if(lst[i]) Add(,,m,lst[i],m,lbt[i]);
Getans(,,m,sb);
return ;
}