//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read3.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {ch=getchar();if (ch=='-') flag=true;}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
/////////////////variables&functions////////////////////
int n,m,type,x,y,now,i;
const int maxn=222222;
struct node
{
node *l,r;
int value;
node():l(0),r(0),value(0){};
node(node *ll,node *rr):l(ll),r(rr),value(0){}
node(int vv):l(0),r(0),value(vv){}
};
char ___[maxnsizeof(node)*90];
char *=___;
inline void *myalloc(size_t size)
{
return (+=size)-size;
}
#define newnode new (myalloc(sizeof(node))) node
struct chairmantree
{
node *root[maxn];
void build(node *x,int v,int L=1,int R=n)
{
if (L==R)
{
x->value=v;
return;
}
int mid=(L+R)>>1;
x->l=newnode();
x->r=newnode();
build(x->l,v,L,mid);
build(x->r,v,mid+1,R);
}
void _build(node *x,int L=1,int R=n)
{
if (L==R)
{
x->value=L;
return;
}
int mid=(L+R)>>1;
x->l=newnode();
x->r=newnode();
_build(x->l,L,mid);
_build(x->r,mid+1,R);
}
node *insert(node *x,int k,int v,int L=1,int R=n)
{
if (L==R) return newnode(v);
int mid=(L+R)>>1;
if (k<=mid) return newnode(insert(x->l?x->l:0,k,v,L,mid),x->r?x->r:0);
else return newnode(x->l?x->l:0,insert(x->r?x->r:0,k,v,mid+1,R));
}
int query(node *x,const int &y,int L=1,int R=n)
{
int mid;
while (1)
{
mid=(L+R)>>1;
if (y<=mid)
{
x=x->l;
R=mid;
}
else
{
x=x->r;
L=mid+1;
}
if (L==R) return x->value;
}
}
}fa,v;
inline int getfa(node *no,const int &x)
{
int temp=fa.query(no,x),before=x;
do
{
before=temp;
temp=fa.query(no,temp);
}while (temp!=before);
return temp;
}
inline bool query(const int &x,const int &y)
{
int temp1=getfa(fa.root[i],x),temp2=getfa(fa.root[i],y);
if (temp1==temp2) return true;
return false;
}
inline void combine(int x,int y)
{
int temp1=getfa(fa.root[i-1],x),temp2=getfa(fa.root[i-1],y);
if (temp1==temp2)
{
fa.root[i]=fa.root[i-1];
v.root[i]=fa.root[i-1];
return;
}
int temp3=v.query(v.root[i-1],temp1),temp4=v.query(v.root[i-1],temp2);
if (temp3>temp4)
{
swap(x,y);
swap(temp3,temp4);
swap(temp1,temp2);
}
fa.root[i]=fa.insert(fa.root[i-1],temp1,temp2);
v.root[i]=v.insert(v.root[i-1],temp2,temp3+temp4);
}
int lastans;
int main()
{
read(n,m);
fa.root[0]=newnode(newnode(),newnode());
int mid=(1+n)>>1;
fa._build(fa.root[0]->l,1,mid);
fa._build(fa.root[0]->r,mid+1,n);
v.root[0]=newnode(newnode(),newnode());
v.build(v.root[0]->l,1,1,mid);
v.build(v.root[0]->r,1,mid+1,n);
now=0;
for (i=1;i<=m;i++)
{
read(type);
if (type==1)
{
read(x,y);
x^=lastans;
y^=lastans;
combine(x,y);
}
else if (type==2)
{
read(x);
x^=lastans;
fa.root[i]=fa.root[x];
v.root[i]=v.root[x];
}
else
{
v.root[i]=v.root[i-1];
fa.root[i]=fa.root[i-1];
read(x,y);
x^=lastans;
y^=lastans;
printf("%d\n",query(x,y));
}
}
return 0;
}
自己想了想再加上ZYX的指导，我晓得了这玩意就是可持久化数组，而可持久化数组就是用可持久化线段树实现，可持久化线段树上面的那些结点不用存数据仅仅用来查。再用WUY之前教的奇奇怪怪的内存池技巧，我写出了这份代码，感觉还是挺方便的
ps 3673当时明明打炸了，但是却很快地a了导致我深信自己代码没错交了3674T飞...最后发现我的启发式合并是假的...
这是3674的代码