首页 > 代码库 > hdu 5023 (线段树 )
hdu 5023 (线段树 )
这道题当时没有做出来,状态不会保存。原来可已用二进制保存状态,做的题太少,暴漏的问题太多了;这么简单的东西,,,,,也不会保存
这道题就是每一次维护区间的和,也就是把它的30种颜色用二进制保存下来。也就1<<30 可以用long long 保存下来
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxx 1111111 #define lson L,m,rt<<1 #define rson m+1,R,rt<<1|1 typedef long long ll; int cnt; ll add[maxx<<2]; int ans[50]; ll sum[maxx<<2]; int n,m; void pushup(int rt){ sum[rt]=sum[rt<<1]|sum[rt<<1|1]; } void pushdown(int rt){ if(add[rt]){ add[rt<<1]=add[rt]; add[rt<<1|1]=add[rt]; sum[rt<<1]=add[rt]; sum[rt<<1|1]=add[rt]; add[rt]=0; } } void build(int L,int R,int rt){ add[rt]=0; if(L==R){ sum[rt]=2;(颜色2相当于1<<1,那么颜色1就1<<0) return ; } int m=(L+R)>>1; build(lson); build(rson); pushup(rt); } void update(int l,int r,int c,int L,int R,int rt){ if(l<=L&&R<=r){ add[rt]=1<<(c-1); sum[rt]=1<<(c-1); return ; } pushdown(rt); int m=(L+R)>>1; if(l<=m) update(l,r,c,lson); if(m<r) update(l,r,c,rson); pushup(rt); } ll query(int l,int r,int L,int R,int rt){ ll ret=0; if(l<=L&&r>=R){ return sum[rt]; } pushdown(rt); int m=(L+R)>>1; if(l<=m) ret|=query(l,r,lson); if(m<r) ret|=query(l,r,rson); return ret; } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ if(n==0&&m==0) break; build(1,n,1); while(m--){ char op[2]; scanf("%s",op); int a,b,c; if(op[0]=='P'){ scanf("%d%d%d",&a,&b,&c); update(a,b,c,1,n,1); } else { memset(ans,0,sizeof(ans)); cnt=0; scanf("%d%d",&a,&b); ll r=query(a,b,1,n,1); for(int i=0;i<30;i++){ if(r&(1<<i)){ ans[cnt++]=i+1; } } int flag =0; for(int i=0;i<cnt;i++){ if(flag){ printf(" %d",ans[i]); } else { printf("%d",ans[i]); flag =1 ; } } puts(""); } } } }
hdu 5023 (线段树 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。