首页 > 代码库 > 多校第4场 HDU 4902 Nice boat 线段树
多校第4场 HDU 4902 Nice boat 线段树
思路:这题比赛的时候宝哥说的思路我觉得对的,就是当是2操作的时候,先把数放到数组里,最后查询输出的时候再统一计算,不过那时敲得烂死了,debug了两天,靠……
上午写的vector在pushDown的时候又忘了clear了,然后MLE了一早上,尼玛,还以为用的数组太大超了,然后又改成结构体,还是MLE,最后把别人的代码交上去发现没MLE,疯了一中午,最后无聊的时候才发现这个错误,尼玛……发现自己调试怎么变得这么弱了呢……
还有一个需要注意的问题是1与2操作的处理上比较容易出错,这也是我WA了一下午的原因……唉……
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<set> #include<cmath> #include<bitset> #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define INF 510010 #define maxn 400010 using namespace std; typedef long long ll; typedef unsigned long long ull; int key[maxn]; short lazy[maxn]; vector<int>ve[maxn]; int n,m; int gcd(int a,int b) { return !b?a:gcd(b,a%b); } void pushdown(int i,int l,int r) { if(l==r) return ; if(lazy[i]==1) { key[i<<1]=key[i<<1|1]=key[i]; lazy[i<<1]=lazy[i<<1|1]=lazy[i]; ve[i<<1]=ve[i<<1|1]=ve[i]; lazy[i]=0; } else { for(int j=0; j<ve[i].size(); j++) { ve[i<<1].push_back(ve[i][j]); ve[i<<1|1].push_back(ve[i][j]); } } ve[i].clear(); } void update(int i,int l,int r,int L,int R,int v,int c) { pushdown(i,l,r); if(L==l&&r==R) { if(c==1) lazy[i]=1,key[i]=v,ve[i].clear(); else ve[i].push_back(v); return ; } int mid=(l+r)>>1; if(R<=mid) update(lson,L,R,v,c); else if(L>mid) update(rson,L,R,v,c); else { update(lson,L,mid,v,c); update(rson,mid+1,R,v,c); } } void query(int i,int l,int r) { pushdown(i,l,r); if(l==r) { for(int j=0; j<ve[i].size(); j++) { if(key[i]>ve[i][j]) key[i]=gcd(key[i],ve[i][j]); if(key[i]==1) break; } printf("%d ",key[i]); return ; } int mid=(l+r)>>1; query(lson); query(rson); } void build(int i,int l,int r) { key[i]=lazy[i]=0; ve[i].clear(); if(l==r) { scanf("%d",&key[i]); return ; } int mid=(l+r)>>1; build(lson); build(rson); } void debug(int i,int l,int r ) { printf("结点:%3d 范围:%3d~~%3d 传值:%11d 标记:%3d\n",i,l,r,key[i],lazy[i]); if(l==r) return ; int mid=(l+r)>>1; debug(lson); debug(rson); } int main() { //freopen("test.txt","r",stdin); int t; cin>>t; while(t--) { int i; scanf("%d",&n); build(1,1,n); scanf("%d",&m); while(m--) { int c,l,r,x; scanf("%d%d%d%d",&c,&l,&r,&x); update(1,1,n,l,r,x,c); //debug(1,1,n); //puts(""); } query(1,1,n); puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。