烤柿題，簡單
zelensky 和 haochangjian 的

1.

AT_abc237_g [ABC237G] Range Sort Query

經典 trick ，考慮我們不關心其他數的位置

所以把 > x 的賦成 1，否則為 0

這樣之后排序就變成區間覆蓋

以及需要維護 0 的個數

線段樹簡單做，不要想根號

2.

AT_agc038_f [AGC038F] Two Permutations

題意轉化很簡單

每個置換環要么不動，要么一起動

將其縮點后，貢獻變成類似兩個環同時選可以獲得 ... 貢獻

顯然網絡流

然后這個很像文理分科，但不一樣，為了處理不同環的貢獻，不要想拆點

然后這個其實是可以直接連的

我懶得寫了

我們發現情況分為 5 種：

• \(P_i=Q_i?=i\)，此時必然 \(A_i?=B_i\)?。
• \(P_i?=i,Q_i!=i\)，當且僅當 \(q_i\)? 被拆分時 \(A_i?=B_i\)?。
• \(P_i?!=i,Q_i?=i\)，當且僅當 \(p_i\)? 被拆分時 \(A_i=B_i\)?。
• \(P_i?!=Q_i?,P_i?!=i,Q_i?!=i\)，當且僅當 \(p_i?\) 和 \(q_i?\) 都被拆分時 \(A_i?=B_i\)?。
• \(P_i?=Q_i?!=i\)，當且僅當 \(p_i\)? 和 \(q_i\)? 都被拆分或都不被拆分時 \(A_i?=B_i?\)。

我們設 \(p_i\)? 被拆分時在 \(S\) 集合中，\(q_i\)? 被拆分時在 \(T\) 集合中，建出最小割模型。

• \(P_i?=Q_i?=i\)，必定耗費 \(1\) 代價。
• \(P_i?=i,Q_i?!=i，q_i\)? 在 \(T\) 集合中耗費 \(1\) 代價，\(S\) 向 \(q_i\)? 連邊權為 \(1\) 的邊。
• \(P_i?!=i,Q_i?=i，p_i\)? 在 \(S\) 集合中耗費 \(1\) 代價，\(p_i?\) 向 \(T\) 連邊權為 \(1\) 的邊。
• \(P_i?!=Q_i?,P_i?!=i,Q_i?!=i，p_i\)? 在 \(S\) 且 \(q_i?\) 在 \(T\) 耗費 \(1\) 代價，\(p_i\)? 向 \(q_i\)? 連邊權為 \(1\) 的邊。
• \(P_i?=Q_i?!=i，p_i\)? 和 \(q_i\)? 在不同集合耗費 \(1\) 代價，\(p_i\)? 和 \(q_i?\) 互連邊權為 \(1\) 的邊。

然后跑最小割即可。

由于是二分圖單位邊權，時間復雜度 \(O(n \sqrt{n}?)\)。

3.

AT_abc305_g [ABC305G] Banned Substrings

一眼板紙

字符串長度很小，暴搜或 AC 自動機都行

然后寫出 dp 矩陣優化即可

4.

AT_abc282_h [ABC282Ex] Min + Sum

柿子中有 min

考慮序列分治

然后板紙沒了

剛開始覺得一個 log ，是雙指針套雙指針，但寫著寫著發現不單調

沒事，用個 lower_bound 就行了

兩個log ， 但第二個 log 跟現在處理的長度有關，超級小