首页 > 代码库 > HDU 4902 Nice boat 成段线段树
HDU 4902 Nice boat 成段线段树
操作1 的时候标记deng[rt]表示下面一段数都是与当前节点的值相同
下次操作2时直接对有deng标记的节点gcd更新
(可能还可以更简单)
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <malloc.h> #include <ctype.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> using namespace std; #define MAXN 11111 #include <queue> #include <vector> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define mid (r+l)>>1 const int maxn=100010; int sum[maxn<<2] ,col[maxn<<2],deng[maxn<<2]; int gcd(int a,int b) { while(1) { if(b==0) return a; int t=b; b=a%b; a=t; } } void pushup(int rt) { sum[rt]=max(sum[rt<<1],sum[rt<<1|1]); } void pushdown(int rt){ if(col[rt]) { col[rt<<1]=col[rt<<1|1]=col[rt]; sum[rt<<1]=sum[rt<<1|1]=sum[rt]; col[rt]=0; } if(deng[rt]) { deng[rt<<1]=deng[rt<<1|1]=deng[rt]; sum[rt<<1]=sum[rt<<1|1]=sum[rt]; deng[rt]=0; } } void build(int l,int r,int rt) { col[rt]=deng[rt]=0; if(r==l) { scanf("%d",&sum[rt]); return; } int m=mid; build(lson); build(rson); pushup(rt); } void out(int l,int r,int rt) { if(r==l) { printf("%d ",sum[rt]); return; } pushdown(rt); int m=mid; out(lson); out(rson); } void update1(int L,int R,int num,int l,int r,int rt) { if(L<=l&&r<=R) { col[rt]=1; deng[rt]=1; sum[rt]=num; return ; } pushdown(rt); int m=mid; if(L<=m) update1(L,R,num,lson); if(m<R) update1(L,R,num,rson); pushup(rt); } void update2(int L,int R,int num,int l,int r,int rt) { if(sum[rt]<num) return ; if(deng[rt]&&L<=l&&r<=R) { sum[rt]=gcd(sum[rt],num); col[rt]=1; deng[rt]=0; return ; } if(l==r) { sum[rt]=gcd(sum[rt],num); return ; } pushdown(rt); int m=mid; if(L<=m) update2(L,R,num,lson); if(m<R) update2(L,R,num,rson); pushup(rt); } int main() { int t,n,q; // freopen("in.txt","r",stdin); scanf("%d",&t); while(t--) { scanf("%d",&n); build(1,n,1); scanf("%d",&q); int op,l,r,x; for(int i=0;i<q;i++) { scanf("%d%d%d%d",&op,&l,&r,&x); if(op==1) update1(l,r,x,1,n,1); else update2(l,r,x,1,n,1); } out(1,n,1); printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。