JZOJ5373. 【NOIP2017提高A组模拟9.17】信仰是为了虚无之人 并查集+启发式合并

题意：构造一个长度为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]);
    }
}