自动搬运

查看原文

来自洛谷，原作者为

	PrinceX AFOed

搬运于2025-08-24 22:54:29，当前版本为作者最后更新于2024-03-14 16:36:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

刚放这题时有一篇题解（是谁已经记不清了），我就是用的他的做法做出的，但是现在被删了。所以我按自己的理解再发一遍。

给定$m$个操作，每个操作形如 $1,l,r,x$ 表示将 $i\in[l,r],a_i\gets x$，或者是 $2,l,r$ 表示求 $\sum_{i=l}^ra_i$ 的值。

现有 $q$ 个询问，每个询问给出 $L,R$，表示求将数列初始置为 $0$ 后依次执行$[L,R]$内的操作，求所有 $2$ 操作的答案和。

$n,m,q$同阶，$\le5e5$，6s。

与官方题解做法不同。 注意区分“查询”和“询问“，查询指2操作。

对操作扫描线，想方设法维护出 $R=i$ 时所有 $L$ 的答案。这样不仅去掉了 $R$ 的限制，而且只需要求屏蔽掉 $<L$ 的操作后的答案，模型简化。

考虑对序列分块，分别计算以下贡献：

• 修改对散块查询的贡献
• 整块修改对整块查询的贡献
• 散块修改对整块查询的贡献

对于情况1，枚举每个位置的查询，我们可以轻松维护出每个位置最新覆盖的数（整块标记和散块标记），并将这些操作更新进答案中。

具体地，假设当前位操作的时刻是 $t$，那么如果 $t\ge L$ 那么会对询问造成贡献。注意到这里的 $t$（修改）共有 $O(m\sqrt n)$ 个，而询问只有 $q$ 个，所以使用 $O(1)-O(\sqrt n)$ 分块，这部分贡献就被处理完了。

对于情况2，如果当前整块的值整个相同（即上一次是整块修改），实际上就和单个数是一样的，所以同样套用刚刚的数据结构做即可。

对于情况3，实际上我们求的是当前查询整块的值不整个相同时所有查询带来的贡献。注意到部分修改一个块只能是散块修改，并且如果整块修改覆盖了原来的散块修改也要去掉散块修改的贡献。易知这里总的操作数是 $O(m)$（上界 $4m$）。

单独考虑所有的块并枚举每个操作。如果当前操作有对当前块的散块修改或者删除散块修改 的修改，就暴力执行。

考虑这里一个散块修改操作的贡献：设其执行时间为 $t$ ，那么对于 $L\le t$ 的询问会造成贡献。贡献就是权值 $\times$ 加入时刻到询问时刻中当前块查询的次数 $-$ 删除时刻到当前时刻中当前块查询的次数。实际上删除和加入本质相同，只是权值互为相反数，之后不再分类讨论。

对于所谓的加入时刻到询问时刻中当前块查询的次数，可以转化成初始时刻到询问时刻的查询次数-初始时刻到加入时刻的查询次数。

考虑维护两个 $O(\sqrt n)-O(1)$ 分块，分别维护初始时刻到当前所有权值的贡献和以及所有权值乘上当前查询次数的贡献和。

因此总复杂度是$O(n\sqrt n)$。本题可以轻松通过。做完可以去试试加强版，时限少了1s，非常卡常。

情况三比较困难，给一下代码： link