D2. Optimal Subsequences (Hard Version) 主席树

题目链接：https://codeforces.com/contest/1262/problem/D2

将数组按大到小排序(相同大小的按下标由小到大排序)，依次将排序后的每个数在原数组中的位置放入主席树。

对于每个询问的k，pos

输出原数组中下标为query(T[0],T[k],1,len,pos)所对应的数字即可

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 200005
#define ll long long
int T[maxn*20],L[maxn*20],R[maxn*20],sum[maxn*20],tot;
ll b[maxn];
struct node{
    int pos,num;
    bool operator <(const node &w)const{
        if(num==w.num)return pos<w.pos;
        return num>w.num;
    }
}a[maxn];
inline int update(int pre,int l,int r,int x)
{
    int rt=++tot;
    L[rt]=L[pre];
    R[rt]=R[pre];
    sum[rt]=sum[pre]+1;
    if(l<r)
    {
        int mid=l+r>>1;
        if(x<=mid)L[rt]=update(L[pre],l,mid,x);
        else R[rt]=update(R[pre],mid+1,r,x);
    }
    return rt;
}
inline int query(int u,int v,int l,int r,int k)
{
    if(l>=r)return l;
    int x=sum[L[v]]-sum[L[u]],mid=l+r>>1;
    if(x>=k)return query(L[u],L[v],l,mid,k);
    else return query(R[u],R[v],mid+1,r,k-x);
}
int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].num);
        a[i].pos=i;
    }
    sort(a+1,a+1+n);
    int len=n;
    tot=0;
    for(int i=1;i<=n;i++)
    {
        b[a[i].pos]=a[i].num;
        T[i]=update(T[i-1],1,len,a[i].pos);
    }
    int k,p;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&k,&p);
        printf("%d
",b[query(T[0],T[k],1,len,p)]);
    }
    return 0;
}