HDU 4902 線段樹||暴力

HDU 4902 線段樹||暴力

給定一個序列，兩種操作

1：把一段變成x。

2：把一段每個數字，如果他大於x，就變成他和x的gcd，求變換完後，最後的序列。

線段樹解法：用lazy標記下即可，優化方法還是很巧妙的，

Accepted 4902 515MS 3308K 1941 B C++

#include "stdio.h"
#include "string.h"
struct node
{
    int l,r,x;// 在葉子節點代表值，樹節點代表成端更新的lazy操作。
}data[400010];

int gcd(int a,int b)
{
    if(b==0) return a;else return gcd(b,a%b);
}
void build(int l,int r,int k)
{
    int mid;
    data[k].l=l;
    data[k].r=r;
    data[k].x=-1;

    if (l==r)
    {
        scanf("%d",&data[k].x);
        return ;
    }
    mid=(l+r)/2;

    build(l,mid,k*2);
    build(mid+1,r,k*2+1);
}

void cover(int l,int r,int k,int x)
{
    int mid;
    if (data[k].l==l && data[k].r==r)
    {
        data[k].x=x;
        return ;
    }

    mid=(data[k].l+data[k].r)/2;

    if (data[k].x!=-1) // lazy 操作
    {
        cover(data[k].l,mid,k*2,data[k].x);
        cover(mid+1,data[k].r,k*2+1,data[k].x);
        data[k].x=-1;
    }
    if (r<=mid) cover(l,r,k*2,x);
    else
        if (l>mid) cover(l,r,k*2+1,x);
    else
    {
        cover(l,mid,k*2,x);
        cover(mid+1,r,k*2+1,x);
    }

}

void updata(int l,int r,int k,int x)
{
    int mid;
    if (data[k].x!=-1) // 操作2的優化
    {
        if (data[k].x<=x) return ; // 如果下面的成端更新值小於x，則不進行操作2
        cover(l,r,k,gcd(data[k].x,x)); // 否則把成端更新的進行操作2再更新
        return ;
    }

    mid=(data[k].l+data[k].r)/2;

    if (r<=mid) updata(l,r,k*2,x);
    else if (l>mid) updata(l,r,k*2+1,x);
    else
    {
        updata(l,mid,k*2,x);
        updata(mid+1,r,k*2+1,x);
    }
}

void pri(int k)
{
    int i;
    if (data[k].x!=-1)
    {
        for (i=data[k].l;i<=data[k].r;i++)
            printf("%d ",data[k].x);
        return ;
    }
    pri(k*2);
    pri(k*2+1);
}
int main()
{
    int Case,op,a,b,x,n,m;
    scanf("%d",&Case);
    while (Case--)
    {
        scanf("%d",&n);
        build(1,n,1);

        scanf("%d",&m);
        while (m--)
        {
            scanf("%d%d%d%d",&op,&a,&b,&x);
            if(op==1) cover(a,b,1,x);
            else updata(a,b,1,x);
        }
        pri(1);
        printf("\n");
    }
    return 0;
}

Accepted 4902 250MS 3336K 754 B C

#include "stdio.h"
#include "string.h"

struct node
{
    int l,r,op;
    __int64 x;
}mark[100010]; __int64 a[101000],pri,b[101000];
__int64 gcd(__int64 a,__int64 b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
int main()
{
    int Case,n,i,j,sum,m;

    scanf("%d",&Case);
    while (Case--)
    {
        scanf("%d",&n);
        for (i=1;i<=n;i++)
            scanf("%I64d",&a[i]);
        scanf("%d",&m);
        for (i=1;i<=m;i++)
            scanf("%d%d%d%I64d",&mark[i].op,&mark[i].l,&mark[i].r,&mark[i].x);

        for (i=1;i<=n;i++) // 對於每個點按操作從後往前更新
        {
            pri=a[i];
            sum=0;
            for (j=m;j>=1;j--)
                if (mark[j].l<=i && mark[j].r>=i)
                {
                    if (mark[j].op==1) //遇到操作1就停止
                    {
                        pri=mark[j].x;
                        break;
                    }
                    else
                    {
                        b[sum++]=mark[j].x; //記錄中間遇到的操作2
                    }

                }
            if (sum==0)
                printf("%I64d ",pri);
            else
            {
                for (j=sum-1;j>=0;j--)
                    if (pri>b[j]) pri=gcd(pri,b[j]);
                printf("%I64d ",pri);
            }

        }
        printf("\n");

    }
    return 0;
}