Summarize
震惊！tth37 竟自己写题目概括
给定一个长度为 $n$ 的整数数列，执行 $q$ 次操作：
- 将 $a_i$ 赋值为 $val$
- 将所有元素同时加上 $val$
- 将所有元素同时乘上 $val$
- 将所有元素同时赋值为 $val$
- 询问第 $i$ 个元素 $a_i$ 的值
- 询问所有元素的和
$1\le n \le 1e9,1\le q \le 1e7$
Solution
还是比较好想的。
将所有元素表示为 $kx+b$，便于实现整体乘法、加法操作。
维护以下信息：大众元素的值、大众元素的数量、特殊元素 $i$ 的值、特殊元素 $i$ 上一次被单独赋值的时间、所有元素的和、上一次整体赋值的时间。
在区间赋值操作时将原始值 $val$ 转化为 $(val-b)\times k^{-1}$，以维护 $kx+b$ 的性质。
Note
特殊读入方法在计算测试数据时不要下标越界！
Code
1 |