[Ynoi2011]ODT

\(O(nlog^2n)\) 的做法非常顯然

直接把樹重鏈剖分一下，每個點維護輕兒子的平衡樹就行

但是這題 \(1e6\) 的數據范圍使得 \(O(nlog^2n)\) 沒那么容易卡過去(當然很多人卡過去了

考慮給一個點很多重兒子

那么若一個點有 \(k\) 個重兒子，修改復雜度就變成 \(O(log_knlog_2n)\)，而查詢復雜度變成 \(O(klog_2n)\) 了

為了均攤我們需要 \(log_kn=k\rightarrow k^k=n\)，發現當 \(k=7\) 時應該是最優的

這樣我們得到了一個復雜度 \(O(7nlogn)\) 的算法，已經足夠通過這道題了

好像還有一個 \(log\) 的做法但是我不會也找不到講解先咕了

[Ynoi2019]魔法少女網站

Ynoi+序列=分塊

考慮把操作分塊

把所有詢問按照x從小到大排序，對于當前的x，把小于等于他的位置設為1,大于的位置設為0，每次x變大就把新符合的變成1

用類似鏈表的東西維護一下

由于需要查詢區間我們考慮分塊維護(因為我們需要 \(O(1)\) 插入，現在唯一的問題就是修改操作中會把1變成0

考慮一個套路就是插入之后按序撤銷，初始讓所有被修改的位置一直是0就行了

復雜度 \(O(n\sqrt{n})\)

[Ynoi2017]由乃的玉米田

前兩個操作可以顯然的用莫隊+bitset做，第三個可以直接莫隊，我們只考慮一下第四個

第四個操作當 \(x\ge\sqrt{n}\) 的時候顯然可以直接在莫隊詢問的時候暴力做

當 \(x

復雜度 \(O(n\sqrt{n}+\frac{n^2}{\omega})\)

[Ynoi2016]掉進兔子洞

顯然的答案就是 \(r_1-l_1+r_2-l_2+r_3-l_3+\sum\limits_a min(cnt_1[a],cnt_2[a],cnt_3[a])\)

用前幾天大神講的那個 \(bitset\) 實現取 \(min\) 的方式得到每個所需區間的 \(bitset\) 然后與一下就行了

得到每個區間的 \(bitset\) 可以直接用莫隊來做(當然空間是開不下的，分多組做就行了)

CF1148H Holy Diver

對每個右端點 \(r\) 維護每個左端點 \(l\) 的 \(mex\)

顯然的一件事是 \(mex\) 隨 \(l\) 的增加而減小，且新加入一個 \(a_r\) 只會影響到之前所有 \(mex=a_r\) 的位置

顯然的 \(mex\) 序列被分成若干段，且隨著 \(r\) 的右移分界點最多增加 \(n\) 個，所以我們每次可以暴力的二分找出所有分界點來區間修改

考慮怎么維護答案，發現每次就是把一個 \(mex\) 相同的區間的 \(mex\) 集體改變

設該權值某個位置在時刻 \(t_1\) ?出現，時刻 \(t_2\) ?消失或詢問，則該位置貢獻為 \(t_2?t_1+1\)，每次修改操作相當于區間加。

對每種權值用動態開點線段樹維護一下就行了

CF704E Iron Man

考慮序列上怎么做

我們讓時間為橫坐標，位置為縱坐標，那么每個點相當于一條線段，我們要找的就是最小的出現相交的橫坐標

考慮對橫坐標做掃描線，發現如果每個時刻把存在的線段按照目前的縱坐標排序那么有交點的線段一定在某一時刻是相鄰的

考慮直接用 \(set\) 維護，加入的時候和前趨后繼求交點，刪除的時候讓前趨后繼求交點

雖然縱坐標是變化的，但是顯然的在出現交點之前線段之間相對位置不變，只要在橫坐標 \(\ge\) 目前求出的交點時退出就行了

放到樹上，直接樹剖一下，每個重鏈跑一遍就行了，復雜度 \(O(mlog?mlog?n)\)