题解
第一次写这种靠数学分析来找特定规律的题目…
观察区间取模的问题，我们可以发现一个数最多会被取模次。（因为一次取模至少会缩小一半，和启发式合并相似）
所以没什么顾虑，暴力做就是了。操作一用lazytag解决，操作二的话维护区间内最大值及其下标，每次暴力找最大的，如果大于模数就单点修改。操作三就是单点修改。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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
using namespace std;
typedef long long ll;
ll seg[400005]={0},tag[400005]={0},_v,sum[400005],loc[400005];
int _a,_b,m,n,siz;
pair<int,ll> Nulll;
void maintain(int id){
if(seg[id<<1]>seg[id<<1|1])
seg[id]=seg[id<<1],loc[id]=loc[id<<1];
else seg[id]=seg[id<<1|1],loc[id]=loc[id<<1|1];
sum[id]=sum[id<<1]+sum[id<<1|1];
}
void build_seg(){
for(siz=1;siz<n;siz<<=1);
int i;
for(i=siz;i<siz+n;i++)
scanf("%lld",&seg[i]),
tag[i]=0,sum[i]=seg[i],loc[i]=i-siz+1;
//seg最大值，sum和，tag标记，loc最大值位置
for(;i<(siz<<1);i++)
seg[i]=sum[i]=tag[i]=loc[i]=0;
for(i=siz-1;i>=1;i--)
maintain(i);
}
void pushdown(int id,ll len){
if(!tag[id])return ;
seg[id<<1]+=tag[id],seg[id<<1|1]+=tag[id];
tag[id<<1]+=tag[id],tag[id<<1|1]+=tag[id];
sum[id<<1]+=tag[id]*(len>>1),sum[id<<1|1]+=tag[id]*(len>>1);
tag[id]=0;
}
void update(int id,int l,int r){
if(l>_b||r<_a)return ;
if(l>=_a&&r<=_b){
seg[id]+=_v,tag[id]+=_v,sum[id]+=(r-l+1)*_v;
return ;
}
pushdown(id,(ll)(r-l+1));
update(id<<1,l,(l+r)>>1);
update(id<<1|1,(l+r+1)>>1,r);
maintain(id);
}
pair<int,ll> query_p(int id,int l,int r){
//查询区间最大值
pair<int,ll> P,p1;
P.first=P.second=-1;
if(l>_b||r<_a)return Nulll;
if(l>=_a&&r<=_b){
P.first=loc[id],P.second=seg[id];
return P;
}
pushdown(id,(ll)(r-l+1));
p1=query_p(id<<1,l,(l+r)>>1);
if(p1.second>P.second)P=p1;
p1=query_p(id<<1|1,(l+r+1)>>1,r);
if(p1.second>P.second)P=p1;
return P;
}
ll query(int id,int l,int r){
if(l>_b||r<_a)return 0;
if(l>=_a&&r<=_b)return sum[id];
pushdown(id,(ll)(r-l+1));
return query(id<<1,l,(l+r)>>1)+query(id<<1|1,(l+r+1)>>1,r);
}
void init(){
scanf("%d%d",&n,&m);
build_seg();
Nulll.first=-1,Nulll.second=-1;
}
void solve(){
for(int i=0;i<m;i++){
int typ,_c,_d;
scanf("%d",&typ);
if(typ==1)
scanf("%d%d",&_a,&_b),
printf("%lld\n",query(1,1,siz));
else if(typ==2){
scanf("%d%d%lld",&_c,&_d,&_v);
ll Mod=_v;
pair<int,ll> P;
for(;;){
_a=_c,_b=_d;
P=query_p(1,1,siz);
if(P.second<Mod)break;
_a=_b=P.first,_v=P.second%Mod-P.second;
update(1,1,siz);
}
//for(int i=0;i<5;i++)
// _a=_b=i+1,
// printf("%lld ",query(1,1,siz));
//printf("\n");
}else{
scanf("%d%lld",&_a,&_v),
_b=_a,_v-=query(1,1,siz),update(1,1,siz);
}
}
}
int main(){
init();
solve();
return 0;
}