1798 - [Ahoi2009]Seq 维护序列seq

线段树sb题(题解bymod998244353)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005;
int mod,n,m,wt[MAXN];
struct tr {
	int l,r,siz;
	ll sum,lt,cf;
} tr[MAXN<<2];
void build(int num,int l,int r) {
	tr[num].l=l;
	tr[num].r=r;
	tr[num].siz=r-l+1;
	tr[num].lt=0;
	tr[num].cf=1;
	if(l==r) {
		tr[num].sum=wt[l];
		return ;
	}
	const int mid=l+r>>1,ls=num<<1,rs=ls|1;
	build(ls,l,mid),build(rs,mid+1,r);
	tr[num].sum=(tr[ls].sum+tr[rs].sum)%mod;
}
void push_down(int num) {
	const int ls=num<<1,rs=ls|1;
	tr[ls].cf=tr[ls].cf*tr[num].cf%mod;
	tr[rs].cf=tr[rs].cf*tr[num].cf%mod;
	tr[ls].lt=(tr[ls].lt*tr[num].cf+tr[num].lt)%mod;
	tr[rs].lt=(tr[rs].lt*tr[num].cf+tr[num].lt)%mod;
	tr[ls].sum=(tr[ls].sum*tr[num].cf+tr[num].lt*tr[ls].siz)%mod;
	tr[rs].sum=(tr[rs].sum*tr[num].cf+tr[num].lt*tr[rs].siz)%mod;
	tr[num].cf=1;
	tr[num].lt=0;
}
void update1(int num,int l,int r,ll val) {
	if(l<=tr[num].l&&tr[num].r<=r) {
		tr[num].sum=tr[num].sum*val%mod;
		tr[num].cf=tr[num].cf*val%mod;
		tr[num].lt=tr[num].lt*val%mod;
		return;
	}
	push_down(num);
	const int ls=num<<1,rs=ls|1;
	if(l<=tr[ls].r)update1(ls,l,r,val);
	if(tr[rs].l<=r)update1(rs,l,r,val);
	tr[num].sum=(tr[ls].sum+tr[rs].sum)%mod;
}
void update2(int num,int l,int r,ll val) {
	if(l<=tr[num].l&&tr[num].r<=r) {
		tr[num].sum=(tr[num].sum+tr[num].siz*val)%mod;
		tr[num].lt=(tr[num].lt+val)%mod;
		return;
	}
	push_down(num);
	const int ls=num<<1,rs=ls|1;
	if(l<=tr[ls].r)update2(ls,l,r,val);
	if(tr[rs].l<=r)update2(rs,l,r,val);
	tr[num].sum=(tr[ls].sum+tr[rs].sum)%mod;
}
int query(int num,int l,int r) {
	if(l<=tr[num].l&&tr[num].r<=r)
		return tr[num].sum;
	push_down(num);
	const int ls=num<<1,rs=ls|1;
	ll s=0;
	if(l<=tr[ls].r)s=(s+query(ls,l,r))%mod;
	if(tr[rs].l<=r)s=(s+query(rs,l,r))%mod;
	return s;
}
int main() {
	scanf("%d%d",&n,&mod);
	for(int i=1; i<=n; ++i)scanf("%d",&wt[i]);
	scanf("%d",&m),build(1,1,n);
	for(int i=1,op,x,y,k; i<=m; ++i) {
		scanf("%d%d%d",&op,&x,&y);
		if(op==1) {
			scanf("%d",&k);
			update1(1,x,y,k);
		} else if(op==2) {
			scanf("%d",&k);
			update2(1,x,y,k);
		} else if(op==3) {
			printf("%d\n",query(1,x,y));
		}
	}
	return 0;
}

by 郭沣