记录编号	544027	评测结果	AAAAAAAAAA
题目名称	苦恼的Van	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	0.240 s
提交时间	2019-10-12 17:50:28	内存使用	11.96 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int sum[400001],mx[400001];
int n,m,a,b,c;
int val[100001];
int ls(int x)
{
	return x<<1;
}
int rs(int x)
{
	return x<<1|1;
}
void pushup(int x)
{
	sum[x]=sum[ls(x)]+sum[rs(x)];
	mx[x]=max(mx[ls(x)],mx[rs(x)]);
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		sum[x]=val[l];
		mx[x]=sum[x];
		return ;
	}
	int mid=(l+r)>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	pushup(x); 
}
void Mod(int x,int l,int r,int nl,int nr,int mod)
{
	if(l==r)
	{
		sum[x]%=mod;
		mx[x]%=mod;
		return;
	}
	if(mx[x]<mod)
		return;
	int mid=(l+r)>>1;
	if(nl<=mid)
		Mod(ls(x),l,mid,nl,nr,mod);
	if(nr>mid)
		Mod(rs(x),mid+1,r,nl,nr,mod);
	pushup(x);
}
int Query(int x,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
		return sum[x];
	int mid=(l+r)>>1;
	int res=0;
	if(nl<=mid)
	{
		res+=Query(ls(x),l,mid,nl,nr);
	}
	if(nr>mid)
	{
		res+=Query(rs(x),mid+1,r,nl,nr);
	}
	return res;
}
int LINYIN()
{
	freopen("van_modify.in","r",stdin);
	freopen("van_modify.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&val[i]);
	}
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a);
		if(a==0)
		{
			scanf("%d%d",&a,&b);
			printf("%d",Query(1,1,n,a,b));
		}
		else
		{
			scanf("%d%d%d",&a,&b,&c);
			Mod(1,1,n,a,b,c);
		}
	}
	return 0;
}
int LWH=LINYIN();
int main()
{
	;
}