概念
对于一个很多询问的题，假如对于一个询问可以二分处理，同时一次 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]]);
}
}