2024/3/19

世界上最痛苦的事就是改线段树

https://www.luogu.com.cn/problem/P3373

直接贴代码,无需多盐

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll N = 1e5+5;
ll tree[N<<2];
ll a[N];
ll add[N<<2], mul[N<<2];
ll mod;

ll ls(ll p){
	return p*2;
}
ll rs(ll p){
	return p * 2 + 1;
}

void push_up(ll p){
	tree[p] = (tree[ls(p)] + tree[rs(p)]) % mod;
}
void push_down(ll p, ll pl, ll pr){
	ll mid = (pl+pr)/2;
	tree[ls(p)] = (mul[p] * tree[ls(p)] + add[p] * (mid - pl + 1)) % mod;
	tree[rs(p)] = (mul[p] * tree[rs(p)] + add[p] * (pr - mid)) % mod;
	
	mul[ls(p)] = (mul[ls(p)] * mul[p]) % mod;
	mul[rs(p)] = (mul[rs(p)] * mul[p]) % mod;
	
	add[ls(p)] = (add[ls(p)] * mul[p] + add[p]) % mod;
	add[rs(p)] = (add[rs(p)] * mul[p] + add[p]) % mod;
	
	mul[p] = 1;
	add[p] = 0;
}

void ChangeAdd(ll p, ll pl, ll pr, ll l, ll r, ll k){
	if(l <= pl && r >= pr){
		add[p] = (add[p] + k) % mod;
		tree[p] = (tree[p] + k * (pr - pl + 1)) % mod;
		return;
	}
	push_down(p, pl, pr);
	ll mid = (pl + pr)/2;
	if(l <= mid) ChangeAdd(ls(p), pl, mid, l, r, k);
	if(r > mid) ChangeAdd(rs(p), mid + 1, pr, l, r, k);
	push_up(p);
	return;
}
void ChangeMul(ll p, ll pl, ll pr, ll l, ll r, ll k){
	if(l <= pl && r >= pr){
		add[p] = (add[p] * k) % mod;
		mul[p] = (mul[p] * k) % mod;
		tree[p] = (tree[p] * k) % mod;
		return;
	}
	push_down(p, pl, pr);
	ll mid = (pl + pr)/2;
	if(l <= mid) ChangeMul(ls(p), pl, mid, l, r, k);
	if(r > mid) ChangeMul(rs(p), mid + 1, pr, l, r, k);
	push_up(p);
	return;
}

void build(ll p, ll pl, ll pr){
	add[p] = 0, mul[p] = 1;
	if(pl == pr){
		 tree[p] = a[pl] % mod;
		 return;
	}
	ll mid = (pl + pr)/2;
	build(ls(p), pl, mid);
	build(rs(p), mid + 1, pr);
	push_up(p);
}

ll query(ll p, ll pl, ll pr, ll l, ll r){
	if(l <= pl && r >= pr) return tree[p];
	push_down(p, pl, pr);
	ll val = 0;
	ll mid = (pl + pr)/2;
	if(l <= mid) val = (val + query(ls(p), pl, mid, l, r)) % mod;
	if(r > mid) val = (val + query(rs(p), mid + 1, pr, l, r)) % mod;
	return val;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	ll n,q;
	cin>>n>>q>>mod;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
	}
	build(1, 1, n);
	while(q--){
		int jud;
		cin>>jud;
		if(jud == 3){
			ll l,r;
			cin>>l>>r;
			 cout<<query(1, 1, n, l, r)<<endl;
		}else if(jud == 2){
			ll l,r,k;
			cin>>l>>r>>k;
			ChangeAdd(1, 1, n, l, r, k);
		}else{
			ll l,r,k;
			cin>>l>>r>>k;
			ChangeMul(1, 1, n, l, r, k);
		}
	}
	return 0;
}