BZOJ4923 [Lydsy1706月赛]K小值查询

题意

维护一个长度为n的正整数序列a_1,a_2,...,a_n，支持以下两种操作：
1 k，将序列a从小到大排序，输出a_k的值。
2 k，将所有严格大于k的数a_i减去k。

(n leq 10^5)

分析

考虑用Treap来维护数的排名。感官上有些数修改之后的相对排名时不会变的。

考虑1到k的数不会被修改。k+1到2k的数修改之后会和前面的数排名交叉，2k+1到inf的数修改后相对排名不变。后面的数打个标记即可。中间的数至少会减少一半，暴力修改插入即可。权值只减不增，类似启发式合并的摊还分析一样，一个数最多会被这样减小(O(log n))次。

时间复杂度(O(n log^2 n))

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
	rg T data=0;
	rg int w=1;
	rg char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
			w=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		data=data*10+ch-'0';
		ch=getchar();
	}
	return data*w;
}
template<class T>il T read(rg T&x)
{
	return x=read<T>();
}
typedef long long ll;

co int N=1e5+7;
int root;
int tot;
namespace T
{
	int ch[N][2],siz[N];
	int val[N],sub[N];
	int pri[N];
	
	int newnode(int v)
	{
		int x=++tot;
		ch[x][0]=ch[x][1]=0,siz[x]=1;
		val[x]=v,sub[x]=0;
		pri[x]=rand();
		return x;
	}
	
	void pushup(int x)
	{
		siz[x]=siz[ch[x][0]]+1+siz[ch[x][1]];
	}
	
	void pushdown(int x)
	{
		if(sub[x])
		{
			if(ch[x][0])
			{
				sub[ch[x][0]]+=sub[x];
				val[ch[x][0]]-=sub[x];
			}
			if(ch[x][1])
			{
				sub[ch[x][1]]+=sub[x];
				val[ch[x][1]]-=sub[x];
			}	
			sub[x]=0;
		}
	}
	
	void split(int x,int v,int&l,int&r)
	{
		if(!x)
		{
			l=r=0;
			return;
		}
		if(val[x]<=v)
		{
			l=x;
			pushdown(l);
			split(ch[l][1],v,ch[l][1],r);
			pushup(l);
		}
		else
		{
			r=x;
			pushdown(r);
			split(ch[r][0],v,l,ch[r][0]);
			pushup(r);
		}
	}
	
	int merge(int x,int y)
	{
		if(!x||!y)
			return x+y;
		if(pri[x]>pri[y])
		{
			pushdown(x);
			ch[x][1]=merge(ch[x][1],y);
			pushup(x);
			return x;
		}
		else
		{
			pushdown(y);
			ch[y][0]=merge(x,ch[y][0]);
			pushup(y);
			return y;
		}
	}
	
	void insert(int&t,int v)
	{
		int x,y;
		split(t,v,x,y);
		t=merge(x,merge(newnode(v),y));
	}
	
	void inserts(int&t,int x)
	{
		if(!x)
			return;
		pushdown(x);
		inserts(t,ch[x][0]);
		inserts(t,ch[x][1]);
		ch[x][0]=ch[x][1]=0,siz[x]=1;
		int l,r;
		split(t,val[x],l,r);
		t=merge(l,merge(x,r));
	}
	
	void change(int&t,int v)
	{
		int x,y,z;
		split(t,v,x,y);
		if(y)
		{
			sub[y]+=v;
			val[y]-=v;
		}
		split(y,v,y,z);
		inserts(x,y);
		t=merge(x,z);
	}
	
	int kth(int&t,int k)
	{
		pushdown(t);
		if(k==siz[ch[t][0]]+1)
			return val[t];
		if(k<=siz[ch[t][0]])
			return kth(ch[t][0],k);
		else
			return kth(ch[t][1],k-siz[ch[t][0]]-1);
	}
}
using namespace T;
using namespace std;

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	srand(20030506);
	int n,m;
	read(n),read(m);
	while(n--)
		insert(root,read<int>());
	while(m--)
	{
		int opt,k;
		read(opt),read(k);
		if(opt==1)
			printf("%d
",kth(root,k));
		else
			change(root,k);
	}
	return 0;
}