NPSC 2021 高中組 pD題解
題解
首先轉換題目如下:
給定序列 和 ，對於 序列，定義一個區間的分數 中前 大元素的和。求出最大分數。
可以驗證 符合 Monge condition ，那用來解決此問題的演算法就多了，於是可以先想 要怎麼很快的算出來。
最簡單的方法當然就是持久化線段樹算前 大，每次操作時間複雜度是 ，而且可以隨機存取式的隨意算cost，這樣就可以使用 SMAWK 演算法在 的時間做完，但空間需要 。所以可以考慮使用 sliding window 算 cost ，會有非常大的可能可以把空間壓到線性。
但在使用 sliding window 算 cost 的時候，只能使用轉移點單調 (Monotone Minima) 或是簡易版 LARSCH ，兩者的時間複雜度皆為 ， 為 sliding window 移動一次和算答案的時間。因為這題 ，所以我們希望 。
如果存在一個 sliding window 能用 的時間加入元素以及計算答案，那就能在 的時間內解決 問題，但此問題在 algebraic computation tree model 下有 的時間複雜度下界[1]，所以加入元素的 sliding window 大概做不到 。
既然加入元素不行，那可以改成考慮刪除。先花 的時間將 和 的元素一起由大到小排成長度為 的序列，將這個序列用 linked list 維護，因為 sliding window 在移動時 只會改變 ，所以可以做到 刪除，且刪除後新的前 大元素和也能在 維護。
轉移點單調和簡易版 LARSCH 的 sliding window 移動順序都支援使用只能刪除和回滾的 sliding window ，所以只須套用這兩個演算法其中之一就可以把此問題做到 時間 空間。
實作細節的部份，可以跟每個節點說遞迴離開的時候要把 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. ↩︎
