做題記錄 again。

P6187 [NOI Online #1 提高組] 最小環

自己想出來的。很牛??！

首先發現把所有互相距離為 \(k\) 的元素拿下來，相鄰的元素之間連邊，你會得到 \(\gcd(n,k)\) 個環（一開始以為是 \(k\) 個……有點菜?。敪h數為 \(1\) 時答案與 \(k=1\) 無異（本質上就是相連的兩個數相鄰），所以我們考慮 \(k=1\) 怎么做。

不知道為什么可以想到觀察打表可以想到增量構造法?？紤]先將 \(a\) 排序，顯然 \(n=3,k=1\) 時的一種最優構造是 \(a_1,a_2,a_3\)，下一次放入 \(a_4\) 的時候必然放在 \(a_2,a_3\) 中間最好，\(a_i\) 必然放在 \((a_{i-2},a_{i-1})\) 之間最好。還可以發現這個構造非常優美，我們上一步的構造總是能夠使下一步操作合法！于是我們就會了 \(k=1\)，也就是所有 \(\gcd(n,k)=1\)。

證明：考慮 \(a_1,a_2,a_3\)，將 \(a_4\) 放入 \((a_1,a_2)\) 中間對答案產生 \(a_4\times (a_1+a_2)-a_1\times a_2\) 的貢獻，放入 \((a_2,a_3)\) 中間對答案產生 \(a_4\times (a_2+a_3)-a_2\times a_3\)。后者與前者作差得到 \((a_4-a_2)(a_3-a_1)\)，顯然這個積總是 \(>0\)，所以可以推廣開來，\(a_i\) 放在 \((a_{i-2},a_{i-1})\) 中間是最優方案。

考慮 \(\gcd(n,k)\neq 1\) 怎么做。顯然每個環的大小都是一樣的，所以此時環長為 \(l=\frac{n}{\gcd(n,k)}\)，很容易猜到將原序列排序之后每 \(l\) 一段，每個環獨占一段，然后做一個 \(k=1\)。因為 \(\gcd(n,k)\) 總是 \(n\) 的因數，記憶化每個 \(\gcd(n,k)\) 的答案，暴力即可做到根號時間復雜度。根號比較好寫。

當然你也可以考慮每一段都只會相對 \(k=1\) 多出 \(\gcd(n,k)-1\) 個斷點，只維護這些斷點并維護與 \(k=1\) 時答案的差異即可做到調和級數。

關于獨占一段的正確性證明可以看 EI 的題解。

P2512 [HAOI2008] 糖果傳遞

超級典題，但是我覺得很難啊。/kk

考慮這樣一個套路：\(x_i\) 表示每個位置向左給多少值，\(x_i>0\) 表示給出去，\(x_i<0\) 表示拿過來，這樣就能表示相鄰兩個位置之間值的轉移，也就能表示一個位置上最終的值，是 \(a_i+x_{i+1}-x_i\)（當然，對于 \(i=n\) 是 \(a_i+x_{1}-x_i\)）。

這個套路出現在 P1031 [NOIP2002 提高組] 均分紙牌 中。你考慮算出每個位置的初值距離平均值的差，鑒于 \(1\) 只能從右邊得到紙牌達成目標，從左到右依次枚舉 \(i\) 做，保證前 \(i-1\) 位都已經合法，再通過操作 \(i+1\) 讓 \(i\) 合法就可以了。

你會發現一來的這個作差操作本質和我們這個設 \(x\) 差不多。那么環形均分紙牌怎么做呢？

考慮方程：

顯然這個方程解不了，我們考慮換元，扔掉最后一個特殊的方程，然后把它全部換成 \(x_1\)。

向上進行遞歸帶入可以得到這么一個式子：\(x_i=x_1+\sum\limits_{j=1}^{i-1}\overline{a}-a_j\)。

很明顯后面整個和式我們是已知的，不妨設 \(c_i\) 代替掉這個和式：

于是又可以得到 \(x_i=x_1-c_i\)。嘗試寫出答案：

將絕對值看做數軸上兩點距離，由初一數學可得，當 \(x_1\) 取 \(c\) 中位數時，距離和最小。因此給 \(x_1\) 取 \(c\) 中位數后直接算答案即可。

P3745 [六省聯考 2017] 期末考試

有點小清新！

一眼望過去好像是巨大分類討論題，冷靜下來會了 \(A\geqslant B\)。怎么都不會 \(A<B\)，想了想大概是一個很晚的課程和一個很早的課程互補，但是不知道怎么補可以結束……看了題解表示自己很憨。

首先，你要牢記這樣一個事實：所有的學生的課程都是一樣的，是所有課程，等待的時間取決于最晚的課程。（我不知道為什么一直沒有從這個角度入手……）又注意到 \(t\) 很小，所以很自然地可以想到枚舉最晚課程的時間 \(x\)。那么學生的不愉快度的貢獻就是 \(\sum\limits_{i=1}^n\max(0,x-t_i)\times C\)，這個容易前綴和出來。

然后你考慮 \(A\geqslant B\)，很明顯這種情況下用 \(B\) 嚴格用于用 \(A\)，所以你直接把所有時間比 \(x\) 晚的全部提前過來就好了。\(A<B\) 肯定是先用一些 \(A\)，不行了再用 \(B\)，直接考慮 \(x\) 前出成績的課程有多少空間可以延后，\(x\) 后出成績的課程總共需要提前多少，討論一下就完了。

P2672 [NOIP2015 普及組] 推銷員

考慮貪心。一開始寫了個偽算過了所有除了最后一個 Hack 的測試點……氣死我了！最后發現方向完全想錯了。

首先把所有人按照他們的推銷貢獻排序，有一種很顯然的想法是直接取前 \(X\) 大然后加上距離最遠的那個的距離貢獻。然而這樣有點問題，有可能可以舍棄掉前面最小的一個，去換一個距離比較遠但是推銷貢獻不大的，靠距離貢獻成為最大。

可以證明只會舍棄一個。

假設舍棄兩個，那么我們需要在距離更遠，且推銷貢獻更小的人當中選兩個，得到的距離貢獻是且僅是他們兩者中更遠的那個造成的，較近的那個只會造成推銷貢獻，那顯然不如撤銷較近的那個。如果距離相等，撤銷掉推銷貢獻更小的那個也一定更好。舍棄兩個不行，兩個以上顯然就更不行了。

對于第一類直接取 \(X\) 大的，從大到小排序之后維護一下前綴推銷貢獻和、前綴最大距離即可算出答案。對于第二類，還是從大到小排序，只取 \(X-1\) 大的推銷貢獻加上后面的最大單個總貢獻（二倍距離加推銷貢獻）即可。

P6787 「SWTR-6」Snow Mountain

感覺不難想啊……可能是因為太懶了不想做了所以沒有認真想？

一眼排序，先不考慮不允許的限制，很容易想到一個看著對得不能再對的傻逼貪心就是對折配對，但是要先從中間開始因為要乘上操作次數。因為 \(n\) 是偶數所以一定可以配完。

接下來考慮有限制怎么辦。首先題目有一個很鬼畜的限制就是一個數最多只和一個比它大的數被禁止，那么你繼續考慮對折配對，所謂對折其實就是把這個序列分成了等長的前半段和后半段，我想讓前半段和后半段匹配。你再仔細一想，你發現我干嘛必須對折呢？貢獻是兩者的最小值，意思就是說我只要讓前半段從大到小匹配，然后每次匹配其實可以在后半段里面隨便選的！于是你又有了一個想法是干掉那些與別的水晶組成禁止關系的后半段水晶：隨便用一個前半段的和它不被禁止的水晶把它干掉，這樣有一些水晶就自由了。

順便考慮無解怎么判定。你發現無解肯定當且僅當有個水晶無論怎么辦都不能被摧毀，那么它一定被其他所有水晶都禁止掉了。除了這種情況都有解。

下面繼續考慮如何在有解的情況下最小化貢獻。

題解說每次匹配掉那個被禁止次數最多的水晶，這樣放出來的自由的水晶是最多的，如果有多個就選擇 \(a\) 值最小的那個……

好的我不會這題。貪心真奇妙。

CF559C Gerald and Giant Chess

你是傻逼，當初沒有認真學會這個做法。

考慮容斥，斥掉經過至少一個黑格子的路徑。

你很容易想到 Key Cup T2，然而這次你再也不能 \(\mathcal O(n^3)\) 了。我們還是欽定一條路徑只在它第一次經過黑格子時去掉，那么設 \(f_i\) 表示第一次經過的黑格子是格子 \(i\) 的路徑數。

首先，經過這個黑格子之后后面隨便走都無所謂了，很明顯組合數即可。考慮怎么求出到達這個格子不經過其他黑格子的方案數。還是容斥，先組合數算出任何到達 \(i\) 格子的所有路徑數，然后斥掉經過別的黑點到達它的路徑數。這種路徑我們仍然只考慮在第一次經過黑格子時計數，那么很明顯到達它能經過的黑點必然橫縱坐標都小于等于它，所以找出這樣的點 \(j\) 作為起點，用它們的 \(f_j\) 乘上 \(j\to i\) 的方案數就是需要從 \(f_i\) 中減掉的部分。

對于每個點做起點求一下和減掉就做完了。

CF621E Wet Shark and Blocks

又被踩了……我不會矩陣優化。

顯然有一個 dp 式子是 \(f_{i,(10j+p)\bmod x}\gets f_{i-1,j}\times cnt_p\)，注意到每相鄰兩項轉移是相似的，并且 \(b\) 很大，考慮矩陣優化。

然后就不會了。

我們把 push 的遞推方式改成 pull 的，顯然這樣才是矩陣優化更加容易的方式，那么很容易得到 \(f_{i,q}\gets \sum\limits_{(10j+p)\equiv q\pmod x} f_{i-1,j}\times cnt_p\)。因為你想讓 \(f_{i-1}\) 的每一項都乘上一個數，于是很容易想到把 \(f\) 構造成一個行向量。這樣矩乘的時候左邊總是一整行和右邊的一列依次乘。然后你考慮右矩陣哪些位置上是要有值的。

想象矩陣乘法過程。左矩陣拿出第一行的第 \(j\) 列元素出來（\(f_{i,j}\)），與右矩陣的第 \(q\) 列第 \(j\) 行元素相乘，再對于每一個 \(j\) 加和得到新矩陣的第一行第 \(q\) 列（\(f_{i+1,q}\)）。所以一個位置 \((j,q)\) 有值當且僅當存在一個 \(p\) 滿足 \((10j+p)\bmod x=q\)。所以在 \((j,(10j+p)\bmod x)\) 的位置放上 \(cnt_p\) 就行了。

還可以這樣想。對于每個 \(i\to i+1\) 的轉移，都是 \(f_{i,j}\) 同時轉移，所以需要把它們看成一個狀態，寫進一個矩陣。因為新狀態是從許多舊狀態轉移過去的，所以需要把這些同時對一個狀態做貢獻的狀態寫在左矩陣的一行上才能同時算到貢獻（bonus：如果一個狀態乘多個值做貢獻，就在右矩陣加很多列）。

菜得不行……

CF1866G Grouped Carriages

不會貪心，可以去死嗎？

一眼二分，要求每個車廂的人數都不超過 \(mid\)。這里一直在思考怎么搞定多出人的車廂，只想到了把每個車廂的人看成一個區間。

先把所有人都請下車，考慮從左往右安排車廂里的人，很明顯這個車廂里的人必須來自那些區間包含它的車廂里的人。所以考慮把所有包含該車廂的區間拿出來，顯然按右端點排序之后優先滿足靠前的區間，寫個數據結構維護一下就完事了。

CF1765L Project Manager

好題。

首先注意到有用的工作日不會太多，因為最多一個項目拖 \(7\) 天之后一定會有進度，一個假期最多跳掉 \(7\) 天，所以 \((7+7)\times 2\times 10^5\) 天之后一定能做完所有項目。

這啟發我們按照時間一天一天模擬。遇到假期跳掉就好了。

我們考慮一天之中會發生的事情。我們首先需要找出在這一天可以并且需要工作的人，然后為每一個人準備一個 set 表示現在堆在他身上的的項目，拿出編號最小的項目做了它。這樣每一次枚舉都能使得一個項目的進度得到推進，枚舉次數不會超過 \(2\times 10^5\)。

考慮如何找出這一天可以且需要工作的人。注意到一個人是否可以工作之和星期幾有關，所以我們開 \(7\) 個 map，如果一個人他有 \(x\) 個被安排的工作，因為工作可以在任何一天做，所以必須給他每一個工作日的 map 他的那一項都放上 \(x\)，只要每個 map 他的那一項不變成 \(0\) 就說明他有工作要做，應當被枚舉到（同理，枚舉到他做工作和項目推進是等價的，次數不會超過 \(2\times 10^5\)）。

綜上所述，我們枚舉天數的時候先得到今天是星期幾，然后把今天的 map 里面有的人全部拿出來，把他們 set 里面第一項的項目推進一下。注意一個人做了一樣工作之后，所有 map 中他的這一項都要減少 \(1\)，因為他少了一個被安排的工作。如果變成 \(0\) 就需要 erase 掉避免枚舉閑人（閑人可能特別多）。

推進項目是簡單的，新加入的那些人多了一項被安排的工作，改改每一個 map 再往他們的 set 里面插一下項目就好了。和初始化差不多，因為初始化等價于把項目推進到第一個人的位置。

P2158 [SDOI2008] 儀仗隊

首先特判 \(n=1\)，然后很快可以發現答案就是 \(1+2\sum\limits_{1}^{n-1}\varphi(i)\)。接下來考慮求歐拉函數前綴和。

顯然用不著莫反，歐拉篩再前綴和就可以了（不能埃氏篩?。?。

首先我們知道，歐拉函數是一個積性函數，所以考慮唯一分解定理，把 \(n\) 的一個質因子拋掉，有 \(\varphi(n)=\varphi(\frac{n}{p^k})\cdot \varphi(p^k)\)，右邊那個 \(\varphi(p^k)\) 顯然因為每個含有 \(p\) 因子的數都不與 \(p^k\) 互質，其他數都與 \(p^k\) 互質所以是 \(p^k-p^{k-1}\)，也就是 \(p^k(1-\frac{1}{p})\)。這樣遞歸分解下去直到 \(1\)，可以發現前面的 \(p^k\) 正好又組成了一個 \(n\) 的形式，于是有：

然后你考慮歐拉篩過程。每次我們讓一個數 \(ip_j\) 被 \(p_j\) 篩掉，那么你考慮 \(i\) 和 \(p_j\) 的整除關系。

1. 如果 \(p_j|i\)，那么它貢獻 \(p_j\)，即 \(\varphi(ip_j)=\varphi(i)\times p_j\)，因為它為 \(ip_j\) 提供了一個質因子（之前那個 product 前面有個 \(n\)）。
2. 如果 \(p_j\nmid i\)，那么它貢獻 \(p_j-1\)，即 \(\varphi(ip_j)=\varphi(i)\times (p_j-1)\)，因為它為 \(ip_j\) 提供的那個質因子 \(p_j\) 第一次出現，會被除掉，只剩下一個 \(p_j-1\)，而后面再次出現就能正常貢獻了。

還是不難理解的。我篩法學的真的差。

CF811E Vladik and Entertaining Flags

好題。

看完題你就有一個大概 \(n\alpha(n)m\sqrt m\) 的莫隊加可撤銷并查集做法，然而這應該過不了。

你發現這東西可能還挺好合并的，考慮線段樹。那么你需要考慮合并的時候會減少的連通塊數量，這個很容易想到并查集。很容易發現每次合并只有最左邊一列和最右邊一列的連通塊信息會有變化，中間的列的信息以后都沒用了，所以我對于每一個線段樹節點上，維護其管理的區間最左邊一列每個位置并查集的祖先編號，最右邊一列每個位置的并查集祖先編號。然后對于每次 pushup 或者合并答案，先把連通塊數量設置為兩邊之和，然后枚舉中間接在一起那兩列的每一行，如果左右的數一樣，并且他們的祖先編號不同，那么就合并在一起，連通塊數量減少 \(1\)。

最后需要更新左兒子左邊那一列上的祖先編號和右兒子右邊那一列上的祖先編號，成為這個節點的信息。

  2222|2222
  2111|1112
  2222|2222
  

  2112|2112
  2222|2222
  2112|2112
  

[ARC166D] Interval Counts

二分之后感覺不好 check，考慮貪心。

顯然最左側的點上必須放滿 \(y_i\) 條線段的左端點，我們考慮從左到右掃點進行增量構造。

• \(y_i=y_{i-1}\)，顯然直接把左邊的線段拉過來是最優的，因為截斷某條線段肯定會減小最小值。
• \(y_i<y_{i-1}\)，這里必須要斷掉 \(y_{i-1}-y_i\) 條線段，那么為了使得最小值最大，顯然需要斷掉左端點最靠左的這么多條線段。
• \(y_i>y_{i-1}\)，這里需要增加 \(y_i-y_{i-1}\) 條線段，很明顯為了使他們盡量長，把它們的左端點放到 \(x_{i-1}+1\) 是最優的。

很容易想到維護一個堆叫做所有還沒有被斷掉的線段的左端點集合，但是這不可行，因為 \(y\) 很大。但是我們可以發現我們添加的線段左端點是單調的，維護一個隊列表示有 \(y\) 條左端點在 \(x\) 的線段，每次拿隊首即可。

P4819 [中山市選] 殺人游戲

Tarjan 復習題。

考慮什么是最優策略。注意到有向圖，并且人之間有認識關系，很容易想到縮點，這樣一個強連通分量總是可以查詢一個人就知道整個塊的信息。

于是我們得到了一個 DAG，考慮 DAG 上的查詢策略，很自然地開始考慮一下入度為 \(0\) 的點。你發現如果入度為 \(0\) 的點都不是殺手，那么你查詢其他點肯定不如查這些點，因為查這些點就能知道他們的出點的情況，像拓撲排序一樣推就能安全地推出來了；而如果有一個入度為 \(0\) 的點是殺手，那么你無論如何檢驗其他點也不得不去檢驗它。綜上，直接一上來就檢驗入度為 \(0\) 的所有點就行了。很明顯由于選擇這些人互相獨立（檢驗一個人不影響我不知道其他人的信息），在一個人那里去世的概率是 \(\frac{1}{n}\)，那么假設有 \(c\) 個這樣的點，在檢驗中去世的概率就為 \(\frac{c}{n}\)，所以活下來的概率就是 \(1-\frac{c}{n}\)，這也就是答案。

……嗎？

那么你無論如何檢驗其他點也不得不去檢驗它。

我都檢驗了其他點了我還檢驗它干什么？

也就是說，如果存在一個大小為 \(1\) 的強連通分量（如果大小不是 \(1\) 那么也必然至少要在強連通分量里面選一個點，沒有區別），滿足它入度為 \(0\)，并且它所連到的所有點都入度 \(\geqslant 2\)，那么我們就可以通過檢驗其他入度為 \(0\) 的點來排除掉除了它以外的任何點。換句話說，一定可以拓撲到所有除了它以外的點，沒有第二個只能通過選了它才能檢驗到。對于這種情況，答案變為 \(1-\frac{c-1}{n}\)。

實現的時候記得去掉重邊。

好題。

P3211 [HNOI2011] XOR和路徑

神題！

首先考慮 dp，發現直接整個 \(f_i\) 表示當前在 \(i\) 節點，走到 \(n\) 節點的異或的期望肯定是不行的，直接轉移用一個點的期望異或上邊權轉移過去看起來就很不靠譜，而且難道你拿小數去異或嗎。

發現對于這個問題每一位應該是獨立的，所以考慮每一位一個 dp 叫做 \(f_u\) 表示 \(u\to n\) 的路徑上這一位為 \(1\) 的概率，\(d_u\) 表示 \(u\) 的出度，那么有：

提取公因數 \(\frac{1}{d_u}\)，乘到左邊去得到：

好好好，但是問題來了，這個圖可能有環，怎么轉移呢？

拆掉和式，移項得到：

于是我們發現，轉移方程上每一個 \(f\) 的系數都是確定的，并且常數項也是確定的，那么我們就可以把 \(n\) 個點的 \(n\) 個轉移方程排在一起，解方程確定 \(n\) 個未知數 \(f\)。

特別地，第 \(n\) 個點的方程應當只留下一項，表示 \(f_n=0\)。

高斯消元，啟動！

因為一定客觀存在這樣一堆 \(f\) 滿足條件，所以顯然是不會無解的。在圖連通的情況下，也不會解出自由元。

這題很陰間，精度要求很高。需要注意消元方式和 eps 大小。還要注意自環只能相當于一條單向邊（不難理解，兩條邊本質相同）。

P3232 [HNOI2013] 游走

我以為會做上面那道題就應該會做這道的。

顯然，得分的總期望就是每一條邊的編號乘上每一條邊被經過的期望次數。于是要算出每條邊的期望次數。

首先想到了這樣一個辦法：\(f_{u,i}\) 表示 \(u\to n\) 情況下邊 \(i\) 的期望經過次數，轉移比較顯然，最后高斯消元解就行了。然而復雜度是錯的：邊數太大了。

注意到一個比較顯然的事實：經過一條邊 \((u,v)\) 的期望次數 \(E'(u,v)\) 只和經過 \(u,v\) 的期望次數 \(E(u),E(v)\) 有關，經過其他點的期望次數與這條邊毫無關系。具體來說可以發現，到達 \(u\) 處的期望次數如果是 \(E(u)\) 的話，那么走上 \((u,v)\) 的期望次數就應該加上 \(\frac{E(u)}{deg_u}\)。進一步我們容易發現 \(u,v\) 兩邊是獨立的，所以可以得到：

問題變為計算 \(E(u),\forall u\in[1,n]\)。

這個容易直接使用 trick 得到，令 \(f_i\) 表示 \(i\) 點的期望經過次數，那么有：

特別地，\(f_n=0\)，因為我們不能從 \(n\) 點離開，它的經過次數不能做任何貢獻。

P2973 [USACO10HOL] Driving Out the Piggies G

拜謝 Chery 選題。拜謝 dyx 筆記。

首先你有一個顯然的想法是 \(f_u\) 表示炸彈在 \(u\) 處爆炸的概率，那么：

這很好理解，但這是錯的。

既然要先讓炸彈走到 \(u\)，我們很容易想到一個理解是：炸彈在 \(u\) 處爆炸的概率就是炸彈走到 \(u\) 的期望次數乘上炸彈爆炸的概率。

求出到達一個點的期望次數是 trivial 的。

P2144 [FJOI2007] 輪狀病毒

用 Matrix-Tree 定理當然非常正確，然而你發現直接做精度特別麻煩，要手寫小數除法，惡心至極。

有人選擇了使用蟒蛇 3，但是 FJOI2007 不能交蟒蛇 3，但是可以交用蟒蛇 3 打的表，所以蟒蛇啟動。

有人觀察 Kirchhoff 矩陣，用行列式結論得出遞推式。很遺憾跨度太大結論太高深我看不懂，而且我本來也不懂 Matrix-Tree 定理。

你發現如果 Matrix-Tree 定理有模數就好辦很多，所以你考慮來一堆互質的小模數，然后用 CRT 還原。

考慮我們取了 \(k\) 個質數，拿到 Matrix-Tree 定理在 \(m_i\) 意義下計算出來的所有答案 \(a_i\)。然后使用 CRT：

根據 CRT，我們有 \(M=\prod\limits_{i=1}^k m_k,M_i=\frac{M}{m_i}\)，求出 \(M_i\) 在模 \(m_i\) 意義下的逆元 \(t_i\)，答案就是：

我們發現這個過程要寫高精度取模、高精度乘法、高精度加法，這太惡心了！我們考慮怎么不寫這些東西。

使用蟒蛇 3。

發現 \(a_i\) 是低精的，\(M_i\) 只要每次 \(\mathcal O(n)\) 算一下對 \(m_i\) 實時取模再去算 \(t_i\) 就是低精的。這唯一需要高精的東西是 \(M_i\)，與這倆玩意做乘法的時候進行一個高精乘低精就行了。但是還有個問題就是 \(\bmod M\) 咋搞呢？？？

你發現有一個美好的性質是 \(m_i\times M_i\equiv 0\pmod M\)，這意味著，如果我們把 \(a_i\times t_i\) 對 \(m_i\) 取模之后再乘上 \(M_i\)，對整體模 \(M\) 的結果毫無影響！所以，你可以先把 \(a_i\times t_i\) 取模，這樣就是一個 \(<m_i\) 的數，乘上 \(M_i\) 之后也 \(<M\)。從而和式中的每一項都 \(<M\)，那么就可以通過判斷大小，每次減掉一個 \(M\) 實現取模完事啦。

P5192 【模板】有源匯上下界最大流

復健網絡流，怎么會是呢？

首先考慮建模。

先來一個超級源點 \(S\) 和超級匯點 \(T\)，然后給每位少女開一個點 \(P_i\)，每一天開一個點 \(Q_i\)，然后一步一步考慮限制：

1. 每位少女 \(x\) 都需要被拍至少 \(G_x\) 張照片，所以 \(Q_x\to T\) 連一條要求流量為 \([G_x,\infty)\) 的邊。
2. 第 \(k\) 天的取材對象 \(C_{k,i}\)，需要被拍 \([L_{k,i},R_{k,i}]\) 張照片，所以 \(P_k\to C_{k,i}\) 連一條要求流量為 \([L_{k,i},R_{k,i}]\) 的邊。
3. 第 \(i\) 天的拍照數量不能超過 \(D_i\) 張，所以 \(S\to P_i\) 連一條要求流量為 \([0,D_i]\) 的邊。

求一個最大流。

我們發現這是一個有源匯上下界最大流，怎么做呢？

link：http://www.rzrgm.cn/lemonniforever/p/18009379/lh-loves-wly

P4528 [CTSC2008] 圖騰

會不了一點。后面的容斥還挺厲害的，自己推了一點和題解不一樣的。

看了題解可以得知，我們可以利用離散化的思想，我們顯然可以把一種形式抽象為 \(a,b,c,d\) 四個位置的排名，以最小的為第一名，那么閃電就是 \(1324\) 型，兩種山峰分別是 \(1243\) 型和 \(1432\) 型。

那么答案就是 \(n(1324)-n(1243)-n(1432)\)。屬實抽象，你根本不知道有什么用。

考慮補集轉化，我們的目標肯定是把項消掉，或者起碼要搞成加法吧。為了不生出來一大堆項，我們可以只把一種類型的兩個位置給確定下來，這樣就是一種空兩位的形式減掉一種固定的形式。

比如 \(n(1324)=n(13??)-n(1342)\)。

隨便往回看一下就能發現 \(1342\) 和 \(1243\) 簡直是一個東西，于是把 \(n(1243)\) 改成 \(n(1?4?)-n(1342)\)。

代回可得答案變成了 \(n(13??)-n(1?4?)-n(1432)\)。

你發現 \(n(1432)\) 你也不會算，咋辦呢？

看了題解可以得知，\(n(1432)=n(1?3?)-n(1234)\)，\(n(1234)\) 肯定比這個好算多了。

代回可得答案變成了 \(n(13??)-n(1?4?)-n(1?3?)+n(1234)\)。

試了試發現 \(n(1?4?),n(1?3?)\) 似乎也不好算，因為需要關注他們兩個中間和兩邊還要有數能插進去滿足排名。

合在一起，\(n(1?4?)+n(1?3?)=n(1???)-n(1?2?)\)，注意這里因為是排列所以不可能出現 \(1?1?\) 的情況，得到答案變為 \(n(13??)+n(1?2?)+n(1234)-n(1???)\)。

好像真的沒什么可以瞪出來的巧合了，這個東西應該要可以算才對。

為了方便，我們讓 \(L_i=\sum\limits_{j<i}[y_j>y_i],R_i=\sum\limits_{j>i}[y_j>y_i]\)。樹狀數組取得是 naive 的。

那么左邊比 \(y_i\) 小的數的個數就應該是 \(i-1-L_i\)，右邊比 \(y_i\) 小的數的個數就應該是 \(n-i-R_i\)。

\(n(1???)\)

枚舉 \(1\)，答案直接 \({R_i}\choose{3}\) 完事了。

\(n(1234)\)

枚舉 \(2,3?\) 的位置 \(i,j?\)，再交換一下求和順序，答案就是 \(\sum\limits_{j=1}^n\sum\limits_{i=1}^{j-1}(i-1-L_i)R_j=\sum\limits_{j=1}^n R_j\sum\limits_{i=1}^{j-1}(i-1-L_i)?\)，顯然給里面那個求和做個前綴和就完了。

\(n(13??)\)

枚舉 \(3\) 的位置 \(i\)，那么左邊的選法就是 \(i-1-L_i\) 種，右邊的選法和 \(1\) 掛鉤，這不好搞。

發現 \(4\) 有 \(R_i\) 種選法，其他位置的選法就是 \(j<i<k,y_i>y_k>y_j\) 的總方案數。

容斥，如果只管 \(y_j<y_i\land y_k<y_i,j<i\)，那么有 \((i-1-L_i)(y_i-1)\) 種方案，需要減掉 \(k< i\land y_j<y_k\) 和 \(y_j\geqslant y_k\) 的部分。

對于 \(k< i\land y_j<y_k\) 的部分的方案數，顯然應該是 \({i-1-L_i}\choose{2}\)。

對于 \(y_j\geqslant y_k\) 的部分的方案數，可以寫成 \(\sum\limits_{j=1}^{i-1}[y_j<y_i]y_j\)，這可以進行一次樹狀數組取得。

\(n(1?2?)\)

枚舉 \(2\) 的位置 \(i\)，那么右邊的選法就是 \(R_i\) 種，左邊的選法就是 \(j<k<i,y_k>y_i>y_j\) 的總方案數。

容斥，如果只管 \(y_i>y_j\) 那么就有 \((i-1-L_i)(i-1)\) 種選法，多算了 \(j<k,y_k<y_i\) 和 \(k\leqslant j\) 的部分。

\(k\leqslant j\) 的部分的方案數，可以寫成 \(\sum\limits_{j=1}^{i-1}[y_j<y_i]j\)，這可以進行一次樹狀數組取得。

\(j<k,y_k<y_i\) 的部分的方案數，顯然應該是 \({i-1-L_i}\choose{2}\)。

于是這部分就做完了。

這些部分拼在一起就萬事大吉了。

P4219 [BJOI2014] 大融合

好題啊，雖然 LCT 做法顯然。能不能把 LCT 卡掉啊

LCT 做法：

加邊直接加，查詢的時候把點 \(x\) 轉到根上，查詢 \((siz_x-siz_y)\times siz_y\) 就完事了。

樹剖做法：

考慮把所有邊全部先加上，維護樹上連通塊并查集。

為了方便，每次把較深的連通塊合并到較淺的連通塊上。即使 \(dep_u<dep_v\)。

為了動態維護 \(siz\)，每次把 \(v\) 合并到 \(u\) 上都需要將 \(u\to \text{find}(u)\) 的路徑上的每一個點的 \(siz\) 都加上 \(siz(v)\)。顯然 \(v\) 應該是它所在連通塊的根，不需要套一個 \(\text{find}\)。

詢問的答案就是 \((siz_{\text{find}(x)}-siz_{y})\times siz_y\)。

樹剖并樹狀數組即可。

P8512 [Ynoi Easy Round 2021] TEST_152

回來兩天硬是一道題都沒自己做出來。

首先區間覆蓋應當使用珂朵莉樹。

首先有一個簡單的想法：掃一遍操作，求出 \(r\) 處整個序列的和，再減去 \(l-1\) 處整個序列的和。但是會又涌現一個問題：\(l-1\) 處有很多位置原本就是有值的，如果 \(l\sim r\) 當中覆蓋了這些位置，這些位置應該當成 \(0\) 來減。

我們發現問題出在統計到了區間外的貢獻，所以我們應該離線，然后把所有詢問按 \(r\) 從小到大排序，對詢問從左到右地進行掃描線。當某個連續段加入的時候直接把 \((r-l+1)\times val\) 放在時間軸的當前時間 \(t\) 上，之后如果被覆蓋，就在原處 \(t\) 上減掉被覆蓋部分的長度 \(\times val\)。

那么當到達一個位置的時候就直接在時間軸上取 \([l,r]\) 上所有值的和就行了。

樹狀數組即可。

好像很自然，沒關系，不妨礙我一直以來是傻逼，不會做一點紫題。

P7215 [JOISC2020] 首都

首先要求的意思就是要你找出一個連通塊，滿足這個連通塊里面的顏色在連通塊外不存在，并且這個連通塊包含的顏色數量最少。

先想個暴力：枚舉樹根，欽定樹根的顏色作最終連通塊，把這種顏色的所有點都加進“有必要走到的點”的集合，然后向下走，遇到一種新顏色就把所有這種顏色的點都加進“有必要走到的點”的集合，走過一個點就把它從集合里刪掉，直到集合空。

我們發現這不好做，因為不知道下面還有沒有有必要走到的點，所以考慮反著來。以隊列的形式維護“有必要走到的點”的集合，但是這次向上走（當然，如果上面那個點已經到過了就不用走了）。遇到一種新顏色就把所有這種顏色的點都加進隊列（當然沒遇到就什么都不做），并打標記再彈走剛剛離開的那個點。注意特判一下根要直接打標記彈走。等到隊列為空的時候所有用到的顏色就是答案。

加上前面枚舉根就是 \(\mathcal O(n^2)\) 的，喜提 \(11\) 分。這個暴力都難死了誰會去想啊

進一步考慮，有一個顯然的結論，假設在顏色 \(x\) 作最終連通塊的時候涉及到 \(y\) 顏色的連通塊，那么 \(y\) 顏色作最終連通塊的時候，答案也會涉及到 \(x\) 顏色，顯然這是不優的。

所以這樣我們就能考慮點分治了。每次把分治中心當成根做一遍 \(\mathcal O(n)\)，當然那種有點在分治樹以外的就不用管了。然后切樹，繼續往下做就沒問題！

事實證明我根本不會點分治。