[THUPC 2024 決賽] 古明地棗的襪子

先把前綴加，全局最大值轉(zhuǎn)換成單點(diǎn)加，最大非空后綴和。

不妨先考慮所有操作的 \(x_i\) 都互不相同的情況。
對(duì) \(a\) 序列分塊，設(shè)塊長 \(B=\sqrt{n}\)。
對(duì)于一個(gè)詢問，如果我們已經(jīng)知道了每個(gè)塊內(nèi)的和以及這個(gè)塊內(nèi)的最大后綴和，那么我們可以 \(O(B)\) 的從后往前掃每個(gè)塊，然后用類似于線段樹維護(hù)最大子段和的方式合并信息，得出全局的最大非空后綴和（注意：因?yàn)橐?strong>非空，所以不能隨便對(duì) \(0\) 取 \(\max\)，但這是細(xì)節(jié)問題，這里不贅述）。具體的，如果我們掃到了第 \(i\) 個(gè)塊，目前的全局和是 \(S\)，最大非空后綴和是 \(maxn\)，現(xiàn)在要加入第 \(i-1\) 個(gè)塊，假設(shè)第 \(i-1\) 個(gè)塊內(nèi)部的和是 \(sum_{i-1}\)，最大后綴和是 \(suf_{i-1}\)，那么就做如下更新：\(\max(suf_{i-1}+S,maxn) \to maxn,S+sum_{i-1} \to S\)。

因?yàn)樾薷牟僮鞯?\(x\) 互不相同，這意味著落在每個(gè)塊里的修改操作只有 \(B\) 個(gè)，也就是說對(duì)于這個(gè)塊來講，本質(zhì)不同的詢問只有 \(O(B^2)\) 個(gè)，如果我們能對(duì)每個(gè)塊預(yù)處理出這 \(O(B^2)\) 種詢問對(duì)應(yīng)的信息就可以在 \(O(n\sqrt{n})\) 的復(fù)雜度內(nèi)回答所有詢問了。

現(xiàn)在只需要知道如和預(yù)處理每個(gè)塊要的 \(O(B^2)\) 個(gè)信息。
先把這個(gè)塊內(nèi)的修改按照 \(x\) 排序，然后考慮分治。
如果當(dāng)前分治區(qū)間是 \([l,r]\)，我們要處理的就是在只考慮所有 \(x_i \in [l,r]\) 的修改操作時(shí)，所有的詢問 \((i,j)(i<j,x_i\in [l,r],x_j\in [l,r])\) 的信息。
我們先遞歸地去處理 \([l,mid]\) 和 \([mid+1,r]\)，在合并時(shí)，先把分治區(qū)間內(nèi)的操作按照編號(hào)排序，枚舉左右端點(diǎn) \(i,j\)，那么區(qū)間 \([i,j]\) 中有一部分操作來自左半?yún)^(qū)間，另一部分來自右半?yún)^(qū)間，并且我們已經(jīng)處理出了這兩部分分別的信息，又因?yàn)槲覀円婚_始是按照 \(x\) 排序的，所以可以直接把他們合并起來，合并方式跟求答案一模一樣。
接下來分析復(fù)雜度，設(shè) \(T(n)=2T(\frac{n}{2})+O(n^2)\)，所以 \(T(n)=O(n^2)\)，即預(yù)處理一個(gè)塊的復(fù)雜度是 \(T(B)=O(B^2)\) 的，總預(yù)處理的復(fù)雜度是 \(O(n\sqrt{ n})\)。

然后對(duì)于每個(gè)修改的 \(x\) 可能相同的情況，現(xiàn)在一個(gè)塊內(nèi)的修改可能不再是 \(O(B)\) 的了，但是我們可以改成把所有修改按照 \(x\) 排序后，直接對(duì)操作序列分塊，然后就和之前的分析一模一樣了。不過需要注意的是，當(dāng)兩個(gè)操作的 \(x_i\) 相同時(shí)，應(yīng)該按照 \(y_i\) 降序排序，這是因?yàn)楫?dāng)兩個(gè)滿足 \(x_i=x_j,y_i<0<y_j\) 的操作 \(i,j\) 同時(shí)被詢問包含時(shí)，他們實(shí)際上是同時(shí)作用在 \(x_i\) 這個(gè)位置的，如果把 \(y_j\) 放在后面，就會(huì)導(dǎo)致在算后綴和的時(shí)候可能會(huì)先把 \(y_j\) 加到后綴里直接去更新答案，但其實(shí) \(y_i\) 也應(yīng)該一起被計(jì)算。

最后就是因?yàn)槟汩_不下 \(O(B^3)\) 的數(shù)組，所以需要倒序預(yù)處理每個(gè)塊的信息，預(yù)處理完之后直接把它貢獻(xiàn)到答案里就可以了。

code
代碼經(jīng)過卡常之后可讀性極差，就不放出來了。