P3332 [ZJOI2013] K大数查询 题解

Description

你需要维护 $n$ 个可重整数集，集合的编号从 $1$ 到 $n$。
这些集合初始都是空集，有 $m$ 个操作：

• 1 l r c：表示将 $c$ 加入到编号在 $[l,r]$ 内的集合中
• 2 l r c：表示查询编号在 $[l,r]$ 内的集合的并集中，第 $c$ 大的数是多少。

注意可重集的并是不去除重复元素的，如 $\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}$。

$1 \le n,m \le 5\times 10^4$。

Solution

这里考虑一个在线做法。

首先显然需要用到树套树。由于树套树不能下传标记，所以考虑标记永久化。

具体地，对于这 $n$ 个可重集维护一颗线段树，在线段树上的每个节点 $[l,r]$ 都维护一个值域线段树，表示在 $[l,r]$ 上每个修改的数打的标记的次数。

那么可以得到一个做法：修改时先在修改区间 $[l,r]$ 所有线段树每个分拆区间上打一次标记。查询时则把询问区间 $[L,R]$ 的所有分拆区间的祖先节点（包括自己） $[l_0,r_0]$ 加入 vector，权值为 $\min(R,r_0)-\max(L,l_0)+1$，然后在这 $O(\log n)$ 个值域线段树上二分。

但是这么做是不对的，因为询问时的分拆区间 $[l_0,r_0]$ 的子树内（去除自己）的标记是没有算到的，而这些没有算到的标记的权值均为其所在节点的区间长度，所以还需要维护第二个树套树，表示每个节点 $[l,r]$ 子树内的标记对 $[l,r]$ 的贡献，这个在修改时维护即可。

具体见代码。

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

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 5e4 + 5, kMaxT = 2e7 + 5;

struct Node {
  int ls, rs, cnt;
} t[kMaxT];

int n, m, sgt_cnt;
int rt1[kMaxN * 4], rt2[kMaxN * 4];

void update(int &x, int l, int r, int ql, int v) {
  if (!x) x = ++sgt_cnt;
  t[x].cnt += v;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (ql <= mid) update(t[x].ls, l, mid, ql, v);
  else update(t[x].rs, mid + 1, r, ql, v);
}

void update_arr(int x, int l, int r, int ql, int qr, int c) {
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    update(rt1[x], -n, n, c, 1);
    return;
  }
  update(rt2[x], -n, n, c, std::min(r, qr) - std::max(l, ql) + 1);
  int mid = (l + r) >> 1;
  update_arr(x << 1, l, mid, ql, qr, c), update_arr(x << 1 | 1, mid + 1, r, ql, qr, c);
}

void getpos(int x, int l, int r, int ql, int qr, std::vector<std::pair<int, int>> &vec) {
  if (l > qr || r < ql) return;
  if (rt1[x]) vec.emplace_back(rt1[x], std::min(r, qr) - std::max(l, ql) + 1);
  if (l >= ql && r <= qr) {
    if (rt2[x]) vec.emplace_back(rt2[x], 1);
    return;
  }
  int mid = (l + r) >> 1;
  getpos(x << 1, l, mid, ql, qr, vec), getpos(x << 1 | 1, mid + 1, r, ql, qr, vec);
}

int query(int l, int r, int64_t c) {
  std::vector<std::pair<int, int>> vec;
  getpos(1, 1, n, l, r, vec);
  int L = -n, R = n;
  for (; L != R;) {
    int mid = (L + R) >> 1;
    int64_t crs = 0;
    for (auto [x, w] : vec) crs += 1ll * w * t[t[x].rs].cnt;
    if (c <= crs) {
      L = mid + 1;
      for (auto &[x, w] : vec) x = t[x].rs;
    } else {
      c -= crs, R = mid;
      for (auto &[x, w] : vec) x = t[x].ls;
    }
  }
  return L;
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int op, l, r; int64_t c;
    std::cin >> op >> l >> r >> c;
    if (op == 1) update_arr(1, 1, n, l, r, c);
    else std::cout << query(l, r, c) << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}