Mato is No.1

【dispatching】
（這題國內數據極弱，暴力能80，下面的解法1，平衡樹即使用Splay Tree實現都能AC）
枚舉管理者所在的結點，然后在這個結點及其所有后代中找到權值前K小的，使得它們的權值和不超過限制，要求求出K的最大值。
解法1：將每個結點及其所有后代的權值存在一個平衡樹里，然后，對于每個結點，若不是葉結點，就將其所有的子樹中，找到最大的那棵子樹，它所表示的平衡樹不動，將其它的子樹表示的平衡樹上的所有結點強行拆開，并插入到這個子樹表示的平衡樹中（這叫啟發式合并），別忘了將該結點本身也合并到這棵平衡樹里。合并好了以后，通過每個點記錄的sum（下面說明），用類似于求結點排名的方法，就可以求出K的最大值了。
容易證明，這樣合并的話，在整個過程中插入的次數是O(NlogN)的，加上平衡樹插入本身的O(logN)，總的時間復雜度為O(Nlog²N）。
具體實現起來有一些技巧：
（1）可以發現，在合并過程中，各個點本身并沒有變，而只是它們之間的關系發生了變化（從不在同一棵樹上變成在同一棵樹上了），因此為了節省空間，可以預先將所有的結點建好，每個結點除了自身權值以外還記錄mul（初始為1）、sz（初始為1）、sz0（初始為1）、sum（初始等于權值）等信息，其中mul為重復次數，sz為考慮mul情況下的樹的大小，sz0為不考慮mul的情況下的樹的大小（也就是實際結點個數），sum表示樹上所有結點的總權值（這個當然要考慮mul了）。之所以維護sz0，是因為每次可以通過找到sz0最大的子樹不動來加速。插入的操作是void ins(int r, int No)，表示將結點No（是結點不是值）插入到以r為根的子樹里，注意這個結點No的mul可能大于1，因此在插入后維護的時候需要注意；
（2）由于在過程中會同時有多棵平衡樹存在，因此每個點還需要記錄一個額外的域rf，rf=-1表示該結點不是任何一棵平衡樹的根結點，rf>=0表示該結點是原樹中編號為rf的結點表示的平衡樹的根結點，同時記錄root[i]表示結點i表示的平衡樹的根結點編號，這樣就可以很方便地實現樹內外的對接（注意這兩個值的維護，尤其是將結點i本身合并到平衡樹里的時候，別忘了把root[i]改掉）。
解法2（正解）：合并的時候使用可并堆（用左偏樹或斜堆實現），時間復雜度O(NlogN)。

【guard】
（這題其實很容易想到網絡流的話說……不過仔細研究一下就可以發現，由于報告上來的只是某一個區間內有木有人，而不是有幾個人，因此無法用網絡流的流量平衡來表示）
首先，某些區間報告木有人，這些區間內的點肯定不符合要求了，可以將它們刪掉，然后對于剩下的（可能是若干段）區間，合并起來，對結點從左到右重新編號（這一步可以用線段樹，也可以排序后直接掃描，見這里，本沙茶比賽時為了省事直接上線段樹了），然后就只需要考慮那些報告有人的區間了囧……當然，這些區間的端點也是要對應地重新編號的，編號完了以后，將所有包含別的區間的區間刪去（因為它們的存在木有意義），方法：對于所有重編號后的區間，將其按照先左端點遞增，后右端點遞減排序，然后設置一個棧，保證棧中的區間左右端點均嚴格遞增，按照排序之后的順序掃描每個區間，每次一個新區間入棧時，棧頂所有右端點大于等于這個新區間右端點的區間出棧，再將新區間入棧，這樣最后棧中的區間就是保留下來的區間了囧……而且已經排序……
然后，如果問題是求至少要多少個人的話，就是一個經典的貪心模型了，掃描排序后的區間，如果一個區間內還木有任何人，就在它的右端點處放一個人。顯然，除了這些放了人的區間的右端點之外，其余的點肯定都不是必須放人的（因為現在已經有一個方案使它們不放人了）。現在的問題是，這些右端點處是否必須放人。
設F[i]為第i個區間及其之后的區間當中，若要每個區間內都有人，至少要幾個人。若第i個區間的右端點不小于最后一個區間的左端點，則F[i]=1（在第i個區間右端點放一個人即可），否則，找到最小的j，使得第i個區間的右端點小于第j個區間的左端點（這個顯然可以二分查找得到），則F[i]=F[j]+1。這樣從后到前推一遍即可。然后，再從前到后，按照上面的貪心算法的流程掃一遍，如果遇到第i個區間的右端點需要放人：若第i個區間的長度為1，顯然這里必須放人，否則嘗試在第i個區間的倒數第2個位置（即右端點之前的那個位置）放人，而右端點不放人（可以證明，不會后來又把這個右端點這里放上人的），類似用二分查找的方式找到這個j，然后看一下(_F + F[j] + 1)（_F為第i個區間前面放人個數）是否大于K，若大于K，則第i個區間的右端點必須放人，否則不必須放人。
此外還有兩種特殊情況，一是M=0的時候在去包含的時候要特判一下（其實這時可以直接特判，若N=K，則所有的地方都必須放人，否則就是-1）；二是，如果去掉那些肯定木有人的點后，剩下的點的個數剛好等于K（不可能小于K的，因為肯定有解），則不用貪心了，剩下所有的地方肯定都必須放人。
總時間復雜度O(NlogN + MlogM)；
這里千萬要注意的一點是，應該先將所有區間重編號再去包含，而不應該先去包含再重編號！！！因為可能有兩個區間本來是不包含的，但重編號以后，包含了。（本沙茶比賽的時候就是這里木有注意到，跪了3個點，杯具了）

【kunai】
40分的暴力做法：枚舉兩個動點，求出它們是否會相撞以及相撞的時間，然后將所有相撞事件按照時間排序，掃描排序后的每個事件，如果相撞的兩個動點都還在，就將它們消去，然后可以求出每個動點移動的距離，求一下并集（線段樹）即可；（本沙茶當時主要是實在木有時間寫這題了，因此連暴力都木有寫）
AC做法：很明顯，一個動點一旦被消去，就不會再次出現了，因此對于每一個點，只需要找到最先和這個點相撞的點即可。顯然能夠相撞的兩個點必然位于同一行/列/對角線上且方向滿足一定限制（其實一共只有6種情況：同一行一種，同一列一種，同一左上右下對角線兩種，同一右上左下對角線兩種）。因此，枚舉這6種情況，直接用掃描法得到最先與它相撞的動點，取相撞時間最小的那個即可，如果都找不到，這個點就是永存的。這樣相撞事件的總數就減少到了O(N)級別，總時間復雜度就是O(NlogN)。
注意：有可能在同一時間有多個動點在同一位置相撞，因此，對于同時發生的相撞事件，應該將它們一起處理，涉及到的點一起消去。