概念

对于一个很多询问的题，假如对于一个询问可以二分处理，同时一次 check 可以只用 \(n\) 的时间处理所有询问的 check 结果，我们可以使用整体二分来做这个题。

思想

设函数 \(\operatorname{solve}(S, L, R)\) 为现在正在处理询问序列 \(S\) 里的询问，答案值域为 \([L, R]\)。

向下递归直到 \(L=R\)，即求出了答案。

否则对于 \(mid\) 执行 check，比较并将 \(S\) 分成两部分向下递归 \([l,mid]\)，\([mid+1,r]\)。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[1000001],lsh[1000001],ans[1000001];
struct qw
{
	int op,l,r,k,i;
}q[1000001],lt[1000001],rt[1000001];
int snmn[1000001];
void add(int x,int w)
{
	while(x<=n)
	{
		snmn[x]+=w; 
		x+=(x&(-x));
	}
}
int sum(int x)
{
	int re=0;
	while(x)
	{
		re+=snmn[x];
		x-=(x&(-x));
	}
	return re;
}
void tp(int l,int r,int L,int R) //l-r询问 L-R答案
{
	int ll=0,rl=0;
	if(l>r) return;
	if(L==R)
	{
		for(int i=l;i<=r;i++)
		{
			if(q[i].op==1) continue;
			ans[q[i].i]=L; 
		}
		return;
	}
	int mid=L+R>>1;
	for(int i=l;i<=r;i++)
	{
		if(q[i].op==1)
		{
			if(q[i].r<=mid)
			{
				add(q[i].k,1);
				lt[++ll]=q[i];
			}
			else
			{
				rt[++rl]=q[i];
			}
		}
		else
		{
			int cnt=sum(q[i].r)-sum(q[i].l-1);
			if(q[i].k<=cnt)
	  		{
				lt[++ll]=q[i];
			}
			else
			{
				q[i].k-=cnt;
				rt[++rl]=q[i];
			}
		}
	}
	for(int i=l;i<=r;i++)
	{
		if(q[i].op==1&&q[i].r<=mid) add(q[i].k,-1);
	}
	for(int i=1;i<=ll;i++)
	{
		q[l+i-1]=lt[i];
	}
	for(int i=1;i<=rl;i++)
	{
		q[l+ll+i-1]=rt[i];
	}
	tp(l,l+ll-1,L,mid);
	tp(l+ll,r,mid+1,R);
}
signed main()
{
	scanf("%d%d",&n,&m);
	m+=n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		lsh[i]=a[i];
	}
	sort(lsh+1,lsh+n+1);
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(lsh+1,lsh+n+1,a[i])-lsh;
	}
	for(int i=1;i<=n;i++)
	{
		q[i].r=a[i];
		q[i].k=i;
		q[i].op=1;
	}
	for(int i=n+1;i<=m;i++)
	{
		q[i].op=2;
		scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
		q[i].i=i-n;
	}
	tp(1,m,1,n);
	for(int i=1;i<=m-n;i++)
	{
		printf("%d\n",lsh[ans[i]]);
	}
}