---
# System prepended metadata

title: AtCoder ABC 234 個人題解 (2022.1.8)
tags: [ABC, AtCoder題解]

---

# AtCoder ABC 234 個人題解 (2022.1.8)
###### tags: `AtCoder題解` `ABC`

https://atcoder.jp/contests/abc234
[My Submissions](https://atcoder.jp/contests/abc234/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=Cookie197)
又是被奇怪的錯誤搞爛的一場![](https://i.imgur.com/swwKwb8.png)


---

## <font color=brown>pD Prefix K-th Max</font>
用一個$PQ$維護就好。如果新數大於目前的答案就把他丟到$PQ$，再把$top$丟掉。每次的答案就是$PQ.top()$。

#### Complexity: 
$O(nlog(k))$
#### Status: 
<font color=greennn>AC</font> 41:41<font color=red>(2)</font>

---

## <font color=green>pE Arithmetic Number</font>
枚舉所有的首項和公差，如果合法就更新最佳答案。

#### Complexity: 
$O(log(x) \times$ 某個很小的常數$)$
#### Status: 
<font color=greennn>AC</font> 30:12

---

## <font color=#02c0bf>pF Reordering</font>
"a permutation of a non-empty, not necessarily contiguous subsequence of $S$"
其實這就表示$S$是什麼不重要，只需要知道字母的個數。

### 觀察
首先可以發現，只要字母的組合數不同，或個數不同，無論怎麼排列都一定會做出不一樣的字串。
當固定某個長度，要加入新字母的時候，只要長度固定，新字母數量固定，就可以做出特定不重複的字串，因此考慮$dp$。

### 狀態和轉移
令$dp(i,j)=$長度為$i$的字串總數，目前看到第$j$個字母。

假設我們有3個$a$ ($="aaa"$) 以及4個$b$等著加入（$b$不一定要用完），那就多少種新的字串？

$b=0:$ 1種
$b=1:$ 有4個空位，1個人，所以是$H_{1}^4 = C_1^4 = 4$
$b=2:$ 有4個空位，2個人，所以是$H_{2}^4 = C_2^5 = 10$
$b=3:$ $H_{3}^4$
$b=4:$ $H_{4}^4$

這也就是$dp(3,1)$ 利用「推的」轉移到$dp(3,2) ~dp(4,2) \cdots dp(7,2)$ 的過程。
可以得到$dp(i+k,j+1) ~+= dp(i,j) \times H_k^{i+1}, for ~k=0 ~to~ cnt[j+1]$。（$cnt[j]$表示存在幾個字母$j$。）
答案就是$dp(n,$"z"$)$。

#### Complexity: 
$O(26n)$狀態，$O(n)$轉移，總共$O(26n^2)$，但好像常數很小？？
#### Difficulty:
<font color=blue>中等</font> (upd:可惡他竟然才淺藍)
#### Status: 
<font color=greennn>AC</font> 57:09



---

## <font color=#C0C102>pG Divide a Sequence</font>
又是序列切切切
所以，以$dp(i,0)$表示把$i$當成新的開頭，$dp(i,1)$表示把$i$當成這一塊的結尾：答案的總和。
初始值$dp(1,0)=1$，答案就是$dp(n,1)$。

### $O(n^2)$ 做法
很容易想到一個$O(n)$轉移。
首先令$f(i,j) = max(arr[i],arr[i+1]...arr[j]) - min(arr[i],arr[i+1]...arr[j])$。
$dp(i,0) = dp(i-1,1)$，因為新的$i-1$這塊還沒關起來，要繼承$i-1$有關起來的值。

要算$dp(i,1)$，則要枚舉他這塊的開頭是誰。所以：
$dp(i,1) = dp(i-1,0) \times f(i-1,i) \\ ~~~~~~~~~~~~~+dp(i-2,0)\times f(i-2,i)\\ ~~~~~~~~~~~~~+dp(i-3,0)\times f(i-3,i) \cdots \\ ~~~~~~~~~~~~~+dp(1,0)~~~~~~\times f(1,i)$
只要從$i-1$跑個迴圈到$1$，同時記好目前的$min,max$就好了。
### $O(n)$ 做法
:::info
Upd : 2022/1/9 AM 11:00
:::
把$f(i,j)$寫回來，變回$max(i..j) - min(i..j)$。

首先我們可以觀察到，在任何時刻，$max$的序列必為非嚴格遞減，$min$的序列必為非嚴格遞增。
:::spoiler Example 1
    arr = 1 9 6 2 7 3 4
    min = 1 2 2 2 3 3 4
    max = 9 9 7 7 7 4 4
:::

假設我們加了一個新的數進來，$min$和$max$的序列會有什麼變化？
:::spoiler Example 2
    arr = 1 9 6 2 7 3 4 8
    max = 9 9 8 8 8 8 8 8
    
    arr = 1 9 6 2 7 3 4 1
    max = 9 9 7 7 7 4 4 1
:::


$max$序列（$min$也是）會有「一段後綴」被改值，而且是改成新的那個數。我們要算的$dp(i,1) =\sum_{k=1}^{i-1} (dp(k,0) \times max[k] - dp(k,0) \times min[k])$，所以可以紀錄：
<font size = "4"> <center>「$max$序列值$=x$」的$dp_0$值總和</center> </font>
我們可以開一個$stack$之類的東西，每次如果看到比自己小或等於自己的$max$就$pop$出來（因為他們的$max$都會變大），把$dp_0$值總和記下來。最後的這些人，再加上現在這個位置的$dp_0$（也就是$dp(i,0)$ ），他們的$max$都會變成$arr[i]$，所以把這個$(arr[i],dp$總和$)$的$pair$丟進$stack$。
要注意 「**所有$max$相同的那些位置，都會被融合成一項！**」

在以上的同時，我們要紀錄一個全域變數「目前$dp_0\times max$的總和」，並在$pop ,~ push~$時同時更新。

對$min$也做一樣的事，只是大小於相反。最後的$dp(i,1)$就是「目前$dp_0\times max$的總和」減掉「目前$dp_0\times min$的總和」。

:::spoiler <font color=greennn>AC code</font> 
```cpp=
#define mp make_pair
stack<pii> big,small; // <val of max/min , tot of dp[0]>
signed main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>arr[i];

    dp[1][0]=1; big.push(mp(arr[1],1)); small.push(mp(arr[1],1)); //注意這裡是1喔
    ll bigtot = 0, smalltot = 0;


    for (int i=2;i<=n;i++){
        dp[i][0] = dp[i-1][1];

        ll num = arr[i], dptot = dp[i][0];
        while(1){
            if (big.empty()) break;
            if (big.top().first<=num) {
                dptot += big.top().second;  dptot %= mod;
                bigtot -= big.top().first * big.top().second % mod;  bigtot = (bigtot + mod) % mod;
                big.pop();
            }else break;
        }
        big.push(mp(num,dptot));
        bigtot += num * dptot % mod;  bigtot %= mod;


        dptot = dp[i][0];
        while(1){
            if (small.empty()) break;
            if (small.top().first>=num) {
                dptot += small.top().second;  dptot %= mod;
                smalltot -= small.top().first * small.top().second % mod;  smalltot = (smalltot + mod) % mod;
                small.pop();
            }else break;
        }
        small.push(mp(num,dptot));
        smalltot += num * dptot;  smalltot %= mod;

        dp[i][1] = (bigtot - smalltot + mod) % mod;
    }
    cout<<dp[n][1]<<endl;
}
:::

#### Complexity: 
$O(n)$

#### Difficulty:
<font color="#C0C102">稍難</font> 
#### Status: --