首页 > 代码库 > HDU 5023 (2014广州网络赛 线段树)
HDU 5023 (2014广州网络赛 线段树)
解题思路:
有两种操作,第一种是将区间 a 到 b 染成颜色 c ,第二种是询问区间 a 到 b 内的颜色,按照顺序输出。 注意到颜色只有三十种,因此我们可以用二进制数表示颜色,通过位运算来操作。
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <vector> #include <queue> #include <set> #include <map> #include <stack> #define LL long long #define FOR(i,x,y) for(int i=x;i<=y;i++) #define rFOR(i,x,y) for(int i=x;i>=y;i--) #define rep(i,x,y) for(int i=x;i<y;i++) #define rrep(i,x,y) for(int i=x;i>y;i--) #define lson l , m , rt<<1 #define rson m + 1 , r , rt<<1|1 using namespace std; const int maxn = 1111111; int col[maxn<<2]; int add[maxn<<2]; void pushup(int rt) { col[rt] = col[rt<<1] | col[rt<<1|1]; } void pushdown(int rt) { if(add[rt]) { add[rt<<1] = add[rt<<1|1] = add[rt]; col[rt<<1] = col[rt<<1|1] = col[rt]; add[rt] = 0; } } void build(int l , int r , int rt) { col[rt] = 2; add[rt] = 1; if(l == r) 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; col[rt] = c; 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); } int res; void query(int L , int R , int l , int r , int rt) { if(L <= l && r <= R) { res |= col[rt]; return ; } if(add[rt]) { res |= col[rt]; return ; } int m = (l + r) >> 1; if(L <= m) query(L , R , lson); if(m < R) query(L , R , rson); } int ans[maxn]; int main() { int N , M ; while(scanf("%d%d",&N,&M)!=EOF) { if(N == 0 && M == 0) break; build(1 , N , 1); int a , b , c; char ch; while(M--) { cin>>ch; if(ch == 'P') { scanf("%d%d%d",&a,&b,&c); if(a > b) swap(a , b); update(a , b , 1<<(c-1) , 1 , N , 1); } else { scanf("%d%d",&a,&b); if(a > b) swap(a , b); res = 0; int n = 0; query(a , b , 1 , N , 1); for(int i=0;i<30;i++) { if(res & (1<<i)) ans[n++] = i + 1; } for(int i=0;i<n-1;i++) printf("%d ",ans[i]); printf("%d\n",ans[n-1]); } } } return 0; }
HDU 5023 (2014广州网络赛 线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。