Luogu P3373: Segment tree

题目

Click me to find a topic
The main idea is to have a sequence of numbers,有三种操作,One is to add a number to each number in an interval;One is to multiply each number in an interval by a number;The last one is a query.

思路

This is actually a template question,只不过相比The most basic line segment treeThere is one more mark,Then the main problem we have to solve is how to maintain these two kinds of marks.
There are two main problems during maintenance：

1. How to hit when marking
2. How to drop when the mark is dropped

The contradiction is actually there,I am adding a kind of markup,Need to process another tag;如果需要,What to do to make the correctness of this tree unchanged.
We can solve it by artificially setting priorities：
对于一个节点k, f[k]represents the interval sum, madd[k]Represents an addition mark, mmul[k]Represents the multiplication flag

1. Consider addition first
   则对于节点k的子节点来说, Specifies when updating child nodes,First process the addition token passed from the parent node,Then process the multiplication mark passed down from the parent node,i.e. add and multiply.Then we are adding numbers to an intervalz的时候,The properties of the four arithmetic operations learned in elementary school,我们可以得到madd[k] += z/mmul[k].Obviously, after this processing, the value of the child node can be updated correctly according to the specified priority.
2. Consider multiplication first
   对于节点k的子节点来说, Specifies when updating child nodes,The multiplication mark passed down from the parent node is processed first,Then process the addition mark passed down from the parent node,That is, multiply and then add.So we are multiplying a number by a rangez的时候,according to the distributive law of multiplicationmadd[k] *= z.

for the above two approaches,The first approach is due to the existence of integer division,Therefore, there may be problems with accuracy;The second approach may cause overflow though,But the question states that the answer needs to be modulo,So the overflow problem is also solved,Then we choose the second option.

代码

#include <cstdio>

using namespace std;
#define lc k<<1
#define rc k<<1|1
typedef long long ll;

const int maxn = 1e5+5;
ll a[maxn], f[4*maxn], madd[4*maxn], mmul[4*maxn];
int n, m, p;

inline void buildTree(int k, int l, int r) {
     // k l r are the subscripts of the current processing node, respectively 当前区间的左端点 当前区间的右端点 下同
    madd[k] = 0; mmul[k] = 1;
    if(l == r) {
     f[k] = a[l]; return; }
    int m = (l+r) >> 1;
    buildTree(lc, l, m);
    buildTree(rc, m+1, r);
    f[k] = (f[lc] + f[rc])%p;
}

inline void pushdown(int k, int l, int r) {
    
    int m = (l+r) >> 1;
    f[lc] = (f[lc]*mmul[k] + madd[k]*(m-l+1))%p;
    f[rc] = (f[rc]*mmul[k] + madd[k]*(r-m))%p;

    mmul[lc] = (mmul[lc]*mmul[k]) % p;
    mmul[rc] = (mmul[rc]*mmul[k]) % p;

    madd[lc] = (madd[lc]*mmul[k] + madd[k]) % p;
    madd[rc] = (madd[rc]*mmul[k] + madd[k]) % p;

    mmul[k] = 1;
    madd[k] = 0;
}

inline void add(int k, int l, int r, int x, int y, ll z) {
    
    if(l == x && r == y) {
    
        madd[k] = (madd[k] + z) % p;
        f[k] = (f[k] + z*(r-l+1)) % p;
        return;
    }
    pushdown(k, l, r);

    int m = (l+r) >> 1;
    if(y <= m) {
    
        add(lc, l, m, x, y, z);
    } else if(x > m) {
    
        add(rc, m+1, r, x, y, z);
    } else {
    
        add(lc, l, m, x, m, z);
        add(rc, m+1, r, m+1, y, z);
    }
    f[k] = (f[lc] + f[rc]) % p;
}

inline void mul(int k, int l, int r, int x, int y, ll z) {
    
    if(l == x && r == y) {
    
        madd[k] = (madd[k]*z) % p;
        mmul[k] = (mmul[k]*z) % p;
        f[k] = (f[k] * z) % p;
        return;
    }
    pushdown(k, l, r);
    int m = (l+r) >> 1;
    if(y <= m) {
    
        mul(lc, l, m, x, y, z);
    } else if(x > m) {
    
        mul(rc, m+1, r, x, y, z);
    } else {
    
        mul(lc, l, m, x, m, z);
        mul(rc, m+1, r, m+1, y, z);
    }
    f[k] = (f[lc] + f[rc]) % p;
}

inline ll query(int k, int l, int r, int x, int y) {
    
    if(l == x && r == y) {
    
        return f[k];
    }
    pushdown(k, l, r);
    int m = (l+r) >> 1;
    if(y <= m) {
    
        return query(lc, l, m, x, y);
    } else if(x > m) {
    
        return query(rc, m+1, r, x, y);
    } else {
    
        return query(lc, l, m, x, m) + query(rc, m+1, r, m+1, y);
    }
}

int main(void)
{
    
    // freopen("in.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 1; i <= n; ++i) {
    
        scanf("%lld", &a[i]);
    }
    buildTree(1, 1, n);
    int x, y, op;
    ll k;
    while(m--) {
    
        scanf("%d", &op);
        if(op == 1) {
    
            scanf("%d%d%lld", &x, &y, &k);
            mul(1, 1, n, x, y, k);
        } else if(op == 2) {
    
            scanf("%d%d%lld", &x, &y, &k);
            add(1, 1, n, x, y, k);
        } else {
    
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, 1, n, x, y)%p);
        }
    }
    return 0;
}