【模板】可持久化文艺平衡树

link

模板。其实思想和普通的用无旋Treap实现可持久化平衡树一样，都是考虑新建状态可能会带来什么影响。无旋Treap的基础就是分裂，可以想见它可以实现和Splay类似的提取区间操作（而且貌似更加直观），然后就是可持久化地进行split和merge。该打标计就打标计，该下放就下放（split和merge都是一路下放），需要注意的是在pushdown函数中，如果要交换左右孩子的话需要新建节点，毕竟可持久化的要求就是咱不能影响过去的事情……

空间好评，整整一个G。还有就是数组开得有点骇人听闻，1e8的long long，恐怕OI生涯里这种题也是不多见的。还有就是要开long long，虽然鬼知道涉及负数的异或运算出题人是怎么想的。

code

#include
#include
#include
//#define zczc
#define int long long
using namespace std;
const int N=200010;
inline void read(int &wh){
	wh=0;int f=1;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
	while(w>='0'&&w<='9'){wh=wh*10+w-'0';w=getchar();}
	wh*=f;return;
}
inline void swap(int &s1,int &s2){
	int s3=s1;s1=s2;s2=s3;return;
}

#define lc t[x].l
#define rc t[x].r
struct node{
	int l,r,data,sum,size,p;bool lazy;
}t[N<<7];
int ti,cnt,root[N];
inline int newone(int val){
	t[++cnt]=(node){0,0,val,val,1,rand(),false};
	return cnt;
}
inline int copy(int x){
	t[++cnt]=t[x];return cnt;
}
inline void pushdown(int x){
	if(t[x].lazy==false)return;
	t[x].lazy=false;
	if(lc)lc=copy(lc);
	if(rc)rc=copy(rc);
	swap(lc,rc);
	if(lc)t[lc].lazy^=1;
	if(rc)t[rc].lazy^=1;
}
inline void pushup(int x){
	t[x].size=t[lc].size+t[rc].size+1;
	t[x].sum=t[lc].sum+t[rc].sum+t[x].data;
}
inline void split(int x,int val,int &a,int &b){
	if(!x){a=b=0;return;}pushdown(x);
	int y=x;x=++cnt;t[x]=t[y];
	if(t[lc].size+1<=val){a=x;split(rc,val-t[lc].size-1,rc,b);}
	else{b=x;split(lc,val,a,lc);}pushup(x);
}
inline int merge(int x,int y){
	if(!x||!y)return x+y;int s=++cnt;
	pushdown(x);pushdown(y);
	if(t[x].p