https://www.luogu.org/problemnew/show/P2023
线段树双懒标记下放
#include <bits/stdc++.h> using namespace std;
const int N = 1e5 + ; #define LL long long
#define lson jd << 1
#define rson jd << 1 | 1 LL w[N << ], size[N << ], fadd[N << ], fmul[N << ], Answer;
int n, Ty, Mod; #define gc getchar() inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
} void Build_tree(int l, int r, int jd) {
size[jd] = (r - l + ); fmul[jd] = ;
if(l == r) {w[jd] = read(); w[jd] %= Mod; return ;}
int mid = (l + r) >> ;
Build_tree(l, mid, lson);
Build_tree(mid + , r, rson);
w[jd] = (w[lson] + w[rson]) % Mod;
} void Down(int jd) {
if(!fadd[jd] && fmul[jd] == ) return ;
w[lson] = w[lson] * fmul[jd] % Mod;
w[rson] = w[rson] * fmul[jd] % Mod;
w[lson] = w[lson] + fadd[jd] * size[lson] % Mod;
w[rson] = w[rson] + fadd[jd] * size[rson] % Mod;
fadd[lson] = (fadd[lson] * fmul[jd] + fadd[jd]) % Mod;
fadd[rson] = (fadd[rson] * fmul[jd] + fadd[jd]) % Mod;
fmul[lson] = fmul[lson] * fmul[jd] % Mod;
fmul[rson] = fmul[rson] * fmul[jd] % Mod;
fadd[jd] = ;
fmul[jd] = ;
} void Sec_G_mul(int l, int r, int jd, int x, int y, int imp) {
if(x <= l && r <= y) {
w[jd] = (w[jd] * imp) % Mod;
fmul[jd] = (fmul[jd] * imp) % Mod;
fadd[jd] = (fadd[jd] * imp) % Mod;
return ;
}
Down(jd);
int mid = (l + r) >> ;
if(x <= mid) Sec_G_mul(l, mid, lson, x, y, imp);
if(y > mid) Sec_G_mul(mid + , r, rson, x, y, imp);
w[jd] = (w[lson] + w[rson]) % Mod;
} void Sec_G_add(int l, int r, int jd, int x, int y, int k) {
if(x <= l && r <= y) {
w[jd] = (w[jd] + size[jd] * k) % Mod;
fadd[jd] = (fadd[jd] + k) % Mod;
return ;
}
Down(jd);
int mid = (l + r) >> ;
if(x <= mid) Sec_G_add(l, mid, lson, x, y, k);
if(y > mid) Sec_G_add(mid + , r, rson, x, y, k);
w[jd] = (w[lson] + w[rson]) % Mod;
} void Sec_A(int l, int r, int jd, int x, int y) {
if(x <= l && r <= y) {
Answer += w[jd];
if(Answer >= Mod) Answer %= Mod;
return ;
}
Down(jd);
int mid = (l + r) >> ;
if(x <= mid) Sec_A(l, mid, lson, x, y);
if(y > mid) Sec_A(mid + , r, rson, x, y);
} int main() {
n = read(); Mod = read();
Build_tree(, n, );
Ty = read();
while(Ty --) {
int opt = read();
if(opt == ) {
int x = read(), y = read(), k = read(); k %= Mod;
Sec_G_mul(, n, , x, y, k);
} else if(opt == ) {
int x = read(), y = read(), k = read(); k %= Mod;
Sec_G_add(, n, , x, y, k);
} else {
int x = read(), y = read();
Answer = ;
Sec_A(, n, , x, y);
cout << Answer << endl;
}
}
return ;
}
/*
5 38
5 4 2 3
1 4 1
2 5
2 4 2
3 5 5
1 4
*/