操作1、3、4都是常规操作，我就不讲了。
然后我们考虑怎么处理区间除法。
首先容易想到对于一个数 x x x，它除一次最少除 2 2 2，那么它最多除 l o g 2 ( x ) log_2(x) log2(x)次就会变成 0 o r 1 0\ or\ 1 0 or 1。
但是会有区间加法，所以这个东东不可以搞。
于是我们注意到一个性质：
如果：
x − ⌊ x d ⌋ = z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor=z-\lfloor\frac{z}{d}\rfloor x−⌊dx⌋=z−⌊dz⌋
那么有对于所有的 y y y，若 x ⩽ y ⩽ z x\leqslant y \leqslant z x⩽y⩽z，则有：
x − ⌊ x d ⌋ = y − ⌊ y d ⌋ = z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor=y-\lfloor\frac{y}{d}\rfloor=z-\lfloor\frac{z}{d}\rfloor x−⌊dx⌋=y−⌊dy⌋=z−⌊dz⌋
证明：
若 x ⩽ y ⩽ z x\leqslant y \leqslant z x⩽y⩽z,那么
⌊ x d ⌋ ⩽ ⌊ y d ⌋ ⩽ ⌊ z d ⌋ \lfloor\frac{x}{d}\rfloor \leqslant \lfloor\frac{y}{d}\rfloor \leqslant \lfloor\frac{z}{d}\rfloor ⌊dx⌋⩽⌊dy⌋⩽⌊dz⌋且 ⌊ y d ⌋ − ⌊ x d ⌋ ⩽ y − x \lfloor\frac{y}{d}\rfloor-\lfloor\frac{x}{d}\rfloor \leqslant y-x ⌊dy⌋−⌊dx⌋⩽y−x
显而易见
移下项：
x − ⌊ x d ⌋ ⩽ y − ⌊ y d ⌋ x-\lfloor\frac{x}{d}\rfloor \leqslant y-\lfloor\frac{y}{d}\rfloor x−⌊dx⌋⩽y−⌊dy⌋
同理可得：
y − ⌊ y d ⌋ ⩽ z − ⌊ z d ⌋ y-\lfloor\frac{y}{d}\rfloor \leqslant z-\lfloor\frac{z}{d}\rfloor y−⌊dy⌋⩽z−⌊dz⌋
故：
x − ⌊ x d ⌋ ⩽ y − ⌊ y d ⌋ ⩽ z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor \leqslant y-\lfloor\frac{y}{d}\rfloor \leqslant z-\lfloor\frac{z}{d}\rfloor x−⌊dx⌋⩽y−⌊dy⌋⩽z−⌊dz⌋
所以当
x − ⌊ x d ⌋ = z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor=z-\lfloor\frac{z}{d}\rfloor x−⌊dx⌋=z−⌊dz⌋
时，对于所有的 x ⩽ y ⩽ z x \leqslant y \leqslant z x⩽y⩽z，都满足：
x − ⌊ x d ⌋ = y − ⌊ y d ⌋ = z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor = y-\lfloor\frac{y}{d}\rfloor =z-\lfloor\frac{z}{d}\rfloor x−⌊dx⌋=y−⌊dy⌋=z−⌊dz⌋
得证。
感觉那么一大段字说了一堆废话……
那么每次我们只要判断一下如果这个区间 [ l , r ] [l,r] [l,r]的：
m i n n − ⌊ m i n n d ⌋ = m a x n − ⌊ m a x n d ⌋ minn-\lfloor\frac{minn}{d}\rfloor=maxn-\lfloor\frac{maxn}{d}\rfloor minn−⌊dminn⌋=maxn−⌊dmaxn⌋
由于肯定有 m i n n ⩽ a l , a l + 1 , . . . , a r ⩽ m a x n minn \leqslant a_l,a_{l+1},...,a_r \leqslant maxn minn⩽al,al+1,...,ar⩽maxn
所以必有
a l − ⌊ a l d ⌋ = a l + 1 − ⌊ a l + 1 d ⌋ = . . . = a r − ⌊ a r d ⌋ a_l-\lfloor\frac{a_l}{d}\rfloor=a_{l+1}-\lfloor\frac{a_{l+1}}{d}\rfloor=...=a_r-\lfloor\frac{a_r}{d}\rfloor al−⌊dal⌋=al+1−⌊dal+1⌋=...=ar−⌊dar⌋
而对于每一个数 a i a_i ai， a i − ⌊ a i d ⌋ a_i-\lfloor\frac{a_i}{d}\rfloor ai−⌊dai⌋就是从 a i a_i ai变为 ⌊ a i d ⌋ \lfloor\frac{a_i}{d}\rfloor ⌊dai⌋需要减多少，所以只要将 a i a_i ai减去 a i − ⌊ a i d ⌋ a_i-\lfloor\frac{a_i}{d}\rfloor ai−⌊dai⌋，就可以实现除法。
所以这就是一个区间减法，因为每个数都要减去这个值。
所以这一段的代码：
void update2(int k,int l,int r,int ql,int qr,ll val) { int x=floor(1.0*minn[k]/val)-minn[k]; int y=floor(1.0*maxn[k]/val)-maxn[k]; if(ql<=l&&r<=qr&&x==y) { sum[k]+=x*(r-l+1);//区间加（减） minn[k]+=x; maxn[k]+=x; lazy[k]+=x; return; } int mid=(l+r)>>1; down(k,l,r,mid); if(ql<=mid)update2(k<<1,l,mid,ql,qr,val); if(qr>mid)update2(k<<1|1,mid+1,r,ql,qr,val); up(k); }时间复杂度： O ( q log ( n ) log ( V ) ) O(q\log(n) \log (V)) O(qlog(n)log(V))。
不会证……
全部代码如下：
#include<bits/stdc++.h> #define N 100010 #define ll long long #define LNF 0x7fffffffffffffff using namespace std; int n,m,a[N]; ll sum[N<<2],minn[N<<2],maxn[N<<2],lazy[N<<2]; void downn(int k,int l,int r,ll val) { sum[k]+=val*(r-l+1); minn[k]+=val; maxn[k]+=val; lazy[k]+=val; } void down(int k,int l,int r,int mid) { if(lazy[k]) { downn(k<<1,l,mid,lazy[k]); downn(k<<1|1,mid+1,r,lazy[k]); lazy[k]=0; } } void up(int k) { sum[k]=sum[k<<1]+sum[k<<1|1]; minn[k]=min(minn[k<<1],minn[k<<1|1]); maxn[k]=max(maxn[k<<1],maxn[k<<1|1]); } void build(int k,int l,int r) { if(l==r) { scanf("%lld",&sum[k]); maxn[k]=minn[k]=sum[k]; return; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k); } void update1(int k,int l,int r,int ql,int qr,ll val) { if(ql<=l&&r<=qr) { downn(k,l,r,val); return; } int mid=(l+r)>>1; down(k,l,r,mid); if(ql<=mid)update1(k<<1,l,mid,ql,qr,val); if(qr>mid)update1(k<<1|1,mid+1,r,ql,qr,val); up(k); } void update2(int k,int l,int r,int ql,int qr,ll val) { if(ql<=l&&r<=qr&&floor(1.0*minn[k]/val)-minn[k]==floor(1.0*maxn[k]/val)-maxn[k]) { ll tmp=floor(1.0*minn[k]/val)-minn[k]; downn(k,l,r,tmp); return; } int mid=(l+r)>>1; down(k,l,r,mid); if(ql<=mid)update2(k<<1,l,mid,ql,qr,val); if(qr>mid)update2(k<<1|1,mid+1,r,ql,qr,val); up(k); } ll query1(int k,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) return minn[k]; int mid=(l+r)>>1;ll ans=LNF; down(k,l,r,mid); if(ql<=mid)ans=min(ans,query1(k<<1,l,mid,ql,qr)); if(qr>mid)ans=min(ans,query1(k<<1|1,mid+1,r,ql,qr)); return ans; } ll query2(int k,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) return sum[k]; int mid=(l+r)>>1;ll ans=0; down(k,l,r,mid); if(ql<=mid)ans+=query2(k<<1,l,mid,ql,qr); if(qr>mid)ans+=query2(k<<1|1,mid+1,r,ql,qr); return ans; } int main() { scanf("%d%d",&n,&m); build(1,1,n); while(m--) { int opt,l,r; scanf("%d%d%d",&opt,&l,&r); l++,r++; if(opt==1) { ll val; scanf("%lld",&val); update1(1,1,n,l,r,val); } if(opt==2) { ll val; scanf("%lld",&val); update2(1,1,n,l,r,val); } if(opt==3) printf("%lld\n",query1(1,1,n,l,r)); if(opt==4) printf("%lld\n",query2(1,1,n,l,r)); } return 0; }