隨手coding筆記 by波路特石

原題連結： https://tioj.ck.tp.edu.tw/problems/1975 這題很神奇，至於神奇在哪先不馬上劇透(? 首先，當$\color{white}{\space M=0\space}$時，有顯然的$\color{white}{\space O(NlgN)\space}$排序解。 但我們換個角度，把區間的工作視為區間加值，那就有差分後的$\color{white}{\space O(N+C)\space}$解法。 這個解法的關鍵在於只要取被加最多次的點的值就是答案，所以接下來在處理「非即時性工作」時我們也將採取同樣的策略－－也就是在加完「即時性工作」後，把每個「非即時性工作」的量分別盡量的、 不重複的 分給 死線前 、 被加的值少 的點，最後再取一次被加最多次的點的值就是答案。 為了方便，我們事先把所有非即時性工作讀進來對死線排序，然後把當前工作$\color{white}{\space i\space}$死線$\color{white}{\space d_i\space}$前的點值全部補進資料結構內，每次拿前$\color{white}{\space w_i\space}$小的值出來每個$\color{white}{\space +1\space}$再丟回去－－這是最直觀的寫法了，首先一般我們會想到用pq來維護前k小，但這樣複雜度會是慘慘的$\color{white}{\space O(N+MClgC)\space}$。 於是很自然的也能發現，重複的值太多了，不妨把全部的值全部壓縮在一起綁成pair拿map維護吧！ ……結果照樣吃了TLE，因為不能重複分配的關係導致單調性失效。 不過這個壓縮在一起的動作卻是關鍵，可以觀察到，我們是把前$\color{white}{\space w_i\space}$小的值+1，假設被加的值種類分別是$\color{white}{\space v_1,v_2, \cdots ,v_t\space}$，那加值完之後不就只是把前面全部拔掉，變成$\color{white}{\space v_1+1,v_2+1,...,v_{t-1}+1\space}$，並且$\color{white}{\space v_t \space}$被拆成兩份而已嗎！？ 這個平移大部份資料位置卻不改變值的動作...

原題連結： https://tioj.ck.tp.edu.tw/problems/1775 久違的文章(? 被某人丟了這題，發現原本這題只有一個人過 本來以為不太可做，結果想了一下發現似乎有那麼一點希望(?)，就花了一段時間刻出來了ww 首先從水母圖的角度切入，很顯然的這是把很多棵樹的根節點連成一個環所形成的圖 接下來就能發現，只要將環上每個點的子樹的所有距離(包含自己)，分別記錄起來排序 且如果環的大小是$\color{white}{\space L\space}$，則對於每個點，得到「點到環的距離」後就可以枚舉環上的每個點二分搜得到除了自己這棵樹以外符合題目條件的個數了。 這裡只花了$\color{white}{\space O(NLlgN)\space}$ 所以接下來我們就能把題目縮減成在樹上的子問題，只要把環切開來一個一個做就好了。 這樣的話我們先來考慮一個類似的小問題： 「給定長度為$\color{white}{\space N\space}$的兩個序列$\color{white}{\space d_i\space}$和$\color{white}{\space k_i\space}$，如果我把序列切成$\color{white}{\space M\space}$塊，試問對於每個$\color{white}{\space i\space}$，滿足$\color{white}{\space d_i+d_j<=k_i\space}$的整數$\color{white}{\space j\space}$，且$\color{white}{\space i,j\space}$不在同一塊的個數有多少個？」 總之會有$\color{white}{\space O(NlgN)\space}$的作法 同樣的問題要如何對應到樹上面呢？ －－沒錯，就是樹分治！ 對於每一棵需要求該問題的樹，我們把這棵樹的重心拆掉之後遞迴下去 在合併一堆小樹時，從重心$\color{white}{\space dfs\space}$出去記錄其他點到自己的距離$\color{white}{\space d_i\space}$，這樣若有$\color{white}{\space M\space}$棵小樹，就對應到上面那個問題了！(不過要記得算上重心本身～...