題目：
給定一棵$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 :
2015年7月12日 星期日
2015年7月11日 星期六
[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 :
考慮把兩個不同的字串$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 :
2015年7月9日 星期四
[POI 12 Stage 2] Template
作法：
首先求出每個點的 Z value ，假設$L$是一個答案，那就代表如果只看字串中那些 Z value $\geq L$的位子，這些位置的相鄰位置的差不會超過$L$。因此我們就可以考慮由小到大枚舉$L$，維護好當前有哪些位置的 Z value $\geq L$，並維護相鄰位置的差的最大值，用可以用個 set 做到這件事。每次把新的數移除的時候就看看他的左右兩個數，並拿這兩個數的差來更新當前的相鄰位置差的最大值。不過實際上用個 linked list 就可以了，複雜度降為$O(n)$。
code :
首先求出每個點的 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 :
假設長度為$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 :
2015年7月8日 星期三
[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 :
考慮枚舉所求子字串的長度$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 :
2015年7月6日 星期一
[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 :
簡單來說就是要問滿足$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 :
假設我們交換的兩數分別為$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 :
2015年7月5日 星期日
[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 :
考慮一個斜的正方形，設他下面頂點指向右邊頂點的向量為$(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 :
2015年7月4日 星期六
[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 :
考慮一個$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 :
我一開始是考慮一個構造：從$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 :
考慮先建出這張圖的最短路徑圖，並且他是有向的。那麼對於那些不在最短路徑圖的中的鐵軌邊就顯然可以拔掉了。在最短路徑圖中，如果$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 :
假設橫著切了$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 :
以下記原字串為$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 :
2015年7月1日 星期三
[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 :
考慮從左邊往右邊掃，當掃到$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 :
考慮對三個字串都建個後綴自動機，那麼假設對於某個出現在三字串中的子字串$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 :
訂閱：
文章 (Atom)