Optimal Subsequences(主席树)

题意:

给定一个序列，长度为n(<=2e5)，有m(<=2e5)个询问，每个询问包含k和pos，要从原序列中选出一个长度为k的子序列，要求是这个序列的和是所有长度为k的序列中最大的，且是字典序最小的，要求输出子序列中第pos个元素。

思路:

显然要是长度为k的序列中和最大，必须要优先选大的数。显然必须全部选的数不需要考虑位置，部分选的数(必定是最小的数)肯定优先选择坐标小的，因此可以将所有数按数值从大到小排，然后坐标从小到达排，前k的数就是每次要选的数。而第pos个元素就是排好的数前k个中坐标值第pos小的，用主席树维护坐标值就好了。

#include <bits/stdc++.h>

using namespace std;

const int maxn=2e5+5;

const int Log=40;

int num[maxn*Log],lson[maxn*Log],rson[maxn*Log];

int root[maxn];

int tot;

int build(int l,int r){

    int pos=++tot;

    if(l<r){

        int mid=(l+r)>>1;

        lson[pos]=build(l,mid);

        rson[pos]=build(mid+1,r);

    }

    return pos;

}

int update(int rt,int l,int r,int p){

    int pos=++tot;

    num[pos]=num[rt]+1;

    lson[pos]=lson[rt];

    rson[pos]=rson[rt];

    if(l<r){

        int mid=(l+r)>>1;

        if(p<=mid) lson[pos]=update(lson[rt],l,mid,p);

        else rson[pos]=update(rson[rt],mid+1,r,p);

    }

    return pos;

}

int query(int Old,int New,int l,int r,int k){

    if(l==r)return l;

    int mid=(l+r)>>1;

    int x=num[lson[New]]-num[lson[Old]];

    if(x>=k) return query(lson[Old],lson[New],l,mid,k);

    else return query(rson[Old],rson[New],mid+1,r,k-x);

}

struct node{

    int v,pos;

}N[maxn];

bool cmp(node a,node b){

    return a.v==b.v?a.pos<b.pos:a.v>b.v;

}

int a[maxn];

int main(){

    int n,q;

    cin>>n;

    for(int i=1;i<=n;i++){

        scanf("%d",&N[i].v);

        N[i].pos=i;

        a[i]=N[i].v;

    }

    sort(N+1,N+1+n,cmp);

    for(int i=1;i<=n;i++)

        root[i]=update(root[i-1],1,n,N[i].pos);

    root[0] = build(1, n);

    cin>>q;

    while(q--){

        int k,pos;scanf("%d%d",&k,&pos);

        int p=query(root[0],root[k],1,n,pos);

        printf("%d\n",a[p]);

    }

}

巴特西

Optimal Subsequences(主席树)

最新文章

热门文章