BZOJ 3110 [Zjoi2013]K大数查询

题目大意

有N个位置，M个操作。 操作有两种:

• "1 a b c"表示在第a个位置到第b个位置，每个位置加入一个数c。（一个位置可能有多个数）
• "2 a b c"表示询问从第a个位置到第b个位置，第C大的数是多少。

操作1只能用区间线段树维护，操作2只能用权值线段树维护，所以没法使用单个数据结构满足所有条件。

所以使用树套树维护。

在权值线段树的每个节点上维护一棵动态开点区间线段树，每棵动态开点区间线段树动态维护在权值线段树的[L,R]区间内的数的分布状况。

插入就是在包含该权值的所有权值线段树节点上进行区间线段树插入；查询就是递归查询，如果权值线段树右儿子的查询结果小于C就向左继续查询(C-右子树size)大的树，否则向右，递归到底l==r就得到了最终答案。

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 25000010
#define lson pos<<1
#define rson pos<<1|1

int n,m,md,a,b,c,tot;
int rt[N],ls[N],rs[N];
unsigned int v[N],lz[N],t;

void pushup(int pos,int l,int r) {v[pos]=v[ls[pos]]+v[rs[pos]];}
void pushdown(int pos,int l,int r)
{
	if(lz[pos])
	{
		int mid=(l+r)>>1;
		if(!ls[pos]) ls[pos]=++tot;
		if(!rs[pos]) rs[pos]=++tot;
		lz[ls[pos]]+=lz[pos],v[ls[pos]]+=lz[pos]*(mid-l+1);
		lz[rs[pos]]+=lz[pos],v[rs[pos]]+=lz[pos]*(r-mid);
		lz[pos]=0;
	}
}

void insert(int &pos,int l,int r)
{
	if(!pos) pos=++tot;
	if(a<=l&&r<=b)
	{
		v[pos]+=(r-l+1);
		lz[pos]++;
		return;
	}
	pushdown(pos,l,r);
	int mid=(l+r)>>1;
	if(a<=mid) insert(ls[pos],l,mid);
	if(b>mid) insert(rs[pos],mid+1,r);
	pushup(pos,l,r);
	return;
}
void add(int pos,int l,int r)
{
	insert(rt[pos],1,n);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(c<=mid) add(lson,l,mid);
	else add(rson,mid+1,r);
}

int query(int pos,int l,int r)
{
	if(a<=l&&r<=b) return v[pos];
	pushdown(pos,l,r);
	int mid=(l+r)>>1,ret=0;
	if(a<=mid) ret+=query(ls[pos],l,mid);
	if(b>mid) ret+=query(rs[pos],mid+1,r);
	return ret;
}
int result(int pos,int l,int r)
{
	if(l==r) return l;
	int mid=(l+r)>>1;
	unsigned int tmp=query(rt[rson],1,n);
	if(t<=tmp) return result(rson,mid+1,r);
	else
	{
		t-=tmp;
		return result(lson,l,mid);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d%d",&md,&a,&b);
		if(md==1) scanf("%d",&c),add(1,-50000,50000);
		if(md==2) scanf("%u",&t),printf("%d\n",result(1,-50000,50000));
	}
	return 0;
}