透彻线段树

Study

1.

区间加

#include <bits/stdc++.h>
using namespace std;
/*
如果人可以长尾巴
会觉得有点难为情呢
因为只要和你在一起,我总会忍不住摇尾巴吧
*/
const int maxn = 1e6 + 10;
#define ls(now) (now << 1)
#define rs(now) (now<<1|1)
#define mid ((l + r) >> 1)
int n, m, a[maxn];
struct seg_tree{
    struct nodes{
        long long l, r, sum, tag;
        long long get(){
            return sum + (r - l + 1) * tag;
        }
    }node[maxn];
    void up(int now){
        return (void)(node[now].sum = node[ls(now)].get() + node[rs(now)].get());
    }
    void down(int now){
        return (void)(node[ls(now)].tag += node[now].tag, node[rs(now)].tag += node[now].tag, node[now].tag = 0);
    }
    void bulid(int l, int r, int now){
        node[now].l = l, node[now].r = r;
        if(l == r) return (void)(node[now].sum = a[l]);
        bulid(l, mid, ls(now)), bulid(mid+1, r, rs(now));
        up(now);
    }
    void chenge(int l, int r, int now, int val){
        if(node[now].r < l or node[now].l > r) return;
        if(l <= node[now].l and node[now].r <= r) return (void)(node[now].tag += val);
        down(now);
        chenge(l, r, ls(now), val), chenge(l, r, rs(now), val);
        up(now);
    }
    void query(int l, int r, int now, long long &ans){
        if(l > node[now].r or r < node[now].l) return;
        if(l <= node[now].l and node[now].r <= r) return (void)(ans += node[now].get());
        down(now);
        query(l, r, ls(now), ans), query(l, r, rs(now), ans);
        up(now);
    }
}tree;
signed main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
    }
    tree.bulid(1, n, 1);
    for(int cmp, x, y, z; m ; m --){
        scanf("%d", &cmp);
        if(cmp == 1){
            scanf("%d%d%d", &x, &y, &z);
            tree.chenge(x, y, 1, z);
        }
        if(cmp == 2){
            long long ans = 0;
            scanf("%d%d", &x, &y);
            tree.query(x, y, 1, ans);
            printf("%lld\n", ans);
        }
    }
    return 0;
}

2.

区间乘+区间加

加法和乘法顺序不一样会导致不同的结果

比如: $(a+b)*c$ 不等于 $ac+b$

而在记录懒标记的时候，加法和乘法两种标记放到一起，并不知道哪个先，哪个后。

所以要确定一个优先级

我们分析一下两种顺序：

1. 先加后乘 : $(a+b)*c$ = $ac + b*c$

2. 先乘后加：$a*c+b$

比较一下，发现，上面的先加后乘相当于下面的式子，在加法上面多乘了一个$c$

所以，我们只要是先加后乘的式子，只要加一个$*c$就可以转化为先乘后加的式子

具体的操作就是在添加乘法标记的时候，把加法标记$*c$就好了

所以，我们就定了一个总顺序：先乘后加（摘自luogu博客）

然后在down下放标记的时候，左右儿子的加法标记传递也要保持先乘后加的顺序，即 ：

void down(int now){
    t[ls(now)].tmp = (t[ls(now)].tmp*t[now].tmp)%p;
    t[rs(now)].tmp = (t[rs(now)].tmp*t[now].tmp)%p; 
    t[ls(now)].tag = (t[ls(now)].tag*t[now].tmp)%p;
    t[rs(now)].tag = (t[rs(now)].tag*t[now].tmp)%p; 
    t[ls(now)].tag = (t[ls(now)].tag+t[now].tag)%p;
    t[rs(now)].tag = (t[rs(now)].tag+t[now].tag)%p;
    t[now].tag = 0, t[now].tmp = 1;
    return;
}

解决方法：先乘后加

//对于每一次的区间乘val，我们对在此次操作前做的区间加也乘上这次的val
t[now].tmp *= val, t[now].tag *= val

完美的解决了问题

#include <bits/stdc++.h>
using namespace std;
/*
如果人可以长尾巴
会觉得有点难为情呢
因为只要和你在一起,我总会忍不住摇尾巴吧
*/
const int maxn = 1e6 + 10;
#define ls(now) (now << 1)
#define rs(noe) (now<<1|1)
#define mid ((l + r) >> 1)
int n, m, p, a[maxn];
long long ans;
struct seg_tree{
    struct nodes{
        long long l, r, sum, tag, tmp;
        nodes(){
            tmp = 1;
            tag = 0;
        }
        long long get(){
            return (((sum%p)*tmp%p)%p + ((r-l+1)*tag)%p);
        }
    }t[maxn];
    void up(int now){
        return (void)(t[now].sum = t[ls(now)].get() + t[rs(now)].get());
    }
    void down(int now){
        t[ls(now)].tmp = (t[ls(now)].tmp*t[now].tmp)%p;
        t[rs(now)].tmp = (t[rs(now)].tmp*t[now].tmp)%p; 
        t[ls(now)].tag = (t[ls(now)].tag*t[now].tmp)%p;
        t[rs(now)].tag = (t[rs(now)].tag*t[now].tmp)%p; 
        t[ls(now)].tag = (t[ls(now)].tag+t[now].tag)%p;
        t[rs(now)].tag = (t[rs(now)].tag+t[now].tag)%p;
        t[now].tag = 0, t[now].tmp = 1;
        return;
    }
    void bulid(int l, int r, int now){
        t[now].l = l, t[now].r = r;
        if(l == r) return (void)(t[now].sum = a[l]);
        bulid(l, mid, ls(now)), bulid(mid+1, r, rs(now));
        up(now);
    }
    void chenge(int l, int r, int now, int val){
        if(r < t[now].l or l > t[now].r) return;
        if(l <= t[now].l and t[now].r <= r) return (void)(t[now].tag += val);
        down(now);
        chenge(l, r, ls(now), val), chenge(l, r, rs(now), val);
        up(now);
    }
    void change(int l, int r, int now, int val){
        if(r < t[now].l or l > t[now].r) return;
        if(l <= t[now].l and t[now].r <= r) return (void)(t[now].tmp *= val, t[now].tag *= val);
        down(now);
        change(l, r, ls(now), val), change(l, r, rs(now), val);
        up(now);
    }
    void query(int l, int r, int now, long long &ans){
        if(r < t[now].l or l > t[now].r) return;
        if(l <= t[now].l and t[now].r <= r) return (void)(ans += t[now].get(), ans %= p);
        down(now);
        query(l, r, ls(now), ans), query(l, r, rs(now), ans);
        up(now);
    }
}tree;
signed main(){
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
    }
    tree.bulid(1, n, 1);
    for(int cmp, x, y, z; m; m --){
        scanf("%d", &cmp);
        if(cmp == 1){
            scanf("%d%d%d", &x, &y, &z);
            tree.change(x, y, 1, z);
        }
        if(cmp == 2){
            scanf("%d%d%d", &x, &y, &z);
            tree.chenge(x, y, 1, z);
        }
        if(cmp == 3){
            scanf("%d%d", &x, &y);
            tree.query(x, y, 1, ans);
            printf("%lld\n", ans);
            ans = 0;
        }
    }
    return 0;
}