分块套分治_专题_LCA

分块套分治

P5611 [Ynoi2013] D2T2

给一个长为 $n$ 的序列，有 $m$ 次查询操作。

查询操作形如 $l\;r\;L\;R$，表示将序列中值在 $[L,R]$ 内的位置保留不变，其他的位置变成 $0$ 时，序列中 $[l,r]$ 区间内的最大子段和，这个子段可以是空的。

对于 $100\%$ 的数据，$1\leq n,m \le 10^5$，序列中所有数的绝对值 $\le 10^9$。

简单来说就是只考虑矩形内的点的最大子段和。

考虑一个区间内只有 $len$ 个值，将序列按 $B$ 分块，每块我们暴力求出 $B^2$ 个值域区间对应的半群信息，求法就是暴力递归，$T(n)=\mathcal O(n^2)+2T(n/2)$，最后还是 $\mathcal O(B^2)$ 的，复杂度 $\mathcal O(\frac nBB^2+m(\frac n B+B))$，平衡到 $\mathcal O((n+m)\sqrt n)$。

合并的过程可能需要带 $\log$。

空间限制 $\text{64MB}$，需要将上述过程离线，每块预处理即可。

P7881 [Ynoi2006] rmpq

P8078 [WC2022] 秃子酋长