题解：P5608 [Ynoi2013] 文化课
Ray_Wu
·
·
题解
思维难度不大，但卡常难度很大。
我的第一篇 Ynoi 题解？
Task
给出一串仅由数字和加法乘法的计算式。有三种操作：
-
区间修改数字；
-
区间修改运算符；
-
查询区间运算结果。
### Solution
一步一步来。
1. 不带修
先考虑不带任何修改怎么做。容易发现这玩意很线段树。两个节点如何合并信息呢？
如果中间运算符为 $+$ 直接两边答案加起来。如果是 $\times$，显然不能直接乘起来。考虑每个节点记录左侧的连乘长度和答案，右侧同理。实际上我们是把左边节点的右端连乘与右边的左边连乘乘起来了。
代码大概长这样：
```cpp
struct Node { int l, r, llen, rlen, lmul, rmul, val; };
inline int len(Node u) { return u.r - u.l + 1; }
inline Node operator + (Node u, Node v) {
Node res;
res.l = u.l;
res.r = v.r;
res.llen = u.llen == len(u) && b[u.r] ? u.llen + v.llen : u.llen;
res.rlen = v.rlen == len(v) && b[u.r] ? v.rlen + u.rlen : v.rlen;
res.lmul = u.llen == len(u) && b[u.r] ? mul(u.lmul, v.lmul) : u.lmul;
res.rmul = v.rlen == len(v) && b[u.r] ? mul(v.rmul, u.rmul) : v.rmul;
res.val = b[u.r] ? ((0ll + u.val + v.val - u.rmul - v.lmul + mul(u.rmul, v.lmul)) % P + P) % P : add(u.val, v.val);
return res;
}
```
这一部分较为简单，能获得 $5$ 分。
2. 修改运算符
在线段树的每个节点上额外记录其右侧的运算符是什么。
用线段树维护区间修改即可。加一个 tag 即可实现。
注意如果你修改了运算符，那么这些区间的答案也会随之而改变。所以要重新 push_up 一轮，才能保证后面的操作不会出错。
现在是 $24$ 分。
3. 修改数值
考虑如果一段区间的数值全被修改为同一个值 $x$ 会发生什么。你会发现这段区间的答案变为了形如 $p_1x^{q_1} + p_2x^{q_2} + \cdots + p_tx^{q_t}$ 的东西。
我们可以开一个 `vector<pair<int, int> >` 强制维护这些二元组 $(p_i, q_i)$（开数组直接爆空间）。设这段区间为 $[l, r]$，发现一个式子：
$$
\sum_{i = 1}^t p_i \times q_i = r - l + 1
$$
这是显然的。由于 $q_i$ 互不相同，本质不同的二元组数量一定 $\le \sqrt{r - l + 1}$，这是好证明的。
所以暴力维护复杂度是对的。合并的时候，归并两个 vector。要判断一下中间的运算符：
- 如果是 $+$，直接归并即可；
- 否则，你需要合并左边区间的右侧连乘与右边区间的左侧连乘。这个可以先删除再添加，有些细节。
存下了这些二元组，区间答案的计算就很显然了。
做完了，复杂度 $O(n \sqrt n)$。
接下来进入调试和卡常环节。提供一些警示后人和卡常技巧：
- **注意输入的值域是 $[1, 2^{32} - 1]$，别以为可以用 int 存，int 上界是 $2^{31} - 1$！！！！！**
- 更新完运算符一定要重新 push_up 一轮答案！你可能会问：为什么不能同时更新运算符和答案？因为两者的修改区间不一样。
- 将函数写进结构体里会快很多。
- 合并两个 vector 时有的地方能 break 就 break。
- **开一个辅助 vector 用于删除 vector 中某个元素并反复 push_back 较慢。直接 [vector erase](https://en.cppreference.com/w/cpp/container/vector/erase) 即可。从中间插入的话可以 [vector insert](https://en.cppreference.com/w/cpp/container/vector/insert)。**
- **一定要尽量规避大量的 push_back，可以先 resize 一个大小然后直接用下标。**
- 快读快输、inline 等常规卡常方法。
祝各位卡常愉快。
大战此题将近一整天才过。看来我离滚回去上文化课不远了啊。