CF1227D2 Optimal Subsequences (Hard Version) 题解

· · 题解

三个月前，我曾写过 1227D1 的题解。

当时写完暴力方法后对着 D2 看了半天，想不出什么好的做法，这题也就一直鸽着没写。今天偶然看到，想到了一个方法，就在这里分享一下吧。

将问题简单化

假设一开始令一序列 b 与序列 a 完全相同，且之后将序列 b 从大到小排序。

当查询子序列长度为 k 时，序列 a 中大于 b_k 的数一定会被选中，等于 b_k 的数排得越前，越优先被选入子序列。

这里就不细说了，如果不理解的可以去看 D1 题解。

算法的分析

这个不难，因为 a_i \le 10^9 而数字只有 2 \times 10^5 个，所以可以再创建一个序列 c 作为序列 a 的离散化数组。

开 n 个 vector（命名为 v），第 i 个 vector 记录离散化后的值等于 i 的数，在序列 a 的下标。

对于同一个 vector，里面的元素应满足单调递增。

查询序列 a 中第 i 个等于 a_j 的数的位置，只要找 v[c[j]][i - 1] 就行了。

如果对每个询问独立进行回答，这个问题会变得困难。

不难看出，询问的 k_i 长度如果递增，一共只需要插入 n 次数字，避免了巨量的增删。

因此，我们可以离线解决这个问题，将操作以 k 从小到大排序。

如果 b[s] 与 b[s + 1] 相等，那么要在子序列中插入一个之前没被插入过，且在序列 a 中最靠前且等于 b[s] 的数。

否则，只需要插入序列 a 中第一个等于 b[s + 1] 的数的位置。

这步的实现见上文「快速定位」的步骤。

由于我很菜，没往平衡树和块状链表等算法思考，就在这里提供一个较好理解的做法吧。

首先这题特殊的地方在于，我们知道所有即将插入的数值，以及它在最终序列的下标。

那换个表示方法，每插入一个数字，就在序列 a 中该数字对应的位置上打一个标记。

如果我们不想让这些没标记的位置添麻烦，我们可以将序列 a 记录标记的前缀和。

最后，如果询问到序列第 pos 个位置的话，我们就找第一个前缀和等于 pos 的位置就可以了。这可以二分解决。

至于前缀和的维护，我们可以操作一个树状数组实现。

总复杂度：O(m \log^2 n)，瓶颈在于二分 + 树状数组。

代码：

#include <algorithm>
#include <cstdio>
#include <vector>
#define INF 1e9
#define eps 1e-6
#define N 200010
typedef long long ll;
using namespace std;

struct query{
    int k, pos, id;
}q[N];
struct S{
    int id, v;
}s[N];
int n, m, a[N], b[N], cnt;
int ss[N], ans[N], t[N];
vector <int> v[N];

bool cmp(S x, S y){
    if(x.v != y.v) return x.v > y.v;
    return x.id < y.id;
}

bool cmpp(query x, query y){
    if(x.k != y.k) return x.k < y.k;
    return x.pos > y.pos;
}

// 树状数组模板

inline int lowbit(int x){
    return x & (-x);
}

void modify(int x){
    while(x <= n)
        t[x]++, x += lowbit(x);
}

int sum(int x){
    int ss = 0;
    while(x >= 1)
        ss += t[x], x -= lowbit(x);
    return ss;
}

int main(){

    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), b[i] = a[i];
    scanf("%d", &m);
    // 离散化
    sort(b + 1, b + n + 1);
    cnt = unique(b + 1, b + n + 1) - b - 1;
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
        s[i].id = i, s[i].v = a[i];
        v[a[i]].push_back(i);
    }
    // 排序操作
    sort(s + 1, s + n + 1, cmp);
    for(int i = 1, k, pos; i <= m; i++)
        scanf("%d%d", &q[i].k, &q[i].pos), q[i].id = i;
    sort(q + 1, q + m + 1, cmpp);   // 离线解决
    int nowk = 0;
    for(int i = 1, L, R; i <= m; i++){
        while(nowk < q[i].k)    // 树状数组维护
            nowk++, modify(v[s[nowk].v][ss[s[nowk].v]]), ss[s[nowk].v]++;
        L = 1, R = n;
        while(L < R){       // 二分找答案
            int mid = (L + R) >> 1;
            if(sum(mid) < q[i].pos) L = mid + 1;
            else R = mid;
        }
        ans[q[i].id] = b[a[L]];
    }
    for(int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);

    return 0;
}