题目：

我是超链接

题解：

懒标记：对区间打下的标记，在用到的时候会pushdown
作用的条件：

• 标记可以合并
• 可以快速更新区间信息（下传方便）

这个题目用到的区间修改，但不满足条件二，也就是无法快速更新区间和，而逐个更新对每个数取模太慢了 有一个很重要的结论：任何一个数log次取模以内就能变为0，并且a%b=a(a < b) 单点更新和区间和并无特殊之处，而对于每个区间取模操作，如同遍历这个区间所有的数字一样，逐个取模更新。但是若某个区间的区间最大值小于mod，那么这个区间就无需有任何操作。这相当于一个剪枝。所以我们需要两个数组，一个记录区间和，一个记录区间最大值。 其实就是一个优秀的剪枝了。

代码：

#include #include #define LL long long using namespace std; const int N=100005; int maxx[N*4],a[N];LL sum[N*4]; void updata(int now) { sum[now]=sum[now<<1]+sum[now<<1|1]; maxx[now]=max(maxx[now<<1],maxx[now<<1|1]); } void build(int now,int l,int r) { if (l==r) { maxx[now]=sum[now]=a[l]; return; } int mid=(l+r)>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); updata(now); } LL qurry(int now,int l,int r,int lrange,int rrange) { if (lrange<=l && rrange>=r) return sum[now]; int mid=(l+r)>>1;LL ans=0; if (lrange<=mid) ans+=qurry(now<<1,l,mid,lrange,rrange); if (rrange>mid) ans+=qurry(now<<1|1,mid+1,r,lrange,rrange); return ans; } void change(int now,int l,int r,int x,int v) { if (l==r) { maxx[now]=sum[now]=v; return; } int mid=(l+r)>>1; if (x<=mid) change(now<<1,l,mid,x,v); else change(now<<1|1,mid+1,r,x,v); updata(now); } void qm(int now,int l,int r,int lrange,int rrange,int x) { if (maxx[now]if (l==r) { sum[now]%=x;maxx[now]%=x; return; } int mid=(l+r)>>1; if (lrange<=mid) qm(now<<1,l,mid,lrange,rrange,x); if (rrange>mid) qm(now<<1|1,mid+1,r,lrange,rrange,x); updata(now); } int main() { int n,m;scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); for (int i=1;i<=m;i++) { int l,r,id,x;scanf("%d",&id); if (id==1) { scanf("%d%d",&l,&r); printf("%I64d ",qurry(1,1,n,l,r)); }else if (id==2) { scanf("%d%d%d",&l,&r,&x); qm(1,1,n,l,r,x); }else { scanf("%d%d",&l,&x); change(1,1,n,l,x); } } }