首页 > 代码库 > hdu4902Nice boat线段树区间更新
hdu4902Nice boat线段树区间更新
#include<iostream> #include<cmath> using namespace std; int n; bool flag; struct node { int mx,l,r,m,mn; }tree[400000]; void create(int l,int r,int k) { tree[k].l=l; tree[k].r=r; tree[k].m=(l+r)>>1; if(l==r) { cin>>tree[k].mx; tree[k].mn=tree[k].mx; return; } create(l,tree[k].m,k<<1); create(tree[k].m+1,r,k<<1|1); tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx); tree[k].mn=min(tree[k<<1].mn,tree[k<<1|1].mn); } int gcd(int a,int b) { if(b==0) return a; gcd(b,a%b); } void up(int l,int r,int w,int k) { if(l==tree[k].l&&r==tree[k].r) { if(flag&&tree[k].mx>w) { if(tree[k].mn==tree[k].mx) tree[k].mx=tree[k].mn=gcd(w,tree[k].mx); else { up(l,tree[k].m,w,k<<1); up(tree[k].m+1,r,w,k<<1|1); } } else if(!flag) tree[k].mx=tree[k].mn=w; return; } if(tree[k].mx==tree[k].mn) { tree[k<<1].mx=tree[k<<1|1].mx=tree[k].mx; tree[k<<1].mn=tree[k<<1|1].mn=tree[k].mn; } if(r<=tree[k].m) up(l,r,w,k<<1); else if(l>tree[k].m) up(l,r,w,k<<1|1); else { up(l,tree[k].m,w,k<<1); up(tree[k].m+1,r,w,k<<1|1); } tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx); tree[k].mn=min(tree[k<<1].mn,tree[k<<1|1].mn); } void find(int no,int k) { if(no==tree[k].l&&tree[k].mx==tree[k].mn) { for(int i=tree[k].l;i<=tree[k].r;i++) cout<<tree[k].mx<<" "; if(tree[k].r==n) cout<<endl; else find(tree[k].r+1,1); return; } if(no<=tree[k].m) find(no,k<<1); else find(no,k<<1|1); } int main() { int exp,i,tmp,q,l,r,t,w; cin>>exp; while(exp--) { cin>>n; create(1,n,1); cin>>q; while(q--) { cin>>t>>l>>r>>w; flag=t==1?0:1; up(l,r,w,1); } find(1,1); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。