记录编号	578475	评测结果	AAAAAAAAAA
题目名称	[雅礼集训 2017 Day1] 市场	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	3.095 s
提交时间	2023-03-18 22:24:37	内存使用	17.37 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long 
using namespace std;
const int N=100001;
int val[4*N],mi[4*N],mx[4*N],lazy[4*N],cl[4*N],ch[4*N];
int a[N];
int ls(int x)
{
	return x<<1;
}
int rs(int x)
{
	return x<<1|1;
}
void pushup(int x)
{
	val[x]=val[ls(x)]+val[rs(x)];
	mi[x]=min(mi[ls(x)],mi[rs(x)]);
	mx[x]=max(mx[ls(x)],mx[rs(x)]);
}
void pushdown(int x,int l,int r)
{
	if(lazy[x])
	{
		int mid=(l+r)>>1;
		val[ls(x)]+=(mid-l+1)*lazy[x];
		val[rs(x)]+=(r-mid)*lazy[x];
		mi[ls(x)]+=lazy[x];
		mi[rs(x)]+=lazy[x];
		mx[ls(x)]+=lazy[x];
		mx[rs(x)]+=lazy[x];
		lazy[ls(x)]+=lazy[x];
		lazy[rs(x)]+=lazy[x];
		lazy[x]=0;
	}
}
void Build(int x,int l,int r)
{
	if(l==r)
	{
		val[x]=a[l];
		mx[x]=a[l];
		mi[x]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	Build(ls(x),l,mid);
	Build(rs(x),mid+1,r);
	pushup(x); 
}
void ADD(int x,int l,int r,int nl,int nr,int V)
{
	if(nl<=l&&nr>=r)
	{
		val[x]+=(r-l+1)*V;
		if(ch[x])
		{
			cl[x]+=V;
		}
		else
			lazy[x]+=V;
		mi[x]+=V;
		mx[x]+=V;
		return;
	}
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	if(nl<=mid)
		ADD(ls(x),l,mid,nl,nr,V);
	if(nr>mid)
	{
		ADD(rs(x),mid+1,r,nl,nr,V);
	}
	pushup(x);
}
void CHANGE(int x,int l,int r,int nl,int nr,int KEL)
{
	if(nl<=l&&nr>=r)
	{
		int mid=(l+r)>>1;
		if((mx[x]-floor(((double)mx[x])/KEL))==(mi[x]-floor((double)mi[x]/KEL)))
		{
			ADD(x,l,r,l,r,-(mx[x]-floor(((double)mx[x])/KEL)));
			return;
		}
		else
		{
			pushdown(x,l,r);
			CHANGE(ls(x),l,mid,nl,nr,KEL);
			CHANGE(rs(x),mid+1,r,nl,nr,KEL);
		}
	}
	else
	{
		pushdown(x,l,r);
		int mid=(l+r)>>1;
		if(nl<=mid)
		{
			CHANGE(ls(x),l,mid,nl,nr,KEL);
		}
		if(nr>mid)
			CHANGE(rs(x),mid+1,r,nl,nr,KEL);
	}
	pushup(x);
}
int Query1(int x,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
	{
		return val[x];
	}
	pushdown(x,l,r);
	int mid=(l+r)>>1,ans=0;
	if(nl<=mid)
	{
		ans+=Query1(ls(x),l,mid,nl,nr);
	} 
	if(nr>mid)
	{
		ans+=Query1(rs(x),mid+1,r,nl,nr);
	}
	return ans;
}
int Query2(int x,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
	{
		return mi[x];
	}
	pushdown(x,l,r);
	int mid=(l+r)>>1,ans=998244353;
	if(nl<=mid)
		ans=min(ans,Query2(ls(x),l,mid,nl,nr));
	if(nr>mid)
		ans=min(ans,Query2(rs(x),mid+1,r,nl,nr));
	return ans;
}
int CHECK(int x,int l,int r,int pos)
{
	if(l==r)
	{
		return val[x];
	}
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	if(pos<=mid)
	return CHECK(ls(x),l,mid,pos);
	else
	return CHECK(rs(x),mid+1,r,pos);
}
int n,q;
signed main()
{
	freopen("2017market.in","r",stdin);
	freopen("2017market.out","w",stdout);
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	Build(1,1,n);
	int a1,a2,a3,a4;
	for(int i=1;i<=q;i++)
	{
		cin>>a1>>a2>>a3;
		a2++;
		a3++;
		if(a1<=2)
			cin>>a4;
		if(a1==1)
		{
			ADD(1,1,n,a2,a3,a4);
		}
		if(a1==2)
		{
			CHANGE(1,1,n,a2,a3,a4);
		}
		if(a1==3)
			cout<<Query2(1,1,n,a2,a3)<<endl;
		if(a1==4)
			cout<<Query1(1,1,n,a2,a3)<<endl;
	}
	return 0;
}