[洛谷T205310] practiceZ
给定两个长为 \(n\) 的序列 \(a,b\)，支持三种操作：
1 l r x：将 \(a\) 序列中区间 \([l,r]\) 的数赋值为 \(x\)；2 l r y：将 \(b\) 序列中区间 \([l,r]\) 的数赋值为 \(y\)；3 l r：求 \(\sum\limits_{i=l}^{r} \sum\limits_{j=1}^{b_i}a_j\)，答案对 \(2^{32}\) 取模。\(1\le n\le 5\cdot 10^5,1\le m\le 3\cdot 10^5\)。
时间限制 \(\text{5000ms}\)，空间限制 \(\text{128MB}\)。
Solution
考虑将 \(b\) 序列分块，我们的目的是时刻维护块内 \(\sum\limits_{i} \sum\limits_{j=1}^{b_i}a_j\)，即答案。
先不考虑 2 操作。我们用珂朵莉树维护 \(a\) 序列的连续段，连续段是均摊 \(\mathcal O(n+q)\) 条，它对一个块的影响是 \(\Delta \times \sum\limits_{i=l}^{r} (块内有多少个 b_j \ge i)\)，右边拆式子就是 \(\sum\limits_{i=1}^{r} (块内有多少个 b_j\ge i)-\sum\limits_{i=1}^{l-1} (块内有多少个 b_j\ge i)\)。因为有 $\mathcal O(\sqrt{n}) $ 个块，所以我们需要支持一个 \(\mathcal O(1)\) 求这玩意的 DS：
因此，我们对于每个块，开两个分块，一个维护 \(b\) 值域前缀和，一个维护 \(b\) 值域后缀个数和即可。
查询的时候，对于整块直接拿答案，散块暴力查，所以我们还需要对 \(a\) 支持一个 \(\mathcal O(\sqrt{n})\) 区间加，\(\mathcal O(1)\) 前缀查的 DS，用分块即可。
现在考虑加上 2 操作。我们再开一个珂朵莉树维护 \(b\) 序列的连续段，连续段内的 \(\sum\limits_{i=1}^{b} a_j\) 是一样的，连续段同样均摊 \(\mathcal O(n+q)\) 条。2 操作，它会影响到原本块内维护的这两个分块，但是都是单点修改，所以我们只要能对这个分块进行 \(\mathcal O(\sqrt{n})\) 修改即可，这个不难。对于整块直接覆盖答案即可，对于散块，重构影响到的位置的答案即可。
现在我们能做到时间复杂度 \(\mathcal O((n+q)\sqrt{n})\)，空间复杂度 \(\mathcal O(n\sqrt{n})\)，空间承受不了。我们可以采用逐块处理的方式，把所有 \(a,b\) 珂朵莉树的连续段全部存下来，然后对于每一块分别扫即可。
在逐块处理的时候，有一个比较棘手的问题，就是对 \(a\) 维护的分块，在每个块都要重新再做一遍，这样就变成暴力了。我们考虑在啥时候要用到它：
- 在查询时，散块的地方用到；
- 在
2操作导致的 \(b\) 连续段，查询 \(\sum\limits_{i=1}^{newb} a_i\) 用到。
第一个，我们在离线前就可以提前计算贡献；第二个，我们把这玩意存下来，离线的时候就可以直接获取。这样，该问题就解决了。
时间复杂度 \(\mathcal O((n+q)\sqrt{n})\)，空间复杂度 \(\mathcal O(n)\)。