题意：多组输入，长度为n的序列，每个人有属性值为 a i a_i ai，多次询问，询问区间 [ l , r ] [l,r] [l,r]，最大的h，使得有起码h个人的属性值也是大于等于h的。
题目链接：C
主席树上判断往左还是往右走就好，优先向右走，否则用一个变量加上右子树，判断左子树。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+7; struct Tree{ int lc,rc,sum; }tree[maxn*50]; int root[maxn]; int tot; int build(int l,int r){ int k=++tot; tree[k].sum=0; if(l==r) return k; int mid=(l+r)>>1; tree[k].lc=build(l,mid); tree[k].rc=build(mid+1,r); return k; } int updata(int p,int l,int r,int id){ int k=++tot; tree[k]=tree[p]; ++tree[k].sum; if(l==r) return k; int mid=(l+r)>>1; if(id<=mid) tree[k].lc=updata(tree[p].lc,l,mid,id); else tree[k].rc=updata(tree[p].rc,mid+1,r,id); return k; } int sum; int myfind(int p,int q,int l,int r){ if(l==r) return l; int mid=(l+r)>>1; if(sum+tree[tree[p].rc].sum-tree[tree[q].rc].sum>=mid+1) return myfind(tree[p].rc,tree[q].rc,mid+1,r); sum+=tree[tree[p].rc].sum-tree[tree[q].rc].sum; return myfind(tree[p].lc,tree[q].lc,l,mid); } int main(){ int n,q,x,y; while(scanf("%d%d",&n,&q)!=EOF){ root[0]=build(1,n); for(int i=1;i<=n;++i){ scanf("%d",&x); root[i]=updata(root[i-1],1,n,x); } while(q--){ scanf("%d%d",&x,&y); sum=0; printf("%d\n",myfind(root[y],root[x-1],1,n)); } } return 0; }