rockdu
题目描述
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为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，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
输入输出样例
说明
【样例说明】
初始时数列为(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;
}
没有帐号? 立即注册