1 条题解
-
0
线段树好题。
考虑加法的值很小，而除的值很大，容易发现除法做的次数并不是特别多。
操作直接线段树简单搞，考虑 操作如果优化。
- 维护区间最大值和最小值，如果他们进行除法后的结果一样，那这就是区间推平操作。
这个显然，写了后可以得到 分，可以过随机数据。
- 如果区间最大值和最小值，进行除法操作后，他们减去的值一样，那么区间中所有的数就相当做了一次区间加。
考虑对一段区间排序后 的值一定是单调不增的，因为前面 的变化量显然大于后面的
代码
#include<bits/stdc++.h> #define int long long #define fir 1,1,n #define seg int p,int l,int r #define lid p<<1,l,mid #define rid p<<1|1,mid+1,r #define mid (l+r>>1) using namespace std; const int N=1e5+5; int a[N]; struct segtree{int mn,mx,sum,la,la1;}tr[N<<2]; void pp(seg){ tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum; tr[p].mn=min(tr[p<<1].mn,tr[p<<1|1].mn); tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx); } void build(seg){ if(l==r){ tr[p].mn=tr[p].mx=tr[p].sum=a[l]; tr[p].la1=1e9; return; } build(lid),build(rid); pp(p,l,r); tr[p].la1=1e9; } void pd(int p,int l,int r){ if(tr[p].la1!=1e9){ tr[p<<1].mx=tr[p<<1].mn=tr[p<<1|1].mx=tr[p<<1|1].mn=tr[p<<1].la1=tr[p<<1|1].la1=tr[p].la1; tr[p<<1].la=tr[p<<1|1].la=0; tr[p<<1].sum=tr[p].la1*(mid-l+1); tr[p<<1|1].sum=tr[p].la1*(r-mid); tr[p].la1=1e9; } if(tr[p].la){ int z=tr[p].la; tr[p<<1].mx+=z,tr[p<<1].mn+=z; tr[p<<1|1].mx+=z,tr[p<<1|1].mn+=z; tr[p<<1].sum+=(mid-l+1)*z,tr[p<<1|1].sum+=(r-mid)*z; tr[p<<1].la+=z,tr[p<<1|1].la+=z; tr[p].la=0; } } void add(seg,int L,int R,int z){ if(l>=L&&r<=R){ tr[p].mn+=z; tr[p].mx+=z; tr[p].sum+=(r-l+1)*z; tr[p].la+=z; return; } if(tr[p].la||tr[p].la1!=1e9)pd(p,l,r); if(L<=mid)add(lid,L,R,z); if(R>mid)add(rid,L,R,z); pp(p,l,r); } int askmin(seg,int L,int R){ if(l>=L&&r<=R)return tr[p].mn; if(tr[p].la||tr[p].la1!=1e9)pd(p,l,r); return min((L<=mid?askmin(lid,L,R):1e9),(R>mid?askmin(rid,L,R):1e9)); } int asksum(seg,int L,int R){ if(l>=L&&r<=R)return tr[p].sum; if(tr[p].la||tr[p].la1!=1e9)pd(p,l,r); return (L<=mid?asksum(lid,L,R):0)+(R>mid?asksum(rid,L,R):0); } void work(seg,int L,int R,int z){ if(l>=L&&r<=R){ int v1=floor(tr[p].mx*1.0/z),v2=floor(tr[p].mn*1.0/z); if(v1==v2){//优化1 tr[p].mx=tr[p].mn=v1; tr[p].sum=tr[p].mx*(r-l+1); tr[p].la=0; tr[p].la1=tr[p].mx; return; } else{//优化2 if(tr[p].mn-v2==tr[p].mx-v1){ int Z=v2-tr[p].mn; tr[p].mn+=Z; tr[p].mx+=Z; tr[p].sum+=(r-l+1)*Z; tr[p].la+=Z; return; } } } if(tr[p].la||tr[p].la1!=1e9)pd(p,l,r); if(L<=mid)work(lid,L,R,z); if(R>mid)work(rid,L,R,z); pp(p,l,r); } int n,m; signed main() {; scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); build(fir); for(int i=1;i<=m;i++){ int T,x,y,z; scanf("%lld%lld%lld",&T,&x,&y); x++,y++; if(T==1){ scanf("%lld",&z); add(fir,x,y,z); } if(T==2){ scanf("%lld",&z); if(z!=1)work(fir,x,y,z); } if(T==3)printf("%lld\n",askmin(fir,x,y)); if(T==4)printf("%lld\n",asksum(fir,x,y)); } return 0; }
- 1