现在的位置: 首页 > 综合 > 正文

hdu4902

2019年02月27日 ⁄ 综合 ⁄ 共 1899字 ⁄ 字号 评论关闭

思路:线段树各种lazy操作即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    int l,r;
    int b;
    long long a;
} t[500000];
long long aa[111111];
int n,m;
void build(int ll,int rr,int rot)
{
    t[rot].l=ll;
    t[rot].r=rr;
    if(ll==rr)
    {
        t[rot].a=aa[ll];
        t[rot].b=1;
        return;
    }
    t[rot].b=0;
    int mid=(ll+rr)/2;
    build(ll,mid,rot<<1);
    build(mid+1,rr,rot<<1|1);
}
void pushdown(int rot)
{
    if(t[rot].b==1)
    {
        t[rot<<1].a=t[rot].a;
        t[rot<<1].b=1;
        t[rot<<1|1].a=t[rot].a;
        t[rot<<1|1].b=1;
    }
    else
    {
        if(t[rot<<1].b==0)
        {
            t[rot<<1].b=t[rot].b;
            t[rot<<1].a=t[rot].a;
        }
        else if(t[rot<<1].b==1)
        {
            if(t[rot<<1].a>t[rot].a)
            {
                if(t[rot].a==0)t[rot<<1].a=0;
                else t[rot<<1].a=__gcd(t[rot].a,t[rot<<1].a);
            }
        }
        else if(t[rot<<1].b==2)
        {
            pushdown(rot<<1);
            t[rot<<1].b=t[rot].b;
            t[rot<<1].a=t[rot].a;
        }

        if(t[rot<<1|1].b==0)
        {
            t[rot<<1|1].b=t[rot].b;
            t[rot<<1|1].a=t[rot].a;
        }
        else if(t[rot<<1|1].b==1)
        {
            if(t[rot<<1|1].a>t[rot].a)
            {
                if(t[rot].a==0)t[rot<<1|1].a=0;
                else t[rot<<1|1].a=__gcd(t[rot].a,t[rot<<1|1].a);
            }
        }
        else if(t[rot<<1|1].b==2)
        {
            pushdown(rot<<1|1);
            t[rot<<1|1].b=t[rot].b;
            t[rot<<1|1].a=t[rot].a;
        }
    }
    t[rot].b=0;
}
void update(int u,int ll,int rr,long long x,int rot)
{
    if(t[rot].l==ll&&t[rot].r==rr)
    {
        if(u==1)
        {
            t[rot].a=x;
            t[rot].b=u;
        }
        else
        {
            if(t[rot].b==1)
            {
                if(t[rot].a>x)
                {
                    if(x==0)t[rot].a=0;
                    else t[rot].a=__gcd(t[rot].a,x);
                }
            }
            else
            {
                if(t[rot].b==2)pushdown(rot);
                t[rot].a=x;
                t[rot].b=u;
            }
        }
        return;
    }
    if(t[rot].b)pushdown(rot);
    int mid=(t[rot].l+t[rot].r)/2;
    if(rr<=mid)update(u,ll,rr,x,rot<<1);
    else if(ll>mid)update(u,ll,rr,x,rot<<1|1);
    else
    {
        update(u,ll,mid,x,rot<<1);
        update(u,mid+1,rr,x,rot<<1|1);
    }
}
void query(int rot)
{
    if(t[rot].b==1)
    {
        for(int i=t[rot].l; i<=t[rot].r; i++)printf("%I64d ",t[rot].a);
        return;
    }
    if(t[rot].b==2)pushdown(rot);
    query(rot<<1);
    query(rot<<1|1);
}
int main()
{
    int l,r,u;
    long long v;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)scanf("%I64d",&aa[i]);
        build(1,n,1);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d%d%I64d",&u,&l,&r,&v);
            update(u,l,r,v,1);
        }
        query(1);
        printf("\n");
    }
    return 0;
}
【上篇】
【下篇】

抱歉!评论已关闭.