[BZOJ1798][Ahoi2009]Seq 维护序列seq
试题描述
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为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
数据规模及约定
N ≤ 100000, M ≤ 100000
题解
线段树，打标记恶心一些。因为有乘法分配律，所以在乘法懒标记下传时把加法的懒标记也乘一下，加法懒标记还是该怎么打怎么打。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 100010
#define LL long long
int n, val[maxn];
LL MOD, sumv[maxn<<2], addv[maxn<<2], timv[maxn<<2];
void maintain(int L, int R, int o) {
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
if(L == R) return ;
sumv[o] = ((sumv[lc] * timv[lc] % MOD + addv[lc] * (LL)(M - L + 1) % MOD) % MOD + (sumv[rc] * timv[rc] % MOD + addv[rc] * (LL)(R - M) % MOD) % MOD) % MOD;
return ;
}
void build(int L, int R, int o) {
timv[o] = 1;
if(L == R) sumv[o] = val[L];
else {
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
build(L, M, lc); build(M+1, R, rc);
maintain(L, R, o);
}
return ;
}
void pushdown(int L, int R, int o) {
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
LL len = (LL)(R - L + 1);
if(timv[o] != 1) {
(sumv[o] *= timv[o]) %= MOD;
if(L != R) {
(timv[lc] *= timv[o]) %= MOD; (addv[lc] *= timv[o]) %= MOD;
(timv[rc] *= timv[o]) %= MOD; (addv[rc] *= timv[o]) %= MOD;
}
timv[o] = 1;
}
if(addv[o]) {
sumv[o] += (addv[o] * len % MOD); if(sumv[o] >= MOD) sumv[o] -= MOD;
if(L != R) {
addv[lc] += addv[o]; if(addv[lc] >= MOD) addv[lc] -= MOD;
addv[rc] += addv[o]; if(addv[rc] >= MOD) addv[rc] -= MOD;
}
addv[o] = 0;
}
return ;
}
void update1(int L, int R, int o, int ql, int qr, LL v) {
pushdown(L, R, o);
if(ql <= L && R <= qr) (timv[o] *= v) %= MOD, (addv[o] *= v) %= MOD;
else {
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
if(ql <= M) update1(L, M, lc, ql, qr, v);
if(qr > M) update1(M+1, R, rc, ql, qr, v);
}
maintain(L, R, o);
return ;
}
void update2(int L, int R, int o, int ql, int qr, LL v) {
pushdown(L, R, o);
if(ql <= L && R <= qr){ addv[o] += v; if(addv[o] >= MOD) addv[o] -= MOD; }
else {
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
if(ql <= M) update2(L, M, lc, ql, qr, v);
if(qr > M) update2(M+1, R, rc, ql, qr, v);
}
maintain(L, R, o);
return ;
}
LL query(int L, int R, int o, int ql, int qr) {
pushdown(L, R, o);
if(ql <= L && R <= qr) return (sumv[o] * timv[o] % MOD + addv[o] * (LL)(R - L + 1) % MOD) % MOD;
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
LL ans = 0;
if(ql <= M){ ans += query(L, M, lc, ql, qr); if(ans >= MOD) ans -= MOD; }
if(qr > M){ ans += query(M+1, R, rc, ql, qr); if(ans >= MOD) ans -= MOD; }
return ans;
}
int main() {
n = read(); MOD = read();
for(int i = 1; i <= n; i++) val[i] = read() % MOD;
build(1, n, 1);
int q = read();
while(q--) {
int tp = read(), ql = read(), qr = read(), v;
if(tp == 1) {
v = read() % MOD;
update1(1, n, 1, ql, qr, v);
}
if(tp == 2) {
v = read() % MOD;
update2(1, n, 1, ql, qr, v);
}
if(tp == 3) printf("%lld
", query(1, n, 1, ql, qr));
}
return 0;
}