题解 P3373 【【模板】线段树 2】

Nekroz · 2018-04-29 18:42:52 · 题解

看到dalao们写的基本上都是数组版的线段树，我就写一个链表版的线段树吧（真的比数组简单，我就是看到链表版的线段树才真正会线段树的）。

这道题比一般的线段树也有所不同,多了一个乘法而已。对付的办法也很容易想到，就是多开一个mul的标记，pushdown的时候就是先下传mul再下传add就可以了（乘法比加法优先级要高）。

具体的乘法cover就是把当前节点的sum，add和mul都乘上一个数。 加法cover和原来一样（add加上一个数，sum加上add乘区间长度）。

来一发惊世骇俗的好玩的链表线段树。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector> 
int n, m, p, a[100005];
struct Segtree {  
    int l, r;  
    Segtree *lc, *rc;  
    long long sum, add, mul;  
    Segtree(int l, int r, Segtree *lc, Segtree *rc) //构造函数1，里面封装了build时候要用的pushup()
        : l(l), r(r), lc(lc), rc(rc), sum(lc->sum + rc->sum), add(0), mul(1) {}  
    Segtree(int l, int r, Segtree *lc, Segtree *rc, int sum)  //构造函数2，对子节点使用
        : l(l), r(r), lc(lc), rc(rc), sum(sum), add(0), mul(1) {}  
    void covermul(long long rhs) { //乘法cover
        sum = sum * rhs % p;
        mul = mul * rhs % p;
        add = add * rhs % p;
    }
    void coveradd(long long rhs) {  //加法cover
        add = (add + rhs) % p;  
        sum = (sum + rhs * (r - l + 1)) % p;   
    }  
    void pushup() {  
        sum = (lc->sum + rc->sum) % p;   
    }  
    void pushdown() {  //先cover乘法再cover加法
        lc->covermul(mul); lc->coveradd(add);
        rc->covermul(mul); rc->coveradd(add);
        mul = 1; add = 0;
    }  
    void multiply(int l, int r, long long rhs) {  //乘法updata
        if (l > this->r || r < this->l) return;  
        else if (l <= this->l && this->r <= r) covermul(rhs);  
        else {  
            pushdown();  
            lc->multiply(l, r, rhs);  
            rc->multiply(l, r, rhs);  
            pushup();  
        }  
        return;  
    }  
    void addition(int l, int r, long long rhs) {  //加法updata
        if (l > this->r || r < this->l) return;  
        else if (l <= this->l && this->r <= r) coveradd(rhs);  
        else {  
            pushdown();  
            lc->addition(l, r, rhs);  
            rc->addition(l, r, rhs);  
            pushup();  
        }  
        return;  
    }  
    long long query(int l, int r) {  
        if (l > this->r || r < this->l) return 0;  
        if (l <= this->l && this->r <= r) return sum;  
        pushdown();  
        return (lc->query(l, r) + rc->query(l, r)) % p;  
    }  
    static Segtree *build(int l, int r) {  //有趣的build
        if (l > r) return NULL;  
        else if (l == r) return new Segtree(l, r, NULL, NULL, a[l]);  
        else {  
            int mid = (l + r) >> 1;  
            return new Segtree(l, r, build(l, mid), build(mid + 1, r));  
        }  
    }  
}*root;  
int main() {
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &a[i]);
    root = Segtree::build(1, n); //链表的专属build
    for (int i = 1; i <= m; i++) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            root->multiply(l, r, k);
        }
        else if (opt == 2) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            root->addition(l, r, k);
        }
        else if (opt == 3) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", root->query(l, r));
        }
    } 
    return 0;
}