题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3110

题目分类：数据结构，树套树

题意：

修改操作每次给一个位置加入k个权值为c的数

询问操作每次询问一个区间内的k大数

题解：

使用树套树的方法维护。

外面一圈用线段树表示数的权值。

里面一圈用线段树维护区间内的数。

二分的时候直接在线段树上二分省去一个log

程序：

#include<cstdio>
using namespace std;
struct node
{
	int lson,rson,lazy,summ;
}a[33000000];
int root[500000],siz,n;
inline void build(int x,int le,int ri)
{
	root[x]=++siz;
	if(le==ri)return;
	build((x<<1),le,(le+ri)/2);
	build((x<<1)+1,(le+ri)/2+1,ri);
}
inline void pushdown(int x,int l,int mi,int r)
{
	int le=a[x].lson,ri=a[x].rson;
	if(le==0)siz++,a[x].lson=siz,le=siz;
	a[le].lazy+=a[x].lazy;a[le].summ+=a[x].lazy*(mi-l+1);
	if(ri==0)siz++,a[x].rson=siz,ri=siz;
	a[ri].summ+=a[x].lazy*(r-mi);a[ri].lazy+=a[x].lazy;
	a[x].lazy=0;
}
inline void update(int x)
{
	a[x].summ=a[a[x].lson].summ+a[a[x].rson].summ;
}
inline int query(int x,int le,int ri,int lec,int ric)
{
//	if(le==1&&ri==(n<<1)+1)printf("qu2:%d %d %d %d %d %d\n",x,le,ri,lec,ric,a[x].summ);
	if(x==0)return 0;
	if(lec<=le&&ric>=ri)return a[x].summ;
	pushdown(x,le,(le+ri)/2,ri);
	int ss=0;
	if(lec<=(le+ri)/2)ss+=query(a[x].lson,le,(le+ri)/2,lec,ric);
	if(ric>=(le+ri)/2+1)ss+=query(a[x].rson,(le+ri)/2+1,ri,lec,ric);
	return ss;
}
inline int edit(int x,int le,int ri,int lec,int ric)
{
	if(x==0)siz++,x=siz;
//	printf("%d %d %d %d %d\n",x,le,ri,lec,ric);
	if(lec<=le&&ric>=ri){a[x].summ+=(ri-le+1);a[x].lazy++;return x;}
	pushdown(x,le,(le+ri)/2,ri);
//	if(lec<=le&&ric>=ri){a[x].summ++;a[x].lazy++;return x;}
	if(lec<=(le+ri)/2)a[x].lson=edit(a[x].lson,le,(le+ri)/2,lec,ric);
	if(ric>=(le+ri)/2+1)a[x].rson=edit(a[x].rson,(le+ri)/2+1,ri,lec,ric);
	update(x);
	return x;
}
inline void edit(int x,int va,int le,int ri,int lec,int ric)
{
//	printf("edit:%d %d %d %d %d %d\n",x,va,le,ri,lec,ric);
	root[x]=edit(root[x],1,(n<<1)+1,lec,ric);
	if(le==ri){return;}
	if(va<=(le+ri)/2)edit((x<<1),va,le,(le+ri)/2,lec,ric);
	else edit((x<<1)+1,va,(le+ri)/2+1,ri,lec,ric);
}
inline int query(int x,int le,int ri,int va,int lec,int ric)
{
//	printf("%d %d %d %d %d %d\n",x,le,ri,va,lec,ric);
	if(le==ri)return le;
	int tmp=query(root[(x<<1)],1,(n<<1)+1,lec,ric);//printf("%d\n",tmp);
	if(tmp<va)return query((x<<1)+1,(le+ri)/2+1,ri,va-tmp,lec,ric);
	return query((x<<1),le,(le+ri)/2,va,lec,ric);
}
int m,x1,x2,x3,x4;
int main()
{
	//freopen("sequence.in","r",stdin);
	//freopen("sequence.out","w",stdout);
	scanf("%d %d",&n,&m);
	build(1,1,(n<<1)+1);
	for (int i=1;i<=m;i++)
	{
		scanf("%d %d %d %d",&x1,&x2,&x3,&x4);
		if(x1==1)
		{
			x4=(n+1)-x4;
			edit(1,x4,1,(n<<1)+1,x2,x3);
		}
		else
		{
			printf("%d\n",n+1-query(1,1,(n<<1)+1,x4,x2,x3));
		}
	}//printf("%d\n",siz);
	return 0;
}