题解：CF1227D2 Optimal Subsequences (Hard Version)

题意

给定一个序列，规定长度为的合法子序列如下：

其元素总和在长度为的子序列中最大；
其字典序最小。

给定次查询，每次查询给定，要求输出长度为的合法子序列的第个元素。

思路

首先观察性质。注意到，这个序列一定由前大元素构成，而题目要求字典序尽量小，那么一定是选择下标尽量小的，所以，我们先按照大小为第一关键字、下标为第二关键字排序。

然后考虑如何解决查询。发现，每次直接构造序列似乎不可行，第个似乎没有直接的表达式可求。所以，我们采用扫描线的思想，将查询按照排序，离线处理。

将数组排序后，选取的顺序一定是从前往后的。所以，长度为的子序列，一定就是前个元素。但是，我们并不知道元素的顺序。所以，我们可以开一个权值线段树来记录元素的下标上对应的数，每次单点修改，区间信息为数的个数。求答案时，跑一边线段树上游走即可。

关于线段树上游走，我们设当前在区间，区间中点为，那么如果左区间的数的个数已经满足当前的需求，那么直接返回左区间的答案；否则返回右区间的答案，此时右区间的需求为，为左区间的数的出现个数。

总感觉有简单的做法，但是脑子被数据结构替代，不想想了。所以同学们，数据结构害人啊！

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 2e5 + 10;

// 查询
struct Query {
  int k, p, id;
  // 省一个 cmp 函数
  bool operator<(const Query &oth) const {
    return k < oth.k;
  }
};

struct Node {
  int val, cnt;
};

// 单点修改线段树
struct SegTree {
  Node dat[MAXN << 2], E = {0};
  Node comb(const Node &dat1, const Node &dat2) {
    return {dat1.val + dat2.val, dat1.cnt + dat2.cnt};
  }
  void modify(int root, int l, int r, int pos, int val) {
    if (l == r) {
      dat[root] = {val, 1};
      return;
    }
    int mid = l + r >> 1;
    if (pos <= mid) {
      modify(root << 1, l, mid, pos, val);
    } else {
      modify(root << 1 | 1, mid + 1, r, pos, val);
    }
    dat[root] = comb(dat[root << 1], dat[root << 1 | 1]);
  }
  int query(int root, int l, int r, int k) {
    if (l == r) {
      return dat[root].val;
    }
    int mid = l + r >> 1;
    if (dat[root << 1].cnt >= k) {
      return query(root << 1, l, mid, k);
    } else {
      return query(root << 1 | 1, mid + 1, r, k - dat[root << 1].cnt);
    }
  }
} T;

int n, m, ans[MAXN];
pii a[MAXN];
vector<Query> Q;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].first;
    a[i].second = i;
  }
  // 将原数组排序
  sort(a + 1, a + n + 1, [](const pii &i, const pii &j) { return i.first > j.first || (i.first == j.first && i.second < j.second); });
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int k, p;
    cin >> k >> p;
    Q.push_back({k, p, i});
  }
  // 将查询排序
  sort(Q.begin(), Q.end());
  int last = 1;
  // 按照 k 从小到大处理查询
  for (Query &q : Q) {
    for (; last <= q.k; last++) {
      T.modify(1, 1, n, a[last].second, a[last].first);
    }
    ans[q.id] = T.query(1, 1, n, q.p);
  }
  for (int i = 1; i <= m; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}