NPSC 2021 高中組 pD題解

發表於 2025-12-27 更新於 2025-12-28 Disqus：

題解

首先轉換題目如下:

給定序列 $a_1,a_2,\dots,a_n$ 和 $b_1,b_2,\dots,b_k$ ，對於 $a$ 序列，定義一個區間的分數 $\text{cost}([l,r))=a_l,a_{l+1},\dots,a_{r-1},b_1,b_2,\dots,b_k$ 中前 $r-l$ 大元素的和。求出最大分數。

可以驗證 $\text{cost}$ 符合 Monge condition ，那用來解決此問題的演算法就多了，於是可以先想 $\text{cost}$ 要怎麼很快的算出來。
最簡單的方法當然就是持久化線段樹算前 $r-l$ 大，每次操作時間複雜度是 $\mathcal{O}(\log (n+k))$ ，而且可以隨機存取式的隨意算cost，這樣就可以使用 SMAWK 演算法在 $\mathcal{O}(n \log (n+k))$ 的時間做完，但空間需要 $\mathcal{O}(n \log n)$ 。所以可以考慮使用 sliding window 算 cost ，會有非常大的可能可以把空間壓到線性。
但在使用 sliding window 算 cost 的時候，只能使用轉移點單調 (Monotone Minima) 或是簡易版 LARSCH ，兩者的時間複雜度皆為 $\mathcal{O}(f \times n \log n)$ ， $f$ 為 sliding window 移動一次和算答案的時間。因為這題 $n \le 10^6$ ，所以我們希望 $f=\mathcal{O}(1)$ 。
如果存在一個 sliding window 能用 $\mathcal{O}(1)$ 的時間加入元素以及計算答案，那就能在 $\mathcal{O}(n)$ 的時間內解決 $\text{Maximum Gap}$ 問題，但此問題在 algebraic computation tree model 下有 $\Omega (n \log n)$ 的時間複雜度下界^[1]，所以加入元素的 sliding window 大概做不到 $\mathcal{O}(1)$ 。

既然加入元素不行，那可以改成考慮刪除。先花 $\mathcal{O}((n+k)\log(n+k))$ 的時間將 $a$ 和 $b$ 的元素一起由大到小排成長度為 $n+k$ 的序列，將這個序列用 linked list 維護，因為 sliding window 在移動時 $r-l$ 只會改變 $1$ ，所以可以做到 $\mathcal{O}(1)$ 刪除，且刪除後新的前 $r-l$ 大元素和也能在 $\mathcal{O}(1)$ 維護。
轉移點單調和簡易版 LARSCH 的 sliding window 移動順序都支援使用只能刪除和回滾的 sliding window ，所以只須套用這兩個演算法其中之一就可以把此問題做到 $\mathcal{O}((n+k) \log (n+k))$ 時間 $\mathcal{O}(n+k)$ 空間。

實作細節的部份，可以跟每個節點說遞迴離開的時候要把 sliding window 復原成遞迴進這個節點時的樣子，會好想以及好寫很多。

轉移點單調的實作，扣很醜輕噴

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using i64 = long long;
using namespace std;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& X) {
  for (auto& x : X) {
    is >> x;
  }
  return is;
}

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

constexpr int kN = 1'000'000;

int a[kN + kN], buf[kN + kN], pr[kN + kN], nx[kN + kN];

array<int, 4> op[kN];

struct sliding {
  int l, r, p, op_sz;
  i64 sum;

  sliding() = default;
  sliding(int N, int K) : l(), r(), p(), op_sz(), sum() {
    iota(buf, buf + N + K, 0);
    sort(buf, buf + N + K, [](int i, int j) {
      return a[i] > a[j] || (a[i] == a[j] && i > j);
    });
    pr[buf[0]] = -1;
    nx[buf[N + K - 1]] = -1;
    for (int i = 1; i < N + K; i++) {
      int x = buf[i - 1], y = buf[i];
      nx[x] = y;
      pr[y] = x;
    }
    for (int i = 0; i < N; i++) {
      sum += a[buf[i]];
    }
    p = buf[N - 1];
    r = N;
  }

  void remove(int i) {
    op[op_sz++] = array{i, pr[i], nx[i], p};
    if (pair{a[i], i} > pair{a[p], p}) {
      sum -= a[i];
    }
    else {
      sum -= a[p];
      p = pr[p];
    }
    if (pr[i] != -1) {
      int x = pr[i];
      nx[x] = nx[i];
    }
    if (nx[i] != -1) {
      int x = nx[i];
      pr[x] = pr[i];
    }
    pr[i] = nx[i] = -1;
  }

  void undo() {
    auto [i, old_pr, old_nx, old_p] = op[--op_sz];
    pr[i] = old_pr;
    nx[i] = old_nx;
    p = old_p;
    if (pr[i] != -1) {
      int x = pr[i];
      nx[x] = i;
    }
    if (nx[i] != -1) {
      int x = nx[i];
      pr[x] = i;
    }
    if (pair{a[i], i} > pair{a[p], p}) {
      sum += a[i];
    }
    else {
      sum += a[p];
    }
  }

  void pop_front() {
    remove(l++);
  }

  void pop_back() {
    remove(--r);
  }

  void push_front() {
    --l;
    undo();
  }

  void push_back() {
    r++;
    undo();
  }

  i64 get() const {
    return sum;
  }
};

inline void solve() {
  int N, K; cin >> N >> K;
  for (int i = 0; i < N + K; i++) {
    cin >> a[i];
  }
  i64 ans = -infty<i64>;
  sliding s(N, K);
  auto rec = [&](auto&& rec, int l, int r, int ql, int qr) -> void {
    if (ql == qr) {
      while (s.r > l) {
        ans = max(ans, s.get());
        s.pop_back();
      }
      while (s.r < r) {
        s.push_back();
      }
      return;
    }
    if (l + 1 == r) {
      for (int i = ql; i < min(qr + 1, l + 1); i++) {
        ans = max(ans, s.get());
        s.pop_front();
      }
      while (s.l > ql) {
        s.push_front();
      }
      return;
    }
    int m = (l + r) >> 1;
    while (s.r > m) {
      s.pop_back();
    }
    i64 best = -infty<i64>;
    int opt = -1;
    for (int i = ql; i < min(qr + 1, m); i++) {
      i64 cost = s.get();
      if (best < cost) {
        best = cost;
        opt = i;
      }
      s.pop_front();
    }
    ans = max(ans, best);
    while (s.l > ql) {
      s.push_front();
    }
    rec(rec, l, m, ql, opt);
    while (s.r < r) {
      s.push_back();
    }
    while (s.l < opt) {
      s.pop_front();
    }
    rec(rec, m, r, opt, qr);
    while (s.l > ql) {
      s.push_front();
    }
  };
  rec(rec, 0, N, 0, N - 1);
  cout << ans << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t; cin >> t; while (t--) solve();
}

一些廢話

原本我是寫簡易版 LARSCH ，需要兩個 sliding window ，想實作加寫搞了三個小時(太笨想很久才想到上面提的實作細節)，然後才發現其實可以轉移點單調。
寫這篇 blog 的時候我 hexo 的 mathjax 爛了，遂改用 katex 。
改完 katex 之後發現我的 footnote 爆了，所以就開始改改改改改，改到連 markdown 的 renderer 都換了。我花在修 blog 的時間都比我寫這題的扣的時間還要長==

Lee, D. T., and Ying-Fung Wu. “Geometric complexity of some location problems.” Algorithmica 1.1 (1986): 193-211. ↩︎