實踐

ans多取合法方案的max/min結果肯定不劣。
對于操作“change x y：把a[x]修改為y”，無論是提前continue掉還是循環末尾，一定要記得令a[x]=y！！！
模數MOD特殊一定要注意！
1. 遇見小模數MOD，可能復雜度與MOD相關。
  
  有可能當n的級別很大時，ans%MOD=0。
注意代碼中012（有前綴0表示八進制數）的十進制數值是10。
字符數組不可使用==，不會報錯，但會警告，運行會得到錯誤的結果。
$a\in \Z,\lfloor a*b\rfloor≠a*\lfloor b\rfloor$。
錯誤的代碼：n=1;a[++n]=n;；結果：a[2]=1。

正確的代碼：n=1;n++;a[n]=n;。
判斷a是否為0，若a為負數，則不能用!a判斷。
spj的題目注意數據范圍可能會因為要服務spj而比正解的復雜度寬松。

思維題

分析題目的特性，再思考如何根據題目其特性高效解決題目。

遇到困難時，先分析題目的特性，再從題目的特性入手解決問題。

最優方案：貪心（當前視野，可能全局不優，復雜度一般$O(N)$或$O(N\log N)$）、動態規劃（全局視野）、網絡流（多元條件，n在300附近）。

如果兩個屬性滿足乘法關系：a*b=c，考慮根號分治思想。

如果$O(N^2)$做法很難繼續優化復雜度，考慮bitset優化常數。

實現細節多：改為進行小范圍枚舉爆搜。

引例、直覺與證明

實踐出真知，沒思路的時候研究樣例（或者自己舉例）。手動模擬方案數比較小時的情況。找字典序最小/大的方案模擬。
打表找規律，要對數據的性質敏感。
逆向思考。
- “構造一個合法序列a，序列b=calc(a)，使得序列b合法”：先構造合法序列b，反過來使得序列a合法。
找反例是個好習慣，往往可以比較精準地直到一個錯誤算法的缺陷究竟在哪里，然后加以改進。
如果決策是一個排列（或者類似的東西），$\text{exchange argument}$ 往往可以奏效，并且它的應用范圍不止于此，比如我們熟知的 $\text{Prim/Kruskal}$ 算法。
分類（不重不漏）、規范化是個好東西，有時可以同時簡化思路、證明和代碼。
多試試抽象題目，剝繭抽絲。
不變量 ($\text{invariant}$) 是個重要的工具。
注意題目的特殊條件。$e.g.$n為奇數。
別忘了數學歸納法。

一些常見的套路性直覺

括號序列問題常常會將左括號設為 $1$，右括號設為 $-1$，因此求一段區間的和為 $0$ 就說明個數相等，用前綴和解決。
三維幾何經常轉化為二維幾何，包括俯視和立面。
通過多維中每維的獨立性可以把它等價位多次一維問題，從而化簡。
有些區間[l,r]的問題可以拆成[1,l-1]與[1,r]的子問題。

《基礎算法14.構造》

技巧

技巧1.嚴格不等$\Leftrightarrow$非嚴格不等

給定一個整數序列 a1,a2,???,an。

請你求出一個遞增序列 b1<b2<???<bn，使得|a1?b1|+|a2?b2|+???+|an?bn| 最小。

嚴格不等→非嚴格不等
令$a_i $→ $a_{i}'$（$a_i':=a_i-i$），$b_i $→ $b_{i}'$（$b_i':=b_i-i$）。

此時只需求出b1'≤b2'≤...≤bn'，且|a1?b1|+|a2?b2|+???+|an?bn| =|a1'?b1'|+|a2'?b2'|+???+|an'?bn'| 。

$b_i+1==b_{i+1}\Leftrightarrow b'_i==b'_{i+1}$。
非嚴格不等→嚴格不等

令上面的-i改成+i即可。

技巧2.“變換1次”$O(N)$

有些題目是先用狀態1從起點走到某個中間點，在中間點變換1次用狀態2走到終點，求最值。

做2個預處理：狀態1從起點走到每一個點的貢獻$c_1[N]$+狀態2每一個點走到終點的貢獻$c_2[N]$。
枚舉中間點i，$ans=\max / \min \{ c_1[i]+c_2[i] \}$。

例題

https://www.luogu.com.cn/problem/CF1706C

https://www.wolai.com/fzoi_wiki/eB6CZxnr34GsbEyhdivF5c

技巧3.模k同余

有些題目要求“最終價值是k的倍數”，可以考慮對狀態模k同余這一技巧，降低狀態量。

有時環形問題也會用到模k同余。

例題

https://www.luogu.com.cn/problem/P2946

https://www.luogu.com.cn/problem/P1516

https://ac.nowcoder.com/acm/contest/42766/B

同余最短路。

技巧4.括號序列

合法括號序列包括：()、(A)、AB，其中A、B代表合法括號序列，這三種情況互相獨立又構成全集。

括號序列的處理方法和合法括號序列的充要條件：

(代表1，)代表-1，前綴和代表當前括號的權值。

合法括號序列的充要條件：任意位置的前綴和非負，并且最后一個位置的前綴和為0。

結論：n個左括號和n個右括號組成的合法括號序列的數量是Catalan數的第n項。
合法括號序列的充要條件：長度為2n，對于任意的$i\in[1,n]$，在前2i-1個括號中至少有i個(，并且序列一共有n個(。

構造任意一個合法括號序列S的方法：
1. 令$S_1=$(。
2. 對于i從2到n：
1. 把2i-2,2i-1放入候選集合。
2. 從候選集合中拿出一個數j，令$S_j$=(。
3. 令序列的剩余位置為)。
```
該方法生成的任何一個括號序列一定是合法括號序列，任何一個合法括號序列一定能通過該方法生成。但是該方法的不同操作可能生成相同的合法括號序列。當把第2.b步增加“從候選集合中刪除小于j的數”的操作時，該方法生成的括號序列與合法括號序列一一對應。
```

給定一個括號序列，求出有多少個互不相同的子串是合法括號串。（互不相同的子串：在原串中的起始位置或終止位置不同。）

為避免重復計數，考慮從左到右遍歷到當前點的括號作為終止位置與前面括號序列會增加多少新的合法括號。

對于“(”：不會增加任何新的合法括號，但是可能影響后面。

對于“)”：

如果權值x大于等于0：
```
 首先合法括號一定會增加1個（“()”或“(A)”）。

 考慮如何計算增加多少個“AB”：手動模擬發現“AB”的增加量等于前面權值為x的“)”個數。

 但是繼續手動模擬會發現權值為<x的“)”前面的括號不能計入貢獻。
```

e.g.“((())()”遍歷到第7個括號（權值為2的“)”）時，“AB”的增加量不能算上第4個括號（權值為2的“)”），因為第5個括號是權值為1<2的“)”。

  如果權值x小于0：不會增加任何新的合法括號，而且后面的前綴和要從0開始。



因此，遍歷到當前節點時，首先把當前括號加入前綴和。

  如果當前括號是權值為x的“)”，備份cnt[x+1]，然后把cnt[x+1]清0，回溯時再復原。

    如果x大于等于0，ans+=1+cnt[x]，然后cnt[x]++。

    如果x小于0，否則遞歸時前綴和從0開始。

例題

  https://www.luogu.com.cn/problem/P5658

技巧5.“缺一二也可”

形如“n個變量，變量之間有相互限制，求滿足所有限制條件的n個變量的具體值”。

看似要枚舉n個變量，實則枚舉n-1個變量即可，剩下1個變量可以由n-1個變量+限制條件推出。復雜度減小一個指數。

如果只考慮2個變量，也許比較好求。可以從2個變量出發，推及到多個變量；或者說枚舉n-2個變量，可能還需要再二分剩下2個變量之和，推出剩下2個變量。

技巧6.01序列/奇偶序列

“00/11”消除

消除后每個位置的奇偶性仍然不變。

把偶數位上的0/1取反，轉化為“01/10”消除，最終狀態為只有0或只有1。最終狀態只與初始的偶數位取反后的0和1的數量關系有關，與位置關系無關。

例題

https://codeforces.com/gym/105484/problem/B
只有一個位置是奇數，找到這個位置。

取前綴和制造可二分性，二分查找。
手寫bitset：可以預處理所有長度為b的2^b個01串的復雜信息。復雜度$O(2^b+\frac{?}{b})$。

技巧7.轉化為01序列

中位數。

可以考慮二分中位數，將原序列上小于mid的數值賦為-1，大于等于mid的賦為1。則集合內的中位數≥二分的數$\Leftrightarrow$集合的總權值≥0。
對序列進行多次變換，但是最終只詢問一個點上的數值的問題

可以考慮二分最終答案，將原序列上小于mid的數值賦為0，大于等于mid的賦為1。將序列變換的問題簡化為01序列變換的問題。如果最終的位置==1，說明二分的值≤實際的答案；否則就二分的值>實際的答案。可以簡化思路或尋找性質。
尋找復制的、出現次數的關系

把一個普通序列轉化為只含 0,1,-1 的序列。從而把上面的關系轉化為數值關系。

技巧8.利用分治轉移dp

$f[i]$：i個……的……，一般f[i]只與個數有關。

先確定一個點x（例如序列上確定一個點，二叉樹上確定根節點），然后可以將問題分成左右兩邊分治：$f[i]=calc(x)\oplus f[l]\oplus f[r]$，所以可以利用分治從f[l],f[r]（l,r<i）轉移到f[i]。
區間dp中，在[l,r]中存在一個元素可作為[l,r]的分界點。

例題

《舉一反三：算法性質：小根堆》。

技巧9.相同數值縮到一個整體

適用條件：$\sum 數值=N$，且答案只與數值及數值的個數有關。

把相同數值縮到一個整體，然后計算答案。復雜度從$O(N)$優化到$O(\sqrt N)$。

例題

A.幸運國家

https://www.wolai.com/fzoi_wiki/u8FquPD7VF4iz9LceCGB1v

技巧10.置換$p_{p_i}$

對于置換$p_{p_i}$，點i向點$p_i$連一條有向邊，易證圖上形成了多個環（包括自環）。把原問題轉化為與環長或環數有關的問題。

例題

思維題17.

https://www.wolai.com/fzoi_wiki/u8FquPD7VF4iz9LceCGB1v

技巧11.維護前驅最大值

適用條件：查詢區間[l,r]是否存在滿足條件的二元組(i,j)。（條件任意。可以是“重復的兩個數”、“兩數之和為w”……）

記錄每個位置的前驅pre[i]：該位置前面第一個與它構成滿足條件的二元組的位置。（下文中后繼的定義與前驅對應）若一個位置x會被多個位置設為前驅，為了保證單點修改權值的復雜度，只把x的后繼的前驅設為x，剩下后面的位置的前驅均設為0。

對于區間查詢[l,r]，查詢區間[l,r]所有位置的前驅最大值是否≥l。

對于單點修改權值，至多需要修改5個位置的前驅：本位置、本位置原來后面第一個與它的值相同的位置（前驅可能從0變到有，替代本位置的前驅）、本位置原來的后繼、本位置現在后面第一個與它的值相同的位置（前驅可能從有變到0，前驅被本位置替代），本位置現在的后繼。

使用線段樹維護區間前驅最大值。使用set[x]維護數值x出現的位置，進而維護每個位置的前驅。單點修改權值時先借助set求出現在的前驅，再在線段樹上單點修改區間前驅最大值。注意一個修改多個位置的前驅的小技巧。

例題

（下面這道題由于二元組的條件是“重復的兩個數”，故一個位置至多只會被1個位置設為前驅）

https://www.luogu.com.cn/problem/P5278

https://www.luogu.com.cn/problem/P6617

https://www.luogu.com.cn/problem/P8327

技巧12.移項使得獨立

適用條件：遇到權值隨距離（$depth_s-depth_p=w_p$）/時間（$time_j-time_i>c_j$）增長。

可以通過移項從而使2個變量獨立，從而變得容易處理：$depth_s=depth_p+w_p$/$time_j-c_j>time_i$。

例題

https://www.acwing.com/activity/content/problem/content/670/

技巧13.絕對值的處理

分類討論去絕對值。
轉化為幾何問題。
絕對值與最值

$|f(x)|=\max(f(x),-f(x))$。

$\sum\limits_i|f(x_i)-g(x_i)|=\sum\limits_i\max(f(x_i),g(x_i))-\sum\limits_i\min(f(x_i),g(x_i))$。

$|f(x)|+|g(y)|=\max\{f(x)+g(y),f(x)-g(y),-f(x)+g(y),-f(x)-g(y)\}$。

$\max\limits_i\{|f(x_i)|\}=\max\limits_i\{f(x_i),-f(x_i)\}$。

$\max\limits_i\{|f(x_i)|+|g(y_i)|\}=\max\limits_i\{f(x_i)+g(y_i),f(x_i)-g(y_i),-f(x_i)+g(y_i),-f(x_i)-g(y_i)\}$。

$\max\limits_i\{|f(x_i)+f(x)|+|g(y_i)+g(y)|\}=\max\{\max\limits_i\{f(x_i)+g(y_i)\}+f(x)+g(y),\max\limits_i\{f(x_i)-g(y_i)\}+f(x)-g(y),\max\limits_i\{-f(x_i)+g(y_i)\}-f(x)+g(y),\max\limits_i\{-f(x_i)-g(y_i)\}-f(x)-g(y)\}$。
序列上的絕對值求和

微元貢獻法。

設i<j，序列a已從大到小排好序，則$|a_j-a_i|=\sum\limits_{k=i}^{j-1}(a_{k+1}-a_k)$。把原式絕對值求和轉化為求每個k的$a_{k+1}-a_k$的貢獻的和，$a_{k+1}-a_k$的貢獻=滿足i≤k,j≥k+1的(i,j)的個數*$a_{k+1}-a_k$。
由$b_i|a_i-x|=
\begin{cases}
b_i(a_i-x)&a_i\ge x
\b_i(x-a_i)&a_i<x
\end{cases} $得：$\sum\limits_i b_i|a_i-x|=(\sum\limits_{a_i\ge x} b_ia_i-\sum\limits_{a_i<x} b_ia_i)+x(\sum\limits_{a_i\ge x} b_i-\sum\limits_{a_i<x} b_i)$。上式的值就是總和-2*<x的前綴和。

技巧14.取模的妙用

壓縮狀態。
若模數p很小且答案含有類似于n!，當n≥p時答案為0。
當答案要求以分數的形式輸出時，若答案的分母至多為2（如掃描線梯形的總面積）且小于p，可以先計算答案的2倍在模p意義下的值，再轉化為分數的形式。

技巧15.質數和互質

在偶數中2是唯一的質數，除2外其他的偶數都是合數（題目復雜度可能就與這點有關）。
[x,x+y-1]最多只有1個≥y的倍數。x和x+y-1不同時為≥y的倍數。

相鄰的正整數一定互質。

相鄰的奇數一定互質。
i與n互質$\Leftrightarrow$n-i與n互質$\Leftrightarrow$i與i+n互質（更相易減術）。
《數學1.1.質數》，《數學1.2.4.1.互質》。
有關質數或者互質的信息是復雜的。該信息一般只能通過上述技巧，或者驗證質數或者互質處理。

技巧16.異或

拆位。

適用條件：求異或之和。
01trie樹。

適用條件：求$a\operatorname{xor}b_i$的最值。
數位dp。

$x\operatorname{xor}y=z\Leftrightarrow x\operatorname{xor}y\operatorname{xor}z=0$：$f_{pos,l_x,l_y,l_z}$：第pos位，x,y,z最高位是否有限定，的方案數。
線性基。
根據現實意義把原問題轉化為方案數$\bmod 2$$\Rightarrow$方案數的奇偶性$\Rightarrow$組合數的奇偶性。

技巧17.區間詢問

在線

直接回答。
拆成[1,l-1]與[1,r]的子問題。

信息是否或如何做到滿足可逆性（可加減性）/信息如何求逆元（$f(l,r)=f^{-1}(1,l-1)\oplus f(1,r)$）？如何回答前綴問題[1,r]？

e.g.主席樹求區間第k小數。
線段樹拆成$O(\log N)$個區間。

信息是否或如何做到滿足結合律？

e.g.線段樹維護區間有序數列求區間小于x的最大的數。

補充：
1. 若詢問多，但序列不長：st表。
  
  信息是否或如何做到可重復性？信息是否或如何做到滿足結合律？
2. 若詢問多且序列長：
  
  對序列線性建立笛卡爾樹轉為 LCA 問題，然后轉為正負 1 RMQ，每log ?n分一段打表預處理。時間復雜度O(N)，詢問復雜度O(1)，空間復雜度O(N)。
貓樹。

是否不修改或者如何快速修改（e.g.維護的是線性基）？信息是否或如何做到滿足結合律？（如何維護插入？）信息是否或如何做到大小與區間長度無關？

離線

拆成[1,l-1]與[1,r]的子問題。

信息是否或如何做到滿足可逆性（可加減性）/信息如何求逆元（$f(l,r)=f^{-1}(1,l-1)\oplus f(1,r)$）？如何維護插入？
把問題[l,r]放到右端點r，從前到后插入元素和回答問題。

如何維護插入？如何在其中回答問題$[l,\infty)$？（可能要結合樹狀數組等）

涉及顏色段、“公共”等：可考慮：后插入的元素覆蓋之前的元素。
莫隊。

如何維護插入和刪除？

技巧18.動態查詢區間內數值的出現次數/前驅后繼

對于每一個數值開一個全局平衡樹儲存該數值出現的位置。必要時使用map對數值離散化，當且僅當訪問root[]/set[]時使用離散化之后的值。

[l,r]內無重復數字$\Leftrightarrow$[l,r]前驅（指在它之前和它的權值相同的元素的位置）最大值<l。

線段樹維護前驅最大值（葉子節點儲存它的前驅）。修改時先在全局平衡樹修改得到此時的前驅，再在線段樹葉子節點更新信息。
[l,r]內存在兩數之和為w$\Leftrightarrow$定義一個位置的前驅為這個位置前面第一個與這個位置加起來等于w的位置，若沒有則為0。特別地，當一個數被多個數設為前驅時，為方便修改，除了離該數最近的數，剩余其它數的前驅設為0（顯然這樣也是正確的）。則此時要求[l,r]前驅最大值≥l。
- 具體實現
  
  對于一次修改，只需修改以下5個位置的前驅：該位置，該位置原來后面第一個與它的值相同的位置，該位置原來后面第一個與它相加得w的位置，該位置現在后面第一個與它的值相同的位置，該位置現在后面第一個與它相加得w的位置。
  
  關于只設某數為距離其最近的與其相加得w的數的前驅，只需判斷如果一個數的前驅的位置在它前面第一個與它的值相同的位置的前面，則直接把該數的前驅設為零。
  
  例題。

技巧19.二維問題

主席樹。

要求不能修改。
樹套樹。
離線，按照某一維排序，另一維用數據結構維護。
dp中的偏序，一維用時間維護，另一維用線段樹維護。
動態查詢區間[l,r]內數值x的出現次數

開一個平衡樹儲存數值是x的位置，在數值x的平衡樹查詢位置小于等于r和小于等于l-1的大小，相減就可以了。

技巧20.劃分序列問題

特征：把序列A劃分成為若干段。

段數最少

《基礎算法5.1.3.2.最小劃分問題》。

價值最值

$f_i=\max\limits_{j=0}^{i-1}/\min\limits_{j=0}^{i-1}(f_j+\bigoplus\limits_{k=j+1}^i a_k)$。

dp轉移優化。
注意觀察有效決策點j的數量的復雜度：《動態規劃8.1.剪枝有效狀態數》：
- 若$\bigoplus$是位運算，則可能對于每個i，最多有$O(\log X)$種不同的$\bigoplus\limits_{k=j+1}^i a_k$。

技巧21.復雜度分析

上界分析

一個整數x和其他多個整數依次取gcd，最多有O(log X)個變化值。

勢能分析

根據分析需要，自行定義一個勢能函數f(s)，表示狀態為s的某一信息，它可以是元素數量，也可以是容器容量，還可以是容器容量減元素數量等等。勢能函數需要滿足是非負整數函數并且初始狀態為0。

方法一：
1. 一些操作會使勢能不變，因此在該勢能定義上這些操作是無效操作，必須剪枝避免。
2. 一些操作會使勢能增大，另一些操作會使勢能減小，因此勢能的最大值即為復雜度。
方法二：

設第i次操作的實際開銷是c_i，使狀態s_{i-1}變成s_i。若c_i+f(s_i)-f(s_{i-1})=O(T(n))，則O(T(n))是均攤復雜度的一個上界。

綜合技巧

對拍
1. 新建checker.cpp。

#include<bits/stdc++.h>
using namespace std;

const int T=1e4;

int main(void)
{
    system("g++ rand.cpp -fsanitize=undefined -fsanitize=address -O2 -o rand");
    system("g++ std.cpp -fsanitize=undefined -fsanitize=address -O2 -o std");
    system("g++ tmp.cpp -fsanitize=undefined -fsanitize=address -O2 -o tmp");
    for(int i=1;i<=T;i++)
    {
        system("./rand > test.in");
        system("./std < test.in > test.ans");
        system("./tmp < test.in > test.out");
        if(system("diff test.ans test.out"))
        {
            puts("WA");
            return -1;
        }
        else printf("AC on #%d\n",i);
    }
    return 0;
}

2. 新建`rand.cpp`。

    輸入數據代碼。

    不需要`freopen`。

    真隨機數：

random_device srd;
srand(srd());

3. 新建`std.cpp`。

    正確率100%的代碼。

    不需要`freopen`。
4. 新建`tmp.cpp`。

    要對拍的代碼。

    不需要`freopen`。
5. `g++ checker.cpp`。
6. `./a.out`。

string filePath1="file1.txt";
string filePath2="file2.txt";
if(compareFiles(filePath1,filePath2))
{
    cout<<"AC"<<endl;
}
else
{
    cout<<"WA"<<endl;
    return 1;
}

IDE編譯命令

-Wl,--stack=題目的空間限制大小（單位是Byte） -std=c++14 -O2

ulimit -s 題目的空間限制大小（單位是KB，1MB=1024KB）
g++ first.cpp
./a.out

如果顯示段錯誤之類的東西就是內存超限了。注意這東西調小了調不回來，如果要調回來需要殺死該終端再開一個新的終端。

測量時間和空間
- 時間：
  
  終端
  
  time ./a.out
  
  程序
  
  1.0*clock()/CLOCKS_PER_SEC
- 空間：
  
  終端
  - 方法一：在a.out正在運行的時候，新建一個新的終端，在新的終端中輸入top。一般第一個進程的VIRT 就是 KB 數。
  - 方法二：在a.out正在運行的時候到系統監視器的進程那一欄去查看a.out的內存。
快讀和快寫

《C++語言.3.快讀和快寫》
卡空間
- 若儲存的數值較小，則可用char（-128_{127）或`short`(-32768}32767)類型儲存數值。
隨機數

《C++語言.標準庫》
優化(a+b)%MOD

前提條件：必須保證a,b<MOD。

inline void add(LL &a,LL b)
{
    a+=b;
    if(a>=MOD) a-=MOD;
    return ;
}

取整
- 向下取整
  - p/q
  - ceil(x)
- 向上取整
  - (p+q-1)/q
  - floor(x)
- 四舍五入
  - x=round(x);
  - printf("%.0lf\n",x+EPS);//printf中的%.0lf自帶四舍五入
  注意：printf中的%.0lf自帶四舍五入（可能會有精度問題），而%d則是向下取整。
內存回收：

int idx;
//建立回收站
int q[M],qidx;
for(int i=1;i<=n;i++) q[++qidx]=i;

//新建
int u= qidx==0 ? ++idx : q[qidx--];

//刪除回收
a[u]=0;
q[++qidx]=u;

將樹變為區間：歐拉序列/括號序列。
哈希/堆的刪除操作：新建一個布爾數組vis[]，vis[x]=true;
判斷一個pair是否出現過：顯然用不了bool數組，可以用map<PII,bool> existed;if(existed[{a,b}]) continue;existed[{a,b}]=true;或set<PII> existed;if(existed.count({a, b})) continue;existed.insert({a, b});
浮點數卡精度

const double eps = 1e-8;
int sign(double x)  // 符號函數
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}
int cmp(double x, double y)  // 比較函數
{
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}

統計一個區間內有多少不同的數，若數值的范圍≤30，狀態壓縮。
依次刪除邊→倒著思考，反過來依次加邊。
“截斷”字符串：str[x]=0;注意這里的0是指ascll碼值為0——空字符。
地圖類題目數據范圍給的是1≤n*m≤100、或矩陣乘法加速二維遞推時，均需要把二維壓縮到一維：

//壓縮
int sets(int x,int y){
    return (x-1)*m+y;
}

//還原
void get(int state,int &x,int &y)
{
    x=(state-1)/m+1,y=(state-1)%m+1;//注意是state-1
    return ;
}

int state=sets(x,y);//壓縮

//還原
get(state,x,y);

常用并查集判斷連通性。

對于一條邊u→v：p[find(u)]=find(v);

判斷x能否走到y：if(find(x)==find(y))
vector.clear()的復雜度從O(N)降到O(1)：

void cle(vector<pair<int,Tree1> > &qwe)
{
    vector<pair<int,Tree1> > ewq;
    swap(qwe,ewq);
    return ;
}

陽間題目有時不告訴你一行輸入幾個數：“接下來的m行，每行是一個實驗的有關數據。第一個數贊助商同意支付該實驗的費用；接著是該實驗需要用到的若干儀器的編號。”
1. 快讀判斷getchar()!='\n'。
2. 使用stringstream。

//基本使用
string str="123 456 789";
stringstream a(str);  //邊定義邊讀入

int x,y,z;
a>>x;   //x=123
a>>y;   //y=456

//清空，二者缺一不可
a.str("");
a.clear();

a<<"666";   //讀入
a>>z;   //z=666

//實戰演練
int res,x[10],idx=0;
string str;
getline(cin,str);//讀一整行
stringstream a(str);
while(a>>res) x[++idx]=res;//直至讀完。注意不可以直接a>>x[++idx]，因為是先讀入再判斷，這樣的話會多讀一個空數（隨機值）

場寬：printf("%2d",a);/*從該輸出數據的最后一個字符開始往前占2個空格的寬度*/printf("%-2d",a);/*從該輸出數據的第一個字符開始往后占2個空格的寬度*/。
對于“刪邊”類問題，可以從全局圖考慮局部圖。
全局平移：用delta維護全局平移量。數據結構中的數值（位置）+delta=實際的數值（位置）。實際的數值（位置）-delta=數據結構中的數值（位置）。
因調整序列而修改（多個位置）前驅時，應先記錄哪些位置的前驅會改變，再調整序列，然后再更新那些位置的前驅。
結論題：多打表。
關于dp最值的騙分技巧：

$e.g.$$dp_{i,j}$：不超過j個的最值。對于每個i，map存$[j,dp_{i,j}]$，即將到i+1時，把$dp_{i,j}$劣于前綴最值的狀態刪除，不轉移給i+1。
與積相關，但是積很大且無模數：取對數。
map判空（x是否訪問過）：h[x]==0 ?。如果x的哈希值本來就是0，那么當x存入map時給哈希值加上一個偏移量即可：h[x]=0+delta;。
六邊形坐標系。
- 圖片
  
  ![](https://secure2.wostatic.cn/static/ih4UR7sdjgYyzLkBDP2NbN/屏幕截圖 2023-02-08 172835.jpg)
像上圖那樣建立x,y坐標系，就可以表示任意一個點的坐標。

有的時候需要像上圖那樣引入“z=x-y軸”。雖然對表示坐標沒有作用，但是有的時候可以幫助思考問題。

借助z軸，可以推得：六邊形坐標系中兩個格子的距離$=\max\{|x_1-x_2|,|y_1-y_2|,|(x_1-y_1)-(x_2-y_2)|\}=\frac{1}{2}(|x_1-x_2|+|y_1-y_2|+|(x_1-y_1)-(x_2-y_2)|)$。
模數MOD特殊一定要注意！
1. 遇見小模數MOD，可能復雜度與MOD相關。
  
  有可能當n的級別很大時，ans%MOD=0。

舉一反三

最小生成樹

母題 $Prim$ 母題 $Kruskal$

序列問題

例題1：最長上升子序列$O(N \log N)$

二分查找在q中找>=a[i]的數中最小的一個，不存在返回len+1。

大數往后面填，小數覆蓋前面。

int a[N];   //序列
int q[N],len;   //最長上升子序列

scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);

for(int i=1;i<=n;i++)
{
    int l=1,r=len+1;    //len+1：給大數留個空
    while(l<r)  //在q中找>=a[i]的數中最小的一個，不存在返回len+1
    {
        int mid=(l+r)>>1;
        if(q[mid]<a[i]) l=mid+1;
        else r=mid;
    }
    len=max(len,r); //如果a[i]是大數二分返回len+1，更新答案
    q[r]=a[i];  //大數往后面填，小數覆蓋前面
}
printf("%d\n",len);

例題2：最長公共子序列

char a[N],b[N];
int f[N][N];    //f[i][j]：前綴子串a[1~i]與b[1~j]的“最長公共子序列”的長度

scanf("%d%d",&n,&m);
scanf("%s%s",a+1,b+1);

//邊界：f[i,0]=f[0,j]=0
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        f[i][j]=max(f[i-1][j],f[i][j-1]);
        if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
    }
        
printf("%d\n",f[n][m]);

例題3：最長先升后降子序列

最長先升后降子序列=從前往后遞推的最長上升子序列+從后往前遞推的最長下降子序列-公共交點。

int f[N],g[N];  //從前往后遞推的最長上升子序列和從后往前遞推的最長下降子序列

for(int i=1;i<=n;i++)
{
    f[i]=1;
    for(int j=1;j<i;j++) if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
}

for(int i=n;i>=1;i--)
{
    g[i]=1;
    for(int j=n;j>i;j--) if(a[i]>a[j]) g[i]=max(g[i],g[j]+1);
}

for(int i=1;i<=n;i++) ans=max(ans,f[i]+g[i]-1); //還要減去公共交點i
printf("%d\n",ans);

例題4：最大上升子序列和

求一個序列所有上升子序列中子序列和的最大值。

只需把最長上升子序列模型更改一下計算貢獻的方式即可。

for(int i=1;i<=n;i++)
{
    f[i]=a[i];
    for(int j=1;j<i;j++) if(a[j]<a[i]) f[i]=max(f[i],f[j]+a[i]);
}

例題5：最長公共上升子序列

對于兩個數列 A 和 B，如果它們都包含一段位置不一定連續的數，且數值是嚴格遞增的，那么稱這一段數是兩個數列的公共上升子序列，而所有的公共上升子序列中最長的就是最長公共上升子序列了。求最長公共上升子序列的長度。

題解

int n,ans;
int a[N],b[N];
int f[N][N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);

    for(int i=1;i<=n;i++){
        int ma=1;
        for(int j=1;j<=n;j++){
            f[i][j]=f[i-1][j];
            if(a[i]==b[j]) f[i][j]=max(f[i][j],ma);
            if(a[i]>b[j]) ma=max(ma,f[i-1][j]+1);
        }
    }

    for(int i=1;i<=n;i++) ans=max(ans,f[n][i]);
    printf("%d\n",ans);

    return 0;
}

例題6：求序列$A$長度為$M$的嚴格遞增子序列

求序列$A$長度為$M$的嚴格遞增子序列。

$f[i][j]$：前$j$個數以$A_j$結尾的數列，長度為$i$的嚴格遞增子序列有多少個（$i$、$j$均可作階段）。

特殊地，令$A_0=-INF$。

狀態轉移方程

const int INF=1<<30,MOD=1e9+7;

memset(f,0,sizeof f);
a[0]=-INF;

f[0][0]=1;
for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
        for(int k=0;k<j;k++)
            if(a[k]<a[j]) f[i][j]=(f[i][j]+f[i-1][k])%MOD;
            
int ans=0;
for(int i=1;i<=n;i++) ans=(ans+f[m][i])%MOD;

數據結構優化

樹狀數組維護前綴和。

在序列A（不包括$A_0$）中的數值的值域上建立樹狀數組。

把外層循環i看作定值。當j增加1時，k的取值范圍從0≤k<j變為0≤k<j+1，也就是多了一個k=j新決策。

設一個決策$(A_k,f[i-1,k])$。

插入一個新決策。在j增加1前，把$(A_j,f[i-1,j])$插入集合：把$A_k$上的位置的值增加$f[i-1,k]$。
給定一個值$A_j$，查詢滿足$A_k<A_j$的二元組對應的$f[i-1,j]$的和：在樹狀數組計算$[1,A_j-1]$的前綴和。

//樹狀數組維護前綴和
#include<bits/stdc++.h>
using namespace std;

const int N=1005,MOD=1e9+7;
int t,n,m,ans;
int a[N],f[N][N];   //f[i][j]：前i個數以Aj結尾的數列，長度為j的嚴格遞增子序列有多少個（i、j均可作階段）
int nums[N],cnt;    //離散化
int tr[N];  //樹狀數組維護前綴和

inline int lowbit(int x){
    return x&-x;
}

void add(int x,int v){
    while(x<=cnt){
        tr[x]=(tr[x]+v)%MOD;
        x+=lowbit(x);
    }
    return ;
}

int sum(int x){
    int res=0;
    while(x>0){
        res=(res+tr[x])%MOD;
        x-=lowbit(x);
    }
    return res;
}

int main(){
    scanf("%d",&t);
    for(int C=1;C<=t;C++){
        ans=0;
        scanf("%d%d",&n,&m);
        cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            nums[++cnt]=a[i];
        }

        //離散化
        sort(nums+1,nums+cnt+1);
        cnt=unique(nums+1,nums+cnt+1)-nums-1;   //注意這里要-1
        for(int i=1;i<=n;i++) a[i]=lower_bound(nums+1,nums+cnt+1,a[i])-nums+1;

        for(int i=1;i<=n;i++) f[i][1]=1;
        for(int j=2;j<=m;j++){
            for(int i=1;i<=cnt;i++) tr[i]=0;
            for(int i=1;i<=n;i++){
                f[i][j]=sum(a[i]-1);
                add(a[i],f[i][j-1]);
            }
        }

        for(int i=1;i<=n;i++) ans=(ans+f[i][m])%MOD;

        printf("Case #%d: %d\n",C,ans);
    }
    return 0;
}

把一個序列A變成非嚴格單調遞增的，至少需要修改 序列總長度-A的最長不下降子序列長度 個數。
把一個序列A變成嚴格單調遞增的，至少需要修改 構造序列B[i]=A[i]-i，序列總長度-B的最長不下降子序列長度 個數。
把一個序列A變成嚴格單調的，至少需要花費多少偏移量？
給定一個序列A，可以選擇一個區間 [l,r]，使下標在這個區間內的數都加一或者都減一，至少要修改 差分后的序列****$\max(\sum|所有正數|,\sum|所有負數|)$ 次，且可以得到不同的序列 $|\sum|所有正數|-\sum|所有負數||+1$ 種。
求序列A的最大連續子段和：$O(N)$掃描該數列，不斷把新的數加入子段，當子段和變成負數時，把當前的整個子段清空。掃描過程中出現過的最大子段和即為所求。

排列問題

回轉排列

對于一個排列$p_1,p_2,\dots,p_n$，記$p_{q_i}=i$，即$q_i$為數值i在$p_1,p_2,\dots,p_n$中的位置。顯然$p_1,p_2,\dots,p_n$和$q_1,q_2,\dots,q_n$一一對應。

定義$p_1,p_2,\dots,p_n$是回轉排列$\Leftrightarrow$$\forall i\in[2,n-1],(q_i-q_{i-1})(q_i-q_{i+1})>0$。

e.g.p=[1,3,4,2],q=[1,4,2,3]；p≠[1,4,2,3],q≠[1,3,4,2]；p=[1,3,2,4],q=[1,3,2,4]；p=[2,4,1,3],q=[3,1,4,2]；p=[3,1,4,2],q=[2,4,1,3]。

有的題目對排列p的兩端有限制，此時計算$p_1,p_2,\dots,p_n$的合法方案數比較方便；有的題目對排列q的兩端有限制，此時計算$q_1,q_2,\dots,q_n$的合法方案數比較方便；

計算$p_1,p_2,\dots,p_n$的合法方案數

位置大小。

《動態規劃7.4..有序序列計數》。

$f_{i,j,0/1}$：把前i個數加入排列，數值i位于前i個數的第j位，并且初始方向是 1在2的左邊/右邊，的合法方案數。

根據i的奇偶性和 0/1 狀態，來確定數值i應該是在i-1的左邊還是右邊，然后枚舉合適的j，進行轉移。

計算$q_1,q_2,\dots,q_n$的合法方案數

數值大小。

《動態規劃2.7.序列·插入·連續段模型》。

區間問題

有些區間[l,r]的問題可以拆成[1,l-1]與[1,r]的子問題。

求前k大區間和：超級鋼琴

這里要知道[l,r]中最大值的位置pos，求出后查詢[l,pos-1][pos+1,r]中的最大值（pos已經用過了不能再用）。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=5e5+10;
int n,m,l,r;
LL ans=0;
int sum[N];
int f[N][20],log_2[N];
struct Seg
{
    int st,l,r,pos,s;
    bool operator < (const Seg &t) const
    {
        return s<t.s;
    }
};
priority_queue<Seg> q;

void st_pre()
{
    for(int i=2;i<=n;i++) log_2[i]=log_2[i>>1]+1;
    for(int i=1;i<=n;i++) f[i][0]=i;
    for(int k=1;1+(1<<k)-1<=n;k++)
        for(int l=1;l+(1<<k)-1<=n;l++)
        {
            int a=f[l][k-1],b=f[l+(1<<(k-1))][k-1];
            f[l][k]=sum[a]>sum[b] ? a : b;
        }
    return ;
}

int st_query(int l,int r)
{
    int k=log_2[r-l+1];
    int a=f[l][k],b=f[r-(1<<k)+1][k];
    return sum[a]>sum[b] ? a : b;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&l,&r);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&sum[i]);
        sum[i]+=sum[i-1];
    }
    st_pre();
    for(int i=1;i+l-1<=n;i++)
    {
        int pos=st_query(i+l-1,min(i+r-1,n));
        int s=sum[pos]-sum[i-1];
        q.push((Seg){i,i+l-1,min(i+r-1,n),pos,s});
    }
    while(m--)
    {
        auto t=q.top();
        q.pop();
        int st=t.st,pos=t.pos,s=t.s,new_pos,new_s;
        ans+=s;
        if(t.l!=pos)
        {
            new_pos=st_query(t.l,pos-1);
            new_s=sum[new_pos]-sum[st-1];
            q.push((Seg){st,t.l,pos-1,new_pos,new_s});
        }
        if(t.r!=pos)
        {
            new_pos=st_query(pos+1,t.r);
            new_s=sum[new_pos]-sum[st-1];
            q.push((Seg){st,pos+1,t.r,new_pos,new_s});
        }
    }
    printf("%lld\n",ans);
    return 0;
}

求前k大區間異或和：異或粽子

我們求一遍前綴異或和，那么 [l,r]的異或和為 $sum_{l-1}\ \text{xor}\ sum_r$

我們先固定右端點 r，然后在 [0,r?1] 查一個數異或 $sum_r $最大。這個可以用可持久化 01trie 實現。

我們將 n 個數（顯然這n個數就是前n大）放入堆中，每次取出最大的那個狀態。最大值的位置是pos，求出后查詢[l,pos-1][pos+1,r]中的最大值（pos已經用過了不能再用）放入堆中。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=5e5+10,M=N*35;
int n,m;
LL ans,sum[N];
int root[N],idx;
int tr[M][2],max_id[M];
struct Seg
{
    int st,l,r,pos;
    LL s;
    bool operator < (const Seg &t) const
    {
        return s<t.s;
    }
};
priority_queue<Seg> q;

void insert(int id,int k,int p,int q)
{
    if(k<0)
    {
        max_id[q]=id;
        return ;
    }
    int v=(sum[id]>>k)&1;
    tr[q][v^1]=tr[p][v^1];
    tr[q][v]=++idx;
    insert(id,k-1,tr[p][v],tr[q][v]);
    max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);
    return ;
}

int query(int l,int rt,LL num)
{
    int p=rt;
    for(int k=31;k>=0;k--)
    {
        int v=(num>>k)&1;
        if(max_id[tr[p][v^1]]>=l) p=tr[p][v^1];
        else p=tr[p][v];
    }
    return max_id[p];
}

int main()
{
    scanf("%d%d",&n,&m);
    
    max_id[0]=-1;
    root[0]=++idx;
    insert(0,31,0,root[0]);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&sum[i]);
        sum[i]^=sum[i-1];
        root[i]=++idx;
        insert(i,31,root[i-1],root[i]);
    }
    
    for(int i=1;i<=n;i++)
    {
        int pos=query(i,root[n],sum[i-1]);
        LL s=sum[pos]^sum[i-1];
        q.push((Seg){i,i,n,pos,s});
    }
    
    while(m--)
    {
        auto t=q.top();
        q.pop();
        ans+=t.s;
        int new_pos;
        LL new_s;
        if(t.l<t.pos)
        {
            new_pos=query(t.l,root[t.pos-1],sum[t.st-1]);
            new_s=sum[new_pos]^sum[t.st-1];
            q.push((Seg){t.st,t.l,t.pos-1,new_pos,new_s});
        }
        if(t.r>t.pos)
        {
            new_pos=query(t.pos+1,root[t.r],sum[t.st-1]);
            new_s=sum[new_pos]^sum[t.st-1];
            q.push((Seg){t.st,t.pos+1,t.r,new_pos,new_s});
        }
    }
    
    printf("%lld\n",ans);
    
    return 0;
}

區間子區間問題

K問題

第k小數
1. 整體第k小數（靜態）
  - 方法一：快速排序求第k小數

int n,k;
int a[N];

void quick_sort(int l,int r,int k)
{
    if(l>=r) return ;//不要忘記這里！！！
    int i=l,j=r,mid=a[(l+r)>>1];
    while(i<=j)
    {
        while(a[i]<mid) i++;
        while(a[j]>mid) j--;
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if(j-l+1>=k) quick_sort(l,j,k);//！！！
    else quick_sort(i,r,k-(j-l+1));//！！！
    return ;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    quick_sort(1,n,k);
    printf("%d\n",a[k]);
    return 0;
}

  - 方法二：二分答案（鋪墊整體二分）

    設當前二分的值是mid，統計序列里cnt個數≤mid。

    若k≤cnt，則答案一定在左半區間，繼續二分；否則在一定在右半區間，令k-=cnt，繼續二分。

整體第k小數（動態修改）

值域線段樹
區間求不大于S的數的個數（動態修改）（鋪墊整體二分）
- 樹狀數組
  
  初始對于任意A[i]≤S，在樹狀數組中執行add(i,1);，表示在第i個位置上有一個不大于S的數（即第i個位置對答案的貢獻+1）。
  
  詢問時答案就是ans=ask(r)-ask(l-1);。
  
  修改A[i]=x時，若A[i]≤S，則執行add(i,-1);，表示刪除第i個位置對答案的貢獻；若x≤S，則再執行add(i,1);。然后別忘了維護原數組A[i]=x;。
區間第k小數（靜態）
- 方法一：整體二分（必須離線）
  
  把所有的操作（包括將數組的原值看作一開始就賦值的操作）先按時間排好序（本來就自然地排好序），然后只要進行1次值域上的二分：
  1. merge(lval,rval,st,ed)：值域為[L,R]的整數序列a，對操作序列q（含刪除、賦值、詢問）進行實現。
  2. 利用樹狀數組，在當前的序列a中，對于q的每個詢問，統計不大于mid的數有c個。
  3. 若k≤c則將該詢問加入操作序列lq中，否則令k-=c加入rq。
  4. 令整數序列a中≤mid的數構成整數序列la，>mid的數構成整數序列ra，操作序列q中涉及≤mid的數的操作構成操作序列lq，涉及≤mid的數的操作構成操作序列rq。注意保持操作的時間順序。
  5. 還原樹狀數組，分治求解merge(lval,mid):la,lq和merge(mid+1,rval):ra,rq。邊界：當操作序列為空時直接返回；當整數序列只剩1個數時得到答案。

int n,m;
int ans[N];
int tr[N];

int idx;
struct Data
{
    int op,x,y,z;
}q[N],lq[N],rq[N];

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int val)
{
    while(x<=n)
    {
        tr[x]+=val;
        x+=lowbit(x);
    }
    return ;
}

int ask(int x)
{
    int res=0;
    while(x)
    {
        res+=tr[x];
        x-=lowbit(x);
    }
    return res;
}

void merge(int lval,int rval,int st,int ed)
{
    if(st>ed) return ;
    if(lval==rval)
    {
        for(int i=st;i<=ed;i++) if(q[i].op>0) ans[q[i].op]=lval;
        return ;
    }
    
    int mid=(lval+rval)>>1;
    int lqidx=0,rqidx=0;
    for(int i=st;i<=ed;i++)
    {
        if(q[i].op==0)
        {
            if(q[i].y<=mid)
            {
                add(q[i].x,1);
                lq[++lqidx]=q[i];
            }
            else rq[++rqidx]=q[i];
        }
        else
        {
            int cnt=ask(q[i].y)-ask(q[i].x-1);
            if(cnt>=q[i].z) lq[++lqidx]=q[i];
            else
            {
                q[i].z-=cnt;
                rq[++rqidx]=q[i];
            }
        }
    }
    
    for(int i=ed;i>=st;i--)
    {
        if(q[i].op==-1 && q[i].y<=mid) add(q[i].x,1);
        else if(q[i].op==0 && q[i].y<=mid) add(q[i].x,-1);
    }
    for(int i=1;i<=lqidx;i++) q[st+i-1]=lq[i];
    for(int i=1;i<=rqidx;i++) q[st+lqidx+i-1]=rq[i];
    merge(lval,mid,st,st+lqidx-1);
    merge(mid+1,rval,st+lqidx,ed);
    
    return ;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int val;
        scanf("%d",&val);
        q[++idx]={0,i,val};
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        q[++idx]={i,l,r,k};
    }
    merge(-INF,INF,1,idx);
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

  - 方法二：主席樹（可以在線）

    p：前一個線段樹，q：當前新建的線段樹。

類似于動態開點新建一個節點q，節點q復制節點p的信息，隨著p往下走在節點q新建新的信息。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5,M=1e4+5;
int n,m;
int a[N];
vector<int> nums;
struct Tree //區間左右端點由函數中l和r決定
{
    int lson,rson;    ////lson：左兒子的編號（注意不是區間左端點）；rson：右兒子的編號；
    int cnt;    //當前區間所包含數的個數
}tr[N*4+N*17];
int root[N],idx;

int build(int l,int r)
{
    int p=++idx;    //類似于動態開點
    if(l==r) return p;
    int mid=(l+r)>>1;
    tr[p].lson=build(l,mid);
    tr[p].rson=build(mid+1,r);
    return p;
}

void pushup(int p)
{
    tr[p].cnt=tr[tr[p].lson].cnt+tr[tr[p].rson].cnt;
    return ;
}

//區間左右端點由函數中l和r決定
int insert(int p,int l,int r,int x)
{
    int q=++idx;
    tr[q]=tr[p];    //復制
    if(l==r)
    {
        tr[q].cnt++;
        return q;
    }
    
    //新建
    int mid=(l+r)>>1;
    if(x<=mid) tr[q].lson=insert(tr[p].lson,l,mid,x);
    else tr[q].rson=insert(tr[p].rson,mid+1,r,x);
    pushup(q);
    return q;
}

int query(int q,int p,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1,cnt=tr[tr[q].lson].cnt-tr[tr[p].lson].cnt; //區間具有前綴和的性質，這樣區間里的數就一定大于L
    if(k<=cnt) return query(tr[q].lson,tr[p].lson,l,mid,k);
    else return query(tr[q].rson,tr[p].rson,mid+1,r,k-cnt);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        nums.push_back(a[i]);
    }
    
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++) a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin();
    
    root[0]=build(0,nums.size()-1);
    
    for(int i=1;i<=n;i++) root[i]=insert(root[i-1],0,nums.size()-1,a[i]);
    
    while(m--)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",nums[query(root[r],root[l-1],0,nums.size()-1,k)]);
    }
    
    return 0;
}

區間第k小數（動態修改）
- 方法一：整體二分（必須離線）
  
  結合第3小問，在第4小問增加修改操作：分成刪除和增添操作。

int n,m;
int a[N];   //原數組
int ans[N];
int tr[N];  //樹狀數組維護單個區間靜態第k小數

//操作序列（按時間排好序）
//當op=-1：刪除某個位置上的數的貢獻；0：在某個位置增添一個數的貢獻；1：詢問
int idx;
struct Data
{
    int op,x,y,z;
}q[N],lq[N],rq[N];  //q：當前操作序列；lq（rq）：分配到左（右）兒子的操作序列

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int val)
{
    while(x<=n)
    {
        tr[x]+=val;
        x+=lowbit(x);
    }
    return ;
}

int ask(int x)
{
    int res=0;
    while(x)
    {
        res+=tr[x];
        x-=lowbit(x);
    }
    return res;
}

void merge(int lval,int rval,int st,int ed) //lval、rval：值域；st、ed：操作序列
{
    if(st>ed) return ;  //空操作序列，返回
    if(lval==rval)  //找到答案
    {
        for(int i=st;i<=ed;i++) if(q[i].op>0) ans[q[i].op]=lval;
        return ;
    }
    
    //分配到左兒子或右兒子
    int mid=(lval+rval)>>1;
    int lqidx=0,rqidx=0;
    for(int i=st;i<=ed;i++)
    {
        if(q[i].op==-1)
        {
            if(q[i].y<=mid) //按值域劃分：對答案有貢獻的數的值小于mid分到左兒子
            {
                add(q[i].x,-1); //刪除某個位置上的數的貢獻，而不是減這個數的值，因此修改操作分成的兩個操作就算分道揚鑣也不會影響正確性
                lq[++lqidx]=q[i];
            }
            else rq[++rqidx]=q[i];
        }
        else if(q[i].op==0) //類似上面
        {
            if(q[i].y<=mid)
            {
                add(q[i].x,1);
                lq[++lqidx]=q[i];
            }
            else rq[++rqidx]=q[i];
        }
        else
        {
            int cnt=ask(q[i].y)-ask(q[i].x-1);
            if(cnt>=q[i].z) lq[++lqidx]=q[i];   //這個區間小于mid的數的個數大于k，因此答案應該在左兒子
            else
            {
                q[i].z-=cnt;    //注意分到右兒子前應減去左兒子的影響
                rq[++rqidx]=q[i];
            }
        }
    }
    
    for(int i=ed;i>=st;i--) //清空樹狀數組
    {
        if(q[i].op==-1 && q[i].y<=mid) add(q[i].x,1);
        else if(q[i].op==0 && q[i].y<=mid) add(q[i].x,-1);
    }
    for(int i=1;i<=lqidx;i++) q[st+i-1]=lq[i];  //節省空間
    for(int i=1;i<=rqidx;i++) q[st+lqidx+i-1]=rq[i];    //節省空間
    merge(lval,mid,st,st+lqidx-1);  //往下分治
    merge(mid+1,rval,st+lqidx,ed);  //往下分治
    
    return ;
}

int main()
{
    memset(ans,-1,sizeof ans);  //輸出時方便判斷是否為查詢操作
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        q[++idx]={0,i,a[i]};
    }
    for(int i=1;i<=m;i++)
    {
        char op[2];
        scanf("%s",op);
        if(op[0]=='Q')
        {
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            q[++idx]={i,l,r,k};
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            
            //修改操作可以分成2個操作。并且因此數組要開3*10^5！
            q[++idx]={-1,x,a[x]};
            q[++idx]={0,x,y};
            
            a[x]=y; //別忘記修改原數組
        }
    }
    merge(0,INF,1,idx);
    for(int i=1;i<=m;i++) if(ans[i]!=-1) printf("%d\n",ans[i]);
    return 0;
}

  - 方法二：主席樹（可以在線）

樹上路徑第k小數
- 主席樹
  
  不要學數據結構學傻了，不要看到樹上路徑就只想到樹鏈剖分，樹鏈剖分+主席樹是做不了的。
  
  該問題很簡單，其實就是樹上兩點間的距離與樹上差分+區間第k小數嘛。tr：當前點到根節點的路徑上的數的出現次數。
  
  代碼鏈接。

$\text{A*}$求第k短路

第一次出隊是最短路，第k次出隊是第k短路。

int h[N],rh[N],e[M],w[M],ne[M],idx;
int d[N],cnt[N];
int n,m,s,t,k;
bool vis[N];

void add(int hh[],int a,int b,int c){
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=hh[a];
    hh[a]=idx;
    return ;
}

//反向邊求估價函數
void dij(){
    priority_queue<PII,vector<PII>,greater<PII> > q;
    memset(d,0x3f,sizeof d);
    d[t]=0;
    q.push({0,t});
    while(q.size()){
        auto t=q.top();
        q.pop();
        int u=t.second;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=rh[u];i!=0;i=ne[i]){
            int j=e[i];
            if(d[j]>d[u]+w[i]){
                d[j]=d[u]+w[i];
                q.push({d[j],j});
            }
        }
    }
    return ;
}

int A_star(){
    priority_queue<PIII,vector<PIII>,greater<PIII> > q;
    q.push({d[s],{0,s}});
    while(q.size()){
        auto tt=q.top();
        q.pop();
        int u=tt.second.second,dis=tt.second.first;
        cnt[u]++;
        if(cnt[t]==k) return dis;   //第一次出隊是最短路，第k次出隊是第k短路
        for(int i=h[u];i!=0;i=ne[i]){
            int j=e[i];
            if(cnt[j]<k) q.push({dis+w[i]+d[j],{dis+w[i],j}});
        }
    }
    return -1;
}

int main(){
    cin>>n>>m;
    while(m--){
        int a,b,l;
        cin>>a>>b>>l;
        add(h,a,b,l);
        add(rh,b,a,l);  //反向邊求估價函數
    }
    cin>>s>>t>>k;
    if(s==t) k++;   //注意特判
    dij();  //預處理估價函數
    cout<<A_star()<<endl;
    return 0;
}

Bellman-Ford求邊數不超過k的最短路

int bellford(){
    memset(d,0x3f,sizeof d);
    d[1]=0;
    for(int i=1;i<=k;i++){//用上一次的邊權擴展，擴展k次，保證經過不超過k條邊
        memcpy(last,d,sizeof d);
        for(int j=1;j<=m;j++){
            int w=q[j].first,u=q[j].second.first,v=q[j].second.second;
            d[v]=min(d[v],last[u]+w);
        }
    }
    return d[n];
}

求在從 1? 到 N? 的路徑中，路徑上第 k? 大的值最小是多少

形如“最大值最小” / “最小值最大”之類的字眼：用二分求解。

自變量：x。

因變量：y，表示對于給定的 x ，從 1 到 N 的路徑中最少要經過邊權大于 x 的邊有多少條。

判定：y≤k-1

我們設原邊權大于 x 的邊的新邊權為 1 ，小于等于 x 的邊新邊權為 0，求出從 1 到 N 的最短路即為 y 的值。01邊權雙端隊列BFS求解。

int n,m,k;

int h[N],e[M],w[M],ne[M],idx;

int dis[N]; //dis[u]：從1到u至少有多少條線路費用大于limit
bool vis[N];
deque<int> q;

void add(int a,int b,int c){
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
    return ;
}

//雙向隊列BFS
bool check(int limit){
    memset(dis,0x3f,sizeof dis);
    memset(vis,false ,sizeof vis);
    dis[1]=0;
    q.push_front(1);

    while(!q.empty()){
        int u=q.front();
        q.pop_front();
        if(vis[u]) continue;    //雙段隊列BFS是判斷u而不是v
        vis[u]=1;
        for(int i=h[u];i!=0;i=ne[i]){
            int j=e[i],d=0;

            if(w[i]>limit) d=1;

            if(dis[j]>dis[u]+d){
                dis[j]=dis[u]+d;

                if(d==0) q.push_front(j);
                else q.push_back(j);
            }
        }
    }

    return dis[n]<=k-1;
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }

    //二分答案轉化為判定
    int l=0,r=INF;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }

    if(l==INF) puts("-1");
    else printf("%d\n",l);

    return 0;
}

任意兩點距離

一般圖：《圖論4.1.1.Floyd求任意兩點間最短路》$O(N^3+Q)$
仙人掌和基環樹：《圖論10.2.求仙人掌上任意兩點的最短距離》$O((N+N\log N)+Q\log N)$
樹：《圖論9.樹上差分與樹上任意兩點的最短距離》$O(N\log N+Q\log N)$
一個簡單環：《動態規劃5.3.求一個簡單環上任意兩點的最短距離》$O(N+Q)$

算法性質

單調棧

解題思路

我們先研究樣例，假設詢問的區間是$[1,10]$，也就是把所有二元組依次進入這個“單調棧”，觀察一下性質：

我們會發現，當第$8$個二元組入棧時，盡管它彈出了棧里很多二元組，為自己成為“成功的”二元組做出了很多努力，但是最終還是沒有把第$4$個二元組彈出棧，十分可惜。

第8個二元組 (2,7)
      |
      v           ->
第7個二元組 (3,4)
第5個二元組 (2,7)         第8個二元組 (2,7)
第4個二元組 (1,9)         第4個二元組 (1,9)

這時我們就會想：如果沒有第$4$個二元組，也就是詢問的區間左端點$L_{query}$$≥4+1=5$，那么第$8$個二元組是不是就成為了“成功的”？

我們經過實踐驗證，發現果真如此。接下來，我們會研究每個二元組入棧時它下面的二元組是什么（如果這個二元組“成功的”入棧后棧內只有它，那我們就假設它下面的二元組是“哨兵”第$0$個二元組{$0,INF$}）？也就是直接使這個入棧的二元組“失敗”的是誰：


第1個二元組	第2個二元組	第3個二元組	第4個二元組	第5個二元組	第6個二元組	第7個二元組	第8個二元組	第9個二元組	第10個二元組
0	0	2	0	4	5	5	4	8	8

我們令第二行的數字都$+1$，得到一個$success[]$數組：


第1個二元組	第2個二元組	第3個二元組	第4個二元組	第5個二元組	第6個二元組	第7個二元組	第8個二元組	第9個二元組	第10個二元組
1	1	3	1	5	6	6	5	9	9

于是我們假設一個猜想：當$L_{query}≥success[i]$時，第$i$個二元組一定是“成功的”。

略證明我們的猜想：

單調棧的一個小性質：單調棧的元素是否被彈出只與后面的元素有關，與前面的元素無關。

略證明：研究單調棧模板的代碼，我們會發現：即將進棧的元素只會把它前面的元素彈出，無論它自己有多“差”，它自己最后**一定**會入棧，然后可能會被后面的元素彈出。

當$L_{query}<success[i]$時，由上面的性質：第$success[i]-1$個二元組一定會入棧。既然詢問區間是$[1,n]$時第$success[i]-1$個二元組在第$i$個二元組到來之前都沒有被彈出，現在第$success[i]-1$個二元組在第$i$個二元組到來之前自然也不會被彈出，仍在棧中的第$success[i]-1$個二元組一定會使第$i$個二元組“失敗”。

當$L_{query}$≥$success[i]$時，第≤$L_{query}$的二元組我們就不用管了，它們都沒有入棧。由上面的性質第$L_{query}$個二元組是否被彈出與前面的二元組無關，一定是被后面的二元組彈出。既然詢問區間是$[1,n]$時所有第≥$L_{query}$的二元組都在第$i$個二元組到來之前被彈出，現在它們在第$i$個二元組到來之前自然也一定會被彈出，第$i$個二元組一定是“成功的”。

同時也注意：當$L_{query}>i$越界時，第$i$個二元組都沒有入棧，自然也不是“成功的”。

因此，我們得到一個結論：當$success[i]≤L_{query}≤i$時，第$i$個元素一定是“成功的”，對答案的貢獻$+1$：我們建立一個$ans[]$數組，以$L_{query}$為下標：

L_query==             1   2   3   4   5   6   7   8   9   10
第1個二元組對答案的貢獻  +1
第2個二元組對答案的貢獻  +1  +1
第3個二元組對答案的貢獻          +1
第4個二元組對答案的貢獻  +1  +1  +1  +1
第5個二元組對答案的貢獻                  +1
第6個二元組對答案的貢獻                      +1
第7個二元組對答案的貢獻                      +1  +1
第8個二元組對答案的貢獻                  +1  +1  +1  +1
第9個二元組對答案的貢獻                                  +1
第10個二元組對答案的貢獻                                 +1  +1

研究上面的圖，我們會發現：當$L_{query}==1$時，對答案有貢獻的二元組有$3$個：第$1$、$2$和$4$個二元組。可是如果我們詢問的區間是$[1,3]$時，也就是$R_{query}<4$時，第$4$個二元組都沒有入棧，自然對答案沒有貢獻，這樣我們會多算答案，怎么辦呢？

我們可以對詢問區間按右端點遞增進行排序。排序后，對于每個詢問，我們把$[R_{Last Query}+1,R_{query}]$的二元組對答案的貢獻加入到$ans[]$，即$ans[L]+=1(success[i]≤L≤i)$，然后$ans[L_{query}]$就是答案。

由于$ans[]$是區間修改，單點查詢，我們用非常合適的樹狀數組$tr[]$維護它。

具體步驟

對于每個二元組：{{$a$,$b$},編號}；
模擬單調棧預處理$success[]$數組。注意先把“哨兵”二元組{{$0$,$INF$},$0$}入棧。對于每一個即將入棧的二元組$i$，先按單調棧彈出棧頂的二元組，然后得到success[i]=stack.top().second+1;，最后再將該二元組入棧。時間復雜度是$O(N)$；
對于每個詢問：{{右端點,左端點},編號}（因為按右端點排序，所以把右端點放在$query[].first.first$的位置）；
將詢問按右端點排序。時間復雜度是$O(QlogQ)$；
排序后，對于每個詢問，我們把$[R_{Last Query}+1,R_{query}]$的二元組對答案的貢獻加入到$ans[]$，即$ans[L]+=1(success[i]≤L≤i)$，然后$ans[L_{query}]$就是答案。
由于$ans[]$是區間修改，單點查詢，我們用非常合適的樹狀數組$tr[]$維護它。每個二元組對答案的貢獻至多只會加入$1$次樹狀數組$tr[]$，因此時間復雜度是$O(NlogN+QlogQ)$；

$N$和$Q$都$≤5 \times 10^5$，因此總的時間復雜度是$O(N+NlogN)$

C++代碼

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<int,int> PII;
typedef pair<PII,int> PIII;
const int N=5e5+5;
int n,q;
int success[N],ans[N];
int tr[N];  //樹狀數組維護
PIII num[N],query[N];
stack<PIII> st;

int read()
{
    int res=0,fff=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') fff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*fff;
}

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int val)
{
    while(x<=n)
    {
        tr[x]+=val;
        x+=lowbit(x);
    }
    return ;
}

int ask(int x)
{
    int res=0;
    while(x)
    {
        res+=tr[x];
        x-=lowbit(x);
    }
    return res;
}

int main()
{
    // freopen("stack.in","r",stdin);
    // freopen("stack.out","w",stdout);
    
    n=read(),q=read();
    
    for(int i=1;i<=n;i++) num[i].x.x=read();
    for(int i=1;i<=n;i++) num[i].x.y=read();
    for(int i=1;i<=n;i++) num[i].y=i;

    //模擬單調棧預處理success[]數組
    st.push({{0,1e6},0});   //注意先把“哨兵”二元組{{0,INF},0}入棧
    for(int i=1;i<=n;i++)
    {
        int ai=num[i].x.x,bi=num[i].x.y;
        while(ai==st.top().x.x || bi>=st.top().x.y) st.pop();   //按照單調棧彈出棧頂的二元組
        success[i]=st.top().y+1;    //得到success數組
        st.push(num[i]);    //最后再將該二元組入棧
    }

    for(int i=1;i<=q;i++)
    {
        query[i].y=i;
        query[i].x.y=read();
        query[i].x.x=read();  //因為按右端點排序，所以把右端點放在query[].first.first的位置
    }
    
    sort(query+1,query+q+1);    //將詢問按右端點排序
    
    int idx=0;
    for(int i=1;i<=q;i++)
    {
        int id=query[i].y,l=query[i].x.y,r=query[i].x.x;
        
        //對于每個詢問，對于[R_{Last Query}+1,R_{query}]的二元組
        while(idx!=r)
        {
            idx++;
            
            //把該二元組對答案的貢獻加入到樹狀數組tr[]
            add(success[idx],1);
            if(idx+1<=n) add(idx+1,-1);
        }
        
        ans[id]=ask(l); //此時ask(L_{query})就是答案
    }

    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);

    return 0;
}

AVL樹
- 題目圖片
AVL樹：在計算機科學中，AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差別為1，所以它也被稱為高度平衡樹。

原題每一個合法排列$\Leftrightarrow$n個節點的AVL樹的每一個中序遍歷

原題就是求將1~n插入AVL樹，也就是n個節點的AVL樹的不同中序遍歷數。
1. 狀態設計：由于AVL樹涉及高度，所以設$f[i][height]$：i個節點，高度為height的AVL樹的不同中序遍歷數。
  
  答案：$ANS=\sum\limits_{height=1}^{18} f[n][height]$。節點數為5000的AVL樹高度最大是18。
  
  轉移：$f[i][height]=\sum\limits_{l=1}^{i}(f[l][height-1]*f[i-1-l][height-1]+f[l][height-1]*f[i-1-l][height-2]+f[l][height-2]*f[i-1-l][height-1])*C_{i-1}^l$。
  
  根據AVL樹的定義，高度為height的AVL樹的左右子樹高度可以為：{height-1,height-1}、{height-1,height-2}和{height-2,height-1}。
  
  因為要求的是AVL樹的不同中序遍歷數，所以在求出AVL樹的不同形態數后，還要乘上組合數$C_{i-1}^l$
```
 組合數含義：當前有i個數，把最大的數作為根節點（假設此AVL樹滿足大根堆），還剩i-1個數。從i-1個數中選出l個數去左子樹，剩下的數就自然去右子樹了
```
  邊界：$f[0][0]=f[1][1]=1$，其余高度為0或1的dp值為0。
2. 優化。
  1. 只需要求出$\sum\limits_{height=1}^{+\infty} f[n][height]$，轉移過程中不是所有的狀態最后都要利用到，因此采用記憶化搜索實現dp。
  2. 預處理$low/up[height]$：高度為height的AVL樹的節點數的下界/上界。這樣就能及時排除不合法狀態，而且轉移時能縮小枚舉左子樹節點數的范圍。
    
    高度為height的AVL樹的節點數的下界/上界遞推式：
    
    下界：
```
 邊界：顯然height=1時，節點數下界=1；height=1時，節點數下界=2。

 高度為height的AVL樹的節點數下界=高度為height-1的一子樹的節點數下界+高度為height-2的另一子樹的節點數下界+根節點。
```
    上界：顯然滿二叉樹就是符合條件且節點數最多的AVL樹。
代碼鏈接。
虛樹

可以證明，點集在樹上的斯坦納樹即為其虛樹。虛樹上的邊權和即為正確答案。

定第一個關鍵點為根。否則當給定2個不在同一條鏈上的關鍵點時，下面的做法會判斷錯誤。

先考慮邊權非0的情況。

在草稿紙上模擬可易證：給定的錯誤代碼是正確的，當且僅當給定的點集$V_1$中的兩個點 u,v的LCA也在 $V_1$中。發現這等價于虛樹的性質：“給定點集$V_1$在原圖上的虛樹點集$V_1'$”和“$V_1$”相同。

求出虛樹點集：根據虛樹的建立，當插入一個關鍵點u時，設v、w是當前（注意題目是一個一個給關鍵點并讓你分別作出判斷，所以后面才給出的關鍵點不屬于當前的關鍵點）關鍵點的集合中以dfn序排序的u的前軀、后繼，我們會把u、lca(u,v)、lca(u,w)插入虛樹（已經插入的就不再插入了），然后我們就會得到此時的虛樹點集。

快速判斷“給定點集$V_1$在原圖上的虛樹點集$V_1'$”和“$V_1$”是否相同：in_tree[u]：點u是否在虛樹中；is_key[u]：點u是否是關鍵點（注意題目是一個一個給關鍵點并讓你分別作出判斷）。利用這兩個數組可求出$more=|V_1'|-|V_1|$。當more=0時兩個點集相同，否則就不同。具體見代碼

邊權為0的情況：只需要將所有由 0邊連接的連通塊視為一個點，一個連通塊被選中當且僅當其中至少有一個點被選中，用并查集維護連通塊，然后應用上述做法即可。

int n;
int key[N];
int h[N],e[M],w[M],ne[M],idx;
int p[N];   //用并查集維護邊權為0的連通塊
int dfn[N],num;
int dep[N],fa[N][20];
int more;   //more=給定點集V_1在原圖上的虛樹點集V_1'的大小-V_1的大小
bool in_tree[N],is_key[N];  //in_tree[u]：點u是否在虛樹中；is_key[u]：點u是否是關鍵點（注意題目是一個一個給關鍵點并讓你分別作出判斷）
struct Tree
{
    int x;
    bool operator < (const Tree &qw) const
    {
        return dfn[x]<dfn[qw.x];    //虛樹以dfn序排序
    }
};
set<Tree> tr;

int find(int x) {}  //并查集

void dfs(int u,int father)
{
    dfn[u]=++num;
    for(int i=h[u];i!=0;i=ne[i])
    {
        int v=e[i];
        if(v==father) continue;
        if(w[i]==0) p[v]=find(u);   //由 0邊連接的連通塊視為一個點
        dep[v]=dep[u]+1;
        fa[v][0]=u;
        for(int k=1;k<=18;k++) fa[v][k]=fa[fa[v][k-1]][k-1];
        dfs(v,u);
    }
    return ;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v,wor;
        scanf("%d%d%d",&u,&v,&wor);
        add(u,v,wor),add(v,u,wor);
    }
    for(int i=1;i<=n;i++) scanf("%d",&key[i]);
    for(int i=1;i<=n;i++) p[i]=i;
    dep[key[1]]=1;  //定第一個關鍵點為根
    dfs(key[1],-1);
    for(int i=1;i<=n;i++)
    {
        int x=find(key[i]);
        if(!is_key[x])  //可能該點所屬的連通塊已經插入虛樹了
        {
            is_key[x]=true;
            tr.insert((Tree){x});
            if(in_tree[x]) more--;
            else in_tree[x]=true;
            auto it=tr.find((Tree){x});
            if(it!=tr.begin())
            {
                it--;
                int pp=find(lca(it->x,x));
                if(!in_tree[pp] && !is_key[pp])
                {
                    in_tree[pp]=true;
                    more++;
                }
                it++;
            }
            if(it!=(--tr.end()))
            {
                it++;
                int pp=find(lca(it->x,x));
                if(!in_tree[pp] && !is_key[pp])
                {
                    in_tree[pp]=true;
                    more++;
                }
                it--;
            }
        }
        if(more==0) putchar('1');
        else putchar('0');
    }
    puts("");
    return 0;
}

兩次bfs求樹的直徑

題目描述

給定n個點，動態連n-1條邊，最后保證連成1棵樹。求每次連完1條邊后，該邊所在樹的直徑長度。

解題思路

由兩次bfs求樹的直徑可知：當每次連完1條邊合并兩棵樹時，新的樹的直徑的端點一定是原來兩棵樹的直徑的四個端點中之二。

因此對每個點開一個并查集，儲存并查集的根和該連通塊（樹）的兩直徑端點。每合并兩棵樹時，在原來兩棵樹的直徑的四個端點中選出距離最遠的兩個端點作為新的樹的直徑，并輸出該直徑長度。

怎么求兩個端點之間的距離呢？
- 離線做法
  
  先把最終的樹建出來。由于樹上兩點之間的距離是確定的，因此最終的樹上兩個端點之間的距離=此時兩個端點之間的距離。
- 在線做法
  
  如果把并查集v合并到并查集u，那么整棵樹v中的每個點i的dep[i]和fa[i][k]都需要重新計算，因此使用啟發式合并。
代碼鏈接。
小根堆

原題等價于：求1到n的所有排列中，滿足小根堆性質的排列的個數。

$f[i]$：i個不同的數的所有排列中滿足小根堆性質的排列的個數。

可以利用分治轉移dp。首先計算出i個節點的完全二叉樹中，根節點的左子樹包含的節點數l，右子樹包含的節點數r。由于根節點的值必須為最小值，所以根節點確定了，分治到根節點的左右子樹。再考慮剩下的i-1個節點，在這i-1個節點中選出l個節點作為左子樹，剩下的r個節點作為右子樹。所以得出轉移：$f[i]=C_{i-1}^l*f[l]*f[r]$。
線段樹

性質
1. 線段樹遞歸到葉子節點當且僅當：操作區間左端點是右葉子節點，操作區間右端點是左葉子節點。
2. 兩個葉子結點的 LCA的節點編號其實就是他們編號的最長公共前綴（二進制下）。

錯誤代碼

分塊題
- 題目圖片
調和級數：$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\ln n$。

所以塊長1~N中塊的總個數是$O(N\log N)$。

一類長度為len的塊的答案=分塊中一類長度為len的塊的貢獻+分塊中暴力的貢獻=分塊中一類長度為len的塊的貢獻+(所有詢問的區間長之和-分塊中一類長度為len的塊的貢獻*相應的塊長len)。因此我們只要統計出分塊中一類長度為len的塊的貢獻即可算出答案。

一個長度為len的塊[l,r]的貢獻=所有滿足$l_q<l,r<r_q$的詢問$[l_q,r_q]$的個數，因此這是一道二維偏序（sort維護r，樹狀數組維護l（因為樹狀數組適于維護$l_q<l$的偏序關系））的題目。
1. 將所有塊以塊長信息存儲在該塊的右端點。$O(N\log N)$
2. 將所有詢問按右端點排序。
3. 從n到1依次枚舉塊的右端點r，先把詢問區間右端點大于一類右端點是r的塊的詢問加入樹狀數組記入貢獻$O(MlogN)$，再把儲存在右端點r的每個塊查詢所有包含該塊（兩端點不重合）的詢問區間（由于二維偏序維護（所有在樹狀數組的詢問區間的右端點$r_q$一定大于r（因為小于等于的還沒有加入，sort維護），只需要查詢樹狀數組中的所有左端點$l_q$小于l詢問區間的個數），此時一定補充不漏）的個數記入長度為len一類塊的貢獻ans[len]$O(NlogNlogN)$。
4. 一類長度為len的塊的答案=分塊中一類長度為len的塊的貢獻+(所有詢問的區間長之和-分塊中一類長度為len的塊的貢獻*相應的塊長len)。

int n,m;
LL ans[N],totlen;//ans[len]：分塊中一類長度為len的塊的貢獻；totlen：所有詢問的區間長之和
vector<int> block[N];//將所有塊以塊長信息存儲在該塊的右端點
struct Query
{
    int l,r;
    
    bool operator < (const Query &q) const//sort維護r，將所有詢問按右端點排序
    {
        return r>q.r;
    }
}que[N];

LL tr[N];//樹狀數組維護l

int main()
{
    n=read(),m=read();
    for(int len=1;len<=n;len++) for(int r=1+len-1;r<=n;r+=len) block[r].push_back(len);//將所有塊以塊長信息存儲在該塊的右端點，O(NlogN)
    for(int i=1;i<=m;i++)
    {
        que[i].l=read(),que[i].r=read();
        totlen+=que[i].r-que[i].l+1;
    }
    sort(que+1,que+m+1);//將所有詢問按右端點排序
    for(int r=n,i=1;r>=1;r--)//從n到1依次枚舉塊的右端點r
    {
        while(i<=m && que[i].r>r)//先把詢問區間右端點大于一類右端點是r的塊的詢問加入樹狀數組記入貢獻
        {
            add(que[i].l,1);//樹狀數組，先把詢問區間右端點大于一類右端點是r的塊的詢問加入樹狀數組記入貢獻，O(MlogN)，O(MlogN)
            i++;
        }
        for(auto len : block[r]) ans[len]+=ask((r-len+1)-1);//樹狀數組，查詢樹狀數組中的所有左端點l_q小于l詢問區間的個數，再把儲存在右端點r的每個塊查詢所有包含該塊（兩端點不重合）的詢問區間（由于二維偏序維護，此時一定補充不漏）的個數記入長度為len一類塊的貢獻ans[len]，O(NlogNlogN)
    }
    for(int len=1;len<=n;len++) printf("%lld ",ans[len]+(totlen-ans[len]*len));//一類長度為len的塊的答案=分塊中一類長度為len的塊的貢獻+(所有詢問的區間長之和-分塊中一類長度為len的塊的貢獻*相應的塊長len)
    return 0;
}

虛樹

我是A題

把題目轉化為給定若干個對頂點為(a,b,c)的直棱柱，求總體積。

觀察給定代碼會發現：三元組有$\frac{2}{9}$的概率會出現(A,<B,<C)，有$\frac{2}{9}$的概率會出現(<A,B,<C)，有$\frac{1}{9}$的概率會出現(A,B,<C)，剩下$\frac{4}{9}$的概率會出現(<A,<B,C)。

對于三元組(A,B,<C)的體積是很好算的——大長方體。出現至少一個三元組(A,B,≥C-50)的概率是$1-(1-\frac{50}{3*10^7})^{3*10^7*\frac{1}{9}}=0.996134098$。因此在大長方體上面最多只有50層體積。

這50層體積暴力一層一層算，把三維問題轉化為二維問題：將三元組（現在只用關心A和B）按照A排序，從大到小掃，記錄長方形的右邊界，當當前的三元組的B大于右邊界時，體積增加；否則根據單調性體積不增加。

除此之外，測試點1~2由于數據范圍小，出現(A,B,≥C-50)的概率小，但是高度≤100，用上面的做法暴力一層一層算也是沒有問題的。
線段樹

構造+線段樹的結構分析

以樣例為例，圖中每個點標有深度（到最遠葉子節點的距離$+1$），由于線段樹接近完全二叉樹，所以最大深度是31（而不是$30$（$2^{30}>10^9$）！！！），保證了時間復雜度。

每次add操作相當于是從根節點到葉子節點選一條鏈，已經選過的點不能加入貢獻（換言之，每次add操作相當于是從最上面到葉子節點選一條鏈，選擇的鏈不能相交）。

一個正確的貪心：每次都選擇一條對當前貢獻最多的鏈。

對于樣例，第一次選擇深度為$6$的一條鏈。第二次選擇深度為$5$且不包含于第一條鏈的一條鏈。第三次由于深度為$6,5,4$的鏈都被包含了，選擇深度為$3$且不被包含的一條鏈……

假設我們求出了$cnt[depth]$：深度為$depth$的點的個數。然后我們從大到小遍歷深度$depth$，若$cnt[depth]\geqslant 1$，則選擇一條深度為$depth$的鏈，并令$cnt[1\sim depth]\leftarrow cnt[1\sim depth]-1$，因為選擇了一條深度為$depth$的鏈就會使得深度為$1\sim depth$的鏈各$1$條被包含。

實際上我們每選擇一條深度為$depth$的鏈不需要在線令$cnt[1\sim depth]\leftarrow cnt[1\sim depth]-1$，可以在求出了$cnt[depth]$后費用提前計算for(int i=1;i≤max_depth;i++) cnt[i]-=cnt[i+1];，然后從大到小遍歷深度$depth$，若$cnt[depth]≥1$，則把$depth$加入貢獻并令$k$減$1$，直至$cnt[1]=0$或$k=0$。這一部分的復雜度是$O(\lceil\log_2 m\rceil)$。

for(int i=1;i<=31;i++) cnt[i]-=cnt[i+1];
int cidx=31;
while(k && cidx>=1)
{
    ans+=min(k,cnt[cidx])*cidx;
    k-=min(k,cnt[cidx]);
    cidx--;
}
printf("%d\n",ans);

所以我們怎么快速求出$cnt[depth]$呢？很明顯這個只與$m$有關。因為$m$確定了，線段樹的形態就確定了。

線段樹是九條可憐很喜歡的一個數據結構，它擁有著簡單的結構、優秀的復雜度與強大的功能，因此可憐曾經花了很長時間研究線段樹的一些性質。——[ZJOI2017]線段樹

于是我們就可以非常開心的打表找規律了。

m= 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
depth=1節點數: 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
depth=2節點數: 0  1  1  2  2  2  3  4  4  4  4  4  5  6  7  8  8  8  8  8  8  8  8  8  9 10 11 12 13 14 15 16 16 16 16 16 16 16 16 16 
depth=3節點數: 0  0  1  1  1  2  2  2  2  2  3  4  4  4  4  4  4  4  4  4  5  6  7  8  8  8  8  8  8  8  8  8  8  8  8  8  8  8  8  8 
depth=4節點數: 0  0  0  0  1  1  1  1  1  2  2  2  2  2  2  2  2  2  3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  5  6  7  8 
depth=5節點數: 0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  3  4  4  4  4  4 
depth=6節點數: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  2  2  2  2  2  2  2

于是我們就可以寫出函數get_cnt(int m,int depth)：求出值域為$[1,m]$的線段樹深度為$depth$的節點數。這一函數的復雜度是$O(1)$的。

int get_cnt(int m,int depth)
{
    if(depth==1) return m;
    int len=p2[depth-2]+1;
    if(m<len) return 0;
    int logm=__lg(m/len);
    int r=p2[logm+1]*len;
    return max(p2[logm],p2[logm+1]-(r-m));
}

總的時間復雜度$O(T\lceil\log m\rceil)=O(31*T)$，常數很小輕松通過。

代碼。

posted @ 2025-10-14 01:06 Brilliance_Z 閱讀(17) 評論(0) 收藏舉報

刷新頁面返回頂部

BrillianceZ

實踐

思維題