首页 > 代码库 > hdu 4902 Nice boat

hdu 4902 Nice boat

2024-07-15 06:50:53   220人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4902

题意：给你n个数，q个操作，操作有两种：1，在[L,R]区间内的数直接变为x。2，在[L,R]区间内比x大的数变成gcd(A[i],x);最后输出n个数。

  1 #include <cstdio>  2 #include <cstring>  3 #include <cmath>  4 #include <cstdlib>  5 #include <algorithm>  6 #define maxn 200000  7 using namespace std;  8   9 int t,n,q; 10 __int64 a[maxn]; 11  12 struct node 13 { 14     int l,r; 15     __int64 num; 16     bool flag; 17 }tree[maxn*4]; 18  19 __int64 gcd(__int64 a,__int64 b) 20 { 21     return b==0?a:gcd(b,a%b); 22 } 23  24 void build(int i,int l,int r) 25 { 26     tree[i].l=l; tree[i].r=r; 27     tree[i].flag=false; 28     if(l==r) 29     { 30         tree[i].num=a[l]; 31         tree[i].flag=true; 32         return ; 33     } 34     int mid=(l+r)>>1; 35     build(i<<1,l,mid); 36     build(i<<1|1,mid+1,r); 37 } 38  39 void update(int i,int l,int r,int x,int flag) 40 { 41     if(tree[i].l>=l&&tree[i].r<=r) 42     { 43         if(flag==1) 44         { 45             tree[i].num=x; 46             tree[i].flag=true; 47             return; 48         } 49         else if(flag==2&&tree[i].flag) 50         { 51             if(tree[i].num>x) 52             { 53                 tree[i].num=gcd(tree[i].num,x); 54             } 55             return ; 56         } 57     } 58     if(tree[i].flag) 59     { 60         tree[i<<1].num=tree[i<<1|1].num=tree[i].num; 61         tree[i<<1].flag=tree[i<<1|1].flag=tree[i].flag; 62         tree[i].flag=false; 63     } 64     int mid=(tree[i].l+tree[i].r)>>1; 65     if(r<=mid) 66         update(i<<1,l,r,x,flag); 67     else if(l>mid) 68         update(i<<1|1,l,r,x,flag); 69     else 70     { 71         update(i<<1,l,mid,x,flag); 72         update(i<<1|1,mid+1,r,x,flag); 73     } 74 } 75  76 void print(int i,int l,int r) 77 { 78      if(tree[i].flag) 79      { 80          for(int j=l; j<=r; j++) 81          { 82              printf("%I64d ",tree[i].num); 83          } 84          return ; 85      } 86      int mid=(l+r)>>1; 87      print(i<<1,l,mid); 88      print(i<<1|1,mid+1,r); 89 } 90  91 int main() 92 { 93     scanf("%d",&t); 94     while(t--) 95     { 96         scanf("%d",&n); 97         for(int i=1; i<=n; i++) 98         { 99             scanf("%I64d",&a[i]);100         }101         build(1,1,n);102         scanf("%d",&q);103         for(int i=1; i<=q; i++)104         {105             int t1,l,r;106             __int64 x;107             scanf("%d%d%d%I64d",&t1,&l,&r,&x);108             update(1,l,r,x,t1);109         }110         print(1,1,n);111         printf("\n");112     }113     return 0;114 }
View Code

 


联系
我们