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

Rockdu · 2017-09-09 17:30:04 · 题解

今天先用cnt分配标号写线段树做了这道题，T成狗，一脸懵逼。于是换成rt*2,rt*2+1又T成狗，70分

好，那么究竟怎么才能不T？很气啊，然后删了几个取模居然80分了。于是豁然开朗，只在最后取模，AC。

这道题告诉我们取模不要乱取的重要性。

#include<cstdio>
using namespace std;
const int maxn = 100005;
int p;
int data[maxn];
#define gadd(a, b) ((((a)%p) + ((b)%p))%p)
#define gtimes(a, b) ((((a)%p) * ((b)%p))%p)
inline int read() {
    int ret = 0, f = 1;
    char c = getchar();
    while(c > '9' || c < '0') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c <= '9' && c >= '0') ret = ret * 10 + c - '0', c = getchar();
    return ret * f;
}
namespace Segtree{
    struct node {
        long long lazy[2], sum;
        int l, r;
    }tree[maxn << 2];
    void push_up(int rt) {
        tree[rt].sum = (tree[rt << 1].sum + tree[rt << 1 | 1].sum) % p;
    }
    void push_down(int rt) {
        if(tree[rt].lazy[0] == 0 && tree[rt].lazy[1] == 1) return;
        (tree[rt << 1].lazy[0] *= tree[rt].lazy[1]) %= p;
        (tree[rt << 1].lazy[0] += tree[rt].lazy[0]) %= p;
        (tree[rt << 1 | 1].lazy[0] *= tree[rt].lazy[1]) %= p;
        (tree[rt << 1 | 1].lazy[0] += tree[rt].lazy[0]) %= p;
        (tree[rt << 1].lazy[1] *= tree[rt].lazy[1]) %= p;
        (tree[rt << 1 | 1].lazy[1] *= tree[rt].lazy[1]) %= p;
        (tree[rt << 1].sum *= tree[rt].lazy[1]) %= p;
        (tree[rt << 1].sum += gtimes((tree[rt << 1].r - tree[rt << 1].l + 1), tree[rt].lazy[0])) %= p;
        (tree[rt << 1 | 1].sum *= tree[rt].lazy[1]) %= p;
        (tree[rt << 1 | 1].sum += gtimes((tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1), tree[rt].lazy[0])) %= p;
        tree[rt].lazy[0] = 0;
        tree[rt].lazy[1] = 1;
    }
    void build(int rt, int l, int r) {
        tree[rt].l = l, tree[rt].r = r;
        tree[rt].lazy[1] = 1;
        if(l == r) {
            tree[rt].sum = data[l] % p;
            return;
        }
        int mid = (l + r) >> 1;
        build(rt << 1, l, mid);
        build(rt << 1 | 1, mid + 1, r);
        push_up(rt);
    }
    long long query(int rt, int l, int r) {
        int tl = tree[rt].l, tr = tree[rt].r;
        if(l == tl && r == tr) return tree[rt].sum;
        push_down(rt);
        int mid = (tl + tr) >> 1;
        if(r <= mid) return query(rt << 1, l, r) % p;
        else if(l > mid) return query(rt << 1 | 1, l, r) % p;
        else return gadd(query(rt << 1, l, mid), query(rt << 1 | 1, mid + 1, r));
    }
    void add(int rt, int l, int r, int dt) {
        int tl = tree[rt].l, tr = tree[rt].r;
        if(l == tl && r == tr) {
            (tree[rt].sum += (tr - tl + 1) * (dt % p)) %= p;
            (tree[rt].lazy[0] += dt) %= p;
            return;
        }
        push_down(rt);
        int mid = (tl + tr) >> 1;
        if(r <= mid) add(rt << 1, l, r, dt);
        else if(l > mid) add(rt << 1 | 1, l, r, dt);
        else add(rt << 1, l, mid, dt), add(rt << 1 | 1, mid + 1, r, dt)    ;
        push_up(rt);
    }
    void times(int rt, int l, int r, int dt) {
        int tl = tree[rt].l, tr = tree[rt].r;
        if(l == tl && r == tr) {
            (tree[rt].sum *= dt) %= p;
            (tree[rt].lazy[1] *= dt) %= p;
            (tree[rt].lazy[0] *= dt) %= p;
            return;
        }
        push_down(rt);
        int mid = (tl + tr) >> 1;
        if(r <= mid) times(rt << 1, l, r, dt);
        else if(l > mid) times(rt << 1 | 1, l, r, dt);
        else times(rt << 1, l, mid, dt), times(rt << 1 | 1, mid + 1, r, dt)    ;
        push_up(rt);
    }
}
int main() {
    int n, m;
    scanf("%d%d%d", &n, &m, &p);
    for(register int i = 1; i <= n; ++i) data[i] = read();
    Segtree::tree[0].lazy[1] = 1;
    Segtree::build(1, 1, n);
    int opt, a, b, c;
    for(register int i = 1; i <= m; ++i) {
        opt = read();
        if(opt != 3) {
            a = read(), b = read(), c = read();
            if(opt == 2)    Segtree::add(1, a, b, c);
            else Segtree::times(1, a, b, c);
        }else {
            a = read(), b = read();
            printf("%d\n", Segtree::query(1, a, b));
        }
    }    
     return 0;
}