C++14(g++5.4) 解法, 执行用时: 207ms, 内存消耗: 7028K, 提交时间: 2020-06-06 10:38:41

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=114514+1919;
ll seg[MAXN<<2];
int a[MAXN],n,m,tag[MAXN<<2];

inline void pushup(int rt)
{
    seg[rt]=seg[rt<<1]+seg[rt<<1|1];
    if(tag[rt<<1]==tag[rt<<1|1]) tag[rt]=tag[rt<<1];
    else tag[rt]=0;
}

void build(int rt,int l,int r)
{
    if(l==r)
    {
        tag[rt]=seg[rt]=a[l];
        return;
    }
    int m=l+r>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}

void modify(int rt,int l,int r,int L,int R,int x)
{
    if(l==r)
    {
        tag[rt]=seg[rt]=__gcd(seg[rt],(long long)x);
        return;
    }
    int lst=tag[rt];
    tag[rt]=__gcd(tag[rt],x);
    if(lst&&x%lst==0) return;
    int m=l+r>>1;
    if(L<=m) modify(rt<<1,l,m,L,R,x);
    if(m<R) modify(rt<<1|1,m+1,r,L,R,x);
    pushup(rt);
}

ll query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return seg[rt];
    int m=l+r>>1;
    ll ret=0;
    if(L<=m) ret+=query(rt<<1,l,m,L,R);
    if(R>m) ret+=query(rt<<1|1,m+1,r,L,R);
    return ret;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int op,x,y,z;
        scanf("%d%d%d",&op,&x,&y);
        if(op==2) printf("%lld\n",query(1,1,n,x,y));
        else scanf("%d",&z),modify(1,1,n,x,y,z);
    }
    return 0;
}

/*
10 10
4 4 4 4 4 4 4 4 4 4
1 1 10 8
2 1 10
*/

C++11(clang++ 3.9) 解法, 执行用时: 187ms, 内存消耗: 5516K, 提交时间: 2020-06-27 19:14:03

#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}
long long s,S[500005];
int y,Max[500005],Min[500005],a[120005];
void build(int L,int R,int x)
{
	if(L==R)
	{
		Max[x]=Min[x]=S[x]=a[L];
		return;
	}
	int M=(L+R)>>1;
	build(L,M,2*x),build(M+1,R,2*x+1);
	S[x]=S[2*x]+S[2*x+1];
	Max[x]=max(Max[2*x],Max[2*x+1]);
	Min[x]=min(Min[2*x],Min[2*x+1]); 
}
void update(int L,int R,int l,int r,int x)
{
	if(Max[x]==1||(Max[x]==Min[x]&&Min[x]==y))return;
	if(L==R)
	{
		Max[x]=Min[x]=S[x]=gcd(S[x],y);
		return;
	}
	int M=(L+R)>>1;
	if(M>=l)update(L,M,l,r,2*x);
	if(M<r)update(M+1,R,l,r,2*x+1);
	S[x]=S[2*x]+S[2*x+1];
	Max[x]=max(Max[2*x],Max[2*x+1]);
	Min[x]=min(Min[2*x],Min[2*x+1]); 
}
void search(int L,int R,int l,int r,int x)
{
	if(l<=L&&R<=r)
	{
		s+=S[x];
		return;
	}
	int M=(L+R)>>1;
	if(M>=l)search(L,M,l,r,2*x);
	if(M<r)search(M+1,R,l,r,2*x+1);
}
int main()
{
	int i,n,m,l,r,op;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	build(1,n,1);
	while(m--)
	{
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)scanf("%d",&y),update(1,n,l,r,1);
		else s=0,search(1,n,l,r,1),printf("%lld\n",s);
	}
}