誠、意地の悪い神の所業か？
奇跡？縁？袂觸合う不思議
花ひとひら揺れて
不意に宿ってた
うなじ解いてく春風
戯れはそこそこに
戀手ほどきしてくだしゃんせ
湯気にほんのり頬染て
夜風に愿ふ
…いざ！！蝶と舞ひ花となりて
衣を亂して祓いましょう
あやなしココロの穢れ
…故！！刀となり楯となりて
この想ひ護り賜え
君が戀の門を殺めた
戀の罠は密やかに仕掛けなきゃ
次の一手すけすけだから困る
鍛錬じゃどうにもなんない
揺れる心模様
どっちが先だ？戀煩ひ
覚悟してとおりゃんせ
夜道と乙女にご用心
湯気の香り漂わせ誘う夜宴
…実に！本日はデェト日和
しどけなく誘いましょ？
憑きませ偲ぶ戀夢…
故！靜となり動となりて
我を導き賜え
君の剣がハァトを射抜いた
…いざ！！蝶と舞ひ花となりて
衣を亂して祓いましょう
前世から繋がる運命
…故！刀となり花と生きて
この愛護り賜え
君はもう縁に選ばれた

基礎數據結構進階

1. 平衡樹合并：

   其實是非常簡單的，就是每次欽定堆值大（也可以是小，看自己的排序方式）的作為根，用其鍵值切（就是 split）另一個樹，分別和左右子樹遞歸即可。

   void frg(int a,int b,int &t){
   	if(!a||!b) return t=a|b,void();
   	if(rd[a]>rd[b]) swap(a,b);
   	t=a,spl(a,b,b,vl[a]);
   	frg(lson,a,lson),frg(rson,b,rson);
   	Upd(t);
   }
   

   復雜度分析可以參考 this，大概是在加、減、除、根號時是單 \(\log\)，取模是雙 \(\log\)

   但是拿這個做線段樹合并是 \(log^2\) 的，具體的，考慮一次合并 \(k\) 段相交值域是 \(k\log n\) 級別的，顯然可以構造一棵完全二叉樹滿足一共有 \(n\log n\) 段值域，讓每一層都有 \(n\) 的貢獻，就是形如 \(1,3,5\) 和 \(2,4,6\) 這樣的。

2. 線段樹雙半群：

   眾所周知，線段樹可以維護半群。

   主要維護兩個群 \(I,T\) 分別表示信息和標記，考慮三個方面，\(I+I\)、\(I+T\)、\(T+T\)。

   一般的 \(I+I\)、\(I+T\) 比較好做，主要是 \(T+T\)，可以一直新加標記嘗試維護，但很麻煩。

   有簡單點的做法，考慮矩陣，矩陣天然滿足結合律，但是有個比較大的常數。

   可以將矩陣拆開，只維護有用的位置，這樣就和標記一樣了。

3. 兔隊線段樹：

   用來維護兩個 \(\min/\max\) 套起來的問題，一般里面的是前后綴，可以帶修。

   經典引入是 P4198 樓房重建

   現求斜率并離散化，問題變為求 \(\sum\limits_{i=1}^n[s_i>\max_{j=1}^{i-1}\{s_j\}]\)

   考慮在 \(l,r\) 上維護最大值 \(max\)，只考慮本區間，即不考慮 \([1,l)\) 的貢獻的和 \(cnt\)。

   考慮合并，發現 \((min,r]\) 只會被 \(\max_{i=l}^{mid}{s_i}\) 影響，于是用 \(calc(i,pre)\) 表示受 \(pre\) 影響后 \(i\) 子樹內的貢獻。

   引用小粉兔的偽代碼。

   \[\displaystyle \begin{array}{l} \textbf{def: } \mathrm{calc}(i, pre) \\ \qquad \textbf{if } (i \text{ is a leaf node}) \\ \qquad \qquad \textbf{return } {\color{green}{[\max[i] > pre]}} \\ \qquad \textbf{else} \\ \qquad \qquad \textbf{if } (\max[\mathrm{leftchild}[i]] > pre) \\ \qquad \qquad \qquad \textbf{return } {\color{blue}{\mathrm{calc}(\mathrm{leftchild}[i], pre)}} + {\color{red}{(\mathrm{cnt}[i] - \mathrm{cnt}[\mathrm{leftchild}[i]])}} \\ \qquad \qquad \textbf{else} \\ \qquad \qquad \qquad \textbf{return } {\color{blue}{0}} + {\color{red}{\mathrm{calc}(\mathrm{rightchild}[i], pre)}} \\ \qquad \qquad \textbf{endif.} \\ \qquad \textbf{endif.} \\ \textbf{enddef.} \end{array} \]

   藍色是左子樹，紅色是右子樹。

   容易發現在統計貢獻時用到了差分，考慮不用可差分性。

   更改節點維護信息，在 \(l,r\) 上只維護右子樹的貢獻，\(calc\)意義不變。

   \[\displaystyle \begin{array}{l} \textbf{def: } \mathrm{calc}(i, pre) \\ \qquad \textbf{if } (i \text{ is a leaf node}) \\ \qquad \qquad \textbf{return } {\color{green}{[\max[i] > pre]}} \\ \qquad \textbf{else} \\ \qquad \qquad \textbf{if } (\max[\mathrm{leftchild}[i]] > pre) \\ \qquad \qquad \qquad \textbf{return } {\color{blue}{\mathrm{calc}(\mathrm{leftchild}[i], pre)}} + {\color{red}{\mathrm{cnt}[i]}} \\ \qquad \qquad \textbf{else} \\ \qquad \qquad \qquad \textbf{return } {\color{blue}{0}} + {\color{red}{\mathrm{calc}(\mathrm{rightchild}[i], pre)}} \\ \qquad \qquad \textbf{endif.} \\ \qquad \textbf{endif.} \\ \textbf{enddef.} \end{array} \]

   查詢時調用 \(calc\) 即可。

   例題：P7230 [COCI2015-2016#3] NEKAMELEONI

   首先發現，對于一個右端點，其左端點一定是右端點以后的數的 \(pre\) 的最小值，設 \(A_i=pre_{i+1}\)，若不存在就設為 \(-n\)，于是問題就變成了求 \(\min_{i=1}^n\{i-min_{j=i}^n\{A_j\}+1\}\)

   直接套兔隊線段樹即可。