【线段树】Seq 维护序列seq

线段树

传送门：BZOJ1798

思路：线段树裸题，加法乘法两个标记，乘法时加法也要标记。

注意：乘法运算时可能爆int。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define LL long long
LL n,m,mo,op,x,y,z,a[120000],sum[300000],cov1[300000],cov2[300000];
void pushdown(int cur,int l,int r,int mid){
	sum[cur<<1]=(LL)(sum[cur<<1]*cov2[cur]+cov1[cur]*(mid-l+1))%mo;
	sum[cur<<1|1]=(LL)(sum[cur<<1|1]*cov2[cur]+cov1[cur]*(r-mid))%mo;
	cov1[cur<<1]=(LL)(cov1[cur<<1]*cov2[cur]+cov1[cur])%mo; cov1[cur<<1|1]=(LL)(cov1[cur<<1|1]*cov2[cur]+cov1[cur])%mo;
	cov2[cur<<1]=(LL)cov2[cur<<1]*cov2[cur]%mo; cov2[cur<<1|1]=(LL)cov2[cur<<1|1]*cov2[cur]%mo;
	cov1[cur]=0; cov2[cur]=1;
}
void update(int cur){sum[cur]=(LL)(sum[cur<<1]+sum[cur<<1|1])%mo;}
void add(int cur,int l,int r,int L,int R,int c){
	if (L<=l && R>=r){sum[cur]=(LL)(sum[cur]+c*(r-l+1))%mo; cov1[cur]=(LL)(cov1[cur]+c)%mo; return;}
	int mid=(l+r)>>1;
	pushdown(cur,l,r,mid);
	if (L<=mid) add(cur<<1,l,mid,L,R,c);
	if (R>mid) add(cur<<1|1,mid+1,r,L,R,c);
	update(cur);
}
void mul(int cur,int l,int r,int L,int R,int c){
	if (L<=l && R>=r){sum[cur]=(LL)(sum[cur]*c)%mo; cov1[cur]=(LL)cov1[cur]*c%mo; cov2[cur]=(LL)cov2[cur]*c%mo; return;}
	int mid=(l+r)>>1;
	pushdown(cur,l,r,mid);
	if (L<=mid) mul(cur<<1,l,mid,L,R,c);
	if (R>mid) mul(cur<<1|1,mid+1,r,L,R,c);
	update(cur);
}
LL query(int cur,int l,int r,int L,int R){
	if (L<=l && R>=r) return sum[cur]%mo;
	LL mid=(l+r)>>1,tmp=0;
	pushdown(cur,l,r,mid);
	if (L<=mid) tmp=(LL)(tmp+query(cur<<1,l,mid,L,R))%mo;
	if (R>mid) tmp=(LL)(tmp+query(cur<<1|1,mid+1,r,L,R))%mo;
	return tmp%mo;
}
int main(){
	memset(cov2,1,sizeof cov2);
	
	scanf("%lld%lld",&n,&mo);
	for (int i=1;i<=n;i++){scanf("%lld",&a[i]); add(1,1,n,i,i,a[i]);}
	
	scanf("%lld",&m);
	for (int i=1;i<=m;i++){
		scanf("%lld",&op);
		if (op==1){scanf("%lld%lld%lld",&x,&y,&z); mul(1,1,n,x,y,z);}
		if (op==2){scanf("%lld%lld%lld",&x,&y,&z); add(1,1,n,x,y,z);}
		if (op==3){scanf("%lld%lld",&x,&y); printf("%lld\n",query(1,1,n,x,y));}
	}
	
	return 0;
}