CF Round 1046(#2135) 總結

A

可以 DP，用 vector 存下這個數出現的位置。

B

考慮移動到無限遠處，如果移到左下角，容易發現離的最近的點就是離 \((-10^9,-10^9)\) 最近的點。這樣就能確定一條直線（確定 \(x+y\)）。

同理移動到左上角又確定一條直線（確定 \(x-y\)）。

需要 8 次詢問。

C

首先把邊雙找出來，容易發現不同邊雙是不會影響的。

考慮一個邊雙內，題目的限制形如每個環的異或和都為 \(0\)，發現這其實可以推出邊雙內所有點的權值相等。所以就做完了。

D1 & D2

考慮到問一個長為 \(n\) 的全是 \(k\) 的序列，可以得到 \(\lceil\dfrac n {w/k}\rceil\)，這大概有 \(O(\sqrt n)\) 種取值。

考慮按 \(B=\sqrt {10^5}\) 分塊，可以問 \(k=B\) 實現，對于 \(w<B\) 可以問 \(10^5\) 個 1；否則可以問 \(\lfloor \dfrac w B\rfloor B,1,\lfloor \dfrac w B\rfloor B,2,\lfloor \dfrac w B\rfloor B,3,\dots\)，一直問到 \(B\)。

這可以通過 D1。

考慮 D2，可以繼續優化，其實每塊的長度可以不固定，問一個 \(k\) 以后，可以知道 \(w\) 在區間 \([L,R]\) 內，只需要問 \(L,1,L,2,L,3\dots\)，一直問到 \(L\) 即可。而對于 \(w<k\) 的情況，同樣可以問 \(k^2\) 個 \(1\)。精細實現即可。

E1 & E2

把 \(0\) 看做 \(-1\)，求出前綴和，等價于 \(\min s +\max s=s_n\)。

考慮格路計數，然后反射容斥。做出 E1 后還要優化。

F

考慮怎么比較 \(f(x),f(y)\)，考慮比較它們的指數 \(\prod f(a_i),\prod f(b_i)\)。

把 \(a_i,b_i\) 都按 \(f(a_i),f(b_i)\) 從大到小排序，我們找到第一個不等的位置，\(f(x),f(y)\) 的大小就是 \(f(a_i),f(b_i)\) 的大小。這是因為若 \(f(a_i)<f(b_i)\) 則它們至少差一個 \(x\) 數量級，那么后面的位無論乘都不會比 \(f(a_i)\) 大。

那么現在只需考慮求出 \(f(x)\) 的排名，然后比較兩個 \(f\) 就是按上述方式比較排名序列。

由于一個點的 \(f\) 大于其子樹內的。考慮按照拓撲序把 \(x\) 丟進堆里，每次取出最小的 \(f(x)\)，維護一個當前排名，若 \(f(x)>f(lst)\) 則將排名加一。然后更新其父親的 \(f\)，發現其父親的 \(f\) 就是繼承其左兒子的排名序列，然后再插入右兒子的排名。

考慮快速比較兩個排名序列，把序列中所有點插到線段樹上，維護節點內的哈希值，比較排名序列就可以線段樹上二分。而繼承左兒子的排名序列就是類似可持久化操作。復雜度 \(O(n\log ^2n)\)。事實上直接用 vector 維護排名序列，然后把序列中相同排名并起來，修改和比較都暴力做，這樣是卡不掉的。