题解 P6109 【[Ynoi2009]rprmq】

终于自己把 EE Round2 补完了，说实话现在码力和思维都不行，每次都需要比赛时间的 2-3 倍时间才能自己想出来并调完，怪不得我 div2 都打不起来。 实力真的不够啊，希望省选的时候不要留下这种遗憾啊。 吐槽：lxl 居然不出分块作为压轴题了，真是神奇。 首先看到 $n,m$ 和 $q$ 不同阶，可以先猜猜复杂度。 刚开始我以为是有根号的，不过怎么想询问一次最少要 $O(\log n)$，感觉怎么分块都不太行。。。这题 $\texttt{6s}$ 是给常数的，不是给 $O(q\sqrt{n}\log n)$ 的。。。 然后询问次数一定是 $O(q)$ 的，那么很自然的想到了分治，类似猫树。 我们把 $x$ 轴作为外层线段树，$y$ 轴作为内层线段树。询问就可以挂在外层线段树上的深度最小区间的 $[l,r]$，使得 $l\le l_1\le \text{mid}+1,\text{mid}\le r_1\le r$，这样我们每次预处理 $[l,\text{mid}]$ 和 $[\text{mid}+1,r]$ 的答案，就可以快速合并。 我们把操作差分成在 $l_1$ 位置把线段树 $[l_2,r_2]+x$，在 $r_1+1$ 位置把线段树 $[l_2,r_2]-x$，这样在一个位置的询问就变成一个前缀的询问。 这就意味着在进入区间 $[l,r]$ 时，我们要先处理 $[1,l-1]$，然后边加边算。 接下来考虑怎么弄答案。矩阵不是很直观，我们可以将题目换一种表述： 先是 $m$ 次操作，在时间 $[l_1,r_1]$ 时会将 $[l_2,r_2]+x$。 再是 $q$ 次询问，在时间 $[l_1,r_1]$ 时会询问 $\text{max}\in [l_2,r_2]$。 这样在一段时间的答案意味着什么，区间历史最大值！ 相当于我们要维护历史最大值，并且要撤销一段时间的操作。 发现撤销比较难撤销，把答案定格在一个时间重新开始会比较简单。 我们再维护一个 $\text{reset}$ 标记，相当于把当前区间历史最大值改成最大值，加法标记历史最大值改成最大值。 两个标记，好像要考虑怎么下传。$\text{reset}$ 标记前的 $\text{add}$ 标记必须下传，$\text{reset}$ 标记后的 $\text{add}$ 标记可以留在那里，并且 $\text{pushdown}$ 的时候优先下传 $\text{reset}$ 标记，这样就解决了标记问题。 这时候就有一个屑高高兴兴写完过了样例，一交上去，$100\rightarrow 1$。 这个屑想了很长时间，发现：一个时间不止有一个操作！ 这意味着可能你在这个时间先 $+3$ 再 $-1$，线段树上询问历史最大值是 $3$，但是实际答案是 $2$。 那怎么办呢？ 还需要将加法操作按 $x$ 排序，加进去的时候从负数开始，减回去的时候从正数开始。其实减回去无所谓，反正都要定格在一个时间。 然后还有一些细节： 1. 在处理 $[l,\text{mid}]$ 的答案时要先定格，但在处理 $[\text{mid}+1,r]$ 的答案时要在时间 $\text{mid}+1$ 这些操作加完后再定格，因为时间 $\text{mid}$ 不包含在里面。 2. 在处理 $[l,\text{mid}]$ 的答案时要先询问再减回去，在处理 $[\text{mid}+1,r]$ 的答案时要先加上去再询问。 大概就这么多了，时间 $O(n\log^2 n+q\log n)$。线段树常数还有一些，直接 ++ 好像不太行。 对于我这种常年不用快读快输的人，要加个快读快输板子。 然后就是线段树板子要快一些。。。我的代码 cpu 监控时间是最优解的六倍（不卡常+不封装），丢人死了，直接复制过来岂不 $T$ 飞？ 难道我去做这道题之前还要再去写一遍 cpu 监控并卡到最优解？ 我比较懒，直接去 cpu 监控那复制了一份最优解，下面板子的部分是 @iostream 的。 ~~希望他/她看到这里不会说我侵权就行了~~ 突然想到自己询问 $=0$ 的地方忘剪枝了，算了，能过就行。 ~~Ynoi 不卡常真好，不用特地在深夜交题了~~ 因 @noip 要求，代码删了，有需要私聊我好了，网课结束前我都在线。