某个1K的树套树

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define P int
#define T return
#define F if
#define W while
#define D(l,r) (l+r|l!=r)
const P N=1e7+10;
P B[N],C[N],o[N],t[N],rt[N],j,n,m,L,R;
P d(P&x,P l,P r)
{
	F(x==0)x=++j;
	F(L<=l&&r<=R){o[x]+=r-l+1,t[x]++;T 0;}
	P i=(l+r)>>1;
	F(L<=i)d(B[x],l,i);F(R>i)d(C[x],i+1,r);
	o[x]+=min(R,r)-max(l,L)+1;
}
P u(P x,P l,P r){
	F(!x)T 0;
	F(L<=l&&r<=R)T o[x];
	P i=(l+r)>>1,e=0;
	F(L<=i)e+=u(B[x],l,i);
	F(R>i)e+=u(C[x],i+1,r);
	T e+t[x]*(min(R,r)-max(L,l)+1);
}
P s(P a,P b,P c){
	P l=1,r=n;
	L=a,R=b;
	W(d(rt[D(l,r)],1,n),l<r){
		P i=(l+r)/2;
		(c<=i)?r=i:l=i+1;
	}
}
P q(P a,P b,P c){
	P l=1,r=n;
	L=a,R=b;
	P p,i;
	W(l<r){
		i=(l+r)>>1;
		p=u(rt[D(i+1,r)],1,n);
		c<=p?l=i+1:(r=i,c-=p);
	}
	T l;
}
main(){
	scanf("%d%d",&n,&m);
	for(P i=1;i<=m;i++){
		P f,a,b,c;
		scanf("%d%d%d%d",&f,&a,&b,&c);
		(f-1)?printf("%d\n",q(a,b,c)):s(a,b,c);
	}
}