传送门
解题思路
直接用线段树维护取模是不好维护的。
而且我们发现一个数x最多取模logx次（每次大小减半），所以可以暴力取模。
维护的信息除了区间和，还有区间最大值，因为当区间最大值<模数时，此操作是无效的。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int n,m;
struct node{
long long max,sum;
}d[maxn*4];
inline void pushup(int id){
d[id].max=max(d[id*2].max,d[id*2+1].max);
d[id].sum=d[id*2].sum+d[id*2+1].sum;
}
void update(int id,int l,int r,int x,int v){
if(l==r){
d[id].sum=d[id].max=v;
return;
}
int mid=(l+r)/2;
if(x<=mid) update(id*2,l,mid,x,v);
else update(id*2+1,mid+1,r,x,v);
pushup(id);
}
long long query(int id,int l,int r,int x,int y){
if(x<=l&&r<=y){
return d[id].sum;
}
int mid=(l+r)/2;
long long res=0;
if(x<=mid) res+=query(id*2,l,mid,x,y);
if(y>mid) res+=query(id*2+1,mid+1,r,x,y);
return res;
}
void update_mod(int id,int l,int r,int x,int y,long long mod){
if(d[id].max<mod) return;
if(l==r){
d[id].sum%=mod;
d[id].max%=mod;
return;
}
int mid=(l+r)/2;
if(x<=mid&&d[id*2].max>=mod) update_mod(id*2,l,mid,x,y,mod);
if(y>mid&&d[id*2+1].max>=mod) update_mod(id*2+1,mid+1,r,x,y,mod);
pushup(id);
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
int a;
cin>>a;
update(1,1,n,i,a);
}
for(int i=1;i<=m;i++){
int tp;
cin>>tp;
if(tp==1){
int l,r;
cin>>l>>r;
cout<<query(1,1,n,l,r)<<endl;
continue;
}
if(tp==2){
int l,r;
long long x;
cin>>l>>r>>x;
update_mod(1,1,n,l,r,x);
continue;
}
if(tp==3){
int k,x;
cin>>k>>x;
update(1,1,n,k,x);
continue;
}
}
return 0;
}