题意：构造一个长度为n数列，给出m个要求，保证第一个满足，每个要求具体描述为li,ri,ki，表示l到r的异或和为k。对于每一个操作，如果能和前i-1个要求不冲突（能构造出一个合法序列），输出1，否则输出0，最后输出合法序列（不合法的要求忽略），要求字典序最小。
大爷好像很喜欢启发式合并= =。被虐了，完全没想到并查集那个地方去。
假设我们现在已经构造出了原序列，接下来的问题就是怎么符合要求。那么我们记录一下前缀和，那么就可以O（1）判断是否符合要求了。
问题是这是假设，那么转移到在线询问上来，我们用并查集，每次启发式合并的同时记录一下路径异或和。同理对于一个询问，如果l,r在一个联通块内，就判断他的异或和是否为k，输出01，如果不在，就直接连边，输出1. 好像是并查集启发式合并模板题
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=4e5+5;
int n,m;
int f[N],op,a[N],sum[N];
inline int find(int x)
{
if (f[x]<0)return x;
a[x]^=a[f[x]];
return f[x]=find(f[x]);
}
inline void merge(int l,int r,int k)
{
int fx=find(l),fy=find(r);
if (fx>fy)swap(fx,fy);
f[fy]=fx;
a[fy]^=(a[l]^a[r]^k);
}
int main()
{
freopen("sanae.in","r",stdin);
freopen("sanae.out","w",stdout);
scanf("%d%d%d",&n,&m,&op);
int last=0;
memset(f,-1,sizeof(f));
fo(i,1,m)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
l^=(op*last),r^=(last*op),k^=(last*op);
if (find(r)==find(l-1))
{
if ((a[l-1]^a[r])==k)last=1;
else last=0;
}
else
{
last=1;
merge(l-1,r,k);
}
printf("%d\n",last);
}
fo(i,0,n)
{
int fx=find(i);
if (i==fx)sum[i]=sum[i-1];
else sum[i]=a[i]^sum[fx];
if (i)printf("%d\n",sum[i]^sum[i-1]);
}
}找到一个更好理解的代码，觉得可以借鉴一下（from ymw）.
易于理解&&优美。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200005;
int n,m,czy,f[N],size[N],cnt,last[N],val[N];
bool vis[N];
struct edge{int to,next,w;}e[N*2];
int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int find(int x)
{
if (f[x]==x) return x;
else return f[x]=find(f[x]);
}
void addedge(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].w=w;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].w=w;e[cnt].next=last[v];last[v]=cnt;
}
void dfs(int x,int fa)
{
vis[x]=1;
for (int i=last[x];i;i=e[i].next)
{
if (e[i].to==fa) continue;
val[e[i].to]=val[x]^e[i].w;
dfs(e[i].to,x);
}
}
int main()
{
freopen("sanae.in","r",stdin);freopen("sanae.out","w",stdout);
n=read()+1;m=read();czy=read();
for (int i=1;i<=n;i++) f[i]=i,size[i]=1;
int ans=0;
while (m--)
{
int l=read(),r=read(),k=read();
if (czy) l^=ans,r^=ans,k^=ans;
r++;
int x=find(l),y=find(r);
if (x!=y)
{
if (size[x]<size[y])
{
f[x]=y;size[y]+=size[x];
addedge(l,r,k);
val[l]=val[r]^k;
dfs(l,r);
}
else
{
f[y]=x;size[x]+=size[y];
addedge(l,r,k);
val[r]=val[l]^k;
dfs(r,l);
}
ans=1;
puts("1");
}
else
{
if ((val[l]^val[r])==k) ans=1,puts("1");
else ans=0,puts("0");
}
}
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++)
if (!vis[i]) val[i]=val[i-1],dfs(i,0);
for (int i=n;i>=2;i--) val[i]^=val[i-1];
for (int i=2;i<=n;i++) printf("%d\n",val[i]);
return 0;
}