题目大意：维护一个长度为 $n$ 的正整数序列 $a$，支持单点修改，区间取模，区间求和。共 $m$ 个操作。
$1\le n,m\le 10^5$。其它数均为非负整数且 $\le 10^9$。
居然被这道水题卡了那么久……
主要难点就是取模操作。
我们发现一个数 $x$ 模 $i(1\le i\le x)$：
$i\le\lfloor\frac{x}{2}\rfloor$ 时：余数小于除数，所以答案小于 $\lfloor\frac{x}{2}\rfloor$。
$i>\lfloor\frac{x}{2}\rfloor$ 时：答案就是 $x-i\$，也小于 $\lfloor\frac{x}{2}\rfloor$。
所以 $x$ 每次被取模都至少减小一半。
那……就是暴力线段树！
线段树再维护一个区间最大值，当模数大于区间最大值时，直接走人。
容易发现如果没有单点修改操作，一个叶子节点最多被暴力到 $\log a_i$ 次。
有单点修改操作？那又怎样？一共只会多 $m$ 个数而已啊！
时间复杂度 $O((n+m)\log n\log a_i)$。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100010; #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ char ch=getchar();int x=0,f=0; while(ch<‘0‘ || ch>‘9‘) f|=ch==‘-‘,ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar(); return f?-x:x; } int n,m,a[maxn],mx[maxn*4]; ll sum[maxn*4]; //和要开long long inline void pushup(int o){ sum[o]=sum[o<<1]+sum[o<<1|1]; mx[o]=max(mx[o<<1],mx[o<<1|1]); } void build(int o,int l,int r){ if(l==r) return void(sum[o]=mx[o]=a[l]); int mid=(l+r)>>1; build(lson); build(rson); pushup(o); } void modify(int o,int l,int r,int p,int v){ if(l==r) return void(sum[o]=mx[o]=v); int mid=(l+r)>>1; if(mid>=p) modify(lson,p,v); else modify(rson,p,v); pushup(o); } ll query(int o,int l,int r,int ql,int qr){ if(l>=ql && r<=qr) return sum[o]; int mid=(l+r)>>1;ll ans=0; if(mid>=ql) ans+=query(lson,ql,qr); if(mid<qr) ans+=query(rson,ql,qr); return ans; } //以上基本操作，不解释。。。 void modulo(int o,int l,int r,int ql,int qr,int v){ if(mx[o]<v) return; //模数大于最大值，走人 if(l==r) return void(sum[o]=mx[o]=sum[o]%v); //到叶子结点，暴力 int mid=(l+r)>>1; if(mid>=ql) modulo(lson,ql,qr,v); //暴力下去 if(mid<qr) modulo(rson,ql,qr,v); pushup(o); } int main(){ n=read();m=read(); FOR(i,1,n) a[i]=read(); build(1,1,n); FOR(i,1,m){ int op=read(),x=read(),y=read(); switch(op){ case 1:printf("%lld\n",query(1,1,n,x,y));break; case 2:modulo(1,1,n,x,y,read());break; case 3:modify(1,1,n,x,y); } } }
CF438D The Child and Sequence（线段树）
原文：https://www.cnblogs.com/1000Suns/p/10357640.html
