首页 > 代码库 > hdu 4902 Nice boat
hdu 4902 Nice boat
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。