Rockdu's Blog

题目描述

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

输入输出格式

输入格式：

第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输出格式：

对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

输入输出样例

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

2
35
8

说明

【样例说明】

初始时数列为(1,2,3,4,5,6,7)。

经过第1次操作后，数列为(1,10,15,20,25,6,7)。

对第2次操作，和为10+15+20=45，模43的结果是2。

经过第3次操作后，数列为(1,10,24,29,34,15,16}

对第4次操作，和为1+10+24=35，模43的结果是35。

对第5次操作，和为29+34+15+16=94,模43的结果是8。

测试数据规模如下表所示

数据编号 1 2 3 4 5 6 7 8 9 10

N= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

M= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

Source: Ahoi 2009

裸的加乘线段树，用ZKW交了一发，快还是要快，但可能是因为姿势不对，没有显著效果。但是经过两次打板子，zkw的正确率有了很大的提升。下面是代码：

#include<cstdio>
#include<cmath>
#include<cctype>
#define LL long long
using namespace std;
const int maxn = 1.5e5 + 10;
int n, m, bit;
LL data[maxn], size[maxn << 2], tree[maxn << 2], adds[maxn << 2], times[maxn << 2], p;
inline void read(int & x) {
    x = 0;static char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 1) + (x << 3) + c - '0', c = getchar();
}
inline void read(LL & x) {
    x = 0;static char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 1) + (x << 3) + c - '0', c = getchar();
}
void push_up(int rt) {
    tree[rt] = (tree[rt << 1] + tree[rt << 1 | 1]) % p;
}
void add_node(int rt, LL x) {
    (adds[rt] += x) %= p, (tree[rt] += size[rt] * x) %= p;
}
void times_node(int rt, LL x) {
    (times[rt] *= x) %= p, (tree[rt] *= x) %= p, (adds[rt] *= x) %= p;
}
void build(int n) {
    for(bit = 1; bit < n + 3; bit <<= 1);/*n:重点！重点！！！*/
    for(register int i = 1; i <= n; ++i) tree[i + bit] = data[i] % p;
    for(register int i = bit; i <= (bit << 1); ++i) times[i] = 1, size[i] = 1;
    for(register int i = bit - 1; i; --i) 
        size[i] = size[i << 1] + size[i << 1 | 1], times[i] = 1, push_up(i);
}
void push_down(int rt) {
    if(rt ^ 1) push_down(rt >> 1);
    if(times[rt] ^ 1) {
        times_node(rt << 1, times[rt]);
        times_node(rt << 1 | 1, times[rt]);
    }
    if(adds[rt]) {
        add_node(rt << 1, adds[rt]);
        add_node(rt << 1 | 1, adds[rt]);
    }
    times[rt] = 1, adds[rt] = 0;
}
void add(int l, int r, LL dt) {
    push_down(bit + l - 1 >> 1), push_down(bit + r + 1 >> 1);
    for(l = bit + l - 1, r = bit + r + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
        if(~l & 1) add_node(l ^ 1, dt);
        if(r & 1) add_node(r ^ 1, dt);
        push_up(l >> 1), push_up(r >> 1);
    }
    l >>= 1;
    for(; l; l >>= 1) push_up(l);
}
void mtp(int l, int r, LL dt) {
    push_down(bit + l - 1 >> 1), push_down(bit + r + 1 >> 1);
    for(l = bit + l - 1, r = bit + r + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
        if(~l & 1) times_node(l ^ 1, dt);
        if(r & 1) times_node(r ^ 1, dt);
        push_up(l >> 1), push_up(r >> 1);
    }
    l >>= 1;
    for(; l; l >>= 1) push_up(l);
}
LL query(int l, int r) {
    LL ans = 0;
    push_down(l + bit - 1 >> 1), push_down(r + bit + 1 >> 1);
    for(l = l + bit - 1, r = r + bit + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
        if(~l & 1)(ans += tree[l ^ 1]) %= p;
        if(r & 1)(ans += tree[r ^ 1]) %= p;
    }
    return ans;
}
int main() {
    read(n), read(p);
    for(register int i = 1; i <= n; ++i) read(data[i]);
    build(n);
    int o, a, b, c;
    read(m);
    while(m--) {
        read(o);
        if(o == 1) read(a), read(b), read(c), mtp(a, b, c % p);
        else if(o == 2) read(a), read(b), read(c), add(a, b, c % p);
        else read(a), read(b), printf("%lld\n", query(a, b));
    }
    return 0;
}