题解：CF1227D2 Optimal Subsequences (Hard Version)

· · 题解

非常简单的贪心题。

显然这个子序列肯定是这样的：

  1. 先选大的数，再选小的数

  2. 每一次会尽量把当前那个数选完

于是我们可以把 a_i 离散化，并把 a_i 出现的位置放在 vector 中。

然后把询问离线下来，按照 k 的大小从小到大排序，方便我们一个一个加数来计算答案。令 f_i 表示 a_i 是否被选到了子序列中。

接下来就是求 pos 位的值，我们考虑二分。记 sum_i=\displaystyle\sum_{j=1}^i f_j，我们在二分的时候只需要判断 sum_{mid} 与 pos 的大小关系即可。

至于如何维护，一个支持单点修改的线段树就行了。

时间复杂度：O(n \log^2 n)

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define lowbit(x) ((x)&(-(x)))
#define abs(x) ((x)>0?(x):(-(x)))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define gc getchar
#define pc putchar
#define sz(v) ((int)(v.size()))
using namespace std;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
inline int read(){
    int x=0,f=1;
    char ch=gc();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=gc();}
    return x*f;
}
inline void print(int x){
    if (x<0) pc('-'),x*=-1;
    if (x<10) pc(x+'0');
    else print(x/10),pc(x%10+'0');
}
const int N=2e5+5;
int a[N],num[N];
vector<int> v[N];
int sum[N];
struct node{
    int k,pos;
    int id,ans;
}qq[N];
bool cmp(node xx,node yy){
    return xx.k<yy.k;
}
int t[N<<2];
void push_up(int p){
    t[p]=t[ls(p)]+t[rs(p)];
}
void update(int l,int p,int pl,int pr){
    if (pl==pr){
        t[p]=1;
        return ;
    }
    int mid=(pl+pr)>>1;
    if (l<=mid) update(l,ls(p),pl,mid);
    else update(l,rs(p),mid+1,pr);
    push_up(p);
}
int query(int l,int r,int p,int pl,int pr){
    if (l<=pl&&pr<=r) return t[p];
    int mid=(pl+pr)>>1;
    int ans=0;
    if (l<=mid) ans+=query(l,r,ls(p),pl,mid);
    if (r>mid) ans+=query(l,r,rs(p),mid+1,pr);
    return ans;
}
bool cmp2(node xx,node yy){
    return xx.id<yy.id;
}
void sol(){
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i],num[i]=a[i];
    sort(num+1,num+n+1);
    int cnt=unique(num+1,num+n+1)-num-1;
    for (int i=1;i<=n;i++) a[i]=lower_bound(num+1,num+cnt+1,a[i])-num;
    for (int i=1;i<=n;i++) v[a[i]].pb(i);
    int q;
    cin>>q;
    for (int i=1;i<=q;i++) cin>>qq[i].k>>qq[i].pos,qq[i].id=i;
    sort(qq+1,qq+q+1,cmp);
    int now=cnt;
    int _=0;
    int __=1;
    for (int i=1;i<=n;i++){
        _++;
        if (_>v[now].size()){
            now--;
            _=1;
        }
        update(v[now][_-1],1,1,n);
        while (qq[__].k==i){
            int L=1,R=n;
            int Ans=0;
            while (L<=R){
                int mid=(L+R)>>1;
                if (query(1,mid,1,1,n)>=qq[__].pos) Ans=mid,R=mid-1;
                else L=mid+1;
            }
            qq[__++].ans=Ans;
        }
    }
    sort(qq+1,qq+q+1,cmp2);
    for (int i=1;i<=q;i++) cout<<num[a[qq[i].ans]]<<endl;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while (t--) sol();
    return 0;
}