[solution] 2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

• [solution] 2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
  • pI - Inversions
    • Full Code

題目網址：https://codeforces.com/gym/101982

pI - Inversions

題目中給定的

$k$ 以下都以

$p$ 表示。

性質 1

填的數字為非嚴格遞減。

證明
可以透過貪心交換證明，暫時略。

接著，定義逆序數對的貢獻分成三類：

1. 已填好的數字與已填好的數字
2. 已填好的數字與未知的數字
3. 未知的數字和未知的數字

性質 2

第 1 類的數字貢獻是固定的。

因此我們可以直接算出第 1 類的貢獻，接下來只要考慮第 2、3 類的貢獻。

性質 3

我們可以快速得知一段區間

$[l,r]$ 中，未知的數字都設成

$x$ 時，第 2 類的貢獻是多少。

證明
我們有辦法快速知道
每個未知的數字放

$x$ 的貢獻，因此也可以透過前綴和知道一個區間未知的數字都設成

$x$ 是多少。

性質 4

我們可以快速得知一段區間

$[l,r]$ 中，有幾個

$0$。

性質 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\mathrm{\_}inv[i][j]$: 前
  $i$ 個 column 如果未知數字都放
  $j$，則這些數字對已經寫好的數字的貢獻（第 2 類）
• $pre\mathrm{\_}zero[i]$: 前
  $i$ 個 column 所有未知數字的數量

為了方便書寫，我們也定義這些函式

• $get\mathrm{\_}range\mathrm{\_}inv(l,r,j)$: 在
  $[l,r]$ 的區間中的未知數字都放
  $j$ 的貢獻（第 2 類）
  • 定義：
    $pre\mathrm{\_}inv[r][j]-pre\mathrm{\_}inv[l-1][j]$
• $get\mathrm{\_}range\mathrm{\_}zero(l,r)$: 在
  $[l,r]$ 的區間中的未知數字的數量
  • 定義：
    $pre\mathrm{\_}zero[r][j]-pre\mathrm{\_}zero[l-1]$

性質 6 - DP 的基底

$dp$ 的基底：

$dp[i][p]=pre\mathrm{\_}inv[i][p]$

因為

$p$ 以上無法填其他數字，在

$j=p$ 的情況下，未知數字的填法是固定的，因此可以直接從

$pre\mathrm{\_}inv[i][p]$ 得知。

最後，來到最關鍵的轉移，這裡會依序考慮複雜度比較差的情況，接著優化轉移，最後優化空間複雜度。

轉移方式可以這樣思考：

1. 因為有性質 1，因此我們從大到小考慮每個要填的數值，接著從前到後。假設現在要處理
   $dp[i][j]$
2. 我們每到一個新的位置
   $i$（圖中的紅色區塊），會考慮一段後綴
   $[l,r]$ 都填
   $j$，並取後綴開頭的前一行取最大值做轉移
3. 取一段的人都當
   $x$ 的貢獻我們分兩類考慮：
   1. 第 2 類（已知對未知）：貢獻就是
      $get\mathrm{\_}range\mathrm{\_}inv(l,r,j)$
   2. 第 3 類（未知對位置）：貢獻就是
      $get\mathrm{\_}range\mathrm{\_}zero(1,l-1)\times get\mathrm{\_}range\mathrm{\_}zero(l,r)$（by 性質 5）

這個藍色的區塊的最大值，我們也用一個陣列紀錄：

• $pre\mathrm{\_}max\mathrm{\_}dp[i][j]$:
  $\underset{k=j}{\overset{p}{max}}dp[k]$。

把上面的轉移寫成式子，可知：

$$\begin{array}{rl}dp[i][j]& =\underset{k=0}{\overset{i-1}{max}}(pre\mathrm{\_}max\mathrm{\_}dp[k][j+1]+get\mathrm{\_}range\mathrm{\_}inv(k+1,i,j)+get\mathrm{\_}range\mathrm{\_}zero(1,k)\times get\mathrm{\_}range\mathrm{\_}zero(k+1,i))\end{array}$$

這樣，我們就得到了一個

$O(nk\times n)$ 的演算法了。

---

下一步我們會將轉移式簡化，並觀察有沒有我們可以優化的地方。

$$\begin{array}{rl}dp[i][j]& =\underset{k=0}{\overset{i-1}{max}}(pre\mathrm{\_}max\mathrm{\_}dp[k][j+1]+get\mathrm{\_}range\mathrm{\_}inv(k+1,i,j)+get\mathrm{\_}range\mathrm{\_}zero(1,k)\times get\mathrm{\_}range\mathrm{\_}zero(k+1,i))\\ & =\underset{k=0}{\overset{i-1}{max}}(pre\mathrm{\_}max\mathrm{\_}dp[k][j+1]+(pre\mathrm{\_}inv[i][j]-pre\mathrm{\_}inv[k][j])+(pre\mathrm{\_}zero[k]-pre\mathrm{\_}zero[0])\times (pre\mathrm{\_}zero[i]-pre\mathrm{\_}zero[k]))\\ & =\underset{k=0}{\overset{i-1}{max}}(pre\mathrm{\_}max\mathrm{\_}dp[k][j+1]+pre\mathrm{\_}inv[i][j]-pre\mathrm{\_}inv[k][j]+pre\mathrm{\_}zero[k]\times pre\mathrm{\_}zero[i]-pre\mathrm{\_}zero[k{]}^2\\ & =pre\mathrm{\_}inv[i][j]+\underset{k=0}{\overset{i-1}{max}}(pre\mathrm{\_}zero[k]\times pre\mathrm{\_}zero[i])+(pre\mathrm{\_}max\mathrm{\_}dp[k][j+1]-pre\mathrm{\_}inv[k][j]-pre\mathrm{\_}zero[k{]}^2)\end{array}$$

可以看到，透過一系列簡化，我們可以清楚的看到這是斜率優化的式子。

其中

$pre\mathrm{\_}zero[k]$ 是斜率，

$(pre\mathrm{\_}max\mathrm{\_}dp[k][j+1]-pre\mathrm{\_}inv[k][j]-pre\mathrm{\_}zero[k{]}^2)$ 是截距。

性質 7

1. 斜率（
   $pre\mathrm{\_}zero[k]$）單調
2. 詢問（
   $i$）單調

有了性質 7，我們就可以進一步使用單調隊列維護轉移點，讓轉移的複雜度從

$O(n)$ 變成

$O(1)$。

這樣，我們就得到了一個

$O(nk)$ 的演算法了。

---

最後，因為記憶體大小限制，上面許多的陣列都要使用狀態壓縮，筆者僅有

$pre\mathrm{\_}inv$ 是使用二維陣列。

Full Code

#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;
}