题意:给定(n(n<=1e5))个数，(m(m<=5000))次询问某段区间第(k)小的数是多少.
分析:算法书上整体二分的例题.直接在值域([-1e9,1e9])上二分答案(mid),然后对于每个询问利用树状数组统计该区间内小于等于(mid)的数的个数,然后整个询问分为两类,一类是答案在(-1e9,mid)的询问,另一类是答案在(mid+1,1e9)上的询问.递归分治下去求解即可.
树状数组要每次更新后又撤回操作,不能建立多个树状数组.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int inf=1e9;
const int N=105005;
const int M=5005;
int n,m,tot,ans[M],c[N];
struct node{int opt,x,y,z;}q[N],ql[N],qr[N];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int v){for(;x<=n;x+=lowbit(x))c[x]+=v;}
inline int ask(int x){int cnt=0;for(;x;x-=lowbit(x))cnt+=c[x];return cnt;}
inline void solve(int l,int r,int st,int ed){
if(st>ed)return;//该区间内没有询问,直接返回
if(l==r){//递归边界,该区间的询问的答案都是l(r)
for(int i=st;i<=ed;++i)
if(q[i].opt>0)ans[q[i].opt]=l;
return;
}
int mid=(l+r)>>1,lt=0,rt=0;//二分
for(int i=st;i<=ed;++i){
if(!q[i].opt){
if(q[i].y<=mid)add(q[i].x,1),ql[++lt]=q[i];
else qr[++rt]=q[i];
}
else{
int sum=ask(q[i].y)-ask(q[i].x-1);
if(sum>=q[i].z)ql[++lt]=q[i];
else q[i].z-=sum,qr[++rt]=q[i];
}
}
for(int i=ed;i>=st;--i)if(!q[i].opt&&q[i].y<=mid)add(q[i].x,-1);//撤销对树状数组的操作
for(int i=1;i<=lt;++i)q[st+i-1]=ql[i];
for(int i=1;i<=rt;++i)q[st+lt+i-1]=qr[i];
solve(l,mid,st,st+lt-1);solve(mid+1,r,st+lt,ed);//分治下去
}
int main(){
n=read();m=read();
for(int i=1;i<=n;++i){//把n个数的序列也当做操作
q[++tot].opt=0;q[tot].x=i;q[tot].y=read();
}
for(int i=1;i<=m;++i){
q[++tot].opt=i;q[tot].x=read();q[tot].y=read();q[tot].z=read();
}
solve(-inf,inf,1,tot);//整体二分
for(int i=1;i<=m;++i)printf("%d
",ans[i]);//离线回答
return 0;
}