QOJ #964. Excluded Min 题解

Description

设 $S$ 为一个包含非负整数的多重集。你可以对 $S$ 进行任意次（可能为零次）以下操作：选择一个在 $S$ 中至少出现两次的数 $x$，删除其中一个 $x$，但插入一个 $(x-1)$ 或 $(x+1)$ 代替（仅当 $x-1$ 非负时才能插入 $x-1$）。定义 $F(S)$ 为通过这些操作能达到的最大 mex（最小未出现的非负整数）。

你将得到一个长度为 $n$ 的数组 $a$，以及 $q$ 个区间查询 $[l,r]$。对于每个查询，求 $F(\{a_l,a_{l+1},\dots,a_r\})$。

$n,q,\max\{a_i\}\leq 5\times 10^5$。

Solution

先考虑对于单组询问怎么快速做。

不妨设答案为 $k$，容易发现 $[0,k-1]$ 最终填的数只能由 $[0,k-1]$ 操作过来。

所以需要满足 $[0,k-1]$ 的数的个数要大于等于 $k$。同时只要满足这个条件就一定合法，因为如果有一个空的位置，则必然会有一个位置有大于等于 $2$ 个数，将这个数操作过来即可让空的位置减一。而总的数的个数大于等于位置的个数，所以一定能操作到没有空位置。

所以单组询问就是找到最大的 $k$，使得 $\leq k-1$ 的数的个数大于等于 $k$。

这个用莫队维护 $k-cnt_{0,k-1}$ 的最大值，可以做到 $O(n\sqrt q\log n)$，过不了。

---

考虑大到小枚举 $k$，对于每个询问区间 $[l,r]$，维护 $[l,r]$ 内取值在 $[0,k-1]$ 的数的个数。

每次让 $k$ 变到 $k-1$，就是将所有取值为 $k-1$ 的位置 $x$ 删掉，并把包含 $x$ 的所有区间 $[l,r]$ 的权值减一。

这是个二维问题，很难做到更优。

注意到上面的做法慢，主要是区间没有单调性，导致删除操作不能维护。

由于一个区间 $[l_1,r_1]$ 包含另一个区间 $[l_2,r_2]$，则第一个区间的答案一定大于等于第二个区间的答案。

所以被包含的区间可以暂时不加入集合，等到所有包含它的区间都得到答案后再加进去。

这样的话区间集合的左右端点就都有单调性了，用 set 加线段树维护即可。

而删区间的过程就是找到当前区间 $x$ 的前驱 $pre$ 和后继 $nxt$，每次找到左端点在 $[l_x,l_{nxt}-1]$ 内，且右端点最大的（相同则选择左端点最小的）未加入区间，如果新区间的右端点大于 $r_{pre}$，则说明可以加入，将 $nxt$ 设为新加入的区间后继续递归即可。

时间复杂度：$O((n+q+V)\log n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

using pii = std::pair<int, int>;

const int kMaxN = 5e5 + 5;

int n, q, mx;
int a[kMaxN], pos[kMaxN], ans[kMaxN];
std::array<int, 3> qq[kMaxN];
std::set<std::array<int, 3>> st1, st2;
std::set<std::pair<int, int>> st3[kMaxN];
std::vector<int> vec[kMaxN * 2], T[kMaxN];

struct BIT {
  int c[kMaxN];
  void upd(int x, int v) {
    for (; x <= n; x += x & -x) c[x] += v;
  }
  int qry(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret += c[x];
    return ret;
  }
  int qry(int l, int r) { return qry(r) - qry(l - 1); }
} bit;

struct SGT {
  pii mx[kMaxN * 4];
  int tag[kMaxN * 4];
  void pushup(int x) {
    if (mx[x << 1].first >= mx[x << 1 | 1].first) mx[x] = mx[x << 1];
    else mx[x] = mx[x << 1 | 1];
  }
  void addtag(int x, int v) {
    mx[x].first += v, tag[x] += v;
  }
  void pushdown(int x) {
    if (tag[x]) {
      addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]);
      tag[x] = 0;
    }
  }
  void build(int x, int l, int r) {
    tag[x] = 0;
    if (l == r) return void(mx[x] = {-1e9, l});
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  void update1(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return addtag(x, v);
    pushdown(x);
    int mid = (l + r) >> 1;
    update1(x << 1, l, mid, ql, qr, v), update1(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }
  void update2(int x, int l, int r, int ql, pii v) {
    if (l == r) return void(mx[x] = v);
    pushdown(x);
    int mid = (l + r) >> 1;
    if (ql <= mid) update2(x << 1, l, mid, ql, v);
    else update2(x << 1 | 1, mid + 1, r, ql, v);
    pushup(x);
  }
  pii query(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return {-1e9, 0};
    else if (l >= ql && r <= qr) return mx[x];
    pushdown(x);
    int mid = (l + r) >> 1;
    auto L = query(x << 1, l, mid, ql, qr), R = query(x << 1 | 1, mid + 1, r, ql, qr);
    if (L.first >= R.first) return L;
    else return R;
  }
} sgt1, sgt2;

void ins(int x) {
  sgt1.update2(1, 1, q, x, {bit.qry(qq[x][0], qq[x][1]), x});
  st1.emplace(std::array<int, 3>{qq[x][0], qq[x][1], x});
  st2.emplace(std::array<int, 3>{qq[x][1], qq[x][0], x});
  st3[qq[x][0]].erase({qq[x][1], x});
  int l = qq[x][0], r = qq[x][1];
  if (st3[l].size()) sgt2.update2(1, 1, n, l, *st3[l].rbegin());
  else sgt2.update2(1, 1, n, l, {-1e9, 0});
}

void del(int x) {
  sgt1.update2(1, 1, q, x, {-1e9, x});
  st1.erase(std::array<int, 3>{qq[x][0], qq[x][1], x});
  st2.erase(std::array<int, 3>{qq[x][1], qq[x][0], x});
  int pre = 0, nxt = n + 1;
  auto it = st1.lower_bound({qq[x][0], qq[x][1], 0});
  if (it != st1.end()) nxt = it->at(0);
  if (it != st1.begin()) pre = prev(it)->at(1);
  while (true) {
    auto p = sgt2.query(1, 1, n, qq[x][0], nxt - 1);
    if (p.first > pre) {
      int y = p.second;
      ins(p.second), nxt = qq[p.second][0];
    } else {
      break;
    }
  }
}

void dickdreamer() {
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    vec[a[i]].emplace_back(i);
    mx = std::max(mx, a[i]);
  }
  for (int i = 1; i <= q; ++i) {
    int l, r;
    std::cin >> l >> r;
    qq[i] = {l, r, i};
  }
  sgt1.build(1, 1, q), sgt2.build(1, 1, n);
  std::sort(qq + 1, qq + 1 + q);
  for (int i = 1; i <= n; ++i) bit.upd(i, 1);
  for (int i = 1; i <= q; ++i) st3[qq[i][0]].emplace(qq[i][1], i);
  for (int i = 1; i <= n; ++i) {
    if (st3[i].size()) sgt2.update2(1, 1, n, i, *st3[i].rbegin());
    else sgt2.update2(1, 1, n, i, {-1e9, 0});
  }
  for (int i = 1, mx = 0; i <= q; ++i) {
    pos[qq[i][2]] = i;
    if (mx < qq[i][1]) {
      mx = qq[i][1], ins(i);
    }
  }
  for (int v = mx + n; ~v; --v) {
    for (auto x : vec[v]) {
      bit.upd(x, -1);
      auto it1 = st1.lower_bound({x + 1, 0, 0}), it2 = st2.lower_bound({x, 0, 0});
      int l = q + 1, r = 0;
      if (it2 != st2.end()) l = it2->at(2);
      if (it1 != st1.begin()) r = prev(it1)->at(2);
      if (l <= r) sgt1.update1(1, 1, q, l, r, -1);
    }
    for (; sgt1.mx[1].first >= v;) {
      int x = sgt1.mx[1].second;
      ans[qq[x][2]] = v, del(x);
    }
  }
  for (int i = 1; i <= q; ++i) std::cout << ans[i] << '\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;
}