题解 P2023 【[AHOI2009]维护序列】

· · 题解

模板题双倍经验？？？

这一题和线段树2基本上是一模一样的，但是推荐大家多写几遍，对线段树的使用更加熟练

此外，推荐使用结构体指针构建线段树，因为有些毒瘤题会让你的线段树不是堆式的。。。所以用链式存储就相当有必要了

其余的写在代码里~

#include <cstdio>

#define ll long long

const int MAXN = 1000000 + 10;

struct Node {
    int l, r;//表示结点区间端点
    ll sum, lazyS, lazyM;//区间和，加法标记和乘法标记
    Node *lc, *rc;//该节点的左子节点和右子节点
} tree[MAXN << 2], *root;//数组模拟链表和根节点的位置

int a[MAXN], n, m, cnt;
ll mod;

void build(Node *p, int l, int r) {//建树
    p->l = l;
    p->r = r;
    p->lazyM = 1;//注意，一定要把乘法标记在建树时就赋值为1
    if (l == r){
        p->sum = a[l] % mod;
        return;
    } 
    int mid = (l + r) / 2;
    Node *lson = &tree[++cnt];
    Node *rson = &tree[++cnt];
    p->lc = lson;
    p->rc = rson;
    build(p->lc, l, mid);
    build(p->rc, mid + 1, r);
    p->sum = (p->lc->sum + p->rc->sum) % mod;
}

void pushDown(Node *p) {//标记的下传，这里是先乘后加，记得左右子节点加法和乘法标记都要乘该节点乘法标记
        p->lc->sum = (p->lc->sum * p->lazyM + p->lazyS * (p->lc->r - p->lc->l + 1)) % mod;
        p->rc->sum = (p->rc->sum * p->lazyM + p->lazyS * (p->rc->r - p->rc->l + 1)) % mod;
        p->lc->lazyM = p->lc->lazyM * p->lazyM % mod;
        p->lc->lazyS = (p->lc->lazyS * p->lazyM + p->lazyS) % mod;
        p->rc->lazyM = p->rc->lazyM * p->lazyM % mod;
        p->rc->lazyS = (p->rc->lazyS * p->lazyM + p->lazyS) % mod;
        p->lazyS = 0;
        p->lazyM = 1;
}

void mulChange(Node *p, int l, int r, ll mul) {//区间乘的操作
    if (l <= p->l && r >= p->r) {
        p->sum = p->sum * mul % mod;
        p->lazyS = (p->lazyS * mul) % mod;
        p->lazyM = (p->lazyM * mul) % mod;
        return;
    }
    pushDown(p);
    int mid = (p->l + p->r) / 2;
    if (l <= mid) mulChange(p->lc, l, r, mul);
    if (r > mid) mulChange(p->rc, l, r, mul);
    p->sum = (p->lc->sum + p->rc->sum) % mod;
}

void addChange(Node *p, int l, int r, ll add) {//区间加的操作
    if (l <= p->l && r >= p->r) {
        p->sum = (p->sum + add * (p->r - p->l + 1)) % mod;
        p->lazyS = (p->lazyS + add) % mod;
        return;
    }
    pushDown(p);
    int mid = (p->l + p->r) / 2;
    if (l <= mid) addChange(p->lc, l, r, add);
    if (r > mid) addChange(p->rc, l, r, add);
    p->sum = (p->lc->sum + p->rc->sum) % mod;
}

ll query(Node *p, int l, int r) {//查询区间和
    if (l <= p->l && r >= p->r) return p->sum % mod;
    pushDown(p);
    int mid = (p->l + p->r) / 2;
    ll val = 0;
    if (l <= mid) val = (val + query(p->lc, l, r)) % mod;
    if (r > mid) val = (val + query(p->rc, l, r)) % mod;
    return val % mod;
}

int main() {
    scanf("%d %d", &n, &mod);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    scanf(" %d", &m);
    root = &tree[0];
    build(root, 1, n);
    while (m--) {
        int x, l = 0, r = 0;
        ll k = 0;
        scanf("%d", &x);
        if (x == 1) {
            scanf(" %d %d %lld", &l, &r, &k);
            mulChange(root, l, r, k);
        } else if (x == 2) {
            scanf(" %d %d %lld", &l, &r, &k);
            addChange(root, l, r, k);
            } else {
                scanf("%d %d", &l, &r);
                printf("%lld\n", query(root, l, r) % mod);
            }
    }
    return 0;
}

线段树的惰性标记也是线段树最优美的地方之一，相信码完此题，你一定会对线段树标记的理解上一个档次。