ABC237G Range Sort Query

思路

这道题跟 P2824 的思路是很相似的。

首先由于我们只需求一个特定的值在排序后的位置，而原序列又是一个排列，因此我们可以将序列中的所有数分为三种：

1. 大于 \(X\) 的；
2. 等于 \(X\) 的；
3. 小于 \(X\) 的。

我们不关心除了 \(X\) 之外的其他值的具体数字，而只关心其与 \(X\) 的大小关系，那么可以将数列抽象为一个 \(01\) 序列。将序列中所有大于等于 \(X\) 的数字赋为 \(1\)，而小于 \(X\) 的数字赋为 \(0\)。然后利用线段树分类讨论即可以做到 \(O(n \log n)\) 模拟题目中的所有排序操作。

但是问题在于，题目是要求我们找到 \(X\) 这一个数字的具体位置，而上述的转化方法不支持我们找到 \(X\) 具体的位置，因为所有大于等于 \(X\) 的数字均对应 \(1\)。这该怎么办呢？

解决方法也很简单，再做一次就好了嘛！只不过这次，我们将所有小于等于 \(X\) 的值赋为 \(0\)，大于 \(X\) 的值赋为 \(1\)。这样，\(X\) 在第一个序列中对应的是 \(1\) ，而在第二个序列中对应的是 \(0\)，然后原序列又是一个排列，即只存在一个 \(X\)，于是利用这个性质我们就可以找到 \(X\)。

那么具体的怎么用线段树来完成 \(01\) 序列的排序操作呢？很简单，由于只存在 \(01\) 两种数字，那么其实排序就是一个区间推平的问题。首先统计出带求区间中 \(1\) 的个数，如果不存在 \(1\) 我们直接跳过，如果存在的话，先把区间拍成 \(0\)，然后若是升序就把所有的 \(1\) 丢到序列的末尾，若是降序就丢到开头，这也是可以直接用区间推平维护的。

那么总的时间复杂度就做到了 \(O(n \log n)\)。

代码

#include <bits/stdc++.h>

using i64 = long long;

struct SegTree {
  int n;
  struct Node { 
    int sum, tag, l, r; 
    Node() { sum = l = r = 0, tag = -1; }
  };
  friend Node operator+(const Node &lhs, const Node &rhs) {
    Node res;
    res.l = lhs.l, res.r = rhs.r, res.sum = lhs.sum + rhs.sum;
    return res;
  }
  std::vector<Node> tree;
  std::vector<int> a;
  SegTree(int _n) { n = _n, tree.resize((n << 2) + 1); }
  void build(int l, int r, int u) {
    if (l == r) {
      tree[u].l = l, tree[u].r = r, tree[u].sum = a[l - 1];
      return;
    }
    int mid = (l + r) >> 1, lc = u << 1, rc = u << 1 | 1;
    build(l, mid, lc), build(mid + 1, r, rc);
    tree[u] = tree[lc] + tree[rc];
  }
  void build(const std::vector<int> &_a) {
    a = _a;
    build(1, n, 1);
  }
  void tagging(int u, int val) {
    tree[u].sum = (tree[u].r - tree[u].l + 1) * val;
    tree[u].tag = val;
  }
  void pushdown(int u) {
    if (tree[u].tag == -1) { return; }
    tagging(u << 1, tree[u].tag), tagging(u << 1 | 1, tree[u].tag);
    tree[u].tag = -1;
  }
  void assign(int l, int r, int u, int val) {
    int s = tree[u].l, t = tree[u].r;
    if (l <= s && t <= r) {
      tagging(u, val);
      return;
    }
    pushdown(u);
    int mid = (s + t) >> 1, lc = u << 1, rc = u << 1 | 1;
    if (mid >= l) { assign(l, r, lc, val); }
    if (mid <  r) { assign(l, r, rc, val); }
    tree[u] = tree[lc] + tree[rc];
  }
  int query(int l, int r, int u) {
    int s = tree[u].l, t = tree[u].r;
    if (l <= s && t <= r) { return tree[u].sum; }
    pushdown(u);
    int mid = (s + t) >> 1, lc = u << 1, rc = u << 1 | 1;
    int res = 0;
    if (mid >= l) { res += query(l, r, lc); }
    if (mid <  r) { res += query(l, r, rc); }
    return res;
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, m, p;
  std::cin >> n >> m >> p;

  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }

  SegTree t1(n), t2(n);
  std::vector<int> b(n), c(n);
  for (int i = 0; i < n; i++) { b[i] = (a[i] >= p), c[i] = (a[i] > p); }
  t1.build(b), t2.build(c);
  
  for (int i = 0; i < m; i++) {
    int opt, l, r;
    std::cin >> opt >> l >> r;

    int cnt1 = t1.query(l, r, 1), cnt2 = t2.query(l, r, 1);
    t1.assign(l, r, 1, 0), t2.assign(l, r, 1, 0);
    if (opt == 2) {
      if (cnt1) { t1.assign(l, l + cnt1 - 1, 1, 1); }
      if (cnt2) { t2.assign(l, l + cnt2 - 1, 1, 1); }
    } else {
      if (cnt1) { t1.assign(r - cnt1 + 1, r, 1, 1); }
      if (cnt2) { t2.assign(r - cnt2 + 1, r, 1, 1); }
    }
  }

  for (int i = 1; i <= n; i++) {
    if ((!!t1.query(i, i, 1)) && (!t2.query(i, i, 1))) {
      std::cout << i << "\n";
      return 0;
    }
  }

  return 0;
}