P11983 [JOIST 2025] 展览会 3 题解

Description

JOI 美术馆计划近期举办一场绘画展览。馆方拥有编号为 $1$ 至 $N$ 的 $N$ 幅画作，其中画作 $i$（$1 \leq i \leq N$）的美观值为 $A_i$。在展览中这些画作将排成一行展示，但具体排列顺序尚未确定。

共有 $M$ 家杂志将对展览进行报道。这些杂志按影响力从大到小依次编号为 $1$ 至 $M$。每家杂志将发布展览中某一连续段画作的摄影照片。具体来说，杂志 $j$（$1 \leq j \leq M$）将发布排列中从左数第 $L_j, L_j + 1, \ldots, R_j$ 幅画作的照片。杂志 $j$（$1 \leq j \leq M$）报道的吸引力定义为该杂志所覆盖画作的最大美观值。

JOI 君作为 JOI 美术馆的馆长，希望通过排列画作使得这些杂志的报道更具吸引力，从而吸引更多参观者。由于影响力更大的杂志能触达更多受众，他优先希望提升更具影响力杂志的报道吸引力。

具体而言，设 $b_j$ 为杂志 $j$（$1 \leq j \leq M$）报道的吸引力，则 JOI 君希望排列画作，使得序列 $b = (b_1, b_2, \ldots, b_M)$ 的字典序最大化。

在这里，对于不同的数列 $b = (b_1, b_2, \ldots, b_M)$ 和 $b' = (b'_1, b'_2, \ldots, b'_M)$，所谓“$b$ 在字典序上大于 $b'$”，是指存在满足 $b_k \neq b'_k$ 的最小下标 $k$（$1 \leq k \leq M$），且对于该 $k$ 有 $b_k > b'_k$。

请编写一个程序，根据待展览画作的信息和报道展览的杂志信息，计算当画作排列使序列 $b = (b_1, b_2, \ldots, b_M)$ 字典序最大化时，每家杂志报道的吸引力。

$1 ≤ N ≤ 10^5,1 ≤ M ≤ 10^5,1 ≤ A_i ≤ N$。

Solution

下面假定 $n,m$ 同阶。

设 $f(S)$ 表示要满足在 $S$ 集合内的区间里每个区间至少有一个点的最少总点数。

首先肯定是贪心地给编号最小的区间 $i$ 选择最大的 $v$，使得 $f(S_v\cup\{[l_i,r_i]\})\leq cnt_v$，并让 $S_v\leftarrow S_v\cup\{[l_i,r_i]\}$。

求 $f(S)$ 的话就直接按照右端点从小到大排序，如果当前区间 $[l,r]$ 不包含任何一个点，就在 $r$ 处放一个点。最后放的点数就是答案。

可以发现这么做选的第 $i$ 个点的位置 $sr_i$ 实际上是所有可能方案中第 $i$ 个点的最大可能下标，倒过来按照左端点从大到小排序贪心能够得到最小可能下标 $sl_i$。下面这个东西有两个性质：

性质 1：$\forall 1\leq i<k,sr_i<sl_{i+1}$。

证明

如果存在 $sl_i\leq sl_{i+1}\leq sr_i\leq sr_{i+1}$，找到最大的满足这个条件的 $i$，则满足 $sr_{i+1}<sl_{i+2}$ 且存在一个区间 $j$，满足 $r_j=sr_i$ 且 $l_j>sr_i\geq sl_{i+1}$，所以倒过来贪心的时候 $i+1$ 这个位置的点一定会选到选 $l_j$ 而不是 $sl_{i+1}$。

性质 2：给 $S$ 加入一个区间 $[L,R]$，$f(S)$ 不变的充要条件是存在 $i$，满足 $[sl_i,sr_i]$ 与 $[L,R]$ 有交。

证明

只需要说明存在一个选点方案，使得 $[L,R]$ 包含其中至少一个点。

找到有交的 $i$，所有 $j<i$ 的点放在 $sr_j$，$j>i$ 的点放在 $sl_j$。这 $k-1$ 个点的放置方案可以解决所有已经加到 $S$ 中 $l\leq sl_{i-1}$ 或者 $r\geq sr_{i+1}$ 的区间。容易发现剩下的区间 $[l,r]$，一定满足 $l\leq sl_i\leq sr_i\leq r$，所以第 $i$ 个点可以在 $[sl_i,sr_i]$ 内随便选，放在和 $[L,R]$ 的交里即可。

如果找不到这样的 $i$ 显然 $f(S)$ 会增加。

考虑从大到小枚举 $v$，设限制是 $lim$，答案为 $v$ 的区间数是 $c$，我们希望用 $O(c\times\text{polylog}(c))$ 的时间复杂度找到这些区间。

首先如果 $f(S)$ 一直会增加的话 $sl_i$ 和 $sr_i$ 会很不好维护，所以考虑先二分找到一个极长的前缀使得这个前缀的 $f(S)$ 不超过 $lim$。

那么这个前缀的 $f(S)$ 一定等于 $lim$ 或者这个前缀把所有区间选完了。

但是直接二分复杂度不是均摊的，因为二分的过程中会用至少 $O(n\log n)$ 的代价 check，$c$ 如果是 $1$ 的话就会退化成 $O(n^2\log n)$。

考虑倍增，暴力 check，找到最大的 $b$ 满足 $2^b\leq c$，那么 $2^b\leq c<2^{b+1}$，在这个区间内再进行二分即可。总时间复杂度变为 $O(c\log^2n)$，均摊就对了！

先维护出这个前缀的区间构成的 $[sl_i,sr_i]$，我们用优先队列维护与某个区间 $[sl_i,sr_i]$ 的相交的编号最小的区间。每次弹出队首并暴力更新 $sl_i$ 和 $sr_i$，由于 $sl_i$ 只会变大，$sr_i$ 只会变小，而分别总共只有 $O(c)$ 种取值，所以 $[sl_i,sr_i]$ 的历史总变化量为 $O(c)$。如果某个 $[sl_j,sr_j]$ 被更新了，就再往优先队列里加入一个与当前的 $[sl_j,sr_j]$ 相交的最小区间。

但是如果一个区间 $[l_j,r_j]$ 完全包含了很多区间，且编号很小，它就会加入队列很多次，复杂度又不对了。但是注意到这个区间最终一定会被加入，并且不会对 $[sl_i,sr_i]$ 造成影响，所以每次 $[sl_i,sr_i]$ 更新前先把所有这样的区间删掉即可。剩下的区间如果有交则说明要么左端点在区间内，要么右端点在区间内，只会算至多两次。

单次的时间复杂度为 $O(c\log^2n)$，总的时间复杂度也就是 $O(n\log^2n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

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

const int kMaxN = 1e5 + 5;

int n, m;
int cnt[kMaxN], l[kMaxN], r[kMaxN], res[kMaxN];
bool vis[kMaxN];

struct List {
  int fir, pre[kMaxN], nxt[kMaxN];
  void init(int n) {
    fir = 1;
    for (int i = 1; i <= n; ++i) {
      pre[i] = i - 1, nxt[i] = (i == n ? 0 : i + 1);
    }
  }
  void del(int x) {
    if (x == fir) fir = nxt[x];
    if (pre[x]) nxt[pre[x]] = nxt[x];
    if (nxt[x]) pre[nxt[x]] = pre[x];
  }
  std::vector<int> getid(int k) {
    std::vector<int> v;
    for (int i = fir; i && k; i = nxt[i], --k) v.emplace_back(i);
    if (k) return {};
    return v;
  }
} list;

struct SGT1 {
  std::vector<int> st[kMaxN * 4];
  void ins(int x, int l, int r, int ql, int v) {
    st[x].emplace_back(v);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (ql <= mid) ins(x << 1, l, mid, ql, v);
    else ins(x << 1 | 1, mid + 1, r, ql, v);
  }
  int query(int x, int l, int r, int ql, int qr) {
    for (; st[x].size() && vis[st[x].back()]; st[x].pop_back()) {}
    if (!st[x].size() || l > qr || r < ql) return 1e9;
    else if (l >= ql && r <= qr) return st[x].back();
    int mid = (l + r) >> 1;
    return std::min(query(x << 1, l, mid, ql, qr), query(x << 1 | 1, mid + 1, r, ql, qr));
  }
} sgt1, sgt2;

struct SGT2 {
  std::vector<pii> st[kMaxN * 4];
  void ins(int x, int l, int r, int ql, pii v) {
    st[x].emplace_back(v);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (ql <= mid) ins(x << 1, l, mid, ql, v);
    else ins(x << 1 | 1, mid + 1, r, ql, v);
  }
  pii query(int x, int l, int r, int ql, int qr) {
    for (; st[x].size() && vis[st[x].back().second]; st[x].pop_back()) {}
    if (!st[x].size() || l > qr || r < ql) return {1e9, 0};
    else if (l >= ql && r <= qr) return st[x].back();
    int mid = (l + r) >> 1;
    return std::min(query(x << 1, l, mid, ql, qr), query(x << 1 | 1, mid + 1, r, ql, qr));
  }
} sgt3;

struct BIT {
  int c[kMaxN];
  void clear() { std::fill_n(c + 1, n, 1e9); }
  void upd(int x, int v) {
    for (; x <= n; x += x & -x) c[x] = std::min(c[x], v);
  }
  int qry(int x) {
    int ret = 1e9;
    for (; x; x -= x & -x) ret = std::min(ret, c[x]);
    return ret;
  }
  void clear(int x) {
    for (; x <= n; x += x & -x) c[x] = 1e9;
  }
} bit1, bit2;

void del(int x) {
  vis[x] = 1, list.del(x);
}

int calc(std::vector<int> id) {
  if (!id.size()) return 1e9;
  std::sort(id.begin(), id.end(), [&] (int i, int j) { return r[i] < r[j]; });
  int cnt = 0, nowr = 0;
  for (auto i : id) {
    if (l[i] > nowr) ++cnt, nowr = r[i];
  }
  return cnt;
}

std::vector<std::pair<int, int>> getseg(std::vector<int> id) {
  std::vector<int> sl, sr;
  {
    std::sort(id.begin(), id.end(), [&] (int i, int j) { return l[i] > l[j]; });
    int nowl = 1e9;
    for (auto i : id) {
      if (r[i] < nowl) sl.emplace_back(l[i]), nowl = l[i];
    }
    std::reverse(sl.begin(), sl.end());
  }
  {
    std::sort(id.begin(), id.end(), [&] (int i, int j) { return r[i] < r[j]; });
    int nowr = 0;
    for (auto i : id) {
      if (l[i] > nowr) sr.emplace_back(r[i]), nowr = r[i];
    }
  }
  assert(sl.size() == sr.size());
  std::vector<std::pair<int, int>> seg;
  for (int i = 0; i < sl.size(); ++i) seg.emplace_back(sl[i], sr[i]);
  return seg;
}

void solve(int v, int cnt) {
  int len = 0;
  { // 倍增找最长前缀
    int k = 0;
    for (int b = 1; b <= std::__lg(m); ++b) {
      if (calc(list.getid(1 << b)) <= cnt) k = b;
      else break;
    }
    int L = (1 << k), R = (1 << (k + 1)), res = L;
    while (L + 1 < R) {
      int mid = (L + R) >> 1;
      if (calc(list.getid(mid)) <= cnt) L = res = mid;
      else R = mid;
    }
    len = res;
  }
  auto vid = list.getid(len);
  for (auto i : vid) del(i), bit1.upd(n - l[i] + 1, r[i]), bit2.upd(r[i], -l[i]);
  auto seg = getseg(vid);
  static int sl[kMaxN], sr[kMaxN];
  // std::cerr << "??? " << v << ' ' << cnt << ' ' << seg.size() << '\n';
  cnt = seg.size();
  for (int i = 1; i <= seg.size(); ++i) std::tie(sl[i], sr[i]) = seg[i - 1];
  sl[cnt + 1] = sr[cnt + 1] = n + 1;
  std::priority_queue<pii, std::vector<pii>, std::greater<>> q;
  std::function<void(int)> fix = [&] (int i) {
    while (true) {
      auto [rr, id] = sgt3.query(1, 1, n, 1, sl[i]);
      assert(id <= m);
      if (id && r[id] >= sr[i]) res[id] = v, del(id);
      else break;
    }
    int id1 = sgt1.query(1, 1, n, sl[i], sr[i]), id2 = sgt2.query(1, 1, n, sl[i], sr[i]);
    if (std::min(id1, id2) <= m) q.emplace(std::min(id1, id2), i);
  };
  std::function<void(int)> upd = [&] (int i) {
    if (vis[i]) return;
    int it = std::lower_bound(sr + 1, sr + 1 + cnt, l[i]) - sr;
    if (it > cnt || std::max(sl[it], l[i]) > std::min(sr[it], r[i])) return;
    del(i), vid.emplace_back(i);
    bit1.upd(n - l[i] + 1, r[i]), bit2.upd(r[i], -l[i]);
    for (int j = std::lower_bound(sr + 1, sr + 1 + cnt, r[i]) - sr; j <= cnt; ++j) {
    // for (int j = 1; j <= cnt; ++j) {
      int val = bit1.qry(n - sr[j - 1]);
      assert(val <= sr[j]);
      if (val == sr[j]) break;
      sr[j] = val;
      assert(sl[j] <= sr[j]);
      fix(j);
    }
    for (int j = std::upper_bound(sl + 1, sl + 1 + cnt, l[i]) - sl - 1; j >= 1; --j) {
    // for (int j = 1; j <= cnt; ++j) {
      int val = -bit2.qry(sl[j + 1] - 1);
      assert(val >= sl[j]);
      if (val == sl[j]) break;
      sl[j] = val;
      assert(sl[j] <= sr[j]);
      fix(j);
    }
  };
  for (int i = 1; i <= cnt; ++i) {
    while (true) {
      auto [rr, id] = sgt3.query(1, 1, n, 1, sl[i]);
      if (id && r[id] >= sr[i]) res[id] = v, del(id);
      else break;
    }
  }
  for (int i = 1; i <= cnt; ++i) fix(i);
  for (; !q.empty();) {
    auto [id, p] = q.top(); q.pop();
    upd(id), fix(p);
  }
  for (auto i : vid) res[i] = v, bit1.clear(n - l[i] + 1), bit2.clear(r[i]);
  // for (auto i : vid) std::cerr << i << '\n';
  // for (auto [l, r] : seg) std::cerr << l << ' ' << r << '\n';
  // std::cerr << "-------------\n";
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    int x;
    std::cin >> x;
    ++cnt[x];
  }
  std::vector<int> vec;
  for (int i = 1; i <= m; ++i) {
    std::cin >> l[i] >> r[i];
    vec.emplace_back(i);
  }
  for (int i = m; i; --i) sgt1.ins(1, 1, n, l[i], i), sgt2.ins(1, 1, n, r[i], i);
  std::sort(vec.begin(), vec.end(), [&] (int i, int j) { return r[i] < r[j]; });
  for (auto i : vec) sgt3.ins(1, 1, n, l[i], {-r[i], i});
  list.init(m), bit1.clear(), bit2.clear();
  std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  for (int i = n; i; --i) {
    if (!cnt[i]) continue;
    solve(i, cnt[i]);
  }
  for (int i = 1; i <= m; ++i) std::cout << res[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;
}