感谢勤奋的srf大蒟蒻！！
线段树1
#include <bits/stdc++.h>
#define maxn 100000
#define LL long long
using namespace std;
inline LL read(){
LL x = 0,f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}
while (c <='9' && c >='0') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
LL n,m,a[maxn+5],f[maxn*8+40],tag[maxn*8+40];
void Build_tree(int note,int x,int y){
if (x == y) f[note] = a[x],tag[note] = 0;
else{
int mid = (x + y) >> 1;
Build_tree(note * 2, x , mid);
Build_tree(note * 2 + 1, mid + 1, y);
f[note] = f[note * 2] + f[note * 2 + 1];
tag[note] = 0;
}
}
void downtag(int note,int x,int y){
if (tag[note] == (LL)0) return;
int mid = (x + y) >> 1;
f[note * 2] = f[note * 2] + tag[note] * (mid - x + 1);
f[note * 2 + 1] = f[note * 2 + 1] + tag[note] * (y - mid);
tag[note * 2] = tag[note * 2] + tag[note];
tag[note * 2 + 1] = tag[note * 2 + 1] + tag[note];
tag[note] = (LL)0;
}
void Add_tree(int note,int x,int y,int ax,int ay,LL k){
if (ax <= x && ay >= y) f[note] = f[note] + (y - x + 1) * k,tag[note] = tag[note] + k;
else{
downtag(note,x,y);
int mid = (x + y) >> 1;
if ( ax <= mid ) Add_tree(note * 2 , x , mid , ax , ay , k);
if ( ay > mid ) Add_tree(note * 2 + 1, mid + 1 , y , ax , ay , k);
f[note] = f[note * 2] + f[note * 2 + 1];
}
}
LL Ask_tree(int note,int x,int y,int ax,int ay){
if (ax <= x && ay >= y) return f[note];
else{
downtag(note,x,y);
int mid = (x + y) >> 1;
LL Ans = 0; // **数据范围**
if ( ax <= mid ) Ans = Ans + Ask_tree(note * 2 , x , mid , ax , ay);
if ( ay > mid ) Ans = Ans + Ask_tree(note * 2 + 1, mid + 1 , y , ax , ay);
return Ans;
}
}
int main(){
n = read(); m = read();
for (int i = 1; i <= n; ++i) a[i] = read();
Build_tree(1,1,n);
while(m--){
int opt = read(),x = read(),y = read();
if (opt == 1){
Add_tree( 1,1,n,x,y,read() );
}
else{
printf("%lld
",Ask_tree( 1,1,n,x,y ) );
}
}
return 0;
}
线段树2
#include <bits/stdc++.h>
#define maxn 100000
#define LL long long
using namespace std;
inline LL read(){
LL x = 0,f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}
while (c <='9' && c >='0') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
LL n,m,a[maxn+5],f[maxn*8+40],taga[maxn*8+40],tagb[maxn*8+40],p;
void Build_tree(int note,int x,int y){
if (x == y) f[note] = a[x],taga[note] = 1,tagb[note] = 0;
else{
int mid = (x + y) >> 1;
Build_tree(note * 2, x , mid);
Build_tree(note * 2 + 1, mid + 1, y);
f[note] = ( f[note * 2] + f[note * 2 + 1] ) % p;
taga[note] = 1;
tagb[note] = 0;
return;
}
}
void downtag(int note,int x,int y){
if (taga[note] != 1){//*
taga[note * 2] = ( taga[note * 2] * taga[note] ) % p;
tagb[note * 2] = ( tagb[note * 2] * taga[note] ) % p;
f[note * 2] = ( f[note * 2] * taga[note] ) % p;
taga[note * 2 + 1] = ( taga[note * 2 + 1] * taga[note] ) % p;
tagb[note * 2 + 1] = ( tagb[note * 2 + 1] * taga[note] ) % p;
f[note * 2 + 1] = ( f[note * 2 + 1] * taga[note] ) % p;
taga[note] = 1;
}
if (tagb[note]){//+
int mid = (x + y) >> 1;
tagb[note * 2] = ( tagb[note * 2] + tagb[note] ) % p;
f[note * 2] = ( f[note * 2] + (mid - x + 1) * tagb[note] ) % p;
tagb[note * 2 + 1] = ( tagb[note * 2 + 1] + tagb[note] ) % p;
f[note * 2 + 1] = ( f[note * 2 + 1] + (y - mid) * tagb[note] ) % p;
tagb[note] = 0;
}
return;
}
void Add1_tree(int note,int x,int y,int ax,int ay,LL k){ // *
if (ax <= x && ay >= y) {
f[note] = (f[note] * k ) % p;
taga[note] = (taga[note] * k) % p,tagb[note] = (tagb[note] * k) % p;
}
else {
downtag(note,x,y);
int mid = (x + y) >> 1;
if (ax <= mid)
Add1_tree( note * 2 , x , mid , ax , ay , k);
if (ay > mid)
Add1_tree( note * 2 + 1 , mid + 1 , y , ax , ay , k);
f[note] = ( f[note * 2] + f[note * 2 + 1] ) % p;
}
}
void Add2_tree(int note,int x,int y,int ax,int ay,LL k){ // +
if (ax <= x && ay >= y)
f[note] = (f[note] + ( y - x + 1 ) * k ) % p,tagb[note] = (tagb[note] + k) % p;
else {
downtag(note,x,y);
int mid = (x + y) >> 1;
if (ax <= mid)
Add2_tree( note * 2 , x , mid , ax , ay , k);
if (ay > mid)
Add2_tree( note * 2 + 1 , mid + 1 , y , ax , ay , k);
f[note] = ( f[note * 2] + f[note * 2 + 1] ) % p;
}
}
LL Ask_tree(int note,int x,int y,int ax,int ay){
if (ax <= x && ay >= y) return f[note];
else{
downtag(note,x,y);
int mid = (x + y) >> 1;
LL Ans = 0;
if ( ax <= mid )
Ans = Ans + Ask_tree(note * 2 , x , mid , ax , ay),Ans = Ans % p;
if ( ay > mid )
Ans = Ans + Ask_tree(note * 2 + 1, mid + 1 , y , ax , ay),Ans = Ans % p;
return Ans;
}
}
int main(){
n = read(); m = read(); p = read();
for (int i = 1; i <= n; ++i) a[i] = read() % p;
Build_tree(1,1,n);
while(m--){
int opt = read(),x = read(),y = read();
if (opt == 1){
Add1_tree( 1,1,n,x,y,read() ); // *
}
else if (opt == 2){
Add2_tree( 1,1,n,x,y,read() ); // +
}
else{
printf("%lld
",Ask_tree( 1,1,n,x,y) );
}
}
return 0;
}