Rockdu's Blog

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.将某区间每一个数乘上x

3.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数乘上k

操作2： 格式：2 x y k 含义：将区间[x,y]内每个数加上k

操作3： 格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果

输出格式：

输出包含若干行整数，即为所有操作3的结果。

输入输出样例

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

17
2

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

（数据已经过加强^_^）

样例说明：

故输出应为17、2（40 mod 38=2）

今天先用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;
}