# [solution] 2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
[TOC]
題目網址：https://codeforces.com/gym/101982
## pI - [Inversions](https://codeforces.com/gym/101982/problem/I)
> 題目中給定的 $k$ 以下都以 $p$ 表示。
:::success
性質 1
填的數字為非嚴格遞減。
**證明**
可以透過貪心交換證明，暫時略。
:::
接著，定義逆序數對的貢獻分成三類：
1. 已填好的數字與已填好的數字
2. 已填好的數字與未知的數字
3. 未知的數字和未知的數字
:::success
性質 2
第 1 類的數字貢獻是固定的。
:::
因此我們可以直接算出第 1 類的貢獻，接下來只要考慮第 2、3 類的貢獻。
:::success
性質 3
我們可以快速得知一段區間 $[l, r]$ 中，未知的數字都設成 $x$ 時，第 2 類的貢獻是多少。
**證明**
我們有辦法快速知道
每個未知的數字放 $x$ 的貢獻，因此也可以透過前綴和知道一個區間未知的數字都設成 $x$ 是多少。
:::
:::success
性質 4
我們可以快速得知一段區間 $[l, r]$ 中，有幾個 $0$。
:::
:::success
性質 5
我們可以快速得知一段區間 $[l, r]$ 中，未知的數字都設成 $x$ 時，第 3 類的貢獻是多少。
我們只會考慮 $[l, r]$ 區間中未知數字向前的貢獻（因為向後的會被重複算到，因此不考慮）。
如果 $x = p$，則貢獻為 $0$。
否則根據性質 1，$[1, l-1]$ 中的未知數字 都比 $x$ 大。因此貢獻就是 $[1, l-1]$ 中 $0$ 的數量乘上 $[l, r]$ 中 $0$ 的數量。
:::
根據上面的性質們，我們先定義這些陣列：
> 只要是有 $pre$ 前綴的，都是指前綴和、前綴 max 等等。
- $dp[i][j]$: 前 $i$ 個 column 中最後一個未知數字放 $j$ （==並且，後面不會有未知數放 $j$==）時，最大的逆序數對數量（第 2, 3 類）
- $pre\_inv[i][j]$: 前 $i$ 個 column 如果未知數字都放 $j$，則這些數字對已經寫好的數字的貢獻（第 2 類）
- $pre\_zero[i]$: 前 $i$ 個 column 所有未知數字的數量
為了方便書寫，我們也定義這些函式
- $get\_range\_inv(l, r, j)$: 在 $[l, r]$ 的區間中的未知數字都放 $j$ 的貢獻（第 2 類）
- 定義：$pre\_inv[r][j] - pre\_inv[l-1][j]$
- $get\_range\_zero(l, r)$: 在 $[l, r]$ 的區間中的未知數字的數量
- 定義：$pre\_zero[r][j] - pre\_zero[l-1]$
:::success
性質 6 - DP 的基底
$dp$ 的基底：$dp[i][p] = pre\_inv[i][p]$
因為 $p$ 以上無法填其他數字，在 $j=p$ 的情況下，未知數字的填法是固定的，因此可以直接從 $pre\_inv[i][p]$ 得知。
:::
最後，來到最關鍵的轉移，這裡會依序考慮複雜度比較差的情況，接著優化轉移，最後優化空間複雜度。
轉移方式可以這樣思考：
1. 因為有性質 1，因此我們從大到小考慮每個要填的數值，接著從前到後。假設現在要處理 $dp[i][j]$
2. 我們每到一個新的位置 $i$（圖中的紅色區塊），會考慮一段後綴 $[l, r]$ 都填 $j$，並取後綴開頭的前一行取最大值做轉移
3. 取一段的人都當 $x$ 的貢獻我們分兩類考慮：
1. 第 2 類（已知對未知）：貢獻就是 $get\_range\_inv(l, r, j)$
2. 第 3 類（未知對位置）：貢獻就是 $get\_range\_zero(1, l-1) \times get\_range\_zero(l, r)$（by 性質 5）
這個藍色的區塊的最大值，我們也用一個陣列紀錄：
- $pre\_max\_dp[i][j]$: $\max\limits_{k=j}^p dp[k]$。
把上面的轉移寫成式子，可知：
$$
\begin{aligned}
dp[i][j]
&= \max_{k=0}^{i-1} (pre\_max\_dp[k][j+1] + get\_range\_inv(k+1, i, j)+ get\_range\_zero(1, k) \times get\_range\_zero(k+1, i))\\
\end{aligned}
$$
這樣，我們就得到了一個 $O(nk \times n)$ 的演算法了。
---
下一步我們會將轉移式簡化，並觀察有沒有我們可以優化的地方。
$$
\begin{aligned}
dp[i][j]
&= \max_{k=0}^{i-1} (pre\_max\_dp[k][j+1] + get\_range\_inv(k+1, i, j)+ get\_range\_zero(1, k) \times get\_range\_zero(k+1, i))\\
&= \max_{k=0}^{i-1} (pre\_max\_dp[k][j+1] + (pre\_inv[i][j] - pre\_inv[k][j]) + (pre\_zero[k]-pre\_zero[0]) \times (pre\_zero[i]-pre\_zero[k]))\\
&= \max_{k=0}^{i-1} (pre\_max\_dp[k][j+1] + pre\_inv[i][j] - pre\_inv[k][j] + pre\_zero[k] \times pre\_zero[i] - pre\_zero[k]^2\\
&= pre\_inv[i][j] + \max_{k=0}^{i-1} (pre\_zero[k] \times pre\_zero[i]) + (pre\_max\_dp[k][j+1] - pre\_inv[k][j] - pre\_zero[k]^2)\\
\end{aligned}
$$
可以看到，透過一系列簡化，我們可以清楚的看到這是斜率優化的式子。
其中 $pre\_zero[k]$ 是斜率，$(pre\_max\_dp[k][j+1] - pre\_inv[k][j] - pre\_zero[k]^2)$ 是截距。
:::success
性質 7
1. 斜率（$pre\_zero[k]$）單調
2. 詢問（$i$）單調
:::
有了性質 7，我們就可以進一步使用單調隊列維護轉移點，讓轉移的複雜度從 $O(n)$ 變成 $O(1)$。
這樣，我們就得到了一個 $O(nk)$ 的演算法了。
---
最後，因為記憶體大小限制，上面許多的陣列都要使用狀態壓縮，筆者僅有 $pre\_inv$ 是使用二維陣列。
### Full Code
:::spoiler
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N = 2e5+10;
const int MAX_K = 100+10;
const int INF = 2e18;
int n, p;
vector<int> v(MAX_N);
vector<vector<int>> pre_inv(MAX_N, vector<int>(MAX_K));
vector<int> pre_zero(MAX_N);
vector<int> pre_max_dp(MAX_N);
void solve1(){
// input
cin >> n >> p;
for (int i=1 ; i<=n ; i++){
cin >> v[i];
}
// pre-process
int ans1 = 0; // 已經填好的數字之間的逆數數對貢獻
{
vector<int> _greater(MAX_K); // _greater[i][j] = v[1]~v[i] 中大於 j 的人有幾個
vector<int> _less(MAX_K); // _less[i][j] = v[i]~v[n] 中小於 j 的人有幾個
for (int i=1 ; i<=n ; i++){
for (int j=1 ; j<=p ; j++){
_greater[j] += v[i]!=0 ? j<v[i] : 0;
pre_inv[i][j] += (v[i]==0 ? _greater[j] : 0);
}
if (v[i]!=0) ans1 += _greater[v[i]];
}
for (int i=n ; i>=1 ; i--){
for (int j=1 ; j<=p ; j++){
_less[j] += v[i]!=0 ? j>v[i] : 0;
pre_inv[i][j] += (v[i]==0 ? _less[j] : 0);
}
}
for (int i=1 ; i<=n ; i++){
pre_zero[i] = pre_zero[i-1]+(v[i]==0);
for (int j=1 ; j<=p ; j++){
pre_inv[i][j] += pre_inv[i-1][j];
}
}
}
// process
// ax+b = 要插入的直線，cx+d = 最後一條直線，ex+f 倒數第二條直線
auto check = [](int a, int b, int c, int d, int e, int f){
return (int)(b-d)*(a-e) >= (int)(b-f)*(a-c);
};
{
vector<int> dp(MAX_N);
for (int i=1 ; i<=n ; i++){
if (v[i]!=0){
dp[i] = dp[i-1];
pre_max_dp[i] = max(pre_max_dp[i], dp[i]);
continue;
}else{
dp[i] = pre_inv[i][p];
pre_max_dp[i] = max(pre_max_dp[i], dp[i]);
}
}
}
for (int j=p-1 ; j>=1 ; j--){
vector<int> dp(MAX_N);
deque<pair<int, int>> dq; // 維護線段 (a, b) 代表 ax+b 的線段，其中 a 為嚴格遞增，b 為嚴格遞減
dq.push_back({0, 0});
for (int i=1 ; i<=n ; i++){
if (v[i]!=0){
dp[i] = dp[i-1];
pre_max_dp[i] = max(pre_max_dp[i], dp[i]);
continue;
}
int x = pre_zero[i];
// 刪掉過期的線段
while (dq.size()>=2 && dq[0].first*x+dq[0].second <= dq[1].first*x+dq[1].second){
dq.pop_front();
}
int ma = dq[0].first * x + dq[0].second;
dp[i] = pre_inv[i][j] + ma;
// 插入線段
int new_a = pre_zero[i];
int new_b = pre_max_dp[i] - pre_inv[i][j] - pre_zero[i]*pre_zero[i];
while (dq.size()>=2 && check(new_a, new_b, dq.back().first, dq.back().second, dq[dq.size()-2].first, dq[dq.size()-2].second)){
dq.pop_back();
}
dq.push_back({new_a, new_b});
// 更新最大值
pre_max_dp[i] = max(pre_max_dp[i], dp[i]);
}
}
int ans2 = 0;
ans2 = *max_element(pre_max_dp.begin(), pre_max_dp.end());
// output
cout << ans1+ans2 << "\n";
return;
}
signed main(){
cin.tie(0), ios::sync_with_stdio(0);
int t = 1;
while (t--){
solve1();
}
return 0;
}
```
:::
{%hackmd @temmie950807/r1KCzgjFh %}
{%hackmd @temmie950807/Prove_Style %}
Sign in with Wallet
Connect another wallet