Optimal Subsequences (Hard Version)

Created by LXC on Tue Mar 12 14:46:06 2024

https://codeforces.com/problemset/problem/1227/D2

ranting: 1800

tag: data structures, greedy

problem

本题为较困难版本。

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,…,a_n$。

有 $m$ 个询问，每次询问给出两个正整数 $k,pos$。你需要找到一个长度为 $k$ 的子序列，且满足如下要求：

• 该子序列的元素和是所有子序列中最大的；
• 该子序列是所有满足上一条件的子序列中字典序最小的一个。

对于每个询问，输出该子序列的第 $pos$ 个元素的值。

$1 \le n,m \le 2 \times 10^5$（这是与简单版本唯一的区别）， $\ 1 \le k \le n$，在同一询问中有 $1 \le pos \le k$。

Translated by HoshizoraZ

solution

离线处理查询，优先回答查询k小的。

对于子序列长度为k，优先选择k个最大的数，如果有多个相同值的数，优先选择下表靠前的数保证字典序最小。

例如$a=[1,2,3,4,3,2,1]$, 优先选择$a_{4} = 4, a_{3} = 3, a_{5} = 3, a_{2} = 2, a_{6} = 2, a_{1} = 1, a_{7} = 1$

接下来就是在固定长度为k的子序列中寻找第$pos$个数的值，我们可以用线段树维护当前所选的k个数的下标，然后二分查找第$pos$个非0的叶子，其下标则是第pos个数的下标。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 200005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

#define LS (id << 1)
#define RS (id << 1 | 1)
ll sum[4 * N];

void push_up(int id) {
    sum[id] = sum[LS] + sum[RS];
}

void build(int id, int l, int r) {
    sum[id] = 0;
    if (l == r) {
        return;
    }
    int m = l + r >> 1;
    build(LS, l, m);
    build(RS, m + 1, r);
}
// 单点增加v
void add(int id, int l, int r, int q, ll v) {
    if (l == r && l == q) {
        sum[id] += v;
        return;
    }
    int m = l + r >> 1;
    if (q <= m)
        add(LS, l, m, q, v);
    if (m < q)
        add(RS, m + 1, r, q, v);
    push_up(id);
}


// 叶子值为0或1,二分找第th个非0值的下标
int bs(int id, int l, int r, int th) {
    if (l == r) return l;
    int m = l+r>>1;
    if (sum[LS]>=th) return bs(LS, l, m, th);
    else return bs(RS, m+1, r, th-sum[LS]);
}

// 区间查询和
// ll ask(int id, int l, int r, int ql, int qr) {
//     if (ql <= l && r <= qr) {
//         return sum[id];
//     }
//     int m = l + r >> 1;
//     ll rt = 0;
//     if (ql <= m)
//         rt += ask(LS, l, m, ql, qr);
//     if (m < qr)
//         rt += ask(RS, m + 1, r, ql, qr);
//     return rt;
// }

void sol() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    map<int,vector<int>, greater<int>> mp;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        mp[a[i]].push_back(i);
    }
    build(1, 1, n);
    int m;
    cin >> m;
    vector<pair<int,int>> q(m);
    for (auto& [i,j]:q) cin >> i >> j;
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return q[x] < q[y];
    });
    vector<int> ans(m);
    int p = 0, sz = 0;
    for (auto& [i,j]:mp) {
        // cout << i << " " << j << endl;
        for (int c:j) {
            add(1, 1, n, c, 1);
            sz++;
            while (p<m && q[idx[p]].first==sz) {
                ans[idx[p]] = a[bs(1, 1, n, q[idx[p]].second)];
                p++;
            }
        }
    }
    // cout << ans << endl;
    for (auto i:ans) {
        cout << i << "\n";
    }

}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}