洛谷P2023 [AHOI2009]维护序列（线段树区间更新，区间查询）

洛谷P2023 [AHOI2009]维护序列

区间修改

当我们要修改一个区间时，要保证 \(ax+b\) 的形式，即先乘后加的形式。当将区间乘以一个数 \(k\) 时，原来的区间和为 \(ax+b\) ，乘以 \(k\) 得 \(k(ax+b)=kax+kb\) 。

区间加一个数更加简单，原来的区间和为 \(ax+b\) ，加上一个 \(k\) 为 \(ax+b+k\) ，合并 \(b\) ，\(k\) 得 \(ax+(b+k)\) 。

标记下传

\[a(a’x+b’)+b = (aa’)\cdot x + (ab’+b)
\]

#include<bits/stdc++.h>using namespace std;
#define lson l, mid, root << 1
#define rson mid + 1, r, root << 1 | 1const int maxn = 100005;
long long tree[maxn << 2];
int n, p, q;
struct L{
    long long mul, add;
}label[maxn << 2];inline void pushUp(int root)
{
    tree[root] = (tree[root << 1] + tree[root << 1 | 1]) % p;
}
inline void pushDown(int root, int len)
{
    if(label[root].add == 0 && label[root].mul == 1) return;
    else{
        tree[root << 1] = (label[root].mul * tree[root << 1] + label[root].add * (len - (len >> 1))) % p;/***长度划分***/
        tree[root << 1 | 1] = (label[root].mul * tree[root << 1 | 1] + label[root].add * (len >> 1)) % p;
        label[root << 1].add = (label[root].mul * label[root << 1].add + label[root].add) % p;
        label[root << 1 | 1].add = (label[root].mul * label[root << 1 | 1].add + label[root].add) % p;
        label[root << 1].mul = (label[root << 1].mul * label[root].mul) % p;
        label[root << 1 | 1].mul = (label[root << 1 | 1].mul * label[root].mul) % p;
        label[root].add = 0; label[root].mul = 1;
    }
}
void build(int l, int r, int root)
{
    label[root].add = 0; label[root].mul = 1;
    if(l == r){
        scanf("%lld", &tree[root]); return;
    }
    int mid = (l + r) >> 1;
    build(lson); build(rson);
    pushUp(root);
}
void update(int l, int r, int root, int L, int R, int tag, int c)
{
    if(L == l && R == r){
        if(tag == 1){
            tree[root] = tree[root] * c % p;
            label[root].add = label[root].add * c % p;
            label[root].mul = label[root].mul * c % p;
        }else{
            tree[root] = (tree[root] + c * (r - l + 1)) % p;
            label[root].add = (label[root].add + c) % p;
        }
        return;
    }
    pushDown(root, r - l + 1);
    int mid = (l + r) >> 1;
    if(L >= mid + 1) update(rson, L, R, tag, c);
    else if(R <= mid) update(lson, L, R, tag, c);
    else{
        update(lson, L, mid, tag, c); update(rson, mid + 1, R, tag, c);
    }
    pushUp(root);
}
long long query(int l, int r, int root, int L, int R)
{
    if(L == l && R == r){
        return tree[root] % p;
    }
    pushDown(root, r - l + 1);
    int mid = (l + r) >> 1;
    if(L >= mid + 1) return (query(rson, L, R) % p);
    else if(R <= mid) return (query(lson, L, R) % p);
    else{
        return ((query(lson, L, mid) + query(rson, mid + 1, R)) % p);
    }
}
int main()
{
    scanf("%d%d", &n, &p);
    build(1, n, 1);
    scanf("%d", &q);
    for(int cas = 1; cas <= q; cas++){
        int tag, t, g, c;
        scanf("%d", &tag);
        if(tag == 1){
            scanf("%d%d%d", &t, &g, &c);
            update(1, n, 1, t, g, 1, c);
        }
        else if(tag == 2){
            scanf("%d%d%d", &t, &g, &c);
            update(1, n, 1, t, g, 2, c);
        }
        else{
            scanf("%d%d", &t, &g);
            printf("%lld\n", query(1, n, 1, t, g) % p);
        }
    }
    return 0;
}