「雅礼集训 2017 Day1」市场

市场

我们不难得到一个简单的算法:维护区间\(\tt min,max,sum\)

对于1.3.4操作，直接打标记，操作即可

关键是如何处理操作2

对于区间\([l,r]\)

1. \(\lfloor \frac{\max a_l\sim a_r}{d}\rfloor =\lfloor \frac{\min a_l\sim a_r}{d}\rfloor\)打上区间覆盖标记
2. \(\max_{i\in[l,r]} a_i-\lfloor \frac{\max a_l\sim a_r}{d}\rfloor =\min_{i\in[l,r]} a_i-\lfloor \frac{\min a_l\sim a_r}{d}\rfloor\)打上区间减标记
3. 递归地进行

下面证明复杂度:

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define ll long long
const int def=2e9+5;
ll sum[400005],fl[400005];
int s,mx[400005],m,mn[400005],cov[400005];
void pushup(int d){
	mx[d]=max(mx[d<<1],mx[d<<1|1]);
	mn[d]=min(mn[d<<1],mn[d<<1|1]);
	sum[d]=sum[d<<1]+sum[d<<1|1];
}void pushdown(int d,int n){
	if(cov[d]!=def){
		mx[d]=mn[d]=cov[d];
		sum[d]=1ll*cov[d]*n;
		if(n!=1){
			fl[d<<1]=fl[d<<1|1]=0;
			cov[d<<1]=cov[d<<1|1]=cov[d];
		}
		cov[d]=def;
	}
	mx[d]+=fl[d];
	mn[d]+=fl[d];
	sum[d]+=1ll*fl[d]*n;
	if(n!=1){
		fl[d<<1]+=fl[d];
		fl[d<<1|1]+=fl[d];
	}fl[d]=0;
}
void build(int l,int r,int d){
	cov[d]=def;
	if(l==r)mx[d]=mn[d]=sum[d]=read;
	else{
		int mid=l+r>>1;
		build(l,mid,d<<1);
		build(mid+1,r,d<<1|1);
		pushup(d);
	}
}
ll query(int l,int r,int tl,int tr,int d){
	if(r<tl||tr<l)return 0;
	pushdown(d,tr-tl+1);
	if(l<=tl&&tr<=r)return sum[d];
	int mid=tl+tr>>1;
	return query(l,r,tl,mid,d<<1)+query(l,r,mid+1,tr,d<<1|1);
}
int query_(int l,int r,int tl,int tr,int d){
	if(r<tl||tr<l)return def;
	pushdown(d,tr-tl+1);
	if(l<=tl&&tr<=r)return mn[d];
	int mid=tl+tr>>1;
	return min(query_(l,r,tl,mid,d<<1),query_(l,r,mid+1,tr,d<<1|1));
}
void add(int l,int r,int c,int tl,int tr,int d){
	pushdown(d,tr-tl+1);
	if(r<tl||tr<l)return;
	if(l<=tl&&tr<=r){fl[d]+=c;pushdown(d,tr-tl+1);return;}
	int mid=tl+tr>>1;
	add(l,r,c,tl,mid,d<<1);
	add(l,r,c,mid+1,tr,d<<1|1);
	pushup(d);
}
ll Div(ll x,ll y){return floor(1.0*x/y);}
void divi(int l,int r,int c,int tl,int tr,int d){
	pushdown(d,tr-tl+1);
	if(r<tl||tr<l)return;
	if(l<=tl&&tr<=r){
		if(Div(mx[d],c)==Div(mn[d],c)){
			cov[d]=Div(mx[d],c);
			pushdown(d,tr-tl+1);
			return;
		}
		if(mx[d]-Div(mx[d],c)==mn[d]-Div(mn[d],c)){
			fl[d]-=mx[d]-Div(mx[d],c);
			pushdown(d,tr-tl+1);
			return;
		}
	}
	int mid=tl+tr>>1;
	divi(l,r,c,tl,mid,d<<1);
	divi(l,r,c,mid+1,tr,d<<1|1);
	pushup(d);
}
void pr(int d,int l,int r){
	pushdown(d,r-l+1);
	if(l==r)printf("%d::",mx[d]);
	else{
		int mid=l+r>>1;
		pr(d<<1,l,mid);
		pr(d<<1|1,mid+1,r);
	}
}
int main(){
	s=read;m=read;
	build(1,s,1);
	while(m--){
		int opt=read,l=read+1,r=read+1;
		if(opt==1)add(l,r,read,1,s,1);
		if(opt==2)divi(l,r,read,1,s,1);
		if(opt==3)printf("%d\n",query_(l,r,1,s,1));
		if(opt==4)printf("%lld\n",query(l,r,1,s,1));
//		pr(1,1,s);cout<<endl;
	}
	return 0;
}
           

因果乃旋转纺车，光彩之多面明镜

浮世苍茫，不过瞬逝幻梦

善恶爱诳，皆有定数

于命运之轮中

吞噬于黄泉之冥暗

呜呼，吾乃梦之戍人

幻恋之观者

唯于万华镜中，永世长存