题解 P3373 【【模板】线段树 2】
fy1234567ok · · 题解
深入分析懒标记优先级问题
看完此文，你或许会对线段树有个新的认识
UPDATE 2020.10.7
加入了 LaTeX 公式推导，加入了线段树本质的探讨，改进了代码
这题挺揪心的
想了半天为什么要先乘法后加法，我补充一下前面题解可能没说清楚的优先级问题
原因是这样的:
加法和乘法顺序不一样会导致不同的结果
如果我维护的值是
而在记录懒标记的时候，加法和乘法两种标记放到一起，并不知道哪个先，哪个后。
所以要确定一个优先级
我们分析一下两种顺序：
-
先加后乘 :
(a+b) \times c = a\times c + b\times c -
先乘后加：
a \times c + b
比较一下，发现，上面的先加后乘相当于下面的式子，在加法上面多乘了一个
所以，我们只要是先加后乘的式子，只要在
具体的操作就是在添加乘法标记的时候，先把加法标记
所以，我们就可以给懒标记定义一个固定的顺序：先乘后加
懒标记下传推导
然后在标记传递 pushdown 的时候
比如: 当前节点编号
以左儿子举例，根据先乘后加的顺序，我们给儿子乘上自己的乘法标记，再加上自己的加法标记
这样，儿子的
已知：懒标记的顺序是先乘后加 , 如果儿子已经有懒标记，它的懒标记如果要维护一个值
那现在又给他加上了
如果
所以在维护懒标记的时候，先在儿子的加法标记上乘一下自己的乘法标记，然后再加上自己的加法标记即可。
所以 pushdown 这样写即可
LL add(LL a,LL b) { return (a+b)%p; } //方便取模
LL mul(LL a,LL b) { return (a*b)%p; }
inline void pushdown(LL o,LL L,LL R) { //划重点
sumv[ls] = mul(sumv[ls],mulv[o]);
sumv[ls] = add(sumv[ls],addv[o]*(M-L+1));
mulv[ls] = mul(mulv[ls],mulv[o]);
addv[ls] = mul(addv[ls],mulv[o]);
addv[ls] = add(addv[ls],addv[o]);
sumv[rs] = mul(sumv[rs],mulv[o]);
sumv[rs] = add(sumv[rs],addv[o]*(R-M));
mulv[rs] = mul(mulv[rs],mulv[o]);
addv[rs] = mul(addv[rs],mulv[o]);
addv[rs] = add(addv[rs],addv[o]);
addv[o] = 0;
mulv[o] = 1;
}看到这里，我相信你已经有能力 AC 这题了，但是.....我们再来深入一步探讨一下
我先加后乘就不行了？你是不是看不起加法？
emmmm.... 如果你就想先加后乘，也不是不可以呀。先乘后加的式子也是可以转换成先加后乘的，让我们来瞧瞧：
如果你要维护
你看，先乘后加的也可以变成先加后乘的形式，只是中间出现了分数。所以你在维护的时候，就要把
嗯，它其实是可以的，但是比先乘后加麻烦了一些，还有求逆元。不过如果您特别喜欢加法，确实可以先加后乘。
看到这里，我相信您已经有能力用先加后乘来 AC 此题了，不过 Duck 不必哈哈哈。
但，我想说的，还不止于此，让我们再再深入探讨一下线段树。
为啥会出现优先级顺序的问题？我怎么想不到？
我相信，当你第一次意识到线段树的懒标记有优先级问题，一定是惨痛的 WA 带给你的。那么为什么线段树会这么麻烦，明明做【线段树模板1】的时候都挺简单的。那么下面，我就来给大家介绍一种万金油的办法，再也不会出现这种优先级的困扰。
线段树本质探讨
1、线段树究竟可以维护什么？
我们知道，线段树维护的是区间信息。并且区间的信息可以聚合。比如我有个序列
所以，线段树可以维护支持结合律的数据 。也就是这个操作
比如加和，乘法，最大 / 最小值
而区间翻转就维护不了：
2、那懒标记又算什么？
我们知道，懒标记用于区间修改。并且你可以用这个懒标记快速得到一个区间修改后的答案。比如加法：
所以对于一个操作
此外，懒标记必须支持下传 pushdown 操作。也就是说，两个懒标记可以聚合在一起。如果
比如乘法操作，给区间
所以支持这样操作的懒标记可以下传。
此外，我们还需要定义懒标记的初始的零状态, 使得：
比如加法:
3、总结
我们如果要维护一个数据，并且支持区间修改。那么必须定义四种操作
-
-
\odot([l,r],v) = sum'[l,r]$ 有定义, 且复杂度 $O(1) -
add(\odot ([l,r],v_1), \odot([l,r], v_2)) = \odot([l,r], v)$ 有定义，且复杂度 $O(1) -
所以只要把上面 4 种操作定义出来了，那线段树就肯定可以维护它。那可能有盲生就发现华点了：
这从头到尾跟优先级有半毛钱关系啊！
所以为什么会有优先级的问题呢？有人可能会说：可是你定义了 2 个懒标记，有 2 种操作啊！
蛤，线段树需要 2 个懒标记吗？
所以，你定义的那两个懒标记，本质上
它是一个懒标记啊啊！！！
那么我们来定义这道题的三种操作
-
a \oplus b = (a + b) \bmod \ p 支持结合律:
((a+b) \bmod \ p + c)\bmod \ p = (a + (b + c)\bmod \ p) \bmod \ p -
\odot([l,r], (a,b)) = sum[l,r] \times a+b \times (r-l+1)$ , 复杂度 $O(1) 我们可以把两个懒标记绑在一起，把他看做一个懒标记
(a,b) ，表示\times a +b , 那么我们就不得不定义一个顺序了。 -
add(\odot([l,r],(a_1,b_1)), \odot([l,r], (a_2,b_2))) = \odot([l,r], (a_1\times a_2, b_1\times a_2+b_2))$, 复杂度 $O(1) -
Zero(\odot) =(1,0)
是不是突然恍然大悟了，原来优先级的问题，在我们定义懒标记的时候，早就应该定义好了。
没错，就是这样！是因为之前我们自己要分成 2 个懒标记，才产生了这样的问题。所以只要我们每次只定义"一个"懒标记就好了。
为了方便每次定义这三种操作。我把整个线段树封装成了一个万能模板，送给大家, 谢谢！
使用样例：
线段树模板1 线段树模板2 小白逛公园
另外，想支持动态开点，分裂，还有其他操作的模板。可以在我的模板上改进一下。(我暂时还没写)
最后是本题的：
完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T, class Lz>
struct SegTree {
/**
* 线段树模板
* Author: fy
* C++ Standard: C++11 如果你是C98，则需要修改构造函数
* 使用：
* 1. 定义合并逻辑
* 1.1 线段树内的区间合并 add
* 1.2 线段树与懒标记的合并 addt
* 1.3 懒标记与懒标记的合并 addtt
* 1.4 懒标记的零状态 ZERO
* 2. 定义
* 2.1 第一个类型 T 是线段树内的类型, 第二个类型 Lz 是懒标记的类型，两者都可以自定义struct
* 第一个参数是传入要维护的数组， 第二个，第三参数是要维护的区间范围 [left, right]
* 第四，第五个，第六个参数分别是 add, addt, addtt函数，表示线段树内部聚合， 线段树与懒标记聚合，懒标记与懒标记聚合
* 第七个参数是懒标记的零状态
* Seg<T,Lz> seg(A, left, right, &add, &addt, &addtt, 0);
* 2.2 默认是区间求和, A是要维护的数组, 后面几个函数均是区间求和的函数
* Seg<int ,int> seg(A);
* 3. 操作
* 3.1 区间修改 [x, y] 值以懒标记的方式传递
* update(x, y, tag);
* 3.2 区间查询 [x, y] , 返回查询的结构，类型 T
* query(x, y)
* 3.3 单点修改 x
* insert(x, val)
*/
#define M ((L+R)>>1)
#define lson (o<<1)
#define rson (o<<1|1)
vector<T> sumv; // 维护的值
vector<Lz> tag; // 懒标记
int LEFT, RIGHT; // 维护的区间范围
// 四种操作
T (*add)(T, T); // 线段树内部聚合
T (*addt)(T, Lz, int, int); // 线段树与懒标记聚合
Lz (*addtt) (Lz, Lz); // 懒标记与懒标记聚合
Lz ZERO; // 懒标记的零状态
SegTree(vector<T> &arr, int left=1, int right=-1,
T (*fadd)(T,T) = [](T a,T b) { return a + b; },
T (*faddt)(T, Lz, int, int) = [](T a, Lz b, int l, int r) { return a + b*(r-l+1); },
Lz (*faddtt)(Lz, Lz) = [](Lz a, Lz b) { return a + b; },
Lz zero = 0) {
if (right == -1) RIGHT = arr.size()-1;
else RIGHT = right;
LEFT = left;
sumv = vector<T>(RIGHT<<2);
tag = vector<Lz>(RIGHT<<2);
add = fadd;
addt = faddt;
addtt = faddtt;
ZERO = zero;
build(arr, 1, LEFT, RIGHT);
}
inline void build(vector<T> &A, int o=1, int L=1, int R=-1) {
if (R == -1) {L = LEFT; R = RIGHT;}
tag[o] = ZERO; // 初始化懒标记
if (L == R) sumv[o] = A[L];
else {
build(A, lson, L, M);
build(A, rson, M+1, R);
sumv[o] = add(sumv[lson], sumv[rson]);
}
}
inline void pushdown(int o, int L, int R) {
if (L == R || tag[o] == ZERO) return;
sumv[lson] = addt(sumv[lson], tag[o], L, M);
sumv[rson] = addt(sumv[rson], tag[o], M+1, R);
tag[lson] = addtt(tag[lson], tag[o]);
tag[rson] = addtt(tag[rson], tag[o]);
tag[o] = ZERO;
}
inline void insert(int x, Lz val, int o=1, int L=1, int R=-1) {
if (R == -1) {L = LEFT; R = RIGHT;}
if (L == R) sumv[o] = addt(sumv[o], val, L, R);
else {
pushdown(o, L, R);
if (x <= M) insert(x, val, lson, L, M);
else insert(x, val, rson, M+1, R);
sumv[o] = add(sumv[lson], sumv[rson]);
}
}
inline void update(int x, int y, Lz val, int o=1, int L=1, int R=-1) {
if (R == -1) {L = LEFT; R = RIGHT;}
if (x <= L && R <= y) sumv[o] = addt(sumv[o], val, L, R), tag[o] = addtt(tag[o], val);
else {
pushdown(o, L, R);
if (x <= M) update(x, y, val, lson, L, M);
if (y > M) update(x, y, val, rson, M+1, R);
sumv[o] = add(sumv[lson], sumv[rson]);
}
}
inline T query(int x, int y, int o=1, int L=1, int R=-1) {
if (R == -1) {L = LEFT; R = RIGHT;}
pushdown(o, L, R);
if (x <= L && R <= y) return sumv[o];
else if (x <= M && y > M) return add(query(x, M, lson, L, M), query(M+1, y, rson, M+1, R));
else if (x <= M) return query(x, y, lson, L, M);
else return query(x, y, rson, M+1, R);
}
};
int MOD, n, m;
inline int add(int a, int b) { // 定义线段树内聚合，同时也是定义加法取模函数
return ((ll)a + b) % MOD;
}
inline int mul(int a, int b) { // 定义乘法，方便取模
return ((ll)a * b) % MOD;
}
inline int addt(int a, pair<int,int> lz, int l, int r) { // 定义线段树与懒标记聚合
return add(mul(a,lz.first), mul(lz.second,(r-l+1)));
}
pair<int,int> addtt(pair<int,int> a, pair<int,int> b) { // 定义懒标记与懒标记聚合
return {mul(a.first,b.first), add(mul(a.second,b.first), b.second)};
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> MOD;
vector<int> A(n+1);
for (int i = 1;i <= n; ++i) {
cin >> A[i];
}
SegTree<int,pair<int,int>> seg(A, 1, n, &add, &addt, &addtt, {1, 0});
for (int i = 1;i <= m; ++i) {
int op, x, y, z;
cin >> op;
if (op == 1) {
cin >> x >> y >> z;
seg.update(x, y, {z, 0});
} else if (op == 2) {
cin >> x >> y >> z;
seg.update(x, y, {1, z});
} else {
cin >> x >> y;
cout << seg.query(x, y) << endl;
}
}
return 0;
}