【原题题面】传送门
【大致题意】
- 给定一个长度为n的非负整数序列a，你需要支持以下操作：
- 1：给定l,r，输出a[l]+a[l+1]+…+a[r]。
- 2：给定l,r,x，将a[l],a[l+1],…,a[r]对x取模。
- 3：给定k,y，将a[k]修改为y。
【数据范围】
n,m<=100000，a[i],x,y<=10。
【题解大意】
维护最大值和区间和，然后通过最大值有没有超过x来判断需不需要取模操作。
【code】
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rep(k,i,j) for(int k = i;k <= j; ++k)
#define FOR(k,i,j) for(int k = i;k >= j; --k)
inline int read(){
int x=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-''; ch=getchar();}
return x*f;
}
#define ls rt<<1
#define rs rt<<1|1
const int mxn = 1e5+;
struct T {ll s;int mx;} tr[mxn<<];
int a[mxn],n,q;
inline void build(int rt,int l,int r){
if(l==r){
tr[rt].s = tr[rt].mx = a[l];
return;
}
int m = l+r >>;
build(ls,l,m),build(rs,m+,r);
tr[rt].s = tr[ls].s + tr[rs].s;
tr[rt].mx = max(tr[ls].mx,tr[rs].mx);
}
inline void update(int rt,int l,int r,int lp,int rp,int x){
if(tr[rt].mx < x) return;
if(lp==rp){
tr[rt].s = tr[rt].mx %= x;
return;
}
int m = lp+rp >>;
if(l<=m) update(ls,l,r,lp,m,x);
if(r>m) update(rs,l,r,m+,rp,x);
tr[rt].s = tr[ls].s + tr[rs].s;
tr[rt].mx = max(tr[ls].mx,tr[rs].mx);
}
inline void update1(int rt,int lp,int rp,int k,int y){
if(lp==rp){
tr[rt].s = tr[rt].mx = y;
return;
}
int m = lp+rp >>;
if(k<=m) update1(ls,lp,m,k,y);
else update1(rs,m+,rp,k,y);
tr[rt].s = tr[ls].s + tr[rs].s;
tr[rt].mx = max(tr[ls].mx,tr[rs].mx);
}
inline ll query(int rt,int lp,int rp,int l,int r){
if(l<=lp&&rp<=r) {return tr[rt].s;}
int m = lp+rp >>;
ll ans = ;
if(l<=m) ans += query(ls,lp,m,l,r);
if(r>m) ans += query(rs,m+,rp,l,r);
return ans;
}
int main(){
n = read(),q = read();
rep(i,,n) a[i] = read();
build(,,n);
while(q--){
int opt = read();
if(opt==){
int l = read(),r = read();
printf("%lld\n",query(,,n,l,r));
}
if(opt==){
int l = read(),r = read(),x = read();
update(,l,r,,n,x);
}
if(opt==){
int k = read(),y = read();
update1(,,n,k,y);
}
}
return ;
}
【调试中出过的错】
1.关于小于号和小于等于
2.关于l与lp(r与rp)的大小