Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1038 Accepted Submission(s):
465
最后输出变化后的一组数。
用线段树写的，主要是利用mark标记 ，全部变成x的话直接把这段变成x，然后加个tree[i].mark就行了，如果往下更新，要把标记和数一起往下传具体看pushdown函数，查询的时候如果延迟标记存在的话直接把这一段输出，因为标记存在这一段肯定是相同的数。。
第2步操作主要是，如果什么已经标记了则全都是相同的数，比较一下求公约数。
如果没标记就要tree[i].left==tree[i].right。比较一下这个数，就行了。
#include<iostream> #include<cstring> #include<cstdio> const int maxx=100010; using namespace std; int a[2*maxx]; struct tree { int right,left; int mark,num; }tree[4*maxx]; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } void build(int i,int left,int right) { tree[i].left=left; tree[i].right=right; tree[i].mark=0; if(left==right) { tree[i].num=a[left]; return ; } int mid=(left+right)/2; build(2*i,left,mid); build(2*i+1,mid+1,right); } void pushdown(int r) { if(tree[r].mark) { tree[2*r].num=tree[2*r+1].num=tree[r].num; tree[2*r].mark=tree[2*r+1].mark=tree[r].mark; tree[r].mark=0; } } void update(int r,int i,int j,int k) { int mid; mid=(tree[r].left+tree[r].right)/2; if(tree[r].left>=i&&tree[r].right<=j) { tree[r].num=k; tree[r].mark=1; return; } pushdown(r);//向下传递。 if(i>mid) update(2*r+1,i,j,k); else if(j<=mid) update(r*2,i,j,k); else { update(2*r,i,mid,k); update(2*r+1,mid+1,j,k); } } void change(int r,int i,int j,int x) { int mid; mid=(tree[r].left+tree[r].right)/2; if(tree[r].mark) { if(i<=tree[r].left&&j>=tree[r].right) { if(tree[r].num<=x) return ; else { tree[r].num=gcd(tree[r].num,x); return ; } } } if(tree[r].left==tree[r].right) { if(tree[r].num>x) { tree[r].num=gcd(tree[r].num,x); return ; } else return ; } pushdown(r); if(i>mid) change(2*r+1,i,j,x); else if(j<=mid) change(r*2,i,j,x); else { change(2*r,i,mid,x); change(2*r+1,mid+1,j,x); } } void prit(int r) { int i; if(tree[r].left==tree[r].right) { printf("%d ",tree[r].num); return ; }// if(tree[r].mark) { for(i=tree[r].left;i<=tree[r].right;i++) printf("%d ",tree[r].num); return; } prit(2*r); prit(2*r+1); } int main() { int t,n,x,y,m,k,v,i; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); build(1,1,n); for(i=1;i<=m;i++) { scanf("%d",&k); if(k==1) { scanf("%d%d%d",&x,&y,&v); update(1,x,y,v); } else { scanf("%d%d%d",&x,&y,&v); change(1,x,y,v); } } prit(1); printf("\n"); } return 0; }
HDU-4902 Nice boat,布布扣,bubuko.com
原文：http://www.cnblogs.com/cancangood/p/3885751.html