各種code分享

裡面放了我寫過的Online Judge的 code ，還有一些模板，之後應該會比較少增加東西了。
連結

[HOJ 284] PE Lesson

作法：

我們先觀察：對於一個排列，要怎麼判斷他是否可以在有限的交換次數內換回來。我們知道一個排列可以拆成很多圈，因此只要把這些圈分開研究就可以了。首先我們可以證明：對於每個圈，他能夠換完並且滿足限制的充要條件為：圈上的只能換一次的人數$\leq 2$。從右推到左不難，只要構造出一種換法就可以了。至於從左推到右，首先我們可以數歸出：對於一個大小為$k$的圈，至少要換$k-1$次才能把所有數歸位。而當作一次交換動作時，相應的兩個人的限制值都會減$1$，也就推得了所有人的限制值總和必須$\geq 2k-2$，所以至多有兩個人只能換$1$次。

另外再注意到，其實重要的只有有多少人能換一次，和有多少人能換兩次而已。因為我們可以任意交換兩人的 index 和限制值而不影響答案。因此現在問題變成：給定$x,y$（代表輸入中有$x$個$1$和$y$個$2$），找出滿足以下條件的$1,...,x+y$的排列個數：排列中的每個圈至多有兩個$1,..,x$之中的數。而這可以先想到一個DP的作法，也就是令$dp[x][y]$為所求的答案，那麼有邊界$dp[x][y]=(x+y)!$當$x\leq 2$。再來看要怎麼求$dp[x][y]$，考慮$x$這個數所在的圈，分成兩種可能：這個圈有$1$個或$2$個$1,...,x$之中的數。枚舉這個圈中用到了幾個$x+1,...,x+y$之間的數就可以得到轉移式：
$\displaystyle dp[x][y]=\sum_{i=0}^{y}dp[x-1][y-i]\frac{y!}{(y-i)!}+$$\displaystyle (x-1)\sum_{i=0}^{y}dp[x-2][y-i]\frac{y!}{(y-i)!}\cdot (i+1)$

可以先寫個程式算出這個DP表格，觀察前幾項可以發現：$\displaystyle dp[x][y]=dp[x][0]\cdot \frac{(x+y)!}{x!}$，所以只要遞推出$dp[x][0]$再計算答案就可以了。至於上面這條的證明就只要直接代入轉移式數歸，然後把組合級數化簡就可以了，詳細過程在這裡省略。

code :

[HOJ 283] Grid coloring

作法：

當$k=1$時作法是顯然的。接下來我們構造只要兩種顏色就可以滿足$\frac{3}{4}$以上的方法。首先把第一列按照不違反左右限制的方法塗完。並且最左邊行和最右邊行的格子的塗法為滿足他和他上面那個格子的限制為準。剩下的格子由上往下一列一列填，同列時由左往右填。假設當前格子為$A$，左邊格子為$B$，上面格子為$C$，右上方格子為$D$，那麼$B$會透過$A$左邊界的條件來限制$A$要放什麼，$C$則是透過上邊界，$D$則是得往下走再往左走來限制。如果這三個限制條件是一樣的話就直接放上那個顏色即可，否則一定有兩個限制條件的顏色一樣，選那個顏色塗即可。而證明也不難，只要發現到連續使用兩次上述塗法至多會跑出一個不合法的地方就可以了。

這題原本是codeforces的題目，官方解和我的不太一樣，也可以參考看看。

code :

[HOJ 282] Empire disruption

作法：

首先注意到，對於每個計劃的相鄰兩個給定的城市，只要$x+y$的值比兩個城市之間的距離左右還大，那麼這兩個城市佔領的區域就會重疊。並且當兩相鄰城市佔領的區域重疊時，他們所佔領的總城市數就會是這兩個城市之間的城市數（含端點）加上$x+y$（不考慮左右邊界的話）。因此我們可以按照詢問的$x+y$值從小到大排序，每次如果發現有相鄰城市佔領的區域重疊了，就把他們黏起來。於是現在會變成有很多被黏起來的相鄰的城市們，我們需要知道總共有幾陀，還有這些城市區間內部的城市數量是多少。而這只要對於每一陀被黏起來的的城市，假設他最左和最右的城市分別是$X$和$Y$好了，那麼就用兩個陣列$le,ri$紀錄好$ri[X]=Y$，還有$le[Y]=X$就可以了。實作上我是將所有的兩個相鄰的給定城市之間的距離 sort ，還有詢問當然按照$x+y$值sort，並且當遇到一個詢問時把所有該黏起來的城市黏起來就可以了。最後要記得考慮超出邊界的問題，這只要用$a[1],a[n]$和當次詢問的$x,y$值就可以判斷了。

code :

[HOJ 278] Many Prizes

作法：

我們只要知道一個人最好是可以到多少，還有最差可以到多少，就可以分別對兩個答案二分搜了。首先看一個人最好可以到多少，最佳情形當然是他剛好一直遇到比他弱的，所以一直贏，直到沒有人比弱為止開始一直輸。假設現在比他弱的人有$x$個，那麼不難得出下一輪比他弱的只會剩$\left \lfloor \frac{x-1}{2} \right \rfloor$個，因此只要一直除下去直到這數字變$0$為止，就知道他可以連續贏幾場了。並且一個人的最差狀況則是一直輸，最後再一直贏，也可以用類似的方法求出會先輸幾場才開始一直贏。

code :

[HOJ 272] 出納員的僱用

作法：

考慮二分搜答案，那麼問題就會變成是否恰好僱用$X$個人並滿足條件。記我們在每個小時僱用的人為$x_1,...,x_{24}$，將他循環延長$7$個，也就是變成$x_1,...,x_{31}$，其中$x_i=x_{i+24}$，那麼我們就可以列出一些條件：首先當然是僱用的人數不能超過給的人數，也就是$x_i\leq num[i]$，其中$num$代表這個時間可以請的人數。還有剛才提到的$x_i=x_{i+24}$，並且因為能夠在某個時間$i$工作的人們開始工作的時間可能會是$i-7,...,i$，也就是這些時間請的人數必須$\geq$需要的人數，因此可以列出$x_{i-7}+...+x_i\geq need[i]$，其中$need$陣列一樣以 $24$ 一循環。不難將這些條件改為前綴和的條件，也就是令$S_i=x_1+...+x_i$，那麼$x_i=x_{i+24}$的條件可以改寫為$S_{i+24}=S_i+X$，其中$X$是前面我們二分搜的值（也就是$x_1+...+x_{24}=S_{24}$），剩下的條件則是顯然的。這樣就可以用差分約束解他了，把圖建出來用 Bellman-Ford 判他有沒有負圈就可以了。

code :

[HOJ 247][IOI 2008] Islands

作法：

首先當然是把所有連通塊分開看，這題簡單來說就是要找水母圖上的最長路（無向的），我們先找出這張水母圖的圈在哪裡，找法從隨便一個點開始沿著他唯一連出去的邊一直走，走到重複的點為止，就找到一個圈了。水母圖上的最長路分兩種，一種是沒有經過圈上的邊的，一種則是有的。對於前者，我們可以枚舉水母圈上的點，考慮這個點連往非水母圈的邊的那些點們，會形成一棵子樹，對這個子樹求最長路徑就可以了。至於經過水母圈上的邊的路徑，因為顯然如果我們已經決定好路徑和水母圈的交集的兩端點的話，剩下就取這個端點往他的子樹方向走過去的最長路就可以了，因此在回傳子樹內部的最長路時要順便回傳子樹根往下走的最長路。於是我們現在有圈上每個點往樹方向走下去的最長路了（以下稱為$val$值），還有圈上每條邊的長度，要求的是「兩點之間的距離$+$兩點的$val$值」的最大值。考慮把圈壓成序列，也就是如果原本圈上的點為$A_1,...,A_k$，考慮序列$A_1,...,A_k,A_{k+1},...,A_{2k-1}$，其中$A_{i+k}=A_i$，並且相鄰點的距離就和原本圈上連接這兩點的距離相等，記$dis[i]$代表$A_1$往右走到$A_i$的距離，和$val[i]$代表$A_i$的 val 值（最長路長），那麼我們要求的東西就是：$(i,j)$滿足$dis[i]-dis[j]+val[i]+val[j]$最大，其中$i-j<k$。因此當固定$i$的時候，我們需要的東西就會是$max\{ val[j]-dis[j] \}$，其中$j=i-k+1,...,i-1$。於是這就可以用 deque 優化在線性的時間內求出來了。

最後我傳上去 MLE 了，載測資來看發現那兩筆是DFS會到$10^6$層左右的，後來我把DFS改成自己用 stack 作才過的，感覺 IOI 沒必要這樣卡記憶體阿OAO......

code :

[CF 559E] Gerald and Path

作法：

我們把一個路燈想像成一根直立的棍子，長度為他可以照到的範圍，那麼現在就變成我們要決定他們要往左倒還是往右倒，使得總覆蓋區間最大。假設現在我們已經全部決定好了，那麼倒下的棍子們會形成好幾陀連通塊（若兩根棍子有交集則在他們之間連邊，考慮這張圖可以獲得一些連通塊），首先不難發現每個連通塊一定都是由連續的棍子所組成的，因此我們可以考慮先求出$dp[i][j]$，代表「從第$i$根到第$j$根棍子倒下後若形成一個連通塊，那麼這個連通塊有哪些可能的左右端點」，也就是一個$dp[i][j]$其實一個 vector<pair<int,int>>，裡面存了很多條線段。這邊可以再發現，如果有兩條線段是互相包含的關係，那麼顯然外面的一定比裡面的還好，因此我們可以只留下必要的線段就可以了，也就是當左端點遞增時右端點也遞增的線段們。不難得知如果我們已經有了所有的$dp[i][j]$的線段，那麼最後就可以再用個DP求出答案了，因此接下來只要關注如何轉移就可以了。

首先當$i=j$的時候顯然有兩個線段，丟進去即可。假設現在我們要算$dp[i][j]$有哪些線段，我們可以先把一些候選的線段丟進$dp[i][j]$中，最後再一次處理掉剛才所說的「被別人包含的線段」。考慮枚舉斷點$k$，那麼我們現在有$dp[i][k]$的一堆線段，還有$dp[k+1][j]$的一堆線段，我們想要用他們合成出新的線段。我們可以先假設$dp[i][k]$裡的線段是被放在左邊的線段，因為可以等一下把$dp[i][k]$和$dp[k+1][j]$交換再作一次即可。考慮枚舉$dp[i][k]$中的線段，當左邊的線段確定後，因為$dp[k+1][j]$中的線段都是當左端點遞增時右端點也遞增的，因此我們只要想辦法找到$dp[k+1][j]$中「和此左線段有交集的右端點最大的線段」就可以了，這可以用一個 lower_bound 達成。這樣轉移複雜度為$O(n^2logn)$，總複雜度為$O(n^4logn)$，不過在 codeforces 上跑得很快，可能是因為線段數量沒有到每個 dp 陣列都$O(n)$那麼多。


code :

[CF 559D] Randomizer

作法：

題目要求的是任取一個子多邊形的內部格點數期望值，顯然必須先使用 Pick's 定理，因為我們有$A=i+\frac{b}{2}-1$，所以我們只要知道子多邊形的$A$值期望值，和$b$值期望值就可以了。首先看$A$值的期望值，對於每個子多邊形，如果我們用整個多邊形去扣掉他，那麼他就會剩下一堆「頂點是原多邊形中的連續幾個點」的子多邊形。因此我們只要先算好要扣掉部份的期望值，再用原本的整個面積去扣掉就可以了。至於要如何算扣掉的部份，對於一個「頂點是原多邊形上連續幾個點」的子多邊形來說，假設他總共有$i$個頂點，那麼不難算出他總共會被算到$2^{n-i}-1$次，並且總共有$2^n-1-n-C_2^n$種子多邊形，因此有$i$個頂點的子多邊形貢獻為$\displaystyle \frac{2^{n-i}-1}{2^n-1-n-C_2^n}\times$其面積。這樣我們可以先獲得一個$O(n^2)$的算法：直接把每一項都加起來，並且在算「有$i$個頂點的子多邊形的面積總和」時可以用$i-1$個頂點的總和花$O(n)$的時間推過來。但觀察這條式子可以發現，當$i$越來越大時其倍率是指數往下跑的，因此我們可以只計算$i$很小的前幾項就好了，稍微估一下大概可以知道一直算到$i=100$左右就很夠了。

再來則是計算$b$的值，我們可以把每條邊拆開看，每條邊的貢獻會是$gcd(x$座標差$,y$座標差$)$（這樣算才能保證把子多邊形的每個邊的貢獻加起來是我們要的值），並且我們想知道他會被算到幾次。假設以這條邊切開原多邊形，所得到的子多邊形其中一邊有$k$個點，那麼不難得出他被算到的次數為：$(2^{n-2-k}-1)+(2^k-1)$，因此我們可以把他拆成兩邊看，也就是我們把主角放在「原多邊形的一段頂點區間」而不是「邊」，這樣就可以套用剛才的作法了，只要考慮那些「頂點區間夠小」的區間就可以了，也是取到長度$100$左右就很夠了。

code :

[CF 559B] Equivalent Strings

作法：

首先我們可以證明，題目給的等於的定義是一個「等價關係」（equivalence relation），可以對字串的長度用數學歸納法即可，因此不難證明，兩個字串是等價的若且唯若：把兩個字串都換成與他等價的字典序最小的字串，兩字串相等。而這個過程就可以用分治來解決了。

另外，這題有很多人直接寫了$O(n^2)$的解卻過了（也就是直接遞迴檢查$4$種可能的子字串配對），例如這份 code 的寫法，實際上可以證明這樣的複雜度其實是$O(n^{1.57})$的，詳細可以參考這篇 comment 。

code :

[HOJ 251][IOI 2008] Pyramid Base

作法：

首先考慮二分搜答案，因為如果能夠在預算內放入邊長$x$的正方形，那顯然可以放入邊長$x-1$的正方形。當確定一個邊長時，我們想要知道他可不可行，而只要注意到：我們只要決定好正方形的左上角就可以了，並且對於平面上的某個障礙物來說，考慮那些「用來當正方形左上角的話會和這個障礙物有交集的格子」，不難發現這些格子形成一個長方形（其座標不難求），因此就可以想成：如果左上角放在這個長方形裡，就要多花（這個長方形的 cost ）元。並且我們想知道這個平面上花費最少的格子是否在預算之中。因此就轉換為經典問題了：給定平面上的一些長方形，每個長方形都把內部的格子同加某個值，求整個平面的最小值是多少。這就顯然可以用掃描線+線段樹做了。

但這樣傳上去TLE了，畢竟$O(nlog^2n)$對$n\leq 400000$來說太大了。但注意到剩下只有$B=0$的情形，因此可以思考另外一種算法。考慮對於每個左界$i$，都找出最大的右界$j$，使得存在一個空的正方形，他的左右界分別為$i$和$j$。注意到如果我們把$i$到$j$這幾排全部壓成一排，並且「有和$i$到$j$交集的障礙物」都被壓成一排中的區間，那麼就變成詢問這一排中有最多連續幾個格子沒有障礙物了。因此我們可以把有交集到的障礙物的兩個$y$座標看成「把這兩數之間的所有數的位置的值都$+1$」，並且詢問的是這個數列裡有最多多少個連續的$0$，因此可以用線段樹做。這樣我們得到了$O(n^2logn)$的算法，也就是對於每個左界$i$直接一個一個往右擴展，當多遇到一個障礙物的左界，就在該區間$+1$的地方$+1$，直到查詢出來的值無法在兩邊界之間形成正方形為止。但只要注意到：如果存在一個正方形的左右邊界是$i,j$，那麼也存在左右邊界是$i+1,j$的。因此就可以改成用雙指標掃過去一次就可以了。複雜度降為$O(nlogn)$

最後提一下，這裡的線段樹必須支援：區間加$1$，區間減$1$和查詢最大連續的$0$數量，作法和「求$n$個矩形在平面上的覆蓋面積」時掃描線所用的線段樹類似，可以參考這篇。

code :

[HOJ 223] H. 項鍊

作法：

$m=1$時是顯然的，$m=2$不難自己構造出來，詳細可以參考 code 。但$m=3$以上的構造就很困難了，我的作法是直接 DFS 下去，剛好因為滿足這種條件的數列蠻多的，所以可以在時限內找到。比較正常的作法應該是把他轉成尤拉迴路問題：考慮一張有$n^{m-1}$個點的有向圖，每個點都代表一個長度為$m-1$字元集$1~n$的字串，並且如果某個點$A$可以經由「在後面加上一個數並丟掉最前面的數」轉換成$B$，那麼就從$A$連到$B$一條邊。這樣邊的總數會是$n^m\leq 3\cdot 10^5$，對這張圖求尤拉迴路就可以了。

code :

[HOJ 220] E. code

作法：

如果題目沒有$i\neq j$的條件的話，式子就可以寫成$\displaystyle (\sum_{i=1}^{n} n\% i)(\sum_{i=1}^{m} m\% i)$，因此這部份可以先分開算再乘起來。至於要怎麼計算$\displaystyle \sum_{i=1}^{n} n\% i$，一樣是把商一樣的區間合併起來看，因為$n$除以從$i$一直到$n/(n/i)$（這裡是整數除法）的這些數都會得到一樣的商，所以在這個區間裡$n\% i$會是一個等差數列，可以合併起來一起算。最後則是要扣掉$i=j$的部份，也就是要計算$\displaystyle \sum_{i=1}^{min(n,m)} (n\% i)(m\% i)$，這一樣可以用剛才的技巧，只不過區間的右端點必須取成$min(m/(m/i),n/(n/i))$而已。這部份則會變成一個二次函數在一個區間裡的所有函數值的總和，而這東西不難用$\displaystyle \sum k^2$的公式求得。

code :

[HOJ 218] C. osu!

作法：

首先找出圓和四條邊界的交點（如果有的話），那麼可以得到相鄰交點中間形成的弧同在矩形內部或外部，因此可以直接選這段弧的中點判斷他是在內部還外部，在內部的話就把答案加上對應的值就可以了。另外要注意圓和邊界完全沒有交點的情形，而這只要一開始就加入兩個假的斷點（$\frac{\pi}{2}$和$-\frac{\pi}{2}$）就可以了。

code :

[HOJ 201] TRAMPOLIN

作法：

首先我們可以把相鄰的同高度的大樓黏起來，並且紀錄好黏起來的這陀大樓原本有幾棟，而如果原本黏起來的大樓中有可以瞬移的大樓，那麼黏起來後的也可以瞬移。因此現在問題轉化為相鄰高度皆不同的問題。首先如出發點往左邊或右邊走都沒辦法達到能夠瞬移的大樓，那麼答案就是往左走或往右走的經過大樓數比較多的那個，反之假設起點可以走到某個可瞬移的大樓，那麼對於所有的制高點（旁邊沒有比他高的大樓的大樓），如果他往左（或往右）走下去之後會可以遇到能瞬移的，那麼我們就可以從起點那邊瞬移到這個制高點，走完這段後再順移回去。因此我們可以先找出所有的這樣的路徑，把他們標記成全部都可以走到。最後只要再選一個制高點然後走到底就好，枚舉看要走哪條路徑可以增加更多被走到的大樓。

code :

[HOJ 187] 小學老師

作法：

首先觀察有哪些數字的$f$值會變成$i$，會發現這就等價於這個數是$1,...,i-1$的倍數，但不是$i$的倍數。因此可以想像$10^{17}$範圍內的數字的$f$值都不會太大，因為$1,...,n$的最小公倍數成長的速度非常快。可以預處理出最大的$f$值只會到$41$，因此對於所求的值，對於每一項$L(i)$來說，可以先把他換成$L(f(i))+1$，這樣就只需要知道$[A,B]$之間有幾個數的$f$值等於$i$了（$i=1,...,41$），而這顯然用前面的等價條件就可以算了。

code :

[HOJ 160] 紅色警戒區

作法：

首先對於每個圓，求出他和其他所有圓的交點，那麼對於相鄰交點形成的弧上的任意點來說，他們的狀態都是一樣的，也就是他們同為邊界或同不為邊界（或是說交點們就是「斷點」）。因此只要取這段弧上的中點，去判斷他是否落在某個圓內部就可以了。另外要注意到，這樣會沒辦法判斷一個圓被另一個圓包住的情形，此時裡面的圓沒有任何斷點，因此要先對每個圓都加入$\frac{\pi }{2}$和$-\frac{\pi}{2}$這兩個斷點（以極角表示斷點）才能自動把他判掉。最後還要處理兩個圓重和的情形，在一開始就直接把重複的丟掉就可以了。

code :

[HOJ 164] 森森砍你的臉

作法：

考慮枚舉正方形左上角右下角所在的對角線，首先我們可以預處理出每個格子的$X$值和$Y$值，$X[i][j]$代表從$(i,j)$這格往右往下長度$X[i][j]$以內的格子都是$1$（或是$(i,j),...,(i,j+X[i][j]-1)$均為$1$，往下同理），$Y[i][j]$則是代表往左往上的，並且兩者都是取最大的值。那麼當我們枚舉一條對角線時，記這條對角線上第$i$格的$X,Y$值分別為$x[i],y[i]$，那我們想找的就是所有二元組$(i,j)$的數量（$i\leq j$），滿足$x[i]\geq j-i+1$，且$y[j]\geq j-i+1$。注意到這條式子中，不管怎麼樣當$i>j$時他一定會成立，因此我們可以把$i\leq j$這個條件拿掉，再扣掉多算到的部份就可以了。將上式移項得$i+x[i]\geq j+1$，$i\geq j+1-y[j]$，那麼就可以轉換成簡單的問題了：考慮平面上的$n$個紅點和$n$個藍點，其中第$i$個紅點的座標為$(i+x[i],i)$，第$i$個藍點的座標為$(i+1,i+1-y[i])$，求滿足「紅點的兩座標均$\geq$藍點的兩座標」的（紅點、藍點）的個數（或是說紅點包住藍點的點對數量）。這可以先把所有點按照$x$座標排序，再用個 BIT 查詢每個紅點包住了幾個藍點就可以了。

code :

[HOJ 199] KAMPANJA

作法：

考慮$d[A][B]$代表從$1$走到$A$走到$B$再走回$A$的路上最少可以經過幾個節點，那麼所求的答案就是$d[2][2]$。首先我們可以用 Floyd 求出任兩點之間的最短路（之後記為$dis[][]$），就可以先得到$d[A][B]$的一些初始值，並且由第一個範測可以觀察到：如果我們任取四個點$A,B,X,Y$，那麼$1\rightarrow X\rightarrow Y\rightarrow 1$實際上可以用$1\rightarrow  A\rightarrow  B\rightarrow  X\rightarrow  Y\rightarrow  A\rightarrow  B\rightarrow  1$來達成，也就是我們可以用$d[A][B]+dis[B][X]+dis[X][Y]+dis[Y][A]-1$來更新$d[X][Y]$的值。注意到上式中當$X,Y,A,B$不全相等時，$dis[B][X]+dis[X][Y]+dis[Y][A]-1\geq 0$，這就類似在求最短路的過程，因此我們可以直接套用 Dijkstra 求得答案。注意到這裡的 Dijkstra 不是用 priority_queue 優化的，而是優化前的「每次掃一遍所有的節點看誰目前距離最小，拿他來鬆弛其他人」，前者複雜度會變成$O(n^4logn)$，後者則是$O(n^4)$（因為這張圖是稠密圖）。

code :

[HOJ 128] Matching

作法：

我們一樣往KMP的方向想，首先我們會需要 fail 函數，回顧他的定義，$fail[i]$代表說「當已經匹配好$1,...,i$時，如果$i+1$失配，那麼要轉換成已經匹配好$1,...,fail[i]$的情形」，而這裡的匹配的定義根一般字串匹配不一樣，是要兩個子序列的「相對大小關係」一樣時則叫作匹配。因此回顧我們在算 fail 函數時的方法，假設當前要決定$i$的 fail 值，令$fail[i-1]=j$，那麼首先我們要判斷「$1,...,i$的長度為$j+1$的後綴」是否和「長度$j+1$的前綴」匹配（再次強調這裡匹配的定義不一樣），而這等價於：「在$x[i-j],...,x[i-1]$之中比$x[i]$小的數的個數」等於「在$x[1],...,x[j]$中比$x[j+1]$小的數的個數」，其中$x$為要求$fail$函數的陣列。因此就可以維護一個 BIT 來查詢所求的答案（因為會支援加數字和刪數字）。如果發現失配了就一樣沿著 fail 往回跳，直到長度變$0$或是匹配成功為止。由這裡就可以發現，其實 fail 函數建立的過程幾乎一樣，只是變成要多維護兩個 BIT ，並用 BIT 來查詢是否匹配成功而已。在和原數列匹配的過程也一模一樣（本來在原本的寫法中建 fail 函數和匹配的過程的程式碼就幾乎一樣了），失配就沿 fail 往前跳，維護好兩個 BIT 即可。最後要記得當找到一個地方成功匹配了模版串時也要沿 fail 往前跳，跟原本的 KMP 一樣。


code :

[HOJ 149] 改建路徑

作法：

我們考慮一個非常樸素的DP：設$dp[i][j]$代表目前已把前$i$個數弄成非嚴格遞增了，則第$i$個數的值為$j$的最小花費，那麼顯然可以寫出轉移式：$dp[i][j]=min\{dp[i-1][k]+|a[i]-j|,k=1,...,j\}$。想像一下$dp[i]$的函數圖形，那麼他就是由$dp[i-1]$先取前綴 min ，再加上$|x-a[i]|$這個函數所形成的圖形（前綴 min 的意思就是前面轉移式中的$min\{ dp[i-1][k],k=1,...,j \}$）。不難發現他其實會形成一個下凸包，並且轉折的點只會出現在$x$座標為原本$a$數列裡出現過的值，並且每次加上$|x-a[i]|$這個函數時，可以看成$a[i]$左邊的斜率全部$-1$，右邊的斜率全部$+1$，因此就可以用線段樹來維護斜率們（所以在這之前要先離散化$a[i]$），並且取前綴 min 的操作可以等價成：把斜率$>0$的部份都設成$0$（因為他會一直維持他是下凸包的良好性質），這也不難在線段樹上做到。最後我們想知道的是$dp[n]$這個函數圖形的最小值是多少，但線段樹中只有紀錄每個區間的斜率，因此只要再多紀錄函數在$0$的值是多少就可以了（而他顯然會是所有$a[i]$的和），從左到右掃一遍就可以獲得$dp[n]$圖形的每個轉折點的座標，取$y$座標最小的點就是答案了。

最後，在「把斜率$>0$的部份都設成$0$」的操作其實可以很簡潔的完成，我們可以對每個線段樹區間都維護他的最小值，那麼就可以直接從根走下去，發現如果當前節點的右孩子的最小值$>0$（其實也只有可能是$1$），就把右孩子全部$-1$，往左孩子遞迴，反之則往右孩子遞迴就可以了。

code :

[HOJ 156] Xor路徑和

作法：

首先我們當然可以只看和$1,n$連通的分量就好了。考慮隨便取一條$1$走到$n$的路徑，設其 xor 值為$X$，然後隨便取一個圖中的圈，假設他邊的 xor 值為$Y$，那麼就存在一條從$1$走到$n$的路徑，使得其 xor 值為$X\; xor\;  Y$。因為只要在走原本的路徑時，走到一半分出去走到圈上的某一個點，繞完一圈後再沿原路走回來，再繼續走到$n$就可以了。因此我們的想法為：隨便取一條$1$走到$n$的路徑，並且找出所有圖中的圈，那麼只要想辦法用這條路徑的 xor 值加上隨便取幾個圈湊出最大的 xor 值就可以了。但這樣顯然會遇到圖中的圈太多的問題，但其實我們可以只保留那些「沒辦法被之前找到的圈的值 xor 出來的圈」就可以了，具體來說，如果有個圈$C$的 xor 值為$X$，並且存在其他圈$C_1,...,C_r$其 xor 值分別為$X_1,...,X_r$，那麼當$X=X_1\; xor \; ... \; xor \; X_r$時$C$就沒有用了，因為如果取到他的話就可以直接把他換成$C_1,...,C_r$（或是說我們取的圈的值都是線性獨立的）。再來注意到，我們考慮一條一條把邊加到圖中，那麼當某條邊$AB$加進去並且形成了新的圈時，我們隨便取一條$A$到$B$的路徑，和新加的這條邊組成了一個圈，那麼（不難證明）在這個圖中所有新形成的圈的 xor 值都可以用這個新的圈的 xor 值和舊的那些圈的值 xor 出來，因此我們就可以獲得至多$m$個圈的 xor 值，並且要想辦法把他刪成線性獨立的（這樣就會不超過 $60$ 個了）。

我們先看要怎麼知道這些圈的 xor 值是多少，事實上我們可以在維護 disjoint set 的時候順便維護這個點沿著他父親走到根，路上經過的邊的 xor 值是多少，只要修改一下 find 的過程就可以了，詳細可以參考 code 。再來則是我們想把$m$個數（向量）刪成線性獨立的$\leq 60$個，這只要直接高斯消去就可以了，細節在此省略。有了這些線性獨立的向量後，剩下的問題是：給定一個數$x$（也就是我們任意取的$1$走到$n$的路徑的 xor 值），我們要想辦法用這些向量 xor 一個數，使得他和$x$的 xor 值盡量大。我們可以考慮由高到低一位一位確定答案，舉例來說，$x$的二進制為$110101$，並且我們已經知道能湊出的盡量大的值為$101***$（後面代表還沒確定），那麼接下來我們想知道能不能用那些向量湊出形如$0110**$的向量，就能確定答案的下一位了。確定這個的方法只要把所有已有的向量的最後兩位砍掉，並且去處理「給定一些向量，是否有辦法湊出給定的某個向量」的問題就可以了，作法當然就直接高斯消去就可以了。

code :

[CF 558E] A Simple Task

作法：

因為對一個區間正排序或逆排序後，所有同樣的字母都會擠在一起，因此就可以想到對每個字母分開維護，那麼對於特定一個字母就只要支援：把某段區間都設成不是這個字母，還有把某段區間都設成這個字母的操作，用個線段樹就可以輕鬆解決了。

code :

[CF 558D] Guess Your Way Out! II

作法：

因為每次獲得的條件都形如：某個區間裡的數有其中一個是答案，或是這個區間裡都不是答案。而對於後者可以改寫成：答案落在兩個區間的聯集中。這樣就可以用以下算法解決：如果我們獲得了某個區間裡的數有其中一個是答案的條件，就把這個區間裡的每個數的值都$+1$，而對於另外一種條件我們也把「兩個聯集起來裡面有答案的線段」裡的數值都$+1$，那麼不難發現全部加完$1$之後那些值變成$Q$的就會是答案的候選人了（$Q$是條件個數）。因此就可以用離散化來做了，把區間加值轉換成在起點有個事件是$+1$，最後一個點的後一格有個事件是$-1$，排序後掃過去就可以知道答案了。

code :

[LA 4454] Subway Timing

作法：

首先考慮二分搜答案，這樣變成對於一個給定的誤差$M$，是否有辦法把邊權都改成$60$的倍數，使得任兩點之間的距離誤差絕對值不會超過$M$。對於一個子樹來說，記他的根為$R$，假設有一種改邊權的方法，使得這棵子樹中任兩點之間的距離誤差絕對值不會超過$M$，並且$R$到這棵子樹中每個點的距離誤差最小值為$a$，最大值為$b$（這裡的誤差指的是「新的距離扣掉舊的距離」的值，有正有負，因此這裡顯然會有$a\leq 0,b\geq 0$），那麼這個設邊權的方法就只有$a,b$是跟之後決策有關的資訊了。也就是一個節點需要的 dp 值會是一大堆的$(a,b)$ 的 pair 。實際上我們可以不用把所有的$(a,b)$都紀錄起來，觀察到如果有兩個 pair $(a_1,b_1),(a_2,b_2)$，滿足$a_2\leq a_1$且$b_2\geq b_1$，那麼取$(a_1,b_1)$一定會比取$a_2,b_2$好，因此我們可以只維護$a$值和$b$值都嚴格遞增的 pair 們就可以了。

轉移比較麻煩，我們可以把題目轉成二元樹比較好DP。轉成二元樹的方法如下圖（對每個節點都做這種轉換即可），其中紅色的點是新加的點，左右圖中的藍色的邊的邊權是相等的，並且紅色邊的邊權為$0$。

轉成二元樹之後工作就只剩下合併兩個子節點的 dp 陣列了，假設當前節點為$x$，並且我們已經決定好$x$連向他兩個子樹的邊的新邊權了，記這兩條邊的誤差分別為$dx,dy$（也就是新邊權扣掉舊邊權的值），那麼考慮左子樹 DP 陣列中的某個$(a_1,b_1)$，還有右子樹中的某個$(a_2,b_2)$，這兩個 pair 分別都代表了他所在子樹的某個設置邊權的方法。接下來我們想知道把這兩個方法並在一起是不是可行的，並且如果可以的話要知道$x$的 DP 陣列必須多丟什麼 pair 進去。我們想要知道這兩個 pair 是否是可行的，而可行的充要條件就是任兩點距離的誤差絕對值$\leq M$。分成$x$到非根節點和左子樹中的點到右子樹中的點來討論，考慮前者則必須滿足：$|a_1+dx|\leq M,|b_1+dx|\leq M,|a_2+dy|\leq M,|b_2+dy|\leq M$。後者的話則必須滿足：$|a_1+a_2+dx+dy|\leq M,|b_1+b_2+dx+dy|\leq M$。並且如果$(a_1,b_1),(a_2,b_2)$都滿足前面那些條件的話，那麼$dp[x]$就會新增一個 pair ：$(min(a_1+dx,a_2+dy,0),max(b_1+dx,b_2+dy,0))$。

我們當然不能枚舉所有左右子樹形成的 pair 的二元組，注意到當我們固定$(a_1,b_1)$時，我們可以把上述條件全部整理成：$a_2\leq$一坨東西、$a_2\geq$一坨東西（$b_2$）亦同，這裡就可以利用這些 pair 的遞增性，可以得到第二個子樹中滿足那些條件的 pair 會落在某個區間中（如果我們已經把子樹中的 pair 們排好序了），而我們不難用二分搜找出這個區間。再觀察到新增的 pair 的式子，可以不妨設$a_1+dx\leq a_2+dy$，因為我們可以把兩個子樹交換再作一次，因此新增的 pair 的第一項的值已經確定了，並且我們知道此時第二項要越小越好，也就是 $b_2$ 越小越好，因此我們只要枚舉第一個子樹中的$(a_1,b_1)$，並且取剛剛找到的那個區間的第一個 pair 就可以了，拿他配上$(a_1,b_1)$去更新$dp[x]$即可（當然當這個區間不存在時就沒辦法更新）。

code :

[POI 17 Stage 3] Monotonicity 2

作法：

首先考慮一個樸素的算法：對於每個$i$，我們知道存在一些以$i$結尾的子字串是滿足題目要求的，那麼對每個子字串來說，都可以用他的長度去更新所有$i$之後的答案（依照這個長度時下一步應該要比$a[i]$大還是小，或是等於）。具體來說，如果有一個$i$結尾的子字串長度為$L$，並且$s[L]$為$<$，那麼就可以用$L+1$去更新$i$以後的值大於$a[i]$的位子的答案。這裡有個非常不顯然的結論，就是其實對於所有$i$結尾的子字串，我們只需要紀錄最長那個的長度就可以了！（證明補在後面），因此就可以用 DP 算出每個位子結尾的最長子序列長度了。具體來說，當算完$dp[i]$時，如果$s[dp[i]]$為$<$，那麼之後如果遇到有某個$>a[i]$的數，都要把他的答案和$dp[i]+1$取 max 。如果是$<$的話也一樣，因此這就可以用一個區間修改加上單點查詢的線段樹來作了。而因為要輸出解，所以在線段樹上會多紀錄說造成這個最大值的 index 是誰。

再來則是證明為什麼紀錄最長的就可以了，假設以$x$結尾有兩個滿足條件的子序列，長度分別是$L$和$l$，其中$L>l$。記兩個子序列的 index 分別為$i_1,...,i_L$和$j_1,...,j_l$（因此有$i_L=j_l=x$），並且不妨設$s[l]$為$<$（當$s[l]$為$=$時證法幾乎一樣，在此省略），並且此時$x$準備要拿$l+1$去更新$y$的答案。令$z=i_l$，如果$a[z]<a[y]$，那麼在我們前面算到$z$的答案時早就已經拿$l+1$去更新$y$的答案了，因此這個情況下長度$l$的這個子字串是完全沒有用的。反之如果$a[z]\geq a[y]$，由$s[l]$為$<$和$x$要拿長度$l$的子字串去更新$y$的答案可以推出$a[x]<a[y]$，所以有$a[z]\geq a[y]>a[x]$，推得$a[z]>a[x]$，因此考慮子序列$a[i_l],...,a[i_L]$，裡面一定存在相鄰的兩項使得左大於右，也就是存在一個 index $i_u$（$l\leq u < L$），滿足$a[i_u]>a[i_{u+1}]$（這也代表了$s[u]$為$>$）。我們取滿足這個條件的最小的$u$，不難發現$a[z]<a[i_u]$，因此有$a[i_u]>a[z]\geq a[y]$，因此當我們在算完$i_u$的答案時，就會拿$u+1$去更新$y$的答案了，所以在這種情況長度為$l$的子序列也是沒有用的，所以就可以直接不紀錄了。

code :

[TIOJ 1071] 字串消去問題(Censorship)

作法：

如果我們能計算出一個二維陣列$ok$，其中$ok[i][j]$代表$S[i,...,j]$是否可以恰好被完整刪除，那麼就可以用簡單的DP求出最後答案了。首先我們知道$S$中有許多子字串是可以「直接被刪除的」，也就是他剛好等於給定字串集合裡的其中一個字串。當我們把這種子字串刪掉時，有可能會造成新的子字串可以被刪掉。例如原字串為$caabbd$，並且可以刪掉$ab$，那麼在第二層就可以把$aabb$刪掉了，也就是$ok[2][5]=1$。我們可以概念上的稱「可直接被刪除的子字串」為一級的子字串，需要經過兩層才能刪除的為二級的子字串，那麼可知一個有辦法被刪除的子字串至多$n$層。因此我們要想辦法從$i$級的子字串的$ok$陣列推出$i+1$級的陣列，重複$n$次就可以得到我們要的$ok$陣列了。假設我們現在想知道$S[L,...,R]$這個子字串是否能在第$k+1$層時被刪掉，那麼考慮所有$S[L,...,R]$的可在第$k$層時被刪掉的子字串們，那麼$S[L,...,R]$可以在第$k+1$層時被刪掉若且唯若：存在$(l_1,r_1),...,(l_t,r_t)$滿足$L\leq l_1\leq r_1 < l_2 \leq r_2 < ... < l_t \leq r_t \leq R$，並且$S[l_i,...,r_i]$均可以在第$k$層被刪掉，還有把$S[L,...,R]$扣掉所有$S[l_i,...,r_i]$後所得到的字串是可以直接刪除的。有了這個之後就可以來算$S[L,...,R]$是否可以在第$k+1$層時刪除了。我們從$S[L]$開始往右邊掃，當遇到$S[i]$時，一個決策是：選一個$r$使得$S[i,...,r]$可以被刪除，那麼轉移到$S[r+1]$的狀態。另一個決策則是將$S[i]$放進一個「暫存字串」中，轉移到$S[i+1]$，並且我們想要在處理完$S[R]$時暫存字串是可以一次被刪除的（就和前面的條件等價了）。因此我們可以用一個 trie 節點搭配當前的 index 來做 DP 狀態，設 $dp[x][i]$ 代表只考慮字串$S[L,...,i]$時，是否可以讓「暫存字串」在 trie 上的節點為$x$，這樣就可以$O(1)$轉移了，總複雜度為$O(n^5)$。

code :

[TOI 2015 4模] P Game

題目：

給定一棵$n$個點的樹，每條邊都有個長度，然後有$Q$次操作/詢問，每次可以佔領一個點，或是詢問某個點到所有已被佔領的點的距離總和。$n,Q\leq 10^5$。

作法：

這題有兩種作法，第一種作法是用平方分割，因為如果是一次佔領完再全部詢問，那麼我們可以用 DFS $O(n)$ 求出每個點的答案，再$O(1)$回答詢問，詳細作法就不提了。而另外一種作法則是：把所有被佔領的點紀錄下來，每次詢問就直接去詢問給定點和所有被佔領點的距離總和，這樣一次的複雜度會是$O(被佔領點個數\cdot logn)$。於是我們考慮把兩種作法合併，當一個一個佔領點時，如果此時佔領的點還沒有那麼多，則直接用求距離再加起來的作法硬算，而當要硬算的點個數達到某個值（假設為$K$）時，就 DFS 一次把所有點的答案都更新好，這樣在詢問時我們就有了詢問的點到前$K$個被佔領點的距離總和了，剩下的部份就硬算即可。這樣可以得到單次詢問的複雜度為$O(Klogn)$，佔領一個點時因為我們不會 DFS 超過$\frac{Q}{K}$次，因此複雜度會是$O(\frac{Q}{K}n)$。由這兩式就可以知道取$K$讓$QKlogn=\frac{Q}{K}n$會是最好的，移項得$K=\sqrt{\frac{n}{logn}}$，總複雜度為$O(Q\sqrt{nlogn})$。但考試時不知道為什麼怎麼取$K$都TLE，後來乾脆取個$100$還$200$就莫名其妙的過了。

事實上可以做到單次詢問$O(logn)$，用的東西叫重心剖分，他的概念是先對原本的樹取重心，把樹分成很多個子樹，再對這些子樹遞迴下去取重心，並且將原樹的重心和其子樹們的重心連起來，這樣我們就得到了一棵重心樹（重心樹上的邊不一定在原樹上出現，但每個點都出現了），不難證明其深度會是$O(logn)$的（之後稱重心樹上的一個子樹為重心子樹）。因此當詢問一個點$x$的答案時，可以直接沿著重心樹往上走（因此要紀錄好每個點在重心子樹上的父親是誰），並在走的過程維護當前答案等於「$x$到當前重心子樹裡所有已被佔領點的距離總和」，這樣一路走到根就獲得答案了。接下來我們要知道如何維護好答案，記當前重心子樹為$T$，他的根$P$，還有如果只看原樹中這棵重心子樹裡的所有點的話，把$P$拔掉會讓他分成許多（原樹中的）子樹，稱其為$T_1,...,T_r$，並且不妨設$x$落在$T_1$裡面。那麼此時所求答案就必須要增加「$x$到所有$T_2,...,T_r$中被佔領點的距離」。這可以拆成兩部份，因為$x$走到這些點都必須經過$P$，因此如果假設在$T_2,...,T_r$中被佔領的點共有$t$個，那麼就可以把所求改成$t\cdot dist(P,x)+P$到$T_2,...,T_r$中被佔領點的距離總和（其中$dist$ 代表兩點在原樹中的距離）。對於前者，我們可以在預處理時，對於每個重心子樹，把他的根到所有他在重心子樹中的點的（在原樹中的）距離都存起來，這樣就能知道$dist(P,x)$了。再來則是要知道$t$，而這可以用「$T$中的被佔領點數扣掉$T_1$中的被佔領點數」得到，因此只要在多佔領一個點時沿重心樹走上去，維護好每個重心子樹中的被佔領點數就好了。最後則是要知道$P$到$T_2,...,T_r$中所有被佔領點的距離總和，這可以拆成「$P$到$T$中所有被佔領點的距離總和」扣掉「$P$到$T_1$中所有被佔領點的距離總和」，因此也只要在新佔領點時維護好這兩個值就可以了，都是利用到已算好的「重心到其子樹中某個點的距離」。

實作有很多寫法，但大部份都很麻煩，畢竟我們要存$P$的每個子樹的一些資訊，還有$P$到其子樹內每個點的距離。一個比較簡潔的記法是，首先我們先對每個點紀錄他是落在重心樹深度多少的地方，那麼如果我們想要紀錄某個重心$P$到某個點$x$的距離，就把這個值存在$dis[dep[P]][x]$裡面就可以了，其中$dep$代表這個點在重心樹上的深度，不難發現這個存法不會讓兩個要存的東西碰撞。再來也蠻麻煩的則是要存：對於每個重心$P$，紀錄他的每個子樹中被佔領的點離他的距離總和，而這也可以只用一個陣列來存，假設$P$在重心樹上落在$T_1$的子節點為$Q$，那麼就直接把$P$到$T_1$中被佔領點的距離總和存到$Q$的位子就可以了，也不難發現這樣不會碰撞。另外剩下的「$P$這個重心子樹中所有被佔領點到他的距離總和和有幾個被佔領點」當然只要存在$P$的位子就可以了。

code :

[POI 13 Stage 3] Palindromes

作法：

考慮把兩個不同的字串$S_1,S_2$接起來會形成回文，不妨設$|S_1|\leq |S_2|$，那麼不難推得他是回文的充要條件為：$S_1$是$S_2$的前綴，並且$S_2$的長度為$|S_2|-|S_1|$的前綴也是回文。因此我們可以考慮先建一個 trie ，那麼就可以得出：對每個字串$S$來說，有幾個字串恰好為$S$的長度為$i$的前綴。並且再用 manacher 處理一個字串的子字串是否為回文的詢問就可以了。但直接建 trie 會 MLE ，因為一個 node 存 26 個子節點太浪費了，於是我苦苦的把子節點的紀錄方式改成用 treap 才過，詳細就參考 code 吧。

code :

[POI 12 Stage 2] Template

作法：

首先求出每個點的 Z value ，假設$L$是一個答案，那就代表如果只看字串中那些 Z value $\geq L$的位子，這些位置的相鄰位置的差不會超過$L$。因此我們就可以考慮由小到大枚舉$L$，維護好當前有哪些位置的 Z value $\geq L$，並維護相鄰位置的差的最大值，用可以用個 set 做到這件事。每次把新的數移除的時候就看看他的左右兩個數，並拿這兩個數的差來更新當前的相鄰位置差的最大值。不過實際上用個 linked list 就可以了，複雜度降為$O(n)$。

code :

[POI 19 Stage 3] Prefixuffix

作法：

假設長度為$L$的前綴後綴為答案，那麼可以知道一定存在一個$k$，使得$S[1,...,k]$和$S[n-k+1,...,n]$長的一模一樣，並且$S[k+1,...,L]$和$S[n-L+1...n-k]$一模一樣（跟題目條件等價）。前面的條件很好檢查，不管是用 hash 還是 Z value 都可以。至於後面那個條件，這時我們需要知道：給定一個$i$，找出最長的長度$L$使得$S[i,...,n+1-i]$這個字串的長$L$的前綴和長$L$的後綴長的一模一樣。也就是我們關心的是位子關於整個字串中點對稱的長的一模一樣的字串。具體來說就是一些$(x,y)$滿足$S[x,...,y]$和$S[n+1-y,...,n+1-x]$長的一模一樣。我們考慮枚舉$(x,y)$數對的中點，那麼可以先二分搜出以某個點為中點的話滿足條件的$(x,y)$最多可以擴展到哪裡（因為有個性質是$(x,y)$滿足的話$(x+1,y-1)$也滿足）。假設我們二分搜出了$(L,R)$這段區間是滿足的，也就是$S[L,...,R]=S[n+1-R,...,n+1-L]$，並且$(L-1,R+1)$不滿足，令$len[i]$代表最大的「滿足$S[i+1,...,n-i]$的長$len[i]$的前綴和長$len[i]$的」的數，那麼這時就要用$R-L+1$去更新$len[L-1]$，$R-L-1$去更新$len[L]$，以此類推直到更新的值$<0$為止。這樣就可以直接往左往右掃得到每個$len$值了，只要當我們收到「把$a$和$x$取 max ，把$a+1$和$x-2$取 max ，...」時在$a$上紀錄$x+2a$的值，並在掃描過程中維護好這個數的值的最大值就可以了。

code :

[POI 19 Stage 2] A Horrible Poem

作法：

考慮枚舉所求子字串的長度$L$，我們知道$L$是給定子字串長度的因數，所以可以只枚舉其因數就可以了。確定$L$之後，假設詢問的區間為$[x,y]$，那麼判斷這個$L$是否可以的方法就只要看$[x,y-L]$和$[x+L,y]$這兩個字串是否一模一樣就可以了，證明並不難。而只要用 hash 就可以$O(1)$判斷了，因此就得到了一個$O(logn)$的解。但這樣傳上去 TLE 了，而只要再注意到：假設詢問的區間中有$x_1$個$a$，那麼分的塊數也一定要是$x_1$的因數，這樣就又縮減一些可能性了。因此我們變成枚舉切的塊數，所有的可能會是某個數的因數，直接用$O(\sqrt{n})$的找因數方法就可以了。

code :

[CF 451E] Devu and Flowers

作法：

簡單來說就是要問滿足$a_1+...+a_n=s$的$n$元組$(a_1,...,a_n)$的個數，並且$a_i\leq f_i$。記「滿足$a_i>f_i$且總和為$s$的$n$元組集合」為$A_i$，那麼所求就會是「總和為$s$的$n$元組」個數扣掉$|A_1\bigcup ... \bigcup A_n|$，因此可以考慮用排容原理。首先看所求的第一項，直接用排列組合的公式可以得到等於$C_{n-1}^{n+s-1}$，這東西直接算就可以了。接下來要考慮$A_i$的部份，我們想要知道好幾個$A_i$交集起來的大小為多少。假設現在我們要算$|A_{c_1}\bigcap ... \bigcap A_{c_r}|$，那麼就是對於每個$i$，都有$a_{c_i}>f_{c_i}$，因此我們先把$s$分給$a_{c_1},...,a_{c_r}$各$f_{c_1}+1,...,f_{c_r}+1$個，剩下再用排列組合的公式算就可以了。因此排容的過程就可以用個 DFS 來做，詳細可以參考 code 比較清楚。

code :

[HOJ 329] Construct?!

作法：

假設我們交換的兩數分別為$x,y$，那麼對於那些數值不是落在$x,y$之間的數，交換之後並不會影響這些數和$x,y$之間的逆序數對數，不管這些數落在交換的兩位置的左右還是中間。對於那些數值落在$x,y$之間的數，只有當他的位子落在交換的兩數字位置之間才會影響逆序數對的數量。由此就可以推出，我們交換的兩個數一定是左邊大右邊小的，才可以讓交換後逆序數對減少越多。假設交換的兩數位置分別為$i,j$，數字則為$x,y$，那麼逆序數對的變化就會等於$2\times$位子落在$i,j$之間的介於$x,y$之間數的個數$+1$（還要加上交換的兩數形成的逆序數對）。這樣就可以轉化為平面上點集的問題了：把$(i,a[i])$看成座標平面上的點，那麼我們要的就是一個矩形的左上角和右下角，使得這個矩形內包含最多的點。考慮所有「左上方沒有點」的點，那麼不難知道所求矩形的左上角一定是取其中的某個點是最好的。同理所求的右下角是取「右下方沒有點」的點是最好的。我們可以$O(n)$找出所有的這樣的點（之後分別叫他們$X$陣列和$Y$陣列），所以現在我們得到了一個樸素的算法：在這些點之間枚舉左上角和右下角，計算其中包含了多少點。但這樣太慢了，我們反過來考慮一個點對哪些矩形有貢獻，對於某個點$P$，考慮所有落在$P$左上方的$X$陣列中的點，和落在$P$右下方的$Y$陣列中的點，那麼任取前者中的一個點和後者中的一個點形成的矩形都可以包住這個點，因此如果我們幫$X$陣列中的數編號$1,...,n_x$，$Y$陣列則編號$1,...,n_y$，那麼一個矩形就可以表示成一個平面上的點，以左上角的編號和右下角的編號來表示。並且我們把每個矩形內的點數寫在他對應的點上，那麼就可以用以下方式來得到所有點的數值：枚舉每個原題中的點，找出他對哪些矩形有貢獻，而被貢獻的這些矩形們的集合對應到的點就會形成一個矩形區域，並且我們需要把這個矩形區域中的點值都$+1$。於是這樣就轉換為新的問題了：平面上有好幾個矩形，問被最多矩形覆蓋的點被覆蓋了幾次，而這可以用個掃描線來做，只需要維護一個最大值線段樹，並支援區間加值操作就可以了。

code :

[CF 449E] Jzzhu and Squares

作法：

考慮一個斜的正方形，設他下面頂點指向右邊頂點的向量為$(x,y)$（也就是如果下端點是$(0,0)$，那麼剩下三個點的座標為$(x,y),(x-y,x+y),(-y,x)$），我們想要知道這個正方形裡面包含了幾個單位正方形，而一個著名的結論是：給定一個$n\times m$的方格表，那麼他的對角線會經過$n+m-gcd(n,m)$個格點。因此就可以用這個結論算出這個正方形包住了幾個單位正方形了：把這個正方形補成邊平形座標軸的正方形，並把他切成四個$x\times y$的長方形，還有中間邊長$|x-y|$的正方形。那麼就可以知道在四個長方形中分別包含了$\frac{xy-x-y+gcd(x,y)}{2}$個所求格子了，再加上中間的正方形$(x-y)^2$個，就共有$(x-y)^2+2(xy-x-y+gcd(x,y))=x^2+y^2-2(x+y-gcd(x,y))$個。並且注意到這種正方形因為要用長$x+y$的正方形包住他，所以會在原本給定的範圍裡出現$(n-x-y+1)(m-x-y+1)$次，其中$x+y\leq min(n,m)$。並且注意到我們也要算$x=0$的情況（上面通式也會對），但是不能也算$y=0$的，否則會重複算到。因此就可以把答案寫成：
$\displaystyle \sum_{x\geq 0,y>0,x+y\leq min(n,m)} (n-x-y+1)(m-x-y+1)(x^2+y^2-2(x+y-gcd(x,y)))$
考慮把$x+y$值相同的一起算，令$t=x+y$，那麼就可以改寫成：
$\displaystyle \sum_{t=1}^{min(n,m)}\sum_{x=0}^{t-1} (n-t+1)(m-t+1)(x^2+(t-x)^2-2t+2gcd(t,x))$
其中用到了簡單的$gcd$的性質：$gcd(x,t-x)=gcd(x,t)$。我們可以把所求的$gcd$的部份拆出來，也就是改寫成
$\displaystyle \sum_{t=1}^{min(n,m)}\sum_{x=0}^{t-1} (n-t+1)(m-t+1)(x^2+(t-x)^2-2t)+$$\displaystyle 2\sum_{t=1}^{min(n,m)}\sum_{x=0}^{t-1} (n-t+1)(m-t+1)gcd(t,x)$
首先第一項其實就是一個$t$的多項式，只是係數會有$n,m$之類的，因此我們可以先預處理好$t^i$的前綴和陣列，其中$i=1,...,6$，就可以在$O(1)$算出第一項了（或是借住電腦的力量直接把通式爆出來XD）。再來則是第二項，把$(n-t+1)(m-t+1)$乘開後會得到其實我們主要需要的東西就是$\displaystyle \sum_{x=0}^{t-1} gcd(t,x)$，還有$\displaystyle \sum_{x=0}^{t-1} t\cdot gcd(t,x)$和$\displaystyle \sum_{x=0}^{t-1} t^2\cdot gcd(t,x)$的前綴和陣列，而我們只要有辦法對每個$t$都算出$\displaystyle \sum_{x=0}^{t-1} gcd(t,x)$的值就可以了。記我們要求的這個陣列為$f$，我們看某個數$i$在哪些$gcd(t,x)$的項出現了，首先$i$要整除$t$，因此只有index 被$i$整除的$f$值要加上一些$i$。至於要加上多少個$i$，因為$gcd(t,x)=i$，所以我們也可以設$x=y\cdot i$，其中$y<\frac{t}{i}$。這樣就可以兩邊同除以$i$，變成$gcd(\frac{t}{i},y)=1$，因此我們需要知道$1,...,\frac{t}{i}-1$中有幾個數和$\frac{t}{i}$互質，這正是歐拉函數 phi ，因此只要先預處理好每個數的 phi 值，再用他算出$f$陣列的值就可以了。

code :

[CF 449D] Jzzhu and Numbers

作法：

考慮一個$n\times 20$的表格，其中第$i$列就是把第$i$個數的二進制表示寫成橫的放在表格中。現在我們要算的東西是：要選出好幾個橫排，使得這些橫排的每個直行裡都至少有一個$0$，我們反過來看單一一個直行中的所有$1$形成的一個$\{ 1,2,...,n \}$的子集合，假設第$i$個直行的這樣的集合為$S_i$（$i=0,...,19$），那麼對於某個集合$T$來說，如果他是某個$S_i$的子集合，那麼$T$就是不符合條件的集合，並且反過來也是對的。因此我們只要算出「$S_0,...,S_{19}$總共有多少種不重複的子集合」就可以了。這可以用排容算，因為「$S_i$的所有子集合」可以看成一個集合，我們要算的就是這$20$個集合的聯集大小。因此我們需要知道：給定一個$\{0,...,19\}$的子集合${c_1,...,c_r}$，那麼$S_{c_1}\bigcap ... \bigcap S_{c_r}$中共有幾個數，對於所有$\{0,...,19\}$的子集合都必須知道這件事的答案。這裡要觀察到，如果$x\in S_{c_1}\bigcap ... \bigcap S_{c_r}$，那麼代表在第$x$列中的第$c_1,...,c_r$個位子都是$1$，也就是可以改寫為$a[x]\& S = S$，其中$S$代表$c_1,...,c_r$用位元壓起來的數。有了這件事之後，假設我們要算的陣列叫$num$陣列（也就是$num[S]$代表上述所說的$S_{c_1}\bigcap ... \bigcap S_{c_r}$大小，其中$S$是由$c_1,...,c_r$位元壓縮起來的）（大小為$2^{20}$），那麼就可以從另一個角度去算$num$陣列，就是在讀入一個$a[i]$時，將所有滿足$S\& a[i]=S$的$S$的$num$值都$+1$（或是說把輸入的$a[i]$看成一個集合的 bit ，那麼舊把這集合的子集合對應的 index 的$num$值都$+1$），那麼全部讀完後就會是我們要的$num$陣列了。而上面這件事又等價於：記$f[x]$代表在輸入中有幾個$x$，那麼$num[S]$的值就會等於所有$f[x]$的值，其中$x$滿足$x\& S=S$（或是說$x$是$S$的子集）。我們考慮固定$S$時要怎麼求出$num[S]$的值，例如$S$的二進制長的像$1010$好了，那麼就直接從最左邊那位往右 DFS 下去，遇到$1$的話代表這位只能放$1$，遇到$0$則代表這位可以放$1$或$0$，這樣我們會DFS到的數就會是$1010,1011,1110,1111$，恰好是所有滿足$S\& x=S$的$x$，把他們的$f$值加起來就是我們要的答案了。觀察剛才DFS的過程，我們可以用「當前已經確定到第幾位了」還有「當前的數字是多少」來當作傳入DFS的參數，那麼就不難發現這其實可以改成一個DP了（$dp[21][2^{20}]$），並且轉移式只要看DFS時是怎麼求答案的就可以了。邊界為當所有位子都確定時就回傳$f$的值，也就是$dp[20][i]=f[i]$。

code :

[CF 449C] Jzzhu and Apples

作法：

我一開始是考慮一個構造：從$2$開始枚舉質數，當枚舉到一個質數$p$時，考慮所有被他整除且還沒被用過的數，如果有偶數個就全部連完，如果有奇數個就想辦法留一個下來。但後來發現不管留哪個都不對，例如當$p=2$且$n=6$時必須留$6$，$n=10$時則必須留$10$。而如果質數枚舉是從$3$開始，把$2$放在最後一個，並且如果$p$的倍數裡有奇數個沒被用過，就把$2p$留下來，這樣就可以把所有有辦法被選的數都選到了。（沒辦法被選到的點有$1$和比$\frac{n}{2}$大的質數）

code :

[CF 449B] Jzzhu and Cities

作法：

考慮先建出這張圖的最短路徑圖，並且他是有向的。那麼對於那些不在最短路徑圖的中的鐵軌邊就顯然可以拔掉了。在最短路徑圖中，如果$1$有連向$x$的邊，並且$1$有另一種走法可以走到$x$，那麼$1$連向$x$的這條邊就可以拔了（注意到如果單單只是$1$有兩種走法走到$x$，那麼是沒有邊可以拔的）。而這其實等價於$x$的入度$>1$，因此只要對每個鐵路終點都判斷這件事就可以了。

code :

[CF 449A] Jzzhu and Chocolate

作法：

假設橫著切了$a$刀，直著切了$b$刀，那麼所求就會是$\left \lfloor \frac{n}{a+1} \right \rfloor\cdot \left \lfloor \frac{m}{b+1} \right \rfloor$，其中$a,b\geq 0$，並且$a+b=k$。可以先改成$\left \lfloor \frac{n}{x} \right \rfloor\cdot \left \lfloor \frac{m}{y} \right \rfloor$，其中$x,y\geq 1$，並且$x+y=k+2$，等等會比較好處理。枚舉所有的$x$顯然是不行的，而因為這條式子有高斯，所以可以用常見的優化方法，因為當上式中$x$慢慢增加時，$\left \lfloor \frac{n}{x} \right \rfloor$的值會在連續的區間保持不變。具體來說，設此時$\left \lfloor \frac{n}{x} \right \rfloor=q$，那麼不難證明$x$的值從$x$一直往上跑到$\left \lfloor \frac{n}{q} \right \rfloor$的話，$\left \lfloor \frac{n}{x} \right \rfloor$的值都會一直保持$q$，因此這段區間可以一起做。而$\left \lfloor \frac{m}{y} \right \rfloor$的部份因為$y$是往下跑的，這裡則可以推出$y$一直往下跑到$\left \lfloor \frac{m}{\left \lfloor \frac{m}{y} \right \rfloor+1} \right \rfloor+1$，因此只要對兩個可以一起做的區間取比較小的就可以了，類似的東西可以參考這篇。

code :

[CF 557E] Ann and Half-Palindrome

作法：

以下記原字串為$S$。首先核心當然就是一個一個確定答案要是$a$還是$b$，或是決定停止加字元並輸出。在確定答案時，一開始答案為空字串，接下來我們必須知道「有多少個半回文子字串的前綴是$a$」，假設有$num$個好了，如果$num\geq k$，那麼可以知道答案的第一個字元會是$a$，否則會是$b$，並且把$k$扣掉$num$後繼續下去（因為當在第一個位子放上$b$的同時答案字串就已經自動大於$num$個半回文子字串了）。另外我們還要知道什麼時候停止繼續加字元，而這只要滿足：假設當前的答案字串為$T$，那麼如果$T$是半回文且他在$S$中的出現次數$\geq k$時，$T$就是我們要的答案，證明並不難。因此我們會需要詢問兩個東西，一個是「給定某個字串$T$，問$S$中有幾個半回文子字串使得他的前綴是$T$」，另一個則是「給定某個字串$T$，問他是否為半回文，並且知道他在$S$裡出現了幾次」。並且這些詢問頂多$O(n)$次。後者中問半回文就直接$O(n)$判斷，在$S$裡出現幾次則用個後綴數組來作就可以了。至於前者比較麻煩，我們考慮先用後綴數組找出所有$T$在$S$裡出現的位置，假設對於某個$i$，$S[i,...,i+|T|-1]$和$T$字串一模一樣，那我們想知道的是有幾個$j$滿足：$j\geq i$，並且$S[i,...,j]$為半回文。這個東西就是某種後綴和，也就是我們如果可以先得出所有的$S$的子字串$S[i,...,j]$是否為半回文，用個二維陣列紀錄起來，再對第二維作後綴和（前綴和也可以），就可以$O(1)$詢問前面所需要的東西了。而這個二維陣列的求法就類似回文的想法，因為對於所有同一個中心點的$S$的子字串來說，設他從中心往左往右的長度為$L$，那麼只考慮所有$L$的奇偶性相同且同中心點的子字串，那麼當長度比較小的不是半回文時，長度比較大的也不是，因此只要枚舉中心點和字串半長度的奇偶性，從中間往外跑就可以了。

code :

[CF 452F] Permutation

作法：

考慮從左邊往右邊掃，當掃到$i$的時候判斷是否存在兩數分別在$i$的左右，使得$a[i]$是他們的平均數。記$a[i]=x$，那麼不存在這樣的兩個數若且唯若「$j$和$2x-j$在$a[1],...,a[i-1]$中同時出現或同時不出現」，對於每個不讓上數值越界的$j$。因此我們考慮維護一個每個數分別出現了幾次的陣列，這樣就會變成詢問這個陣列中的其中一段是否和另一段倒過來一模一樣，並且支援把陣列中的$0$改成$1$。考慮維護正反的這樣的陣列，並且用 hash 來判字串相等，那麼求一個子字串的 hash 值就可以用 BIT 來作。這裡用的 hash 函數和一般的不太一樣，子字串$s[i...j]$的 hash 值會是 $a[i]+a[i+1]x+...+a[j]x^{j-i}$ ，這樣才能用 BIT 算出子字串的 hash 值（因為要修改，所以才用 BIT），並且要預處理出$x^{-1}$的所有冪次，才能快速算出 hash 值。詳細可以參考 code 。

code :

[CF 452E] Three strings

作法：

考慮對三個字串都建個後綴自動機，那麼假設對於某個出現在三字串中的子字串$T$來說，令$u_1,u_2,u_3$分別是三個自動機吃了字串$T$之後達到的狀態，而我們知道$u_i$其實會代表某個範圍長度的子字串（也就是這篇中講到的 min 值和 max 值），因此這樣可以得到我們必須要在答案陣列中的某個區間同時加上一個數，他的值是這三個節點的 right 集合大小的乘積（right 集合的定義也在上面那篇中有提到）（因為 right 集合就是子字串的出現位置集合，取他的大小就是這個子字串出現的幾次）。先不談要怎麼求每個節點的 right 集合大小，事實上只有這三個後綴自動機是不夠的，因為這三個節點的 min 值和 max 值不盡相同，也就是這三個節點代表的子字串集合不一樣，沒辦法知道要在答案的哪個區間加上 right 集合大小的積。因此我們需要第四個後綴自動機，他是將三個字串中間用沒看過的字元串起來得到的，那麼就可以同時對這四個後綴自動機DFS並求答案了。具體來說，當DFS到某個節點時，設四個節點分別為$u_1,u_2,u_3,u$，那麼我們就知道要用$u_1,u_2,u_3$的 right 集合大小乘積去更新$u$的 min 值到 max 值這個區間的答案，對這四台自動機 DFS 一次即可（每次只走前三台有轉移邊的節點，至於第四台當前三台都有轉移邊的話他也必定會有）。

於是重點剩下要怎麼知道一個節點的 min,max 值，還有 right 集合的大小。max 值在構造的時候就已經算好了，min 值比較好算，因為如果 $u$ 在自動機中的父親是 $p$ ，那麼 $u$ 的 min 值就會是$p$的 max 值再$+1$，詳細也在上面那篇裡有。至於 right 集合的大小，作法為：首先將所有用前綴轉移到的節點的值設成$1$，那麼一個節點的 right 集合大小就會是他在 parent 樹中子數裡的數值總和。而 parent 樹有個特性，就是一個節點的的 max 值會比他父親的 max 值還大，所以可以把所有節點按照 max 值排序，按照 max 值大到小拿自己的 right 集合大小值更新父親的 right 集合大小值就可以了。

code :

[CF 555E] Case of Computer Network

作法：

因為是要把邊定向，所以對於一個邊雙連通分量來說，把裡面的邊的方向定成兩兩互相可達是最佳的，不難證明沒有這樣定的話改成這樣定會更好。因此首先找出所有的邊雙連通分量，並縮成一個點，這樣就變成樹上的問題了：給定一棵樹和一些起點終點，問是否有辦法幫所有邊定向，使得起點都可以走到終點。當給定一條路徑$a\rightarrow b$時，假設他們的LCA為$c$，那麼就可以先把路徑拆成$a\rightarrow c$和$c\rightarrow b$。因此問題可以再簡化成：將沿著$a$往父親走一直走到$b$的這條路徑上的邊都標上$1$或$2$，問是否有矛盾（$1,2$分別代表這條邊是往上還是往下）。考慮樸素的算法，也就是每次直接往上走完整條鍊，這樣複雜度會爆掉，不過只要注意到：當正在沿著$a$往父親跳的時候，如果這時跳到了一個點，他連向他父親的邊已經被標記過了，如果這條邊上的數字和當前要標記的數字不一樣則產生矛盾，否則可以直接往上跳到第一個「他連向他父親的邊還沒被標記」的點，節省時間。這部份可以用個類似 disjoint set 的東西來作，詳細可以參考 code ，這樣就可以讓複雜度變回好的了。

code :

[CF 452D] Washer, Dryer, Folder

作法：

一開始每台機器可以運行的時間都是$0$，因此第一件衣服可以馬上丟進去。再來依次處理每件衣服，找出他最早可以丟進去的時間並放進去。至於如何找最早的時間，我們對三台機器都維護一個 priority_queue ，裡面分別存每台機器要到時間多少時才有空，那麼每次從中取出最小的三個時間就可以算出下一次的衣服要在什麼時候放進去了。並且也可以計算出處理這件衣服的機器分別會在什麼時候結束工作。

code :

[CF 555D] Case of a Top Secret

作法：

首先看要如何模擬，可以把繩子的動作分成兩種，第一種是當前繩子往下垂並且物體正在往右邊移，另一種則是當前繩子是往上的並且物體正在往左邊移。把輸入的座標排序就可以用 lower_bound / upper_bound 找出繩子接下來會繞誰轉，就可以模擬了。但直接做會TLE，首先觀察到我們可以先把繩子的長度縮減到比$a[n]-a[1]$還短，其中$a[1],...,a[n]$代表已排序後的釘子座標。接下來考慮模擬時要如何優化，設當前繩子繞著$a[i]$轉，並且是前面所述的第一種狀態，如果他是由第二種狀態轉移過來的，那麼顯然會滿足$a[i]-a[i-1]>L$，其中$L$為當前繩子長度。首先求出他之後會繞著$a[x]$轉，那麼他的長度就會變為$L-(a[x]-a[i])$。如果每次長度都減少了一半以上，那麼模擬的次數就會變成$O(logL)$，會是好的。但如果在這次$L$的長度沒有減少一半以上，那麼不難發現再繞完$x$旋轉的下一步會再去繞$i$旋轉，重複繞這兩個點旋轉直到$L$小於他們之間的距離為止，因此我們可以直接把$L$的長度縮減成$L\% (a[x]-a[i])$，並由他們的商來判斷此時是繞$i$轉還是繞$x$轉。由於此時$(a[x]-a[i])<\frac{L}{2}$，所以$L$也會至少砍半，而對於第二種狀態作法也幾乎一樣，因此這樣就得到了單次詢問$O(lognlogL)$的算法了。

code :

[CF 555C] Case of Chocolate

作法：

假設這次的詢問是$(x,y,L)$，那麼如果我們已經知道在第$1,...,x-1$行中每行的最上面那個被吃掉的格子座標的話，就可以算出答案了。對於$U$的詢問也一樣可以用類似的資料結構來做。但是$n$太大了，所以考慮先把輸入都離散化，這樣就可以用線段樹來做了：維護兩棵線段樹，並且當詢問$(x,y,L)$時（詢問為$U$時幾乎一模一樣），我們會需要在其中一棵線段樹中查詢「最大的$i$使得$i,...,x$中的最大值$\leq y$」的$i$，這顯然可以在$logn$的時間內做到，但我比賽時寫了二分搜答案的作法，複雜度多一個$log$，不至於TLE。查詢完後再去更新另一棵線段樹上的值就可以了。

另外也有不用線段樹的作法，詳細可以參考這篇，比線段樹的作法簡潔多了。

code :

[CF 555B] Case of Fugitive

作法：

可以蓋在$i$和$i+1$中間的橋的長度必須滿足$\geq l[i+1]-r[i]$，且$\leq r[i+1]-l[i]$，因此先將所有橋的長度排序，那麼可用的橋會在排序序列中形成一個區間，這樣就轉換為經典問題了，也就是現在有$m$個點和$n-1$個區間，問是否有辦法幫每個區間選一個他對應的點，滿足選出的每個點都不同。考慮從第$1$個點開始往右掃，當掃到一個點$i$時，把所有左端點$\leq i$的區間加進某個資料結構中，如果此時資料結構沒有東西，那麼代表$i$這個點可以不用被取，否則取出資料結構中右端點值最小的區間出來，不難證明這個 greedy 是對的，而這只要用個 priority_queue 就可以了。

code :

[CF 453E] Little Pony and Lord Tirek

作法：

我們先處理每個$s[i]$都是$0$的情形（也就是初始值都是$0$）。考慮用線段樹，把詢問的區間拆成好幾個小區間，分別求出答案再加起來。對於某個線段樹節點代表的區間$[L,R]$而言，我們想要快速求出這個區間中的答案總和。如果這個區間擁有良好的性質：在$t_0$秒的時候這個區間全部都被設成$0$，並且之後不再動到他（因此一開始所有節點都有這個良好性質，並且$t_0$值都是$0$），那麼假設當前詢問時間是$t$秒，就可以把$[L,R]$中的小馬們分成兩類，一類是「經過了$t-t_0$秒沒辦法長到最大值」的，另一類則是長不到的，那麼對於前者，他所貢獻的答案就會是$r[i]\cdot (t-t_0)$，後者貢獻的答案則為$m[i]$。因此我們可以考慮先對每隻馬算出他「要長幾天才會長到最大值」（之後記為$t[i]$），並且在每個線段樹的節點$[L,R]$中，把「這區間中的所有馬按照$t$值排序後的結果」記錄下來，並且算出這些馬的$r$值和$m$值的前綴和陣列，這樣就能快速查詢答案了。但上述算法的前提是這個節點擁有前面所講的好性質（以下簡稱這個節點是好的），如果沒有的話就只好再把詢問區間拆開遞迴下去，直到遇到的節點是好的為止。並且我們也容易維護有哪些是好的：當遇到一個詢問時，如果詢問區間遞迴下去經過的節點被詢問區間完全覆蓋了，那麼在詢問過後他就會變成好的。並且當詢問時如果走到了一個好的節點，但是詢問區間沒有完整覆蓋這個節點的區間的話，就要把這個好的標記往下 push ，並且自己在詢問過後就不再是好節點了。總結以上算法，對於每個節點要記錄的東西有：這個區間中按$t$值排序的馬們，排完序後的馬們的$r$值、$m$值前綴和，還有在詢問時需要維護的$ok$值（代表他是否是好的）和$t_0$值，其中$t_0$代表如果$ok=1$，則$t_0$是最近一次將整個區間設成$0$的時間。以上算法解決了$s[i]$全部都是$0$的情形，但實際上一般情形也可以這樣做，因為這樣一開始時所有區間都是不好的，一次詢問下來會遞迴到底，也就是把詢問區間拆成長度均為$1$的區間暴力處理，顯然長度為$1$可以直接算出答案。不難發現暴力算的次數加起來不會超過$n$次，因此這部份複雜度會是好的。但整個算法我還證不太出他的複雜度是多少，可能是$O(qlog^2n)$之類的......

另外我還有在別人的 comment 中看到另一種作法，詳細見這裡，寫的還蠻清楚的。

code :

[CF 453D] Little Pony and Elements of Harmony

作法：

這題我是看官方解寫的，但他寫的很不清楚，這裡紀錄一下詳細，雖然應該有不用用到這種東西的作法......

題目簡單來說就是要求向量$A^t\cdot e_0$是多少，其中$A$是一個$n\times n$的矩陣，滿足他的$(i,j)$項為$b[bit(i\; xor\; j)]$（其中用$bit(x)$代表$x$的二進制中$1$的個數），$e_0$則是一個給定的$n$維向量。如果$A$有$n$個線性獨立的 eigenvector，設其為$v_0,...,v_{n-1}$，並且對應的 eigenvalue 為$\lambda _0,...,\lambda _{n-1}$，那麼可以先把$e_0$拆成$v_i$的組合，也就是令$c_0,...,c_{n-1}$滿足$\displaystyle e_0=\sum_{i=0}^{n-1} c_iv_i$，那麼所求就會$\displaystyle =A^t\sum_{i=0}^{n-1} c_iv_i=\sum_{i=0}^{n-1}c_iA^tv_i =\sum_{i=0}^{n-1} c_i\lambda _i^tv_i$。所以接下來的步驟就是先求出$c_i$和$\lambda _i$，算出$v_i$前面的係數之後再想辦法組合起來。

神奇的是$A$這個矩陣的確有$n$個 eigenvector ，並且$v_i$的第$j$項恰好等於$(-1)^{bit(i\& j)}$（這篇中所有的證明都放在最後）。記矩陣$H=\begin{bmatrix}v_0 & v_1 & \dots & v_{n-1}\end{bmatrix}$，並且回到$\displaystyle e_0=\sum_{i=0}^{n-1} c_iv_i$這個式子，他就會等價於
$e_0=H\cdot \begin{bmatrix}c_0\\c_1\\\vdots\\c_{n-1}\end{bmatrix}$，所以$\begin{bmatrix}c_0\\c_1\\\vdots\\c_{n-1}\end{bmatrix}=H^{-1}e_0$。又因為$H$是對稱的，還有$v_0,...,v_{n-1}$兩兩正交，所以可以得到$H\cdot H=n\cdot I$，也就是$H^{-1}=\frac{1}{n}H$，所以這裡本質上就是要算$H$乘以一個向量得到的向量是多少。

我們把求$H$乘上一個向量的作法留到後面，先來看$\lambda _i$的求法。因為$Av_i=\lambda _iv_i$，所以我們只要比對兩邊第一項的值就好了。可以得到$\displaystyle \sum_{k=0}^{n-1} b[bit(k)](-1)^{bit(i\& k)}=\lambda _i$（這裡代入了$A$的第$(0,k)$項為$b[bit(0\; xor \; k)]=b[bit(k)]$，還有$v_i$的第$k$項為$(-1)^{bit(i\& k)}$）。令另一個$n$維向量$d$的第$k$項等於$b[bit(k)]$，那麼上式可以改寫為$\lambda _i = d \cdot v_i$，因此把$n$條式子（$i=0,...,n-1$）寫在一起就可以變成$\begin{bmatrix}\lambda _0\\\lambda _1\\\vdots\\\lambda _{n-1}\end{bmatrix}=\begin{bmatrix}v_0^T\\v_1^T\\\vdots\\v_{n-1}^T\end{bmatrix}\cdot d=H\cdot d$，因此這裡也會變成求$H$乘上一個向量的問題。

最後則是求出所求的向量$\displaystyle \sum_{i=0}^{n-1} c_i\lambda _i^tv_i$，他可以改寫成$\begin{bmatrix}v_0 & v_1 & \dots & v_{n-1}\end{bmatrix}\cdot \begin{bmatrix}c_0\lambda _0^t \\ c_1\lambda _1^t\\\vdots\\c_{n-1}\lambda _{n-1}^t \end{bmatrix}$，因此一樣是求$H$乘一個向量，所以現在問題剩下這件事要怎麼作了。事實上我們可以用遞迴來定義$H$，定義$H_0$代表只有一個$1$的$1\times 1$的矩陣，$H_i$則定義為$\begin{bmatrix}H_{i-1} & H_{i-1} \\ H_{i-1} & -H_{i-1}\end{bmatrix}$，其中他是$2^i\times 2^i$的矩陣，那麼這邊的$H$就會是$H_m$（這不難由前面$H$的定義得出）。有了這個遞迴式就能幫助我們在$O(nlogn)$的時間內算出$H$乘上一個向量是多少了。考慮「求出$H_i\begin{bmatrix}u_0 \\ \vdots \\ u_{2^i-1} \end{bmatrix}$」這個問題，由上面的遞迴式可得他就等於$\begin{bmatrix}H_{i-1} & H_{i-1} \\ H_{i-1} & -H_{i-1}\end{bmatrix}\begin{bmatrix}u_0 \\ \vdots \\ u_{2^i-1} \end{bmatrix}$，因此我們先遞迴下去算出$H_{i-1}\begin{bmatrix}u_0 \\ \vdots \\ u_{2^{i-1}-1} \end{bmatrix}$和$H_{i-1}\begin{bmatrix}u_{2^{i-1}} \\ \vdots \\ u_{2^i-1} \end{bmatrix}$，假設分別得到$U_1$和$U_2$，那麼不難得到所求就會等於$\begin{bmatrix}U_1+U_2 \\ U_1-U_2 \end{bmatrix}$，也就是能在線性的時間內合併兩個子問題，因此複雜度是$O(nlogn)$。他的寫法就有點類似FFT，但這個簡潔多了。

=======================================================================

最後補上前面沒證的證明，一個是為什麼$v_i$們就會是$A$的 eigenvector ，還有為什麼$v_i$們兩兩正交。兩兩正交比較好證，我們要證明$v_i\cdot v_j=0$（其中$i\neq j$），這等價於$\displaystyle \sum_{k=0}^{n-1} (-1)^{bit(i\& k)+bit(j\& k)}=0$，假設$i,j$的第$x$個 bit 不同，那麼考慮上式中將第$k$項和第$k\; xor \; 2^x$項配對，不難證明這兩項一個是$1$一個是$-1$，因此總和為$0$。最後證明$v_i$為 eigenvector ，考慮$Av_i=\lambda _i v_i$這式子兩邊的第$j$項，可以得到$\displaystyle \sum_{k=0}^{n-1}b[bit(j\; xor \; k)](-1)^{bit(i\& k)}=\lambda _i (-1)^{bit(i\& j)}$，我們要證明的是當$j$跑遍$0,...,n-1$時$\lambda _i$都會是固定的。考慮左式中$b[z]$的係數，可以得到他會是$\displaystyle \sum_x (-1)^{bit(i\& x)}$，其中$x$跑遍所有和$j$差了$z$個 bit 的數（也就是$bit(j\; xor \; x)=z$）。考慮把$j$的第$r$個 bit 改掉時$b[z]$的係數會如何變化，分成$i$的第$r$個 bit 是$0$或$1$兩種情況，而不管是哪種情況在計算$b[z]$的那條式子中的$x$們必須把他們的第$r$個 bit 都改掉才會滿足他和新的$j$差$z$個 bit ，因此當$i$的第$r$個 bit 是$1$的時候，對於所有的$b[z]$係數中的$(-1)^{bit(i\& x)}$都會乘上一個負號，否則係數都不會變。回到我們要證明的那條式子，剛才說明了當$j$的某個 bit 改變時左式會發生什麼事，而右式中的$(-1)^{bit(i\& j)}$也恰好會發生一樣的改變，當$j$變動的 bit 在$i$那邊也是$1$時則變為$-1$倍，否則不變，這就得到了當$j$跑遍所有$0,...,n-1$的數時$\lambda _i$都會是定值，因此$v_i$為$A$的 eigenvector。


code :

[CF 553D] Nudist Beach

作法：

考慮二分搜答案，那麼可以先對每個點算出「如果取他的話至少要取幾個他的鄰居」，以下稱其為$num$值，再來要判斷是否有可能。最好的情況是取下了所有非堡壘的點，因為這時每個點可以獲得最多的被取到的鄰居數，但有些點儘管如此還是不能被取的，他們就是「$num$值大於鄰居中非堡壘點」的點，所以必須先把他們去除掉。把他們去除後又可能多了一些新的不能取的點，因此就可以得到這會是某種BFS的過程：先把一開始的$k$個點標成不可取他的，並推入 queue 中，每次從 queue 取出一個點時，更新他所有鄰居的「當前還有幾個鄰居是可以被取的」的值，如果發現有一個鄰居的值已經$<$他的$num$值時就也把他推入 queue 裡面。過程結束後如果還有沒被BFS到的點那麼就是可行的，否則不行，這個算法的充要條件證明則算是顯然的。

code :

[CF 553C] Love Triangles

作法：

首先把圖轉換成「兩人相愛若且唯若兩點之間連邊」，觀察這張圖會有什麼特性。首先當$A,B$連邊且$B,C$連邊時，$A,C$也要連邊，因此可以知道每個連通塊一定都是完全圖。再來如果有大於兩個的連通塊，那麼在三個連通塊中各挑一個點就形成了兩兩沒有連邊的三角形，和題意矛盾，因此至多只有兩個連通塊。這樣就轉換成經典問題了：給一張圖，還有一些「兩點之間同色」和「兩點之間異色」的條件，問有幾種塗兩色的方法。這只要先用 disjoint set 判有沒有可能，若有可能則答案為$2$的(連通塊數量$-1$)次方，其中這裡的圖是「當給定條件$x,y$同色或異色」時則在$x,y$之間連一條邊所得到的圖。

code :

[CF 453C] Little Pony and Summer Sun Celebration

作法：

首先如果有兩個連通塊裡都有$1$那顯然無解，因此現在只要考慮有一個連通塊有$1$的情形。通常這種構造題只要隨便取個生成樹DFS下去就可以了。考慮在DFS的過程中，當DFS完$x$這個點時$x$必須要完成他的目標，然後回到他父親（記為$f$）。如果發現$x$還需要被走一次，那麼就走$f\rightarrow x\rightarrow f$就可以讓$x$多走一次了，而如果$x$不用再被走一次就直接回去$f$。這樣可以處理根節點以外的所有點，至於如果回到根節點時還沒滿足條件，那麼隨便取他的一個孩子$s$，走$s\rightarrow x\rightarrow s$就可以了。

code :

[CF 455E] Function

作法：

觀察$f$函數的式子可以發現他就類似某種最短路，$i$指的就是走了$i$步，因為$f(i,j)$都是從$f(i-1,x)$轉移過來的。觀察到這件事就可以先把原題轉換成最短路問題：考慮一張$n+1$個點的圖，第$i$有連到自己的邊權為$a[i]$的邊($i=1,...,n$)，$i$也有連到$i+1$的邊權為$a[i+1]$的邊($i=1,...,n-1$)，並且$n+1$有連到$i$的邊權為$a[i]$的邊($i=1,..,n$)，那麼$f(i,j)$就等於從$n+1$開始走$i$步到達$j$的最短距離。假設現在要算$f(x,y)$，如果從$n+1$開始第一步走到$k$，那麼走$i$步的距離就可以表示成$\displaystyle \sum_{i=k}^{y} c[i]\cdot a[i]$，其中$c[i]$同時也代表這條路徑在$i$走了$c[i]-1$次自環。並且由走$x$步的限制可知$\displaystyle \sum_{i=k}^{y} c[i]=x$，並且顯然的有$c[i]\geq 1$，因此$k$必須滿足$k\geq y-x+1$。接下來看達到最小值時$c$陣列應該要長怎樣，考慮$a[k],...,a[y]$中最小的那個數，那麼把所有的$c$都集中到那個數一定是最好的，並且如果那個數不是$k$的話可以把$k$的$c$值也丟到他身上，因此最佳解中$c$陣列一定長的像：$c[k+1]=...=c[y]=1$。此時我們得到的路徑長度$=a[k+1]+...+a[y]+(x-y+k)a[k]$
$=S[y]-S[k]+(x-y+k)a[k]$
$=S[y]-(y-x)a[k]+(k\cdot a[k]-S[k])$，其中$S[i]=a[1]+...+a[i]$。
其中的$S[y]$可以先不用理他，最後再加到答案上就可以了。至於後面那項，因為在詢問的時候只有$y-x$的值會變，$a[k],S[k]$的值都是不變的（$k$固定時），因此當不同的$y-x$代入時可以把這東西看成一個一次函數，也就是令直線$L[i]:y=-a[k]\cdot x+(k\cdot a[k]-S[k])$，那麼這樣在詢問$f(x,y)$時就等價於詢問$y-x$這個數代入$L[y-x+1],...,L[y]$的最小值是多少。這可以用線段樹套凸包來作，具體來說，假設線段樹的某個節點區間為$[L,R]$，那麼就在這個節點先算好第$L,...,R$條直線形成的上凸包長怎樣（紀錄頂點們和直線們），這樣就可以在這個節點上用$log$的時間查詢某個數代入這個區間中所有直線所得到的最小值是多少了。而當詢問一個區間時就只要把他拆成好幾個線段樹的節點，合併起來就是答案了。

code :

[CF 455D] Serega and Fun

作法：

通常這種時限比較長而且操作很奇怪的題目都可以考慮根號作法。考慮把整段序列切成$\sqrt{n}$塊，再根據題目的要求決定每塊中要維護的資料結構是什麼。當要把某段區間循環右移時，把他拆成已經切好的幾小塊，就可以得到每個小塊中所必須支援的操作為「將這塊中的某個區間整個右移（因此最右邊的數會消失），並且在左邊補上$x$」。並且大部分的情形右移的區間都是整個塊，因此可以考慮當操作的區間不是整塊的時候暴力重建這個資料結構即可，也就是我們只需要快速的支援「將整塊往右移並在左邊補上$x$」這個操作。至於詢問也是拆成好幾個小塊，對於詢問區間不完全是整塊的部份暴力掃過去就可以了，因此我們需要在一塊中詢問某個數出現了幾次，所以只要在這塊中用一個陣列$cnt$紀錄所有數字出現的次數就可以了。當把整塊中的數都右移時，我們會需要知道此時這塊中的最後一個數是多少，才能維護好$cnt$陣列，也就是會需要查詢某塊中的第$k$個數是誰，並且支援右移操作。這可以用一個環狀的結構來維護，具體來說是一個陣列$a$和一個起點值$st$，代表從$a[st]$開始往後走$i$步就是代表這塊中的第$i$個數是誰（以下記這塊的長度為$sz$），也就是當我們想知道這塊中的第$i$個數時，要查詢的是$a[(st+i)\% sz]$的值。這樣就可以輕鬆維護循環右移操作了，只要把$st$值減一再維護好$cnt$陣列就可以了。

code :

[CF 455C] Civilization

作法：

由條件知到他的圖會是一個森林。這題只要注意到連接兩個連通塊時連接兩連通塊的重心是最好的選擇，因此只要對每個連通塊計算他的最長鍊是多長就可以了，最長鍊的計算方法為：先任遠一個點對他DFS，找出離他最遠的點，再以找到的那個點當根做一次DFS，所得到的最長距離就是這棵樹的最長練了。假設兩個連通分量的最長鍊分別為$x,y$，那麼連接他們的重心之後會產生一條長為$\left \lceil \frac{x}{2} \right \rceil+\left \lceil \frac{y}{2} \right \rceil+1$的鍊，再和$x,y$取 max 就是新連通塊的最長鍊長度了，至於實作用個 disjoint set 並維護好最長鍊值就可了。類似的題目還有 IOI 2013 Dreaming （HOJ 288）。

code :

[CF 455B] A Lot of Games

作法：

首先當然是決定如果$k=1$時誰有必勝策略，這可以先建出所有字串的 trie 後DP得到。這樣解決了$k=1$的問題，但$k=2$時可能第一局先手故意輸掉，下一局再用必勝策略獲勝之類的（因為下一場的先手會給輸方），因此我們還需知道誰有必敗策略，這和必勝策略的求法幾乎一樣。有了這兩個之後就只要討論四種情形就好了：能夠必勝的是先手還後手，能夠必敗的是先手還後手（這個必敗指的是他可以強迫自己輸，而不是他的對手有必勝策略）。如果後手能夠必勝，那麼他就一路贏到底就好了。否則當先手必勝時，討論一下即可知道當先手可以必敗時必定先手贏，後手可以必敗時則是當$k$是奇數時先手贏了。

code :

[CF 457C] Elections

作法：

考慮枚舉$0$號的得票數，那麼策略就是先買票數$\geq$他的候選人的最便宜的幾張票，讓他的票數小於自己的，這時如果自己的票數已經超過預定的了，那就代表這次是無效的，否則再從剩下的票裡面選最小的幾張票補滿就好了。至於要如何加速到$O(nlogn)$，考慮從小到大枚舉得票數，那麼可以用一個資料結構維護剛才所說的後者的動作中的「在剩下的票裡選最小的幾張票」，他必須支援「加入一個數」和「詢問這些數裡前$k$小的數的總和」是多少，而這可以用一個分裂合併式的 treap 完成。

code :

[CF 457B] Distributed Join

作法：

感覺題目寫的不太好懂......簡單來說就是，現在有左邊$n$坨資料，右邊$m$坨資料，每坨資料裡都有一定數量的行。一次操作可以把某一行複製到某坨資料中塞進去，問至少要幾次操作才能滿足在左邊任選一行，右邊任選一行，都有某一坨資料裡面含了這兩行（任兩行的內容都不一樣）。首先觀察最佳解會有怎樣的特性，對於某一行來說，簡稱「這一行被複製到了哪幾坨資料」為他的目的地，那麼某坨資料中的所有行的目的地都一樣。因為如果某坨中有兩行的目的地不一樣（假設這坨在左邊），對於其中一種目的地來說，那幾坨的聯集裡面一定包含了所有右邊的行，因此可以把目的地坨數比較多的那個方法換成比較少的，這樣答案不會更差，因此一坨資料中任兩行的目的地相同。再來則是最佳解中至少有一坨資料內的每一行是沒被複製過的（之後簡稱這件事為這坨資料不動），因為如果每坨的資料都有動，那麼隨便取一坨，稱他為$A$，考慮這坨資料的目的地集合$S$和所有進行過的操作，把所有「把某行複製到$S$中某一坨」的操作都替換成「把那行複製到$A$」，顯然這樣替換還是可以滿足原題條件，並且總複製次數不會增加。因為這裡的假設是每坨資料都有動，因此不會發生「某坨資料的目的地集合嚴格變大」這件事（否則代表他原本的目的地集合就是空集合）。

因此我們可以假設右邊有一坨資料不動，之後將左右的資料對調再求一次答案即可。不妨設右邊不動的資料們的行數分別為$b_1,...,b_k$，剩下的為$b_{k+1},...,b_m$，那麼因為這幾坨都不動，所以對於左邊的每一行都要複製進$b_1,...,b_k$的每坨資料中，這需要花$k\cdot (a_1+...+a_n)$次操作。而因為$b_{k+1},...,b_m$都有動，也就是他們的目的地至少有一個，所以這部份至少要進行$b_{k+1}+...+b_m$次操作。而我們的確可以只用$k\cdot (a_1+...+a_n)+b_{k+1}+...+b_m$完成任務，只要把$b_{k+1},...,b_m$中每一行都複製進$b_1$就可以了。因此對於固定的$k$來說，取$b$中前$k$大的數是最好的，所以只要先把$b$由大到小排序，掃過去並維護前綴和就可以了。

code :

[CF 459E] Pashmak and Graph

作法：

考慮把邊權從小到大排序，一條一條加進圖中，並維護好當前圖的以每個點為終點的最長路長就可以了。但要處理邊權一樣時的問題，解決方法是先把這些邊權一樣的邊的起點都找出來，把這些點和他們的當前答案值存下來，再用存下來的值去更新這些邊的終點的答案就可以了。

code :

[CF 552E] Vanya and Brackets

作法：

只要注意到加上的括號一定會落在兩個乘號的中間就好了。但如果整個表達式的乘號太少就會有問題，因此我們可以在字串最前面加上$1*$，最後面加上$*1$就可以了。枚舉括號的位置，剩下就是要如何算出表達式的值是多少。對於一個表達式來說，考慮從左邊掃到右邊，維護兩個數字$x,y$分別代表「當右邊再出現了一個數為$a$時，表達式的值為$x+y\cdot a$」。例如當算完$1+2*3+4*5*$這個部份時，$x=7,y=20$。並且不難維護好這兩個值。而對於括號分開的三個表達式也都用一樣的方法就可以算出來了。

code :

[CF 461E] Appleman and a Game

作法：

考慮給定字串$s$之後要如何用最少步湊出$s$。這只要取一個最長的$s$的前綴，滿足他是$t$的子字串，把他拼上去之後重複這個過程就好了，因為如果我們取的是比較短的子字串，那麼可以用「把第一個子字串伸長，第二個子字串的前面截掉」來把原本的湊法換成剛才講的湊法。因此當我們想要算長度為$n$的$s$最差狀況下要幾次才能湊出來，可以考慮取某個$t$的子字串$U$，滿足他的後面再加上$c$之後就不會是$t$的子字串了（$c$是$ABCD$中的某一個），那麼就可以在$s$的最前面寫上$U$這個字串，並且約定下一個字元放的是$c$，這樣湊出$s$的第一步就是選$t$的$U$這個子字串並放上去了。由這個就可以想到，令$dp[i][j]$代表長度為$i$，開頭為$j$的字串最差狀況下要用幾個$t$的子字串湊出來，那麼為了計算$dp[i][j]$，我們需要取一個開頭是$j$的$U$字串放在所求字串的最前面才行（$U$和前面提到的一樣），也就是如果我們記開頭為$j$的$U$字串，且他後面準備要放的字元是$k$時的最短長度為$L[j][k]$，那麼就可以列出轉移式了：$dp[i][j]=max\{ dp[i-L[j][k]][k]+1 \},k=0,1,2,3$。其中我們以$0,1,2,3$分別代表$A,B,C,D$。

而首要工作就是要先求出$L[i][j]$是多少，這可以用後綴自動機加上簡單的DP得到，關於後綴自動機可以參考這篇，寫的蠻詳細的。

再來我們想要求出當$i$很大時的$dp$值。仔細觀察轉移式可以發現，可以把他解讀成當第二維從$j$走到$k$之後，第一維的值就會增加$L[j][k]$，這就有點類似在一張圖上從$j$走到$k$的距離是$L[j][k]$一樣，因此如果考慮構造一張四個點的圖，其中任兩點$j,k$之間連一條有向邊，邊權為$L[j][k]$，那麼問題就轉化成了：從某一個點開始一直走，走到總權重的和$\geq n$時最多走了幾步。而這個問題可以二分搜解決，等於是變成要算出走$m$步後走過的最短距離為多少，這可以用倍增法算出，也就是預先算出「從$i$走了$2^k$步到$j$所走的最短路徑長」就可以了。

code :

[CF 461D] Appleman and Complicated Task

作法：

首先把所有格子以$x+y$的奇偶性分成兩類，這兩類可以分開處理，因為題目給的條件中當某個格子的顏色改變的時候，不會影響到所有和他不同類的格子是否滿足條件。再來注意到，考慮把白色賦值成$1$，黑色則為$0$，那麼題目的條件就變成：對於每一個$(i,j)$，$c_{i-1,j}\; xor \; c_{i,j-1}\; xor \; c_{i,j+1} \; xor \; c_{i+1,j}=0$，其中$c_{i,j}$代表$(i,j)$的顏色的值。而$xor$可以看成二進制下的加法，所以可以把條件改寫成$c_{i-1,j}+c_{i,j-1}+ c_{i,j+1}+ c_{i+1,j}=0$，或是$c_{i-1,j}=c_{i,j-1}+ c_{i,j+1}+ c_{i+1,j}$。以下稱第一類格子為$x+y$值為奇數的，第二類則是偶數的。接下來我們先只考慮第一類格子，可以發現到當正方形中的主對角線旁邊的兩排格子的顏色都確定後，整個盤面上的所有第一類格子的值都確定了，所以只要確定好這兩排的值就好了（他們就是$x,y$座標差$1$的格子們）。並且由$(1,1)$的條件限制可得$c_{1,2}=c_{2,1}$，再由$(2,2)$的條件限制得$c_{2,3}=c_{3,2}$，一直推下去就可以得到$c_{i,i+1}=c_{i+1,i}$了。因此接下來記$C_i=c_{i,i+1}$，那麼我們想要知道：當題目給了一個限制條件$c_{x,y}$是$0$或$1$的時候（他是第一類格子），會對$C_i$造成什麼限制。

上圖中代表每一格分別是由哪些$C_i$所$xor$出來的，這樣可以發現一個規律：$(i,j)$會是由$C_{\frac{i-j-1}{2}}$和$C_{\frac{i+j-1}{2}}$所$xor$出來的，並且再觀察$(7,5)$的限制條件，會得到$C_1=C_6$，還有$(7,3),(7,1)$的限制條件分別可以得到$C_2=C_5$和$C_3=C_4$，而這也是蠻顯然的條件，因為整個盤面會對兩條對角線對稱。因此一般來說，必須要有$C_{i}=C_{n-i}$。由上圖可推得，當我們得到了「$c_{x,y}$是多少」的條件時，其實就等於獲得了$C_p\; xor \; C_q$等於多少，也就是他們兩個是否相等的條件。並且當給定的$(x,y)$本身就是$C_i$的一員時條件就變成「$C_i$等於多少」。因此這樣就轉換成經典問題了：給定一張圖，跟其中一些節點的顏色，並且給定許多「某兩個點同色」和「某兩個點異色」的條件，問共有幾種塗法。而這只要對每個連通塊分開做，並把所有答案乘起來。並且當某個連通塊不滿足那些條件限制時答案為$0$，否則當這個連通塊中已經有某個點的顏色確定的話答案為$1$，如果沒有的話就是$2$。

至於第二類格子的處理和上面類似，這時是只要決定主對角線上的顏色就好了，並且一樣記$C_i=c_{i,i}$，那麼這次可以得到$(i,j)$會是由$C_{\frac{i-j}{2}}$和$C_{\frac{i+j}{2}}$所$xor$出來的，並且一樣有盤面對稱的條件，也就是$C_{i}=C_{n+1-i}$，之後的處理就和前面一模一樣了。

code :

[CF 463E] Caisa and Tree

作法：

首先因為修改操作至多$50$次，所以可以直接把他當成沒有修改，在有修改時就直接砍掉重建就好了。對於一個節點$x$來說，假設他的質因數為$p_1,...,p_r$，那麼對於$x$子樹裡的所有點來說，如果某個點$y$的值有$p_1,...,p_r$中任意一個質因數，那麼就可以用$x$去更新$y$的答案，並且$y$的答案要取深度最深的點。因此就可以想到，對這棵樹DFS，假設當前點是$u$，那麼對每個質因數都維護一個數，代表如果之後遇到的點的值有這個質因數的話，就可以用他來更新答案，不難在DFS時更新和回溯那些值，所以就可以$O(1)$回答詢問了。

code :

[CF 464E] The Classic Problem

作法：

這題我是照官方解寫的。重點就是要實作一個資料結構來模擬二進制的操作，有：把$0$修改成$1$，詢問某個位置的右邊第一個$0$落在哪裡，把一串連續的$1$全部改成$0$，還有詢問兩棵子樹是否一模一樣（在判斷兩棵線段樹的大小時會用到）。對於詢問某個位置的右邊第一個$0$，我們可以對每個節點紀錄「緊貼在這個區間右邊的連續的$1$有幾個」，例如$0110011$的值就是$2$，這樣就不難直接從線段樹的根走下去獲得答案了。再來則是判斷兩棵子樹是否相等，我的作法是對每個 bit 都 random 一個 unsigned long long 給他，則一棵子樹的 hash 值就是所有他底下是$1$的 bit 的 random 值 xor 起來的結果，可以用把個這樣的 hash 值包起來來避免碰撞。最後把這東西包起來就可以丟進 Dijkstra 裡了。

code :

[CF 464D] World of Darkraft - 2

作法：

首先由期望值的線性的特性可以知道，其實可以看成只有一種裝備，每次打完怪之後只有$\frac{1}{k}$的機率可以讓他有機會升級，剩下則什麼都不變。最後答案就是只有一種裝備的答案再乘以$k$。

記$dp[i][j]$代表打完$i$隻怪之後，裝備等級為$j$時期望賺的錢，那麼計算$dp[i][j]$時要考慮由以下幾種狀態轉移過來：

$dp[i-1][j-1]$，機率$=\frac{1}{kj}$，賺的錢$=j-1$。

$dp[i-1][j]$，機率$=\frac{1}{k(j+1)}$，賺的錢$=x$。其中$x\in [1,j]$。

$dp[i-1][j]$，機率$=\frac{k-1}{k}$，賺的錢$=0$。

但轉移式並沒有那麼顯然。考慮某個進行了$i-1$次操作的過程（例如可能是不變、獲得等級$2$裝備、不變、獲得等級$1$裝備），並且最後裝備等級是$j$，那麼這一連串的操作有一個發生的機率$p$，還有他賺的錢數$c$。因此$dp[i-1][j]$中就會有一項等於$p\cdot c$，並且$dp[i-1][j]$就是所有操作$i-1$次變成等級$j$的方法的$p\cdot c$總和。現在要從$dp[i-1][j]$轉移到$dp[i][j]$，假設轉移的機率為$q$（也就是$\frac{1}{k(j+1)}$），獲得的錢為$x$，那麼就要在$dp[i][j]$中加上$(pq)\cdot (c+x)$，並且$dp[i][j]$一樣是所有可能的方法的(機率*錢數)的總和。因為$pq(c+x)=q(pc)+pqx$，因此把$(p,c)$取遍所有$dp[i-1][j]$中的值時，$q\cdot (pc)$的總和就會是$q\cdot dp[i-1][j]$，$pqx$的總和則因為$p$的總和其實就是「進行$i-1$次操作後等級為$j$的機率」，所以可以改寫成$P[i-1][j]\cdot qx$，其中$P[i][j]$代表進行$i$次操作後等級為$j$的機率，並且$P$的遞迴式蠻顯然的。因此就可以得到這樣的轉移式：
$\displaystyle dp[i][j]=dp[i-1][j-1]\cdot \frac{1}{kj}+P[i-1][[j-1]\cdot \frac{1}{kj}\cdot (j-1)$
$\displaystyle +\sum_{x=1}^{j} (dp[i-1][j]\cdot \frac{1}{k(j+1)}+P[i-1][j]\cdot \frac{1}{k(j+1)}\cdot x)$
$\displaystyle +\frac{k-1}{k}\cdot dp[i-1][j]$
其中這三行分別對應三種轉移過來的狀態，並且第二行的顯然可以化簡成$O(1)$計算的東西。因此我們得到了一個$O(n^2)$的算法。

如同很多需要算機率和期望值的題目一樣，若列出的轉移式為$O(n^2)$的，但數字範圍不允許這種複雜度，那麼就可以考慮把機率值太小的地方直接砍掉不算他。在這題中，注意到經過$n$天之後期望的等級不會太大，因為每次增加$1$的機率會越來越小。如果要算準確的話，當等級$i$時只有$\frac{1}{i+1}$的機率會增加，也就是期望需要$i+1$天才能增加$1$，因此可以列出$2+3+...+(x+1)=n$，其中$x$是期望的等級數。因此期望等級數大約在$\sqrt{2n}$左右，因此就可以考慮把超過$\sqrt{2n}$太多的$dp$值直接當成$0$。所以我們的DP陣列的第二維就只要開$1000$左右就可以了，這樣就得到了$O(n\sqrt{n})$的算法。

這樣傳上去很哀傷的TLE了，後來我加了個「若$dp$值或$P$值太小就直接把他的值變成$0$」就過了，並且自己測跑的時間快了非常多，至於為什麼可以參考這篇，要是之前我沒有看到那篇這題可能就要TLE到死了......

code :

[CF 464C] Substitutes in Number

作法：

對於一連串的替換操作，可以發現到其實「$1$」這個字不管是落在原字串的哪裡，最後一定都會變成一個固定的很長的字串，這對於$0,...,9$都成立。因此如果我們能算出每個字元在經過所有的替換之後變成的字串的長度，和這個字串本身模$10^9+7$的值，就可以$O(n)$算出答案了。具體來說，假設原字串是$123456$，並且一連串的操作把$6$變成了$777$，$5$變成了$888$，$4$變成了$999$，那麼我們可以算出原本的$4$變成$999$之後應該要乘上$10$的幾次才會是他實際上的值，不難發現他其實就是「$5$最後的字串長度$+6$最後的字串長度」，所以就得到了$999\cdot 10^6$。只要這樣算出每個字元的答案的總和就可以了。

至於如何求最後字串長度和模$10^9+7$的值（以下稱其為$len$值和$val$值），可以把整個過程倒過來看。當沒有進行任何替換時，$0~9$的長度都是$1$，$val$值則是他本身。再來觀察只有進行最後一次替換時$0~9$的$len$值和$val$值應該會是多少，假設這次替換是$x->S$，那麼可以發現此時$len[x]=S$的長度，$val[x]$則變成了$S$代表的值，其他數的$len,val$則不變。

再來我們的目的是，假設現在已經有了「考慮第$i$個替換到最後一個替換時，每個數的$len$和$val$值」，想要推到「考慮第$i-1$個到最後一個時」的兩種值，而這很容易從上面觀察出一般的情形，可以發現其實新的$len[x]$值就是由舊的$len$陣列中，把$S$的每一個字元代入再加起來的結果，而$val[x]$則比較複雜，不過基本上和前面所講的「$O(n)$算出原數列的答案」的精神類似，因為我們知道$S$中的每個字元在經過了第$i$次到最後一次替換之後會變成什麼值了，所以就可以求出$S$經過了第$i$次到最後一次替換後會變成多少，而這個值就是新的$val[x]$了。

最後要注意到，$len$值會爆 long long，事實上我們可以把$len$值拿去模$10^9+7-1$，因為其實可以發現$len$值就是被用來放在$10$的冪次，以求得一個字元真正代表的值的，而因為$10^9+7$是一個質數（記為$p$），由費馬小定理知$a^{p-1}\equiv 1(mod p)$，因此把$len$值加減$p-1$並不會影響結果，所以模$p-1$才會是對的。

code :

[CF 467E] Alex and Complicated Task

作法：

首先想法是 greedy ，我們只要找到一個最小的$i$，使得$a[1],...,a[i]$中存在一個長度為$4$的子序列，滿足他形如$x,y,x,y$即可。當找到這個$i$之後顯然最好的方法就是取那$4$個數，然後把一切清空，當成原數列只有$a[i+1],...,a[n]$去作就可以了。因此問題變為要如何決定那樣子的最小的$i$。

考慮從$1$開始往右掃描，當遇到一個數是之前出現過的數時，假設此時掃描到$a[x]$，並且前一個出現過同樣數字的位子為$a[y]$，那麼我們可以把$a[x],a[y]$之間的所有數字當標記上$a[x]$（注意不是標記位置，是標記數值），因為之後只要一遇到$a[x],a[y]$中間的任何一個數，我們就找到所求的序列了。而為了避免重複標記相同位置的數，可以用一個 stack 來維護，每次加入新數字時，如果這個數字已經在 stack 裡出現過了，那麼就不斷 pop 直到遇到那個數為止，並且把中間 pop 掉的數都標記上當前的數的值。而只要當前遇到的數字是已被標記過的，那麼就等於找到所求的最小$i$了，把那$4$個數丟進答案裡並把所有資料結構清空即可。另外還要注意到也有可能四個數相同，而這只要再多用一個 map 紀錄一個數字出現了幾次就可以了，當一有某個數字出現$4$次時也等於找到一組解了。

code :

[CF 551E] GukiZ and GukiZiana

作法：

將整個序列切成$\sqrt{n}$塊，我們先看每一塊中必須支援什麼操作才有辦法處理題目的要求。對於把原數列的某個區間同加一個數的操作，把他拆成由好幾個已經切好的好幾塊組成，對於其中一塊來說，可能要加的區間完整覆蓋他，或是沒有完整覆蓋，並且滿足沒有完整覆蓋的塊頂多只有$2$個。至於題目的詢問，只要能夠在每塊中查詢某個數第一次和最後一次出現的位置就可以了，枚舉$\sqrt{n}$塊即可找出答案。因此對於每一塊，我們可以用一個 map<long long,vector<int>> ，代表某個數值出現的所有位置（因為可能一個數被加超過 int），還有一個$tag$值代表這裡面所有數都應該要增加$tag$，也就是當查詢的值為$x$時要去 map 的 key 值為$x-tag$的 vector 裡面找。而當我們要把一塊中的部份幾個數同加一個值時，就直接把那塊砍掉重建就好了，因為每次操作至多發生兩次這樣的事，所以複雜度不會爛掉。

但這樣傳上去TLE了，我後來加了個優化才過：因為詢問的數頂多到$10^9$，而且每次對一個區間加的數都是非負的，所以當某個位子的數超過$10^9$時他就再也不可能被詢問到了，因此可以在重建某一塊時直接忽略掉那個位子的數。另外對於每一塊也一樣，如果有一天某一塊的$tag$值超過$10^9$，那麼那一塊就廢掉了，之後重建就可以不用裡他了。這樣就可以把所有 long long 都改回 int ，因為測資很大，所以這樣就可以快很多了。

code :

[CF 468E] Permanent

作法：

這題我是按照官方解寫的，但官方解寫的蠻簡略的，這裡紀錄一下詳細作法。

我們要處理的問題現在已經轉換成要求「在一張二部圖中的所有有$t$條邊的匹配的權重總和」，其中一個匹配的權重等於裡面所有邊的邊權乘積。對每個$0\leq t\leq 50$都要求出這個東西的答案（要注意到空匹配的權重等於$1$）。我們可以把每個連通塊分開求，然後再合併成所求的答案陣列。具體來說，如果其中一個連通塊的答案陣列為$a$（也就是$a[0],...,a[50]$分別是那個連通塊的答案），另一個的則為$b$，那麼可以得到在這兩個連通塊中有$i$條邊的匹配的權重總和等於$\displaystyle \sum_{j=0}^{i} a[j]\cdot b[i-j]$，因為兩個連通塊中的邊數加起來要等於$i$。至於為什麼是直接相乘，因為$a[j]$其實是由好幾個$j$個數（邊權）的乘積加起來得到的，其中每個乘積都代表一種這個連通塊中的選$j$條邊的匹配方法，$b[i-j]$也類似，因此把這兩個數相乘就對應了「所有在第一塊中選$j$條，在第二塊中選$i-j$條的所有匹配的權重和」，恰好就是我們要的了。

因此現在就對每個連通塊分開處理，在第一種算法中，因為他是二部圖，設在這個連通分量中被分成的兩部份分別有$x,y$個點，那麼考慮$dp[i][j]$代表所有滿足以下條件的匹配的權重總和：這個匹配在第一部份中只用到了前$x$個點，並且在第二部份中有被匹配到的點的集合恰好為$j$。這樣的DP可以在$O(|E|\cdot 2^y)$的時間內找出所有的 DP 值，其中$|E|$是這個連通塊的邊數（DP的轉移式蠻顯然的，這裡省略），進而求出這個連通塊的答案。因此當$x$或$y\leq 17$時就可以使用這個算法。這裡要先處理好這個連通塊中的那$x$個點和$y$個點分別是誰，還有一個點是落在他那部份的第幾個點。

再來則是第二種算法，先找出這個連通塊的任意一個生成樹，把所有非樹邊都找出來，然後$2^k$暴力枚舉要用哪些非樹邊。所以這裡如果有一個點屬於被選到的兩條邊的話就是不合法的。選完之後算出共有幾條邊，還有這些邊的權重乘積，並且把被蓋到的點都標記起來，等一下不能夠選到有碰到這些點的邊。再來則是對這棵生成樹DP，因為我們需要的東西是「這棵樹中所有有$t$條邊的匹配的權重總和」，所以每個節點紀錄的東西就會是一個陣列，代表「在他以下的這棵子樹裡，所有有$t$條邊的匹配的權重總和」的對於每個$t$的答案。再來看如何轉移，因為在算$x$的DP陣列時，有一種可能是「取了$x$連到他其中一個兒子的這條邊當作匹配邊」，因此我們紀錄的狀態還要再多一維（只有$0$或$1$），代表那棵子樹的根是否有被匹配。這樣就可以轉移了，注意到這裡是要從$x$的子樹的DP陣列們合併成$x$本身的DP陣列，這可以一個子樹一個子樹合併，也就是當我們合併完前$i$棵子樹時，$x$本身的DP陣列會是「只考慮$x$的前$i$棵子樹，加上$x$這個點形成的子樹」的DP陣列。具體來說，記$dp[i][j][k]$代表滿足「以$i$為根的子樹中，選了$j$對匹配點，$k$代表是否有選到根（$k=0$代表沒有）」這些條件的匹配的權重總和，並且假設現在在算$x$的DP陣列，記$x_1,...,x_r$為所有$x$的子節點，那麼記$dp2[i][j][k]$代表「只看$x_1,...,x_i$這些子樹再加上$x$形成的子樹，裡面選了$j$對匹配點，$k$的意義一樣」的匹配的權重總和，那麼就不難列出轉移式了：
$dp2[i-1][j][0]\cdot (dp[x_i][j_2][0]+dp[x_i][j_2][1])$  轉移到  $dp2[i][j+j_2][0]$
$dp2[i-1][j][1]\cdot (dp[x_i][j_2][0]+dp[x_i][j_2][1])$  轉移到  $dp2[i][j+j_2][1]$

$dp2[i-1][j][0]\cdot dp[x_i][j_2][0]\cdot w_{x,x_i}$  轉移到  $dp2[i][j+j_2+1][1]$

其中第三條轉移式只有在$x$和$x_i$都沒有被標記起來時才可以用，$w_{x,x_i}$代表$x$和$x_i$之間的這條邊的權重，邊界為$dp2[0][0][0]=1$。

如同許多需要在樹上合併DP陣列的題目一樣，因為每個節點的DP陣列大小都要開$k\cdot 2$，所以如果直接作的話單次DP複雜度會到$O(k^3)$，再乘上枚舉非樹邊的最差狀況$2^{17}$會TLE掉，而這只要注意到：對於一個子樹$x$來說，$dp[x][j][k]$在$2\cdot j>size[x]$時就都會是$0$了，因為沒有那麼多點可以匹配，其中$size[x]$是$x$的子樹的大小。因此當我們在從$dp2[i-1]$這個陣列去計算$dp2[i]$這個陣列時，令$S=x$的前$i-1$棵子樹的$size$總和$+1$，那麼我們只要用$dp2[i-1]$這個陣列的前$S/2+1$個值來轉移就好了（也就是$dp2[i-1][0][k],...,dp2[i-1][S/2][k]$），因為剩下的一定都是$0$。並且在枚舉$dp[x_i][j_2][k]$時$j_2$一樣枚舉到$size[x_i]/2$就夠了，後面的也都會是$0$。加了這件事之後單次DP複雜度就能降回$O(k^2)$了，證明可以參考這篇。大部份需要在樹上合併DP陣列的題目都可以用這件事來降複雜度。

code :

[CF 468D] Tree

作法：

首先先觀察最佳解的排列會滿足什麼特性。現在等於是樹上有$n$條路徑，分別是$i$走到$p[i]$。如果兩條路徑$(i,p[i])$和$(j,p[j])$沒有公共點的話，那麼把$p[i],p[j]$交換會讓答案更大，因此就可以得到在最佳解時任兩條路徑都有公共點。接下來證明若在一棵樹上有很多條路徑，並且任兩條路徑都有公共點，那麼所有路徑有一個公共點。記這些路徑為$P_1,...,P_k$，考慮$P_1$和其他路徑的交集部份，他們都是由$P_1$上的某一段連續的點組成的（所以可以看成一個區間），並且易證明任兩個區間都有交集，否則原圖中會出現圈，矛盾。那麼這個命題就變得顯然了，因為這樣的$n$個區間必定會有一個公共點。

再來我們想知道有哪些點有資格被當作所有路徑都經過的點。對於某個點$P$來說，考慮$P$的最大的子樹，如果這棵子樹的大小$>\left \lfloor \frac{n}{2} \right \rfloor$，那麼顯然$P$不能被當作剛才所說的公共點，因為在那棵子樹裡的點都必須連向不在那棵子樹裡的點，但那棵子樹裡的點太多了，所以矛盾。因此我們得到了公共點必須滿足「把他拔掉後剩下的所有子樹大小都$\leq \left \lfloor \frac{n}{2} \right \rfloor$」。並且不難證明這是充要條件，任意構造一個就可以了，在這裡省略。有了這個條件後就不難想到取重心應該是對的，而事實上也只有重心會滿足這個條件，證明就補在這篇的最後面。

因此就可以得到第一個答案是所有點到重心的距離和的兩倍，麻煩的是要求出字典序最小的解。首先以重心為根建成有根樹，我們把題目轉成二分圖完美匹配來看，對於$i$指向$p[i]$，可以把他看成「$i$的出點」連向了「$p[i]$的入點」，所以如果把每個點都拆成出點和入點，並且若$i,j$在不同的重心的子樹裡，那麼在$i$的出點和$j$的入點之間連一條邊，這樣就變成了求這張圖的字典序最小的完美匹配了。首先考慮這樣的算法：當要決定$p[i]$為多少時，就從$1$開始往上枚舉，找出第一個「$i$的出點連了他的入點之後整張圖還存在完美匹配」的點，並且他還沒被別人選過，那麼$p[i]$就等於他。但問題是要知道存在完美匹配的條件，才能從剩餘的候選人裡選出值最小的拿來當$p[i]$。記重心的所有子樹們為$T_1,...,T_r$，對於某個瞬間來說，假設$T_i$的出點數量為$a_i$，入點數量則為$b_i$（因此在一開始$a_i=b_i=T_i$的大小），那麼可以列出一條蠻顯然的式子：$a_i\leq b_1+...+b_{i-1}+b_{i+1}+...+b_r$，因為$T_i$中的剩下的出點必須去找$T_i$以外的子樹的入點來連，所以顯然個數要比候選人少。而由 Hall 定理（二分圖存在完美匹配的充要條件）可以得到這件事就是充要條件了。將上式改寫成$a_i+b_i\leq b_1+...+b_r$，並且易知$b_1+...+b_r$等於還沒匹配的點的對數，也就是我們得到了在任一瞬間，對於所有的$i$都必須滿足$a_i+b_i\leq$還沒匹配的點的對數。因此就得到了這樣的算法：當要計算$p[i]$時，先看看有沒有哪棵子樹的$a+b$的值已經等於還沒匹配的點的對數了（這裡還沒匹配的點的對數其實就等於$n-i+1$），如果有的話那麼$p[i]$就必須要從那棵子樹裡取，那麼就取那棵子樹中值最小的點即可。如果沒有這樣的子樹的話，就可以取$i$所在的子樹以外的所有點，因此也取這些點中的最小的點即可。實作上可以對每棵子樹紀錄一個 set ，代表還有哪些入點還沒用，還有一個 set 裡面放了每棵子樹的入點的最小值，根一個 set<pair<int,int>> ，其中 pair 的第一個值為某棵子樹的$a+b$值，第二個則為這是第幾棵子樹，維護好這些東西就好了。另外還要特判根，也就是要記得判$i$是根的情形，還有有可能取的$p[i]$是根的情形。

最後，以下證明前面提到的「一個點是重心若且唯若可以被當作公共點」。

設$P$為重心，若$P$不可被當作公共點，設$T_1$是$P$的大小$> \left \lfloor \frac{n}{2} \right \rfloor$的子樹，其根為$Q$，那麼把$Q$拔掉的話，包含$P$的那棵子樹的大小就會$<n-\left \lfloor \frac{n}{2} \right \rfloor=\left \lceil \frac{n}{2} \right \rceil$$\leq  \left \lfloor \frac{n}{2} \right \rfloor+1\leq T_1$的大小，並且把$Q$拔掉後的其他子樹大小顯然都會小於$T_1$的大小，因此把$Q$拔掉會讓剩餘的最大子樹的大小比把$P$拔掉的還要小，則$P$不是重心，矛盾。因此重心可以被當作公共點。

再來證明非重心的點不能被當作公共點，一樣設$P$為重心，並且$Q$不是重心，他落在$P$的$T_1$子樹中，那麼有$T_1$的大小$\leq \left \lfloor \frac{n}{2} \right \rfloor$，因此整棵樹扣掉$T_1$的大小$\geq \left \lceil \frac{n}{2} \right \rceil$，因此可以得到若$Q$想要當公共點，他就必須是$T_1$的根，並且滿足$T_1$的大小剛好是$\left \lfloor \frac{n}{2} \right \rfloor$，並且整棵樹扣掉$T_1$的大小要剛好是$\left \lceil \frac{n}{2} \right \rceil$，所以就可以得到$n$為偶數，$T_1$的大小為$\frac{n}{2}$，所以$Q$也是重心，矛盾。

code :

[CF 471E] MUH and Lots and Lots of Segments

作法：

首先大概可以想到把所有連通塊分開作（如果兩條線段有相交的話就在他們之間連邊，這樣子形成的連通塊）。對於一個連通塊來說，可以發現如果答案是用這個連通塊的話，所有線段會形成一個類似生成樹的東西，但也不完全是，而如果把一條線段的每個單位長全部拆開來，他就的確變成了一棵生成樹了，因此就只要算出這個連通塊的線段總共覆蓋了多少個格點，再減一就會是這個連通塊砍完多餘線段後剩下的線段長度了，這個部份就可以用掃描線作了。但要注意到如果有兩條同方向的線段有交集要先處理掉，把直的和橫的線段都轉換成同方向沒有公共點的線段們。再來問題剩下要如何把每個連通塊都分出來，這裡反而比較麻煩，首先考慮一個比較樸素的算法，利用掃描線按照縱座標由下往上掃描，維護此時有哪些$x$座標有鉛直的線段，並且在遇到一條橫線時把所有他有交到的鉛直線和他都連到同一個連通塊中，這裡可以用 disjoint set 實作。問題是這樣太慢了，而注意到要被歸到同一個連通塊裡的鉛直線們是在座標上連續的一段區間，所以可以考慮用 Treap 加上 lazy tag 來維護所有的當前鉛直線，當我們要把一段區間的所有區間都歸到同一個連通塊時，就把那段區間的 Treap 切下來，在他的根放上 lazy tag 然後 merge 回去就好了。並且這時也可以順便算答案，因為當遇到一條橫線，我們把對應的區間切下來時，被切下來的這棵 Treap 的大小就是這條橫線交到的直線數量，有了這些值和每條線段所屬的連通塊後就不難算出每個連通塊的答案，取最大的那個就是我們要的了。

code :

[CF 472G] Design Tutorial: Increase the Constraints

作法：

這題我是照官方解寫的，而有很多人是直接想辦法加速位元運算來過的，但我沒有仔細看他們的寫法，詳細可以去看看別人寫的 code 。總之我寫了FFT，首先把原始的第一個字串拆成好幾塊，每一塊都做一次FFT求得那一塊和第二個字串反過來的多項式乘積。對每個詢問都把他拆成遇處理好的幾塊根左右的一些小渣渣，那兩小塊就暴力做就可以了，但不能一個一個比，一個簡單的加速方法就是把這兩個字串的$64$個 bit 壓成一個數，然後直接對他位元運算，然後用$\_\_builtin\_popcountll()$這個函式來算出一個 long long 裡有幾個 bit 是$1$。這樣就能讓暴力那部份的常數少$64$倍。具體來說，只要先對兩個字串的每個位置都遇處理一個數，代表「從這個數開始往後數64個（若到底了就停），這些 bit 壓起來的值是多少」就可以了。

對了，這次的FFT我換成了模大質數和原根版本的FFT，以一個質數的原根來取代$1$的$n$次單位根，並且所有數字和運算都是在模那個大質數意義下進行的，詳細可以參考這篇。（這種寫法好像叫作NTT）

code :

[CF 472F] Design Tutorial: Change the Goal

作法：

這題我是照著官方解寫的，這裡紀錄一下大概作法和證明。

首先就是對給定的陣列和目標陣列做高斯消去，找出這兩個陣列的基底們。假設前者的為$u_1,...,u_x$，後者的則為$v_1,...,v_y$。再來我們需要一個函數把$v_i$以$u$們表示出來，或是回傳無解。也就是我們想要找出$a_1,...,a_x\in \{0,1\}$，使得$\displaystyle \sum_{i=1}^{x} a_i\cdot u_i = w$，其中$w$是一個給定的向量。這也可以透過高斯消去得到解，只要在作完高斯消去時從最後一個變數往前解回去就可以解出所有的$a_i$了（因為此時矩陣已變成了 row echelon form），詳細可以參考 code 。因此就從$v_1$開始，找出他用$u$表示的型式，然後不難把$u_i$們的$u_1$ xor 成$v_1$（因為已經知道他的組成了），並且做完這件事後（不難證明）$u_i$們還會是一組基底。而當我們已經把$u_1,...,u_k$都歸位了（也就是他們分別等於$v_1,...,v_k$時），首先找出$v_{k+1}$對$u_i$們的分解，這時因為我們不能再動到$u_1,...,u_k$，所以如果$u_{k+1}$本身不在$v_{k+1}$的組成中時必須拿$u_{k+2},...,u_x$這些向量的其中一個來和$u_{k+1}$交換，並且滿足這個向量在$v_{k+1}$的組成中。這件事是總是辦的到的，因為如果$v_{k+1}$的組成中沒有任何$u_{k+1},...,u_x$裡的向量，那麼就代表他是由$u_1,...,u_k$組成的，而$u_1,...,u_k$分別等於$v_1,...,v_k$，也就代表$v_1,...,v_k$可以組成$v_{k+1}$，和$v$是一組基底矛盾，因此這樣做不會有問題。最後還要注意到的是，如果$y<x$，那麼要記得把$u_{x+1},...,u_y$全部都自己 xor 自己變成$0$，才會和目標陣列高斯消去後的結果一樣。

code :

[CF 472E] Design Tutorial: Learn from a Game

作法：

首先當$n=1$或$m=1$時暴力枚舉即可。其他情形先確認是否所有珠子的個數都是對的，如果不是那就顯然無解。

首先可以想到策略大概就是一個一個把珠子歸位。首先拿起和目標盤面右下角同色的珠子，用他來轉，然後由上到下一排一排歸位，同排時由左到右一個一個歸位，直到剩下兩排時再從左到右兩顆兩顆歸位。當我們想要把$(x,y)$的珠子歸位時，如果當前手指的位置不在這裡，並且這格和目標格的顏色一樣，那麼什麼都不用作。反之找一個和這格的目標格顏色相同的珠子，假設位於$(x_1,y_1)$，那麼此時要想辦法把$(x_1,y_1)$轉到$(x,y)$上。首先找一條$(x_1,y_1)$走到$(x,y)$的路徑（走八方位都可以），這可以用DFS完成，並且在DFS時每次只走「離終點距離最近」的那幾個後繼節點。找到這條路徑後，假設$(x_1,y_1)$走上這條路徑的下一步是$(x_2,y_2)$，那麼此時只要想辦法讓手指的位置走到$(x_2,y_2)$，途中要避免走到$(x_1,y_1)$，然後再和$(x_1,y_1)$交換即可。因此我們需要一個「找一格到另一格的路徑，其中避免走到另外一格」的函式，不難發現一定存在這樣的路徑，實作也是DFS就可以了（和前面講到的那個DFS可以寫在一起）。

code :

[CF 549F] Yura and Developers

作法：

通常這種需要考慮區間最大值的題目，可以先令整個數列的最大值的位置為$x$，那麼所有包含了$x$的區間的最大值都會是$x$，這樣問題就變成要如何找有幾個包含$x$的區間，滿足他裡面的總和模$k$是給定的一個數。處理完這個之後就可以拆成$x$左邊和$x$右邊遞迴下去解了。考慮樸素的作法，就是直接枚舉包含了$x$的區間，這樣複雜度會高達$O(n^2)$，不過仔細想想可以發現，假設現在固定了所求區間的右端點，我們想要知道有幾個左端點可以讓這個區間滿足條件，而把一個區間的數的總和改寫成前綴和相減後就可以得到，這個問題就等價於「在前綴和陣列的某一個區間中有幾個數模$k$是某個特定的數」。這可以透過建立模$k$的餘數的所有出現的位置加上二分搜得到答案。於是現在處理上述問題的複雜度變成了其中一邊的長度再乘上$logn$，不過最差狀況下這樣還是會退化到$O(n^2logn)$，而事實上只要每次都取短的那邊去枚舉就好了，這樣複雜度就會是好的。因為當一個點被枚舉到一次時，他所在的區間就至少縮短了兩倍，因此每個點至多被枚舉到$logn$次，所以總複雜度就會是$O(nlog^2n)$。

code :

[CF 549G] Happy Line

作法：

這題只要觀察到：當$a_i$和$a_{i+1}$交換時，所有數形成的$i+a_i$的集合都不會變，因為當交換時這兩數的$i+a_i$值是從$(i+a_i,i+1+a_{i+1})$變成$((a_{i+1}+1)+i,(a_i-1)+i+1)$ 。並且顯然這是充要的，也就是如果兩數列的$i+a_i$集合相同，那麼就可以把一個變成另一個（只要一個一個放到對的位子就好了）。所以現在有了$i+a_i$的集合，我們想要讓$a_1,...,a_n$是遞增的，那麼$a_1$的值越小越好，那麼就取$i+a_i$集合裡最小的那個數扣掉$1$就是所求的$a_1$了，這樣取會是最好的。同理$a_2$會取集合裡第二小的數，以此類推。因此只要按照$i+a_i$值排序就可以找出解了。

code :

[CF 549C] The Game Of Parity

作法：

記總共有$x$個奇數和$y$個偶數。首先發現，如果最後一個人拿的時候奇數和偶數都至少還有一個，那他就贏了，因為他一定可以選其中一個使得他贏。所以非最受一手的那人就要想辦法把其中一堆拿光。這樣就分成四種情況：先手/後手最後拿、還有$k$是奇數/偶數。當先手最後拿時，如果$k$是奇數，那麼後手只能把$x$拿光，否則後手可以選擇把$x$拿光或把$y$拿光。當後手最後拿時，如果$k$是奇數，那麼先手就必須把$y$拿光，$k$是偶數時則必為後手贏。最後要記得判掉$n=k$的情形，這東西陰了一堆人=ㄦ=

code :

[CF 549B] Looksery Party

作法：

這題簡單來說就是，給定$n$個字串，還有一個目標字串$S$，要求在這$n$個字串裡選出幾個，使得把他們逐位加起來之後每位都和$S$不一樣。首先當$S$裡沒有$0$的時候顯然什麼都不取就可以了，而如果有一個位子$x$是$0$的話，因為題目保證第$i$個字串的第$i$項會是$1$，那麼就考慮直接取第$x$個字串看看，這樣可以發現：不管之後如何選，$x$那個位子的值只會增不會減，也就是之後可以完全忽略他了。這樣就得到了一個非常簡潔的算法：當還有位子的值和$S$的那個位子的值一樣時，就取對應的那個字串，一直作到滿足目標為止就可以了。

code :

[CF 477E] Dreamoon and Notepad

作法：

這題我是看了官方解的大概才會作的，這裡紀錄一下詳細的作法。

首先在讀入問題時，就可以把「按一次HOME」和「一路按往上/下到指定那列，再按左右調整到所求的位置」的答案算好了，後者需要一次RMQ，我是用 Sparse Table $O(1)$查詢的，因為之後也需要RMQ，用$O(1)$可以降一些複雜度。

對於官方解中的第二種情形，假設此次詢問是$(x_0,y_0),(x_1,y_1)$，其中可以假設$x_0\leq x_1$。那麼假設我們在第$x$列的時候按下了END，那麼走的步數就會是：$x_1-x_0+|y_1-min\{ a_x,...,a_{x_1}\} |+1$（注意到因為沒有按下END的情形已經在前面處理過了，所以這裡的$+1$是一定會存在的），並且$x$還要滿足$x\geq x_0$，因此此時會需要$min\{ a_x,...,a_{x_1}\}$這個東西的函數圖形。而不難知道這是一個隨著$x$變小而變小的階梯狀函數，所以考慮當$x$從$x_1$開始往左邊跑，把所有「$a_x$創新小」的點紀錄起來，具體來說那些「創新小」的點就是滿足$a_x<a_{x+1},...,a_{x_1}$的$(x,a_x)$（包含$x_1$本身）。有了這些點就可以很好的代表這個函數圖形了（之後稱這些點為這個函數的「代表」）。假設我們現在已經有了這個函數圖形（也就是這些點們），那麼可以發現我們要 minimize 的函數只和$y_1$和階梯函數的差值有關，因為這個階梯函數是單調的，所以只要找代表點們和$y_1$最接近的地方就可以了，因此就用一個 lower_bound 找出第一個$x$座標$\geq x_0$的代表是誰（假設叫$id_1$），然後從$id_1$到最後一個代表裡用一個 lower_bound 找出第一個$y$座標$\geq y_1$的代表是誰（假設叫$id_2$）（把代表點的$x$座標和$y$座標分開存就可以輕鬆 lower_bound 了），那麼就可以拿$id_2-1$和$id_2$代入上面那坨我們要 minimize 的函數裡面更新答案。這裡有可能所有代表的$y$座標都同時大於$y_1$或小於$y_1$，不過這樣的算法可以好好的處理這種情形。

但實作上總不能對每次詢問再去找出他的$x_1$造出的$min$函數的代表們，所以才離線處理所有詢問。把所有詢問按照$x_1$由小到大排序，用一個 stack 來存當此時詢問的 $x_1$ 值是 $i$ 的話他的代表們會長怎樣，那麼當詢問的$x_1$值變大的時候就不難維護這些代表們了。注意到這裡只處理了$x_0\leq x_1$的情形，當$x_0 > x_1$ 時必須略過這個詢問（因為現在這個 stack 不會是我們要的） ，這個到後面講實作的時候再來提要怎麼處理他。

再來是官方解中的第三種情形（這邊不用假設$x_0\leq x_1$），那麼此時就是先往上走到第$x$列，然後按下END（或不按），再往下走到目標列。我們先討論有按END鍵的情形，因為就算沒有按也可以按下一次（雖然沒有意義），之後再看怎樣的情形是可以不用按END鍵的，兩個都拿去更新答案就會對了。如果往上走到第$x$列，那麼總共的步數就會是$|y_1-min\{ a_x,...,a_{x_1}\} |+(x_0-x)+(x_1-x)+1$$=|y_1-min\{ a_x,...,a_{x_1}\} |-2x+x_0+x_1+1$。想像$x$從$x_0$開始慢慢變小，那麼一樣$min\{ a_x,...,a_{x_1}\}$會變小，$-2x$會變大，所以可以推得這個函數達到最小值的時候，其$x$座標一定會是那個$min$函數的一個代表。因為如果不是的話，那麼取這個點右邊的一個點，他的$min$函數值跟原本自己的一樣（因為他不是代表），但所求值中的$-2x$值變小了，因此所求函數在不是代表的數不可能達到最小值。再來想像當$x$一直變小，到有一天$min\{ a_x,...,a_{x_1}\}$ 變得$\leq y_1$時，比這個$x$小的所有數都不會讓這個函數取到最小值了，因此可以把求這個函數的最小值分為兩段來處理，一段是讓那坨$min$值$\geq y_1$的，另一段則是那坨$min$值$\leq y_1$的，由上面的推論知道第二段裡只須考慮一個點就好。對於第一段裡的代表們來說，可以把絕對值拆開，就變成$min\{ a_x,...,a_{x_1}\}-y_1-2x+x_0+x_1+1$$=(min\{ a_x,...,a_{x_1}\}-2x)+(x_0+x_1+1-y_1)$。因此我們要在$min$函數的代表們的一段區間中，詢問「代表的$y$座標扣掉兩倍的$x$座標」的最小值是多少，其中這個區間是滿足$min\{ a_x,...,a_{x_1}\} \geq y_1$且$x\leq x_0$的代表$x$們（一樣可以分別用個 lower_bound 求出）。因此在離線處理詢問維護 stack 的同時也要維護一棵線段樹，這顆線段樹用來維護的底層序列的第$i$項的值就是現在在 stack 中的第 $i$ 個代表的$y$座標扣掉兩倍$x$座標的值。那麼當把一個東西 push 進 stack 的時候就等於修改這棵線段樹的底層序列的某個值， pop 的時候則什麼都不用作，這樣就能得到上述函式的最小值了。

接下來還要處理不用按END的情形，還有被分出來的$min$值$\leq y_1$的那個代表。先看前者，既然不用按END，那麼代表此時是從第$x_0$列往上走到第$x$列，然後直接往下走回第$x_1$列，並且我們需要 minimize 的式子和剛才那條幾乎一樣，兩式只有差$1$，所以可以套用剛才的一些結果。在這裡分成兩種情形來看，首先是$x_0\leq x_1$時，由剛才的結論可知最佳解$x$一定是一個代表，那麼此時就必須滿足$a_x\leq y_0$，又因為$a_x$是個代表，所以可以寫成$min\{ a_{x_1},...,a_x \} \leq y_0$。反過來當$x$滿足他是一個代表，並且$a_x\leq y_0$時，不難得出從$x_0$往上走到$x$時其橫座標會停留在$a_x$，所以此時不用按END。再來則是$x_0\geq x_1$時，那麼當從$x_0$往上走的時候，會先經過$x_1$，此時其橫座標會是$min\{ y_0,a_{x_1},...,a_{x_0} \}$，並且由一樣的理由可以得到此時$x$必須滿足$a_x\leq min\{ y_0,a_{x_1},...,a_{x_0} \}$，且他也是充要條件（這就可以用之前建好的 Sparse Table 來算）。因此這樣就得到了「不用按END」的那些列的範圍了，只要再用一次 upper_bound 就可以得到此時$x$必須$\leq$某個值，再和前面「不考慮是否要按END」時得到的區間交集，就知道要對線段樹的哪一段 query 了，然後拿上面的式子的值去更新答案（但此時是少了$+1$的）。

最後則是被分出來的$min$值$\leq y_1$的那個代表，由上面的條件容易確認當$x$等於他時到底要不要按END，一樣拿他去更新答案即可。

到這裡我們解決了官方解中的第一、三種情形，還有第二種情形的一半，接下來則是要把整個$a$數列反轉，把每一個詢問也反轉（原本的$x_0,x_1$變成$n+1-x_0,n+1-x_1$），再重做一次上述過程就可以了（Sparse Table 要重建，線段樹則不用理他），這樣就能把官方解中剩餘的情形（二的一半和四）補完了。

code :

[CF 477D] Dreamoon and Binary

作法：

這題我的作法跟官方解幾乎一樣，但最後輸出答案的時候可能會有問題。因為題目要問的是「最後一塊的數字大小加上切的塊數」的最小值，所以可能可以想到最後一步就是枚舉最後一段的開頭是誰，那麼從$dp[i][n]$就可以得出答案。但我們總不能把所有所求的答案用大數表示出來後再來比大小，這樣時間可能會很恐怖。只要注意到因為切的塊數$\leq n\leq 5000$，並且當最後一個區間越來越大時，最後一塊的數字大小幾乎是一直在乘$2$的（因為最後一塊的開頭當然也不能是$0$），因此在大約十幾之後數字大小就會成為主要的關鍵。因此最後的找法就變成：先考慮長度$\leq 20$的後綴，如果有可以達到的狀態，把他們的答案的值都算出來，找出他們的最小值，那麼這個數就會是答案了。否則從長度$20$的後綴開始往長度大的方向找，找到的第一個合法狀態就會是答案了。

code :

[CF 550E] Brackets in Implications

作法：

這題就是個構造題，看了這份code之後就覺得我寫的解也太複雜了QQ
首先我是考慮用遞迴來輸出解，所以對於一個區間$[L,R]$來說，當要 print $[L,R]$ 中的數時，用一個 map 來存這個區間的切的端點是誰，也就是令那個值等於 $mid$ 的話，要先遞迴下去$[L,mid]$輸出，再遞迴下去$[mid+1,R]$輸出。首先觀察出當$a[n]=1$時無解，所以只須考慮$a[n]=0$的情形。注意到因為$1\rightarrow 0=0$，因此可以先讓所有的$0$把他左邊所有的$1$都吃掉，讓整串剩下全部都是$0$。如果只剩一個$0$那就做完了。否則如果剩下的$0$的個數$\geq 3$，那麼就可以把倒數第二和第3個$0$包起來變成$1$，$1$再往左把所有的$0$作用掉，最後再和右邊的$0$作用。至於兩個$0$的情形，如果$a[n-1]=0$，那麼可以推得此時也無解（怎麼消都還是長一樣），所以只須考慮原本的兩個$0$之間有$1$的情形，這時則可以先用$1$把那個$0$消掉，這樣就變成只有一個$0$的情形了。

code :

[CF 550D] Regular Bridge

作法：

這題我的構造跟官方解的一樣，這裡就寫一下我是怎麼想到的。
因為要有橋，所以大概可以想到把橋的兩邊分開構。因為每個點的度都要是$k$，所以當把橋拔掉後，其中一個連通分量裡每個點的度會長的像：$k-1,k,...,k$。因此當$k$是偶數的時候無解，因為度總和必須是偶數。當$k$奇數時，$k=1$題目構完了，如果$k=3$，先試著構一個度為$2,3,3,3,3$的圖（因為$3$個$3$時奇偶性不對，$3$個以下時點太少），假設五個點分別為$ABCDE$，那麼先連$BD,CE$，剩下的只要再找一個圈就可以了，也就是連上$AB,BC,CD,DE,EA$，這樣就構完$k=3$的情形了。仔細觀察可以發現，其實他就是一個$k+2$接完全圖，拔掉$A$和其中兩個點（$C,D$）連的邊，然後把剩下的點（$B,E$）兩兩配對，把他們之間的邊拔掉所得來的，並且這個構造容易推廣到$k$是更大的奇數的情形，於是在把兩個這樣的圖用橋連起來就做完了。

code :

[CF 480E] Parking Lot

作法：

把整個過程反過來，變成原本有很多格子是被佔的，當一格一格移除時詢問此時的答案是多少，那麼顯然答案會是遞增的。假設當前答案為$A$，那麼當移除一個格子$(x,y)$時，如果答案變大了，那就代表新的正方形一定包含了(x,y)。因此我們需要判斷「是否存在一個正方形，邊長為$A+1$，並且包含了$(x,y)$」。每次修改一個點之後就一直增加答案，直到不存在那麼大的正方形為止，那麼可以知道這個函數只會被呼叫$O(n)$次，因此可以考慮在$O(nlogn)$的時間實作他。

假設現在要處理的是包含$(x_0,y_0)$的邊長為$k$的正方形，那麼在這個正方形有覆蓋到的每一個橫排中，都包含了$y$座標為$y_0$的格子，並且這個正方形有可能覆蓋的橫排至多有$2k-1$個。因此如果我們對每個橫排，都找出$y$座標離$y_0$最近但比$y_0$小/大的格子，就知道如果那個正方形摸到了這個橫排，那麼他一定要被卡在哪兩個格子之間了。也就是對每個$i\in [x_0-k+1,x_0+k-1]$，記$L[i],R[i]$代表在這個橫排中，第$L[i]$到第$R[i]$個格子都是未被佔領的，並且其中包含了$y_0$。注意到如果$y_0$本身就已經被佔領了，那麼就可以把這個區間為設為$[y_0,y_0-1]$之類的空區間。有了這些$L,R$值之後，只要看連續$k$個橫排的$L$值的最大值，和同樣這$k$排的$R$值的最小值，看相差是否有$\geq k-1$就可以了。因此就從上往下掃，用兩個 multiset 維護$L,R$值們就好了。另外記得預處理每個橫排中有哪些被佔領的格子，把他們加入一個 set 中，才可以用 lower_bound 快速找出$L,R$的值。

code :

[CF 480D] Parcels

作法：

首先把每個箱子的進入時間和出去時間畫在數線上，轉換成一條線段，那麼可以到如果有兩個箱子都有出現在台子上，那麼要嘛一個箱子的線段完全包含另一個的，要嘛兩個箱子的線段不相交（端點可以碰到），或是說他會形成一個類似樹形結構的東西，所以大概可以想的到是某種DP。以下我們稱滿足上述條件的線段們為「合法的」，還有如果把這些線段（箱子）拿去模擬放在平台上的話平台所需支撐的最大重量為這群線段的「最大重量」。

我們要處理的問題是「在這個耐重$S$的台子上，使用那$n$條線段所獲得的最大價值」，因此我們可以加上第$n+1$個箱子，他對應的線段是$[0,2n-1]$，耐重是$S$。因此就可以考慮以下的DP狀態：$dp[i][j]$代表現在只考慮所有第$i$條線段所包含的線段（包括$i$本身），那麼當在這之中選出一群合法的線段，並且這群線段的「最大重量」不超過$j$時，所能獲得的最大價值。在轉移的部份，如果$i$沒有自己以外包含在他內部的線段，那麼他的所有$dp$值都是顯然的。否則第一種轉移方法是：不取第$i$條線段，此時我們可以選好幾條包含在$i$內的線段$S_1....,S_r$，滿足任兩條線段不相交（可以端點重合），轉移到$dp[S_1][j]+...+dp[S_r][j]$。另一種轉移方法則是取$i$，那麼就會直接等價於$dp[i][min(str[i],j-wei[i])]$的情形了，其中$str$代表那個線段的強度，$wei$則是代表重量。顯然第一種轉移沒辦法直接轉，這裡我們可以再用一個DP，因為當$i,j$確定時，對於所有包含在$i$內的線段$k$（$k\neq i$），取他的話等於價值增加了$dp[k][j]$，也就是會是固定的，因此這裡就可以轉換成簡單的問題：數線上有$m$條線段，每條線段都有他的價值，求取好幾條線段使得他們兩兩不相交（可以端點重合）的話價值總和的最大值。這顯然可以先對每條線段的右端點排序、離散化，然後令$dp2[i]=$只考慮線段座標落於$[1,x]$之類的線段時所能獲得的最大價值，則轉移是顯然的。

總結來說，可以先把所有線段按照右端點由小到大排序，一樣時按左端點由大到小排序，那麼上面說的DP過程就可以按照$1,2,...$的順序來做了。並且在作一條線段的DP值時，找出有哪些線段被他包含在裡面，假設有$k$條好了，那麼就可以在$O(klogk+Sk)$的複雜度內求出這條線段的所有DP值了，其中$S$是箱子們的最大強度。

code :

[CF 482E] ELCA

作法：

這題我的作法根官方解只有後半部不一樣，就是在算答案的那部份。前面幾步一樣就是當我們要處理連續的好幾個詢問時，把整棵樹重建（因為可能有一些點被拔到其他地方了），先把那些重要的點找出來，之後叫他們黑點，其餘的則為白點。並且把黑點構成的樹建出來，稱他為新樹，原本題目給的則為原樹。我們要維護的值有兩個東西，就如官方解裡寫的$path$值和$ch$值。首先看如何求$path$值，令$d[x]=(size[fa[x]]-size[x])\cdot val[fa[x]]$，其中$size[x]$為$x$（在原樹）子樹的大小，$fa[x]$則代表$x$在原樹的父節點，$val[]$則是那個節點上標的值，則$x$的$path$值就是由$x$開始一路往上走，走到$1$之前把所有的節點的$d$值加起來（對了，我還有多把$1$標成黑點，這樣新樹的根也是$1$了，不用再區分）。由這件事就可以得到$path$值的算法：如果對每條新樹中的邊都紀錄這條邊上經過的所有點的$d$值總和，那麼一個黑點的$path$值就可以一路沿著祖先的邊走上去並加總得到了。具體來說，假設$x\rightarrow y$是新樹中的一條父親指向孩子的邊，並且令$y$沿著原樹的父親走上去經過的路徑為$y=s_1,...,s_{r-1},s_r=x$，那麼就讓$x\rightarrow y$這條邊上紀錄的值等於$d[s_1]+...+d[s_{r-1}]$（之後叫他$dsum$值）。

再來則是$ch$值（在我的code裡是叫作$pnum$），對於原樹中的一個點$x$，容易得出他的$ch$值會等於$\displaystyle size[x]^2-(\sum_{i}size[i]^2)$，其中$i$跑遍所有$x$的子節點。在建圖的時候可以先對原樹DFS一次，求出每個點的$ch$值，重點是當我們把一個點拔掉和接回去的時候要如何更新每個黑點的$ch$值。如果每次操作完都重新算一次所有黑點的$ch$值的話複雜度會是好的（黑位黑點不多），但不能重算所有黑白點的，因此只能對新樹DFS一次。所以就可以得到對於每條$x\rightarrow y$的邊，我們必須紀錄$size[s_{r-1}]$是多少（$s_i$同上面的記號）（之後叫他這條邊的$ssz$值），這樣才能在新樹中DFS時算出每個黑點的$ch$值。因此每條新樹中的邊會紀錄$dsum$值和$ssz$值。但光這樣還不夠算出黑點的$ch$值，因為在原樹中有可能黑點有一個子樹是全部都是白的，我們當然也要知道他的大小的平方和，因此對每個黑點$x$還要紀錄一個值$sz2sum$，代表：若$t_1,...,t_z$為$x$在原樹中所有全白子樹們的大小，則其為$t_1^2+...+t_z^2$，這樣就能在重新DFS時算出每個點的$ch$值了。

整理一下上面的算法，在處理每次詢問時我們要維護好的值有：每條新樹邊上的$dsum$值、$ssz$值，還有每個黑點的$size$值、$val$值（這兩個在維護前面那些東西時會需要）、$sz2sum$值、新樹中的父節點、$pnum$值（這是在詢問結束後再對新樹DFS計算）。當拔掉一個節點$y$的子樹時，會影響到的東西有：從$y$沿著新樹邊走上去的所有邊上的兩個值，和路上經過節點的$size$值，並且要記得順便計算$y$的$path$值是多少。那些數的變動值不難由定義得出，這邊就省略。在接回去的時候影響到的東西也是那些，所以照做一次就可以了，而在接上去時這條新產生的邊的$dsum$值和$ssz$值顯然分別會是$d[y]$和$size[y]$。最後記得再DFS一次求$pnum$。至於此次詢問是改一個點$x$的值的話，會影響到的則是所有$x$連到他孩子的邊上的$dsum$值，變動大小也不難推出。

這樣傳上去之後WA第三筆，我辛苦的把他的樹畫出來模擬後發現我漏了好幾個很容易忘記的東西，一個是當我們拔去$y$所在的子樹時，記$y$的父親為$f$，那麼$f$的$sz2sum$值必須要增加！因為此時$f$多了一棵全白的子樹，他原本是用來連接$y$的，現在$y$沒了當然要加回他的$sz2sum$中。另外則是我在DFS計算$pnum$值的時候，如果此時這個點是新樹的葉節點，那麼就直接 return （因為在原樹建完，處理詢問之前會有一次DFS，把每個黑點的$pnum$值都算好了，而在新樹中的葉節點的$pnum$值顯然在這好幾次詢問中都會保持相同）。這樣會有個很不明顯的問題，就是有可能一個黑點在新樹中的子節點都被拔光了，自己成為了葉節點，那麼在算他的$pnum$值就直接 return 了，這不是我們想要的。解決這個問題的方法就是當我們發現把一個點拔掉之後會讓他父親成為葉節點時，就趕快把他的$pnum$值算好就好了（其實就是$size$值平方扣掉$sz2sum$值）。

code :