某个1K的树套树

BZOJ3110强哥的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);

	}

}