【TOI2019 二模 pD】離不開的新手村

題目敘述

給定一張$\color{white}{\space N\space}$點$\color{white}{\space M\space}$邊的有向圖，每個點有他的難度滿足「難度介於$\color{white}{\space 1\sim N\space}$之間」且「任兩個點難度相異」。

一個數字$\color{white}{\space i\space}$滿足「從任意的難度$\color{white}{\space \leq i\space}$的節點出發時，怎麼走都不會走到難度$\color{white}{\space >i\space}$的節點」時，數字$\color{white}{\space i\space}$就是『好的』，請你計算這張圖『好的』數字種類(介於$\color{white}{\space 1\sim N\space}$之間)。

接下來會有$\color{white}{\space Q\space}$次修改，每次修改會交換某兩個節點上的難度，請在每次修改後輸出新的『好的』數字種類。

子任務1(5分)：$\color{white}{\space 1\leq N,M \leq 100,1\leq Q \leq 100\space}$。
子任務2(16分)：圖是一條有向路徑。
子任務3(13分)：$\color{white}{\space M=N-1\space}$，每個點皆存在走到節點$\color{white}{\space 1\space}$的有向路徑。
子任務4(10分)：$\color{white}{\space 1\leq Q \leq 1000,|a-b|\leq 10000\space}$。
子任務5(25分)：每個點的入度不超過$\color{white}{\space 10\space}$。
子任務6(31分)：$\color{white}{\space 1\leq N,M \leq 500000,1\leq Q \leq 50000\space}$。

Time limit: 15 second

範測測資

Input: 5 5 1 2 3 4 5 2 4 3 1 2 1 4 3 5 3 3 2 4 2 3 5 3

Output: 3 4 5 4

作法

在解題之前，我們需要通靈一些東西(?)。
如果我們考慮把點依照難度由小到大一個一個加進圖裡面，那等價我們要計算有幾個時刻，使得不存在一條邊指到空(未加入)的節點。

可以發現，對於每條邊難度$\color{white}{\space a\space}$指到難度$\color{white}{\space b\space}$，若$\color{white}{\space a\space}$的難度比$\color{white}{\space b\space}$的難度大，那就不會出事；可是若$\color{white}{\space a\space}$的難度比$\color{white}{\space b\space}$的難度小，表示在時刻$\color{white}{\space [a,b)\space}$這個區間內，這條邊會出現在圖裡，卻指到空的節點。

我們發現每一條邊都有可能打到一條時刻的區間，於是我們可以把原題轉換成線段覆蓋問題，等價於求有多少點介於$\color{white}{\space 1\sim N\space}$之間且沒有被任何一條邊覆蓋到。

很顯然的，交換兩個難度等價於兩次單點修改，而一個點的難度改變了就只會改變自己相鄰所有邊所打到的區間，所以我們需要一個支援「區間加值」、「查詢有多少點是$\color{white}{\space 0\space}$」的資料結構－－這點操作完全可以拿我們在寫矩形覆蓋面積使用到的線段樹來支援。

所以我們目前至少獲得了一個$\color{white}{\space O(QM\log N)\space}$的作法。

此時我們必須做一點觀察，看著所有進到同一個點(難度$\color{white}{\space h\space}$)的邊所對應到的區間都是形如$\color{white}{\space [x,h)\space}$的形式，也就是右界都是固定的，由於我們只在意每個時刻是否「沒被蓋到過」，蓋到一次以上後蓋幾次都不在意了，所以我們可以只找到$\color{white}{\space [x,h)\space}$中$\color{white}{\space x\space}$最小的那個線段去覆蓋就可以了。這裡我們可以對每個點都開一個multiset去維護指到自己的人的最小值。

這時可以發現，覆蓋的線段總數會是$\color{white}{\space O(N)\space}$的，修改一個點時除了處理自己蓋的這條邊外，還要跑過所有自己指到的點去看看會不會對其造成影響，這時很慘的我們的複雜度依舊是$\color{white}{\space O(Q(入度Max)\log N)\space}$，不過至少可以拿到subtask 2,3的分數。

若反過來思考的話，也可以獲得對稱的複雜度$\color{white}{\space O(Q(出度Max)\log N)\space}$，拿到subtask 5的分數，但還是拿不到滿分。

試著再觀察一下，雖然我們甚至可以把兩種做法合併起來，對於每一種點都維護出$\color{white}{\space [指到自己的\min ,指到自己的\max)\space}$的這種區間，但瓶頸完全在於修改一個點會需要更動到太多人的multiset－－那如果有multiset的點數不要太多呢？

這時候大膽的想法就出現了(?)，考慮用$\color{white}{\space degree\space}$去分割：

以下把$\color{white}{\space N,M\space}$之量級視為一樣。
令$\color{white}{\space degree\geq K\space}$的是大點，$\color{white}{\space <K\space}$的是小點

首先把每個大點維護出
$\color{white}{\space [min(可到自己的點的難度,自己的難度),max(自己可到的點的難度,自己的難度))\space}$
用兩個multiset搞掉
這樣可以cover到所有大→大、大→小、小→大的邊

把所有小→小的邊$\color{white}{\space a\to b\space}$都維護出$\color{white}{\space [a,b)\space}$這個區間

這樣在修改大點的時候
大點除了改自己的區間 ($\color{white}{\space \log N\space}$)
還要主動修改所有其他相鄰的大點的區間和multiset ($\color{white}{\space \frac{N}{K}\log N\space}$)

修改小點的時候
主動修改所有其他相鄰的大點的區間和multiset
暴力修改所有連到自己的小->小的邊維護出的區間
(兩者加起來不超過$\color{white}{\space K\log N\space}$)

若$\color{white}{\space K\space}$取$\color{white}{\space \sqrt N\space}$總共的複雜度即為$\color{white}{\space Q\sqrt N\log N\space}$，而根據題目那時間限制感覺就可行XD。

實際上修改大點的常數可能會略大，所以我後來把$\color{white}{\space K\space}$取到3000才過。

附上code：