厦门大学“网宿杯“17届程序设计竞赛决赛（同步赛）H.时间管理

大致题意：
一个序列，可以执行两种操作。

• 对区间 内的元素依次对x取 ，然后将结果赋值给 .
• 求区间元素和。

分析：这道题跟区间开方思路类似。
每次对一个区间进行gcd的话一般会有大部分会变成1，可以用一些小技巧来保证复杂度不会太差，用一个tag变量去标记一下这个区间是不是全都相等，再用一个sam变量去标记区间全相等的时候的元素大小，这样修改的时候对于区间元素都相等的直接对sam进行gcd即可。最后用一个线段树维护标记。(虽然区间开方的题目我是用分块,不过线段树还是挺好写的

#include<bits/stdc++.h>
#define ls cur<<1
#define rs cur<<1|1 
using namespace std;

typedef long long ll;
const int maxn=2e5+10;

ll sum[maxn<<2],a[maxn<<2],ma[maxn<<2],gd[maxn<<2],tag[maxn<<2],sam[maxn<<2];


void pushup( int cur )
{
    sum[cur]=sum[ls]+sum[rs]; 
    tag[cur]=tag[ls] & tag[rs];
    if( tag[cur] ) 
    {
        if( sam[ls]==sam[rs] ) sam[cur]=sam[ls]; 
        else tag[cur]=0;
    }
}

void pushdown( int cur ,int l,int r )
{
    if( tag[cur] )
    {
        int mid=l+r>>1;
        sam[ls]=sam[rs]=sam[cur];
        sum[ls]=(mid-l+1)*sam[ls];
        sum[rs]=(r-mid)*sam[rs];
    }

}

void build( int cur,int l,int r )
{
    if( l==r )
    {
        sum[cur]=a[l];
        tag[cur]=1;
        sam[cur]=a[l];
        return;
    }
    tag[cur]=0;
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(cur);
}

void update( int cur,int l,int r,int L,int R,ll p )
{
    if( L<=l && r<=R )
    {
        if( tag[cur] )
        {
            sam[cur]=__gcd(sam[cur],p);
            sum[cur]=sam[cur]*(r-l+1);
            return;
        }
    }
    pushdown(cur,l,r);
    if( l==r )
    {
        sam[cur]=sum[cur]=__gcd(a[l],p);
        return;
    }
    int mid=l+r>>1;
    if( mid>=L ) update(ls,l,mid,L,R,p);
    if( mid<R )  update(rs,mid+1,r,L,R,p);
    pushup(cur);
}

ll get_sum( int cur,int l,int r,int L,int R )
{
    if( L<=l && r<=R ) return sum[cur];
    int mid=l+r>>1;
    ll ans=0;
    pushdown(cur,l,r);
    if( L<=mid ) ans+=get_sum(ls,l,mid,L,R);
    if( R>mid ) ans+=get_sum(rs,mid+1,r,L,R);
    return ans;
}


int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for( int i=1;i<=n;i++ ) scanf("%lld",&a[i]);

    build(1,1,n);
    while( m-- )
    {
        int opt,l,r,x;
        scanf("%d%d%d",&opt,&l,&r);
        if( opt==1 )
        {
            ll x;
            scanf("%lld",&x);
            update(1,1,n,l,r,x);
        }
        if( opt==2 ) 
        printf("%lld\n",get_sum(1,1,n,l,r) );
    }
}