###### tags: `OI`
# 111-2 延平中學校內賽題解
以下題解如果有問題，歡迎找出題者討論：
* E-mail: dave910602@gmail.com
* Facebook: 郭軒語（Dave Kuo）
* Discord: HNO2#4672
特別感謝 SorahISA 幫忙驗題。
## pA. 取餘數
### Subtask 1
直接讀入三個數字後，判斷 $a_0 \bmod a_1 = a_2$ 是否成立即可。需要特別判掉 $a_1 = 0$。
### Subtask 2
用三層迴圈枚舉 $i,j,k$，分別檢查是否有 $a_i \bmod a_j = a_k$ 即可。
:::spoiler AC code
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int &i : a)
cin >> i;
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
if (a[j] != 0 && a[i] % a[j] == a[k])
ans++;
cout << ans << '\n';
}
```
:::
## pB. 上課座位
### Subtask 1
使用二維陣列讀進整個座位表 (可以用 `char[*][*]` 或 `vector<string>` 等等)，假設讀進去的陣列是 `seats`。
之後對於每個 `seats[i][j] == '0'` 的位置去看 `seats[i-1][j] == '0'`, `seats[i+1][j] == '0'`, `seats[i][j-1] == '0'`, `seats[i][j+1] == '0'` 是否都成立。
這裡提供一個實作時的技巧：可以把要判斷的方向都存成一個向量 array (也就是類似 `dx[4]={0,0,1,-1}; dy[4]={1,-1,0,0}` 這樣)，之後用一個 for loop 判斷所有方向。
### Subtask 2
和上一個 Subtask 類似，只是需要加上判斷每個方向是否有可能超出二微陣列範圍。
:::spoiler AC code
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> seats(n);
for (auto &i : seats)
cin >> i;
vector<int> dx = {0, 0, 1, -1};
vector<int> dy = {1, -1, 0, 0};
auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (seats[i][j] == '1')
continue;
bool ok = 1;
for (int k = 0; k < 4; k++) {
if (valid(i + dx[k], j + dy[k]) && seats[i + dx[k]][j + dy[k]] == '1')
ok = 0;
}
if (ok)
ans++;
}
cout << ans << '\n';
}
```
:::
## pC. 序列價值
### Subtask 1
枚舉所有可能的區間 $[l,r]$，之後檢查是否區間內的數字都一樣，然後找出裡面最大的。檢查區間內是否數字都一樣，可以看是否存在相鄰數字不一樣。
### Subtask 2
和上一個 subtask 類似，只是在枚舉 $r$ 的時候可以順便看相鄰數字是否都一樣。類似這樣：
```cpp=
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (j > i + 1 && a[j] != a[j - 1])
break;
// do something
}
}
```
### Subtask 3
可以注意到一件事：當所有數字都非負時，固定右界時左界一定是取一直往左延伸的最大區間一定最好。所以我們可以由左到右枚舉每個數字，並且同時計算 $cur,cnt$ 兩個變數，代表目前右界的值以及連續出現了幾次。當要從 $i$ 變到 $i+1$ 時，如果 $cur$ 和 $a_{i+1}$ 相同就把 $cnt$ 加 $1$，否則就把 $cnt$ reset 為 $1$。之後再更新 $cur$。
### Subtask 4
當至少有一個非負整數時和 Subtask 3 一樣，但是當全部數字都是非負時要輸出最大的負數。
:::spoiler AC code
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int &i : a)
cin >> i;
long long ans = a[0], last = 0, cnt = 0;
for (int i : a) {
if (i == last)
cnt++;
else
last = i, cnt = 1;
ans = max(ans, last * cnt);
}
cout << ans << '\n';
}
```
:::
## pD. 切棍子問題
### Subtask 1
直接照題意模擬即可。具體實作方法是用一個 array 紀錄每個切點有沒有被切過，詢問時從那個詢問點開始往左往右找。
### Subtask 2
所有詢問都在所有裁切的操作之後，所以我們可以先求出每一段棍子長度是多少。要求出每一段是多少的話，可以由左而右掃過每個切點，前後兩個切點之間長度就是兩者之差，把這個差 assign 給兩切點之間中間的所有詢問點。(雖然每一段長度都不一樣，但是加起來是 $n$ 所以可以放心開一個迴圈直接改。) 之後每筆詢問就可以 $O(1)$ 回答。
### Subtask 3
我們用一個 `std::set` 紀錄所有的切點，一開始這個 set 只有 $\{0,n\}$。之後當遇到一個 query = 1 時，把這個切點放入 set; 當遇到一個 query = 2 時，找出這個 set 裡第一個比 $x$ 大的點，他和前一個的差就是答案。
實作上需要注意「找出這個 set 裡第一個比 $x$ 大的點」這個操作，對應到 STL set 操作就是 `s.lower_bound(x)`, 他個前一個 iterator 可以用 `prev(it)` 找到。注意不能寫 `lower_bound(s.begin(), s.end(), x)`，因為 set 沒有 random access 的功能，所以這個操作實際上是 $O(n \log n)$。
這題也有別種做法，例如說使用 DSU + 時光倒流可以做到 $\mathcal{O}(q \alpha(n))$，或者是使用區間資料結構直接找到每個詢問點左邊和右邊的切點，都是很經典的作法。
:::spoiler AC code
```cpp=
#include <iostream>
#include <set>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
set<int> s = {0, n};
while (q--) {
int type, x;
cin >> type >> x;
if (type == 1) {
s.insert(x);
} else {
auto nearest = s.lower_bound(x);
auto prev_nearest = prev(nearest);
cout << (*nearest) - (*prev_nearest) << '\n';
}
}
}
```
:::
## pE. 裝飾組裝
### Subtask 1
因為 $n$ 很小，所以可以嘗試所有可能的組裝方式：$n=1,2$ 有一種，$n=3$ 有三種。找出所有裡面最小的即可。
### Subtask 2
有一個直觀的想法是，把所有東西切成均勻大小的兩半，之後兩半都合併完成以後再將兩邊合併。
先講結論：這個作法是對的，正確性證明可以在 subtask 4 得到。所以我們可以用一個遞迴函式去 `f(x)` 去計算當有 $x$ 個裝飾品的最小費用。時間複雜度是 $O(n \log n)$。
### Subtask 3
和 Subtask 4 作法一樣，只是 Subtask 4 需要用到 Heap，這個 subtask 就是給不會用或不知道 Heap 的。
### Subtask 4
和經典問題 [Add all](https://zerojudge.tw/ShowProblem?problemid=d221) 的做法很像，維護一個 min heap (也就是 `std::priority_queue`)。把所有重量放進 heap，每次拿重量最小的兩個合併起來，只是合併的代價變成 $2(x+y)$。
這個做法為什麼是對的呢？Add all 的原型是 [Huffman code](https://en.wikipedia.org/wiki/Huffman_coding)，證明也和他很像。簡單來說就是合併的過程可以看做一棵二元樹，然後要證明以下兩件事：
1. 在固定 tree structure 的情形下，最佳解一定會有兩個重量最小的 code 是最深的相鄰的節點。
2. 當把這兩個點合併起來以後，剩下 $n-1$ 個點繼續遞迴下去做得到的結果一定最優。
1 可以使用排序不等式等方式證明，2 可以使用反證法證明，如果有興趣可以自行查閱詳細證明 ([資訊之芽 Greedy 那一篇](https://www.csie.ntu.edu.tw/~sprout/algo2023/ppt_pdf/week05/greedy.pdf)就講得不錯，可以從第 23 頁開始看。)
:::spoiler AC code
```cpp=
#include <iostream>
#include <queue>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
priority_queue<ll, vector<ll>, greater<>> pq;
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
pq.push(x);
}
while (pq.size() > 1) {
ll x = pq.top();
pq.pop();
ll y = pq.top();
pq.pop();
pq.push((x + y) * 2);
}
cout << pq.top() << '\n';
}
```
:::
## pF. 費氏數列問題
### Subtask 1
因為範圍很小，$1^i, 2^i, 3^i, F_i$ 都可以直接寫在 code 裡面，就可以直接計算。
### Subtask 2
這個 subtask 主要的任務在計算 $a^i, b^{n-i}$ 和 $F_i$。$a^i$ 可以直接用一個陣列計算，大概類似這樣：
```cpp=
A[0] = 1;
for (int i = 1; i <= n; i++)
A[i] = A[i - 1] * a % MOD;
```
$F_i$ 可以使用簡單的 DP 算出來。小心 mod 運算不要 overflow！
### Subtask 3
從這個 subtask 開始需要考慮矩陣。考慮以下矩陣：
$M = \begin{bmatrix}
1 & 1 & 0 \\[0.3em]
0 & 1 & 1 \\[0.3em]
0 & 1 & 0
\end{bmatrix}$
$b_i = \begin{bmatrix}
sum_i \\[0.3em]
F_{i+1} \\[0.3em]
F_{i}
\end{bmatrix}$
其中 $sum_i = F_0 + \cdots + F_i$。則可以發現 $b_i = Mb_{i-1}$，因此 $b_n$ = $M^n b_0$。由於矩陣乘法有結合律，因此 $M^n$ 可以先算，而這一項可以使用快速冪的方法算出來。[這裡](https://hackmd.io/@fdhscpp110/matix_fast_pow)有這個技巧的詳細說明。
### Subtask 4
和上一個 Subtask 很像，只是矩陣變成
$M = \begin{bmatrix}
1 & 1 & 0 \\[0.3em]
0 & a & a^2 \\[0.3em]
0 & 1 & 0
\end{bmatrix}$
$b_i = \begin{bmatrix}
sum_i \\[0.3em]
a^{i+1}F_{i+1} \\[0.3em]
a^iF_{i}
\end{bmatrix}$
$sum_i = a^0F_0 + \cdots + a^iF_i$
### Subtask 5
和 Subtask 3,4 很像，可以注意到一件事：把整條式子整理一下以後就能得到 $b^n(\sum_{i=1}^n (ab^{-1})^i F_i)$。裡面那一項和 Subtask 4 一樣的做法，之後再乘上 $b^n$ 就是答案。
有一個小問題是 $b^{-1}$ 在 mod 底下代表的意義是什麼。事實上有個東西稱為模反元素 (或模逆元)，就是在 mod 底下滿足 $x^{-1} \cdot x \bmod 10^9+7 = 1$ 的 $x^{-1}$。而因為 $10^9+7$ 是質數，根據費馬小定理這個數字就是 $b^{(10^9+7)-2} \bmod 10^9+7$。
:::spoiler 有關這題的 fun fact
這題在比賽前 8 個小時被檢查到官解是錯的。幸好我有自己再檢查...
:::
:::spoiler AC code
```cpp=
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
constexpr ll MOD = 1'000'000'007;
struct matrix {
ll A[3][3];
void set_empty() { memset(A, 0, sizeof A); }
void set_identity() {
set_empty();
A[0][0] = A[1][1] = A[2][2] = 1;
}
matrix operator*(const matrix &rhs) const {
matrix ret;
ret.set_empty();
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++) {
ret.A[i][j] = (ret.A[i][j] + A[i][k] * rhs.A[k][j]) % MOD;
}
return ret;
}
} m;
ll pow_num(ll x, ll y) {
ll ret = 1;
while (y) {
if (y & 1)
ret = ret * x % MOD;
y >>= 1;
x = x * x % MOD;
}
return ret;
}
matrix pow_matrix(matrix x, ll y) {
matrix ret;
ret.set_identity();
while (y) {
if (y & 1)
ret = ret * x;
x = x * x;
y >>= 1;
}
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll a, b, n;
cin >> a >> b >> n;
ll f = a * pow_num(b, MOD - 2) % MOD;
ll f2 = f * f % MOD;
matrix m;
m.A[0][0] = 1, m.A[0][1] = 1, m.A[0][2] = 0;
m.A[1][0] = 0, m.A[1][1] = f, m.A[1][2] = f2;
m.A[2][0] = 0, m.A[2][1] = 1, m.A[2][2] = 0;
matrix m_pow = pow_matrix(m, n);
ll ans = m_pow.A[0][1] * f % MOD;
cout << ans * pow_num(b, n) % MOD << '\n';
}
```
:::
## pG. 寶石城
在這題中，我們用圖論的術語：每個小鎮是一個節點，而每座橋是一條邊。
### Subtask 1
在 Subtask 1~3 中，因為樹的結構是一條長鍊，所以可以直接把他當作序列處理。在這個 Subtask 只需要依題意列舉所有 $[l,r]$ 之間的所有長度是 $1$ 或 $2$ 的子序列即可。注意 $l>r$ 的情形！
### Subtask 2
當所有詢問長度是 $1$ 時，相當於詢問一個序列中每個區間裡面有多少同樣的字元。這個可以使用前綴和的技巧做到。
### Subtask 3
我們需要支援一個字串的一個區間有多少個子序列可以是 $qs_i$。最簡單的方法一樣是建立前綴和：對於每個長度是 $1$ 和 $2$ 的字串計算每個前綴有多少個這個字串。具體算長度是 $2$ 的前綴的方法：假設要算 $[1,r]$ 出現了幾次 `ac`，其實他就是 $[1,r-1]$ 出現了幾次 `ac` 再加上$[1,r-1]$ 出現了幾次 `a` (如果 $s_r$ 是 `c`)。
長度是 $1$ 的很簡單，長度是 $2$ 的話，假設我們要計算 `s = ac` 在 $[l,r]$ 出現了幾次，那運用前綴和就是 `ac` 在 $[1,r]$ 出現了幾次，扣掉在 $[1,l-1]$ 出現了幾次 `ac`，以及扣掉 $[1,l-1]$ 出現 `a` 的次數乘以 $[l,r]$ 出現的 `c` 的次數。
### Subtask 4
接下來的測資都是在樹上進行。Subtask 4 & 5 的話因為 $n,q$ 很小，可以每筆在 $O(n)$ 時間內算出。這筆只需要用 DFS 求出 $u_i$ 到 $v_i$ 的路徑，之後算出有幾個字元是 $qs_i[0]$。
### Subtask 5
和 Subtask 4 類似，只是要在 $O(n)$ 時間內算一條路徑上有多少個子字串是 $qs_i$。可以用前面 Subtask 3 算前綴和的方法求出。
### Subtask 6
這個 Subtask 相當於以下問題：給你一棵樹，其中有些節點已經塗黑，請求出一條路徑上有多少個染色點。這個問題其中一個最經典的做法就是倍增：對於每個節點 $i$，我們求出他到 $2^j, j = 0,\cdots,\log n$ 層祖先有多少個染黑點，之後用類似求 LCA 的方法算出答案，只是我們在算 LCA 的同時要同時算有多少個黑點。[這裡](https://yuihuang.com/lowest-common-ancestor/)有一個很完整的倍增法求 LCA 的說明。
### Subtask 7
和 Subtask 6 一樣用倍增法，只是要維護的東西變多很多。可以看 AC code 取得更完整的細節理解。
:::spoiler AC code
```cpp=
#include <iostream>
#include <vector>
using namespace std;
constexpr int MAXN = 300'007, LOG_MAXN = 21;
vector<int> G[MAXN];
string str;
int depth[MAXN];
int par[MAXN][LOG_MAXN], s[MAXN][LOG_MAXN][3];
long long d[MAXN][LOG_MAXN][9];
void dfs(int now, int p) {
par[now][0] = p;
for (int i : G[now]) {
if (i == p)
continue;
depth[i] = depth[now] + 1;
dfs(i, now);
}
}
int solve_single(int u, int v, string query) {
if (depth[u] < depth[v])
swap(u, v);
int target = query[0] - 'a';
int cntu = 0, cntv = 0;
for (int i = 20; i >= 0; i--) {
if ((depth[u] - depth[v]) >> i & 1) {
cntu += s[u][i][target];
u = par[u][i];
}
}
if (u == v)
return cntu + s[u][0][target];
for (int i = 20; i >= 0; i--) {
if (par[u][i] != par[v][i]) {
cntu += s[u][i][target];
cntv += s[v][i][target];
u = par[u][i];
v = par[v][i];
}
}
return cntu + cntv + s[u][1][target] + s[v][0][target];
}
long long solve_double(int u, int v, string query) {
if (depth[u] < depth[v]) {
swap(u, v);
swap(query[0], query[1]);
}
int target1 = query[0] - 'a', target2 = query[1] - 'a';
int u_s1 = target1, u_s2 = target2, u_d = target1 * 3 + target2;
int v_s1 = target2, v_s2 = target1, v_d = target2 * 3 + target1;
long long cntu_s = 0, cntu_d = 0, cntv_s = 0, cntv_d = 0;
for (int i = 20; i >= 0; i--) {
if ((depth[u] - depth[v]) >> i & 1) {
cntu_d += d[u][i][u_d] + cntu_s * s[u][i][u_s2];
cntu_s += s[u][i][u_s1];
u = par[u][i];
}
}
if (u == v) {
return cntu_d + cntu_s * s[v][0][v_s1];
}
for (int i = 20; i >= 0; i--) {
if (par[u][i] != par[v][i]) {
cntu_d += d[u][i][u_d] + cntu_s * s[u][i][u_s2];
cntu_s += s[u][i][u_s1];
u = par[u][i];
cntv_d += d[v][i][v_d] + cntv_s * s[v][i][v_s2];
cntv_s += s[v][i][v_s1];
v = par[v][i];
}
}
cntu_d += d[u][1][u_d] + cntu_s * s[u][1][u_s2];
cntu_s += s[u][1][u_s1];
cntv_d += d[v][0][v_d] + cntv_s * s[v][0][v_s2];
cntv_s += s[v][0][v_s1];
return cntu_d + cntv_d + cntu_s * cntv_s;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
cin >> str;
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, -1);
for (int i = 1; i <= n; i++)
s[i][0][str[i - 1] - 'a'] = 1;
for (int level = 1; level <= 20; level++)
for (int i = 1; i <= n; i++) {
int prev_par = par[i][level - 1];
if (prev_par == -1) {
par[i][level] = -1;
for (int k = 0; k < 3; k++)
s[i][level][k] = s[i][level - 1][k];
for (int k = 0; k < 9; k++)
d[i][level][k] = d[i][level - 1][k];
} else {
par[i][level] = par[prev_par][level - 1];
for (int k = 0; k < 3; k++)
s[i][level][k] = s[i][level - 1][k] + s[prev_par][level - 1][k];
for (int k = 0; k < 9; k++) {
d[i][level][k] = d[i][level - 1][k] + d[prev_par][level - 1][k];
int first_char = k / 3, last_char = k % 3;
d[i][level][k] +=
s[i][level - 1][first_char] * s[prev_par][level - 1][last_char];
}
}
}
while (q--) {
int u, v;
string query;
cin >> u >> v >> query;
if (query.length() == 1) {
cout << solve_single(u, v, query) << '\n';
} else {
cout << solve_double(u, v, query) << '\n';
}
}
}
```
:::
## pH. 大樓拆除
這題原題是 2022-2023 Winter Petrozavodsk Camp, Day 4: KAIST+KOI Contest 的 pD: Building Bombing。([Link](https://codeforces.com/gym/104345/problem/D)，有稍微簡化)
### Subtask 1
注意到第一棟樓一定不會被拆掉，所以最後留下的一定只有第一棟樓。因此第二棟以後嚴格比他高的都要拆掉。
### Subtask 2
第一棟被看到樓一定是最左邊的，那第二棟被看到的會是哪一棟呢？我們可以枚舉所有可能的第二棟樓 $i$ (要比 $h_1$ 高)，之後算出 ($[2,i-1]$ 裡比第一棟高的) + ($[i+1,n]$ 裡比第二棟高的) 最小值。前面那一項就是一個前綴和，後面那一項可以使用一個 BIT 或線段樹算出來。
### Subtask 3
考慮 DP。令 $dp[i][j]$ 代表一共累積了 $j$ 棟樓，而第 $j$ 高被看到的樓是 $i$ 時最少需要拆幾棟樓。我們有以下 DP 轉移：
$dp[i][j] = \min_{l > i, h_l > h_i} dp[l][j-1] + sum(i+1,l-1,h_i)$
其中 $sum(l,r,x)$ 代表區間 $[l,r]$ 中有多少 $h_i$ 大於 $x$。初始值是 $dp[i][1] = sum(i+1,n,h_i)$，答案就是 $dp[1][k]$。
### Subtask 4
和 Subtask 3 做法很像，只是如果直接依照上面 DP 式做是 $O(n^3k)$，但是可以發現 $sum(\cdot,\cdot,\cdot)$ 可以用前綴和表示，因此時間複雜度就可以降到 $O(n^2k)$。
### Subtask 5
同樣是 Subtask 3 的轉移式，只是用線段樹加速轉移。
這裡特別說明一下怎麼用線段樹加速轉移。我們的運算順序是從 $dp[\cdot][j]$ 轉到 $dp[\cdot][j+1]$，轉移的順序是 $h_i$ 由大到小。線段樹支援區間加值和區間詢問最小值，一開始時每一格的值是 $dp[i][j-1] + INF$，$INF$ 是一個充分大的常數。當要轉移 $dp[i][j]$ 時，我們假設 $h_l > h_i$ 的 $dp[l][j]$ 都已經算過。我們做以下事情：
* $dp[i][j]$ 設為 (線段樹中 $[i+1,n]$ 中最小值) + ($[i+1,n]$ 中比 $h_i$ 大的有幾個)
* 線段樹中第 $i$ 個位置減 $INF$
* 線段樹中 $[1,i-1]$ 加 $-1$
這個的正確性不太好理解，大概描述一下：設置 $INF$ 的目的在於從正確的地方轉移，不要從 $h_l < h_i$ 的地方轉移。至於那個 $-1$ 的部分，可以想成兩個前綴相減，當從 $dp[l][j-1]$ 轉到 $dp[i][j]$ 時，我其實就是 $sum(i+1,n,h_i)$ 減 $sum(l+1,n,h_i)$，而那個減 $sum(l+1,n,h_i)$ 就是 $-1$ 的部分。
:::spoiler AC code
```cpp=
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
constexpr int MAXN = 1e5 + 7;
constexpr int INF = 1e9;
struct segtree {
int mn[MAXN << 2], tag[MAXN << 2];
void init(int n) {
for (int i = 0; i <= 4 * n; i++)
mn[i] = tag[i] = 0;
}
void push(int now) {
mn[now << 1] += tag[now];
tag[now << 1] += tag[now];
mn[now << 1 | 1] += tag[now];
tag[now << 1 | 1] += tag[now];
tag[now] = 0;
}
void pull(int now) { mn[now] = min(mn[now << 1], mn[now << 1 | 1]); }
void modify(int now, int l, int r, int ql, int qr, int x) {
if (ql > qr)
return;
if (l >= ql && r <= qr) {
mn[now] += x;
tag[now] += x;
return;
}
int m = (l + r) >> 1;
push(now);
if (ql <= m)
modify(now << 1, l, m, ql, qr, x);
if (qr > m)
modify(now << 1 | 1, m + 1, r, ql, qr, x);
pull(now);
}
int query(int now, int l, int r, int ql, int qr) {
if (ql > qr)
return INF;
if (l >= ql && r <= qr) {
return mn[now];
}
int m = (l + r) >> 1;
push(now);
if (qr <= m)
return query(now << 1, l, m, ql, qr);
else if (ql > m)
return query(now << 1 | 1, m + 1, r, ql, qr);
else
return min(query(now << 1, l, m, ql, qr),
query(now << 1 | 1, m + 1, r, ql, qr));
}
} tree;
struct bit {
int bit[MAXN], n;
void init(int n_) {
n = n_;
for (int i = 0; i <= n; i++)
bit[i] = 0;
}
void add(int x, int dd) {
for (int i = x; i <= n; i += (i & (-i)))
bit[i] += dd;
}
int query(int x) {
int ret = 0;
for (int i = x; i > 0; i -= (i & (-i)))
ret += bit[i];
return ret;
}
} b;
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n + 2);
for (int i = 1; i <= n; i++)
cin >> a[i];
a[n + 1] = INF + 1;
vector<pair<int, int>> ord;
for (int i = 1; i <= n + 1; i++) {
ord.push_back(make_pair(a[i], -i));
}
sort(ord.begin(), ord.end());
reverse(ord.begin(), ord.end());
vector<int> dp(n + 2, INF);
dp[n + 1] = 0;
for (int _ = 1; _ <= k; _++) {
tree.init(n + 1);
b.init(n + 1);
for (int i = 1; i <= n + 1; i++)
tree.modify(1, 1, n + 1, i, i, dp[i] + INF);
vector<int> newdp(n + 2, INF);
for (auto [val, pos] : ord) {
pos = -pos;
int base_val = b.query(n + 1) - b.query(pos);
newdp[pos] =
min(newdp[pos], base_val + tree.query(1, 1, n + 1, pos + 1, n + 1));
tree.modify(1, 1, n + 1, pos, pos, -INF);
tree.modify(1, 1, n + 1, 1, pos, -1);
b.add(pos, 1);
}
swap(newdp, dp);
}
cout << (dp[1] >= INF ? -1 : dp[1]) << '\n';
}
```
:::
Sign in with Wallet
Connect another wallet