hdu 5412 （动态区间第k小，整体二分）

参考了这篇博客：http://blog.csdn.net/v5zsq/article/details/50775827

树套树感觉好麻烦，就学了下整体二分，发现还是挺简单的。每个询问都进入了第32层，所以复杂度大概是O（nlogn*32）。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005,INF=0x3f3f3f3f;
int c[N];
void add(int x,int y)
{
	for (int i=x;i<N;i+=i&-i) c[i]+=y;
}
int get(int x)
{
	int tmp=0;
	for (int i=x;i;i-=i&-i) tmp+=c[i];
	return tmp;
}
int n,m;
int a[N];
int ans[N];
struct event
{
	int tp,x,y,z,id;
}Q[N*3],q1[N*3],q2[N*3];
int f[N*3];
int tot;
void solve(int l,int r,int head,int tail)
{
	if (head>tail) return; //这句很关键，否则递归次数会变成2*INF次
	if (l==r)
	{
		for (int i=head;i<=tail;i++)
			if (Q[i].tp==3) ans[Q[i].id]=l;
		return;
	}
	int mid=(l+r)/2;
	for (int i=head;i<=tail;i++)
	{
		if (Q[i].tp==1&&Q[i].y<=mid) add(Q[i].x,1);
		if (Q[i].tp==2&&Q[i].y<=mid) add(Q[i].x,-1);
		if (Q[i].tp==3) f[i]=get(Q[i].y)-get(Q[i].x-1);
	}  //对于每个询问搞出区间内不大于mid的个数

	for (int i=head;i<=tail;i++)
	{
		if (Q[i].tp==1&&Q[i].y<=mid) add(Q[i].x,-1);
		if (Q[i].tp==2&&Q[i].y<=mid) add(Q[i].x,1);
	}  //清空树状数组

	int cnt1=0,cnt2=0;
	for (int i=head;i<=tail;i++)
	{
		if (Q[i].tp<3)
		{
			if (Q[i].y<=mid) q1[++cnt1]=Q[i];
			else q2[++cnt2]=Q[i];
		}
		else
		{
			if (f[i]<Q[i].z) Q[i].z-=f[i],q2[++cnt2]=Q[i];
			else q1[++cnt1]=Q[i];
		}
	}//分离询问

	int tmp=0;
	for (int i=1;i<=cnt1;i++) Q[head+tmp]=q1[i],tmp++;
	for (int i=1;i<=cnt2;i++) Q[head+tmp]=q2[i],tmp++;
	solve(l,mid,head,head+cnt1-1);
	solve(mid+1,r,head+cnt1,tail);
}
int main()
{
	while(~scanf("%d",&n))
	{
		tot=0;
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			Q[++tot]={1,i,a[i],i}; //把一开始的值也当作事件来看待
		}
		scanf("%d",&m);
		for (int i=1;i<=m;i++)
		{
			ans[i]=-INF;
			int tp,x,y,z;
			scanf("%d%d%d",&tp,&x,&y);
			if (tp==1)
			{
				Q[++tot]={2,x,a[x],0,i};
				Q[++tot]={1,x,y,0,i};
				a[x]=y;  //修改就是删除一个数再插入一个数
			}
			else
			{
				scanf("%d",&z);
				Q[++tot]={3,x,y,z,i};
			}
		}
		solve(0,INF,1,tot);
		for (int i=1;i<=m;i++)
			if (ans[i]!=-INF) printf("%d\n",ans[i]);
	}
}