学步园

这道题是昨天多校联合比赛的1006题，我是用线段树（区间树）做的，这道题还可以用暴力做。

但是用线段树耗时1200ms,时间复杂度很低。而暴力至少得8000ms,

但是这道题提交了很多遍，但都是wrong ansers ,今天再重新交了一遍，之所以wrong 是因为杭电用%I64d 输入输出。而我用的是long long 

坑......................

附上代码：

    #include <stdio.h>
    #include <string.h>
    #include <cmath>
    #include <iostream>
    typedef long long ll;
    using namespace std;

    const  int  maxn=101000;
    struct node
    {
        int l,r,cover;  // 这里的cover的值要么为0 要么为1 ，当cover==1的时候表示这个区间所有的值都相等
        ll inc;         //这个值的意思用于1操作和2操作时的记录，这样就不必要每次操作到叶子节点，时间复杂度能下去；
    }data[maxn*8];

    ll a[maxn+1];
    ll GCD(ll a,ll b)   //最大公约数公式
    {
      if(!b)return a;
      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].inc=0;
        data[k].cover=0;
        if (l==r)
        {
          data[k].inc=a[l];
          data[k].cover=1;
          return ;
        }
        mid=(l+r)/2;
        build(l,mid,k*2);
        build(mid+1,r,k*2+1);
    }

    void change(int k,int l,int r,ll x) //1 操作。。。。
    {
        int mid;
        if (data[k].l==l&&data[k].r==r)  //找到这个区间后，把要更改的x值用inc记录，然后cover==1,表示这个区间内所有数都为x了
        {
            data[k].inc=x;
            data[k].cover=1;
            return ;
        }
        if(data[k].cover==1)  //这一步的意思是，当所要更改的区间是子区间，那么这个cover等于1就被破坏了，那么我们将这个节点的属性转移给左右节点
        {
          data[2*k].cover=data[k].cover;
          data[2*k+1].cover=data[k].cover;
          data[2*k].inc=data[k].inc;
          data[2*k+1].inc=data[k].inc;
          data[k].cover=0;
          data[k].inc=0;
        }
        mid=(data[k].l+data[k].r)/2;
        if(r<=mid) change(2*k,l,r,x);
        else if (l>mid) change(2*k+1,l,r,x);
        else {change(2*k,l,mid,x); change(2*k+1,mid+1,r,x);}
    }
    void gcd(int k,int l,int r,ll x)   //2操作
    {
     int mid;
     if(data[k].l==l&&data[k].r==r&&data[k].cover==1)
      {
         if(data[k].inc>x)
         {
            data[k].inc=GCD(data[k].inc,x);
            data[k].cover=1;
         }
         return;
      }
       if(data[k].cover==1) //同理如果所要更改的区间是子区间，那么这个cover=1就被破坏了，所以要属性转移
        {
          data[2*k].cover=data[k].cover;
          data[2*k+1].cover=data[k].cover;
          data[2*k].inc=data[k].inc;
          data[2*k+1].inc=data[k].inc;
          data[k].cover=0;
          data[k].inc=0;
        }
     mid=(data[k].l+data[k].r)/2;
     if (r<=mid)gcd(2*k,l,r,x);
     else if(l>mid)gcd(2*k+1,l,r,x);
     else
        {
          gcd(2*k,l,mid,x);
          gcd(2*k+1,mid+1,r,x);
        }
    }

    void sove(int k)   //这个函数是用于最后输出处理的，如果某个节点的cover值等于1,那么就让这个节点以下的所有叶子节点的值都等于inc
    {
     if(data[k].cover==1)
     {
       for(int i=data[k].l;i<=data[k].r;i++)a[i]=data[k].inc;
       return ;
     }
     sove(2*k);
     sove(2*k+1);
    }
    int main()
    {
     int T,n,m,op,l,r;
     ll x;
     cin>>T;
     while(T--)
     {
      memset(a,0,sizeof(a));
      scanf("%d",&n);
      for(int i=1;i<=n;i++)scanf("%I64d",&a[i]);  //以后要记住输入也得用%I64d
      build(1,n,1);
      scanf("%d",&m);
      while(m--)
      {
       scanf("%d%d%d%I64d",&op,&l,&r,&x);
       if(op==1)change(1,l,r,x);
       else if(op==2)gcd(1,l,r,x);
      }
      sove(1);
      for(int i=1;i<=n;i++)
        printf("%I64d ",a[i]);  //输出用I64d；
      printf("\n");
     }
     return 0;
    }