这题还有一种做法是整体二分,其实本质上就是权值线段树上二分
另外注意的一点是,负数的时候/2和右移有些许区别。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; struct node{ int op,x,y,k,id; }q[N],lq[N],rq[N]; int ans[N]; int tr[N]; int lowbit(int x){ //lowbit函数 return x&-x; } void add(int x,int c){ //单点修改函数 int i; for(i=x;i<=N;i+=lowbit(i)){ tr[i]+=c; } } int sum(int x){//区间查询函数 int res=0; int i; for(i=x;i;i-=lowbit(i)){ res+=tr[i]; } return res; } void solve(int vl,int vr,int ql,int qr){ if(ql>qr){ return ; } if(vl==vr){ for(int i=ql;i<=qr;i++){ if(q[i].op==2) ans[q[i].id]=vl; } return ; } int mid=vl+vr>>1; int tmp1=0,tmp2=0; for(int i=ql;i<=qr;i++){ if(q[i].op==1){ if(q[i].x<=mid) add(q[i].y,1),lq[++tmp1]=q[i]; else rq[++tmp2]=q[i]; } if(q[i].op==2){ int n=sum(q[i].y)-sum(q[i].x-1); if(n>=q[i].k){ lq[++tmp1]=q[i]; } else{ q[i].k-=n; rq[++tmp2]=q[i]; } } } for(int i=ql;i<=qr;i++){ if(q[i].op==1){ if(q[i].x<=mid) add(q[i].y,-1); } } for(int i=1;i<=tmp1;i++) q[ql+i-1] = lq[i]; for(int i=1;i<=tmp2;i++) q[ql+tmp1+i-1] = rq[i]; solve(vl, mid, ql, ql+tmp1-1); solve(mid+1, vr, ql+tmp1, qr); } int main(){ int n,m; cin>>n>>m; int i; for(i=1;i<=n;i++){ int x; scanf("%d",&x); q[i]=node{1,x,i}; } for(i=1;i<=m;i++){ int l,r,k; scanf("%d%d%d",&l,&r,&k); q[i+n]=node{2,l,r,k,i}; } solve(-1e9,1e9,1,n+m); for(i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }View Code