Description：

有 $n$ 个序列，刚开始每个序列只有 $1$ 个元素，每个元素有两个属性 $A$ 和 $B$ ， $m$ 个操作，分为 $6$ 种：

1、修改第 $i$ 个序列的第 $j$ 个元素的 $A$ 属性。

2、修改第 $i$ 个序列的第 $j$ 个元素的 $B$ 属性。

3、将第 $y$ 个序列接在第 $x$ 个序列后。

4、询问第 $x$ 个序列第 $l$ 到第 $r$ 个元素中 $A$ 属性大于 $val$ 的个数。

5、询问第 $x$ 个序列第 $l$ 到第 $r$ 个元素中 $A$ 属性第 $k$ 大。

6、询问第 $x$ 个序列第 $l$ 到第 $r$ 个元素中， $A$ 属性在 $[a_l,a_r]$ 范围内的 $B$ 属性最大值。

$1\leqslant n\leqslant 250000,1\leqslant m\leqslant 450000$

Solution：

看最后一个询问就知道肯定要写二维数据结构，那最大的可能性就是树套树了。观察一下操作不难发现应该是 $A$ 一维 $id$ 一维，但是由于我们要查询区间第 $k$ 大，那 $A$ 就应该是外层，于是我们用以 $A$ 为下标的动态开点线段树作为树套树的外层，用以 $id$ 为下标的 $fhq-treap$ 为树套树的外层，第 $1,2$ 个操作就是删除和插入，第三个可以用线段树合并做，每次把对应节点的平衡树也合并起来，第四个，第五个和第六个显然就是在线段树上查询。

Code：

#include<bits/stdc++.h>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

#define MAXN 250010

#define N 1000000

int n,m;

#define ls t[rt].lc

#define rs t[rt].rc

namespace FHQ

{

	struct node{int lc,rc,prio,id,tag,a,b,si,bmx;node(){id = tag = a = b = bmx = 0;}}t[MAXN * 30];

	int ptr = 0,del[MAXN * 30],del_ptr = 0;

	int newnode(){int k;if(del_ptr)k = del[del_ptr--];else k = ++ptr;t[k].prio = rand();return k;}

	void recycle(int rt){memset(&t[rt],0,sizeof(&t[rt]));del[++del_ptr] = rt;return;}

	int cnode(int id,int va,int vb){int k = newnode();t[k].id = id;t[k].a = va;t[k].b = t[k].bmx = vb;t[k].si = 1;return k;}

	void maintain(int rt){t[rt].si = t[ls].si + t[rs].si + 1;t[rt].bmx = max(max(t[ls].bmx,t[rs].bmx),t[rt].b);return;}

	void addtag(int rt,int tag){if(rt == 0)return;t[rt].tag += tag;t[rt].id += tag;}

	void down(int rt){if(ls != 0)addtag(ls,t[rt].tag);if(rs != 0)addtag(rs,t[rt].tag);t[rt].tag = 0;}

	int merge(int a,int b){if(a == 0 || b == 0)return a + b;

		if(t[a].prio < t[b].prio){down(a);t[a].rc = merge(t[a].rc,b);maintain(a);return a;}

		else{down(b);t[b].lc = merge(a,t[b].lc);maintain(b);return b;}}

	void split(int rt,int k,int &x,int &y){

		if(rt == 0){x = y = 0;return;}down(rt);if(t[rt].id <= k){x = rt;split(rs,k,rs,y);}else{y = rt;split(ls,k,x,ls);}maintain(rt);return;}

	void insert(int &rt,int id,int a,int b){int x,y;split(rt,id,x,y);rt = merge(x,merge(cnode(id,a,b),y));return;}

	void remove(int &rt,int id){int x,y,z;split(rt,id - 1,x,y);split(y,id,y,z);recycle(y);rt = merge(x,z);return;}

	node num(int rt,int p){if(p == t[ls].si + 1)return t[rt];down(rt);if(p <= t[ls].si)return num(ls,p);return num(rs,p - t[ls].si - 1);}

	int idcnt(int &rt,int l,int r){int x,y,z,res;split(rt,l - 1,x,y);split(y,r,y,z);res = t[y].si;rt = merge(x,merge(y,z));return res;}

	int bmax(int &rt,int l,int r){int x,y,z,res;split(rt,l - 1,x,y);split(y,r,y,z);res = t[y].bmx;rt = merge(x,merge(y,z));return res;}

}

namespace ST

{

	struct node{int lc,rc;int tag,root;}t[MAXN * 30];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root[MAXN];

	#define mid ((l + r) >> 1)

	void addtag(int rt,int tag){t[rt].tag += tag;FHQ::addtag(t[rt].root,tag);return;}

	void pushdown(int rt){addtag(ls,t[rt].tag);addtag(rs,t[rt].tag);t[rt].tag = 0;return;}

	void ins(int &rt,int id,int vala,int valb,int l,int r){if(rt == 0)rt = newnode();FHQ::insert(t[rt].root,id,vala,valb);

		if(l == r)return;pushdown(rt);if(vala <= mid)ins(ls,id,vala,valb,l,mid);else ins(rs,id,vala,valb,mid + 1,r);}

	void rem(int rt,int id,int vala,int valb,int l,int r){FHQ::remove(t[rt].root,id);

		if(l == r)return;pushdown(rt);if(vala <= mid)rem(ls,id,vala,valb,l,mid);else rem(rs,id,vala,valb,mid + 1,r);}

	struct st{int id,a,b;};

	st askv(int i,int p){FHQ::node k = FHQ::num(t[root[i]].root,p);return (st){k.id,k.a,k.b};}

	int merge(int a,int b){if(a == 0 || b == 0)return a + b;

		t[a].root = FHQ::merge(t[a].root,t[b].root);pushdown(a);pushdown(b);

		t[a].lc = merge(t[a].lc,t[b].lc);t[a].rc = merge(t[a].rc,t[b].rc);

		return a;}

	int query(int rt,int L,int R,int le,int ri,int l,int r){if(rt == 0)return 0;if(L <= l && r <= R)return FHQ::idcnt(t[rt].root,le,ri);

		pushdown(rt);if(R <= mid)return query(t[rt].lc,L,R,le,ri,l,mid);if(L > mid)return query(t[rt].rc,L,R,le,ri,mid + 1,r);

		return query(t[rt].lc,L,R,le,ri,l,mid) + query(t[rt].rc,L,R,le,ri,mid + 1,r);}

	int query(int rt,int k,int L,int R,int l,int r){if(l == r)return l;pushdown(rt);int s = (rs == 0 ? 0 : FHQ::idcnt(t[rs].root,L,R));

		if(k <= s)return query(t[rt].rc,k,L,R,mid + 1,r);else return query(t[rt].lc,k - s,L,R,l,mid);}

	int maxb(int rt,int L,int R,int le,int ri,int l,int r){if(rt == 0)return 0;if(L <= l && r <= R)return FHQ::bmax(t[rt].root,le,ri);

		pushdown(rt);if(R <= mid)return maxb(t[rt].lc,L,R,le,ri,l,mid);if(L > mid)return maxb(t[rt].rc,L,R,le,ri,mid + 1,r);

		return max(maxb(t[rt].lc,L,R,le,ri,l,mid),maxb(t[rt].rc,L,R,le,ri,mid + 1,r));}

}

int main()

{

	srand(time(NULL));

	scanf("%d%d",&n,&m);

	int opt,x,y,l,r,val,al,ar,a,b;

	using namespace ST;

	for(int i = 1;i <= n;++i){a = rd();b = rd();ins(root[i],1,a,b,1,N);}

	int la = 0;

	for(int i = 1;i <= m;++i)

	{

		opt = rd();

		if(opt == 1){x = rd() ^ la;y = rd() ^ la;val = rd() ^ la;st v = askv(x,y);rem(root[x],v.id,v.a,v.b,1,N);ins(root[x],v.id,val,v.b,1,N);}

		if(opt == 2){x = rd() ^ la;y = rd() ^ la;val = rd() ^ la;st v = askv(x,y);rem(root[x],v.id,v.a,v.b,1,N);ins(root[x],v.id,v.a,val,1,N);}

		if(opt == 3){x = rd() ^ la;y = rd() ^ la;addtag(root[y],FHQ::t[t[root[x]].root].si);root[x] = merge(root[x],root[y]);}

		if(opt == 4){x = rd() ^ la;l = rd() ^ la;r = rd() ^ la;val = rd() ^ la;printf("%d\n",la = query(root[x],val + 1,N,l,r,1,N));}

		if(opt == 5){x = rd() ^ la;l = rd() ^ la;r = rd() ^ la;val = rd() ^ la;printf("%d\n",la = query(root[x],val,l,r,1,N));}

		if(opt == 6){x = rd() ^ la;l = rd() ^ la;r = rd() ^ la;al = rd() ^ la;ar = rd() ^ la;printf("%d\n",la = maxb(root[x],al,ar,l,r,1,N));}

	}

	return 0;

}