C++14(g++5.4) 解法, 执行用时: 809ms, 内存消耗: 9700K, 提交时间: 2019-04-27 09:14:54

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+5;
int n;
ll tree[N<<1],tag[N<<1];
void pushup(int rt)
{
    tree[rt]=__gcd(tree[rt<<1],tree[rt<<1|1]);
    tag[rt]=tag[rt<<1]&&tag[rt<<1|1];
}
void bulid(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%lld",&tree[rt]);
        tag[rt]=0;
        return ;
    }
    int mid=(l+r)>>1;
    bulid(l,mid,rt<<1);
    bulid(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R)
{
    if(tag[rt]) return ;
    if(l==r)
    {
        tree[rt]=sqrt(tree[rt]);
        if(tree[rt]==1) tag[rt]=1;
        return ;
    }
    int mid=l+(r-l)/2;
    if(L<=mid) update(l,mid,rt<<1,L,R);
    if(R>mid) update(mid+1,r,rt<<1|1,L,R);
    pushup(rt);
}
ll query(int l,int r,int rt,int L,int R)
{
    if(tag[rt]&&l<=L&&R<=r) return 1;
    if(L<=l&&R>=r) return tree[rt];
    int mid=l+(r-l)/2;
    if(R<=mid) return query(l,mid,rt<<1,L,R);
    else if(L>mid) return query(mid+1,r,rt<<1|1,L,R);
    else return __gcd(query(l,mid,rt<<1,L,R),query(mid+1,r,rt<<1|1,L,R));
}
int main()
{
    int q;
    scanf("%d",&n);
    bulid(1,n,1);
    scanf("%d",&q);
    while(q--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a==0) update(1,n,1,b,c);
        else cout<<query(1,n,1,b,c)<<endl;;
    }
    return 0;
}

C++ 解法, 执行用时: 335ms, 内存消耗: 11240K, 提交时间: 2021-12-01 22:19:00

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=2e5+10;
ll a[N],g[N<<2],ma[N<<2];
void pushup(int rt){
	g[rt]=__gcd(g[rt<<1],g[rt<<1|1]);
	ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
void build(int l,int r,int rt){
	if(l==r){
		g[rt]=a[l],ma[rt]=a[l];
		return;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}
void update(int L,int R,int l,int r,int rt){
	if(L<=l&&R>=r&&ma[rt]==1){
		return;
	}
	if(l==r){
		g[rt]=(ll)sqrt(g[rt]);
		ma[rt]=(ll)sqrt(ma[rt]);
		return;
	}
	int m=(l+r)>>1;
	if(L<=m) update(L,R,lson);
	if(R>m) update(L,R,rson);
	pushup(rt);
}
ll query(int L,int R,int l,int r,int rt){
	 if(L<=l&&R>=r){
	 	return g[rt];
	 }
	 int m=(l+r)>>1;
	 if(R<=m) return query(L,R,lson);
	 else if(L>m) return query(L,R,rson);
	 else return __gcd(query(L,R,lson),query(L,R,rson));
}
int main(){
	int n,m,op,l,r;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	build(1,n,1);
	scanf("%d",&m);
	while(m--){
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
			printf("%lld\n",query(l,r,1,n,1));
		else update(l,r,1,n,1);
	}
	return 0;
}