首页 > 代码库 > hdu 5023 A Corrupt Mayor's Performance Art(线段树)
hdu 5023 A Corrupt Mayor's Performance Art(线段树)
题目链接
题意：有一个长度 n 的序列，初始染色2，有两种操作，P x ,y ,z,区间x---y染色为z，另一种Q x，y，查询区间 x -- y 有几种颜色，并输出，会覆盖
分析：lz[]为0，表示下面颜色不统一，统一是>0; f[]表示该节点下有多少种颜色，是30种颜色的二进制表示。
刚开始做时，用1<<i 不对，不知道为什么，int的范围按理不会超的。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #define LL __int64 8 #define lson l, (l+r)/2, 2*rt 9 #define rson (l+r)/2+1, r, 2*rt+110 const int maxn = 1000000+10;11 using namespace std;12 int lz[4*maxn], f[4*maxn], x;13 void pushdown(int rt)14 {15 if(lz[rt]!=0)16 {17 lz[2*rt] = lz[rt];18 f[2*rt] = (1<<(lz[rt]-1));19 lz[2*rt+1] = lz[rt];20 f[2*rt+1] = (1<<(lz[rt]-1));21 lz[rt] = 0;22 }23 }24 void pushup(int rt)25 {26 f[rt] = (f[2*rt]|f[2*rt+1]);27 }28 void update(int ll, int rr, int c, int l, int r, int rt)29 {30 if(ll>r) return;31 if(rr<l) return;32 if(ll<=l && rr>=r)33 {34 lz[rt] = c;35 f[rt] = (1<<(c-1));36 return;37 }38 pushdown(rt);39 update(ll, rr, c, lson);40 update(ll, rr, c, rson);41 pushup(rt);42 }43 void query(int ll, int rr, int l, int r, int rt)44 {45 if(ll>r) return;46 if(rr<l) return;47 if(ll<=l && rr>=r)48 {49 x |= f[rt];50 return;51 }52 pushdown(rt);53 query(ll, rr, lson);54 query(ll, rr, rson);55 }56 int main()57 {58 int n, m, i;59 int a, b, c, sum;60 char ch;61 while(~scanf("%d%d", &n, &m))62 {63 if(n==0 && m==0) break;64 lz[1] = 2; f[1] = 2; //相当于初始化65 while(m--)66 {67 getchar();68 scanf("%c", &ch);69 if(ch==‘P‘)70 {71 scanf("%d%d%d", &a, &b, &c);72 update(a, b, c, 1, n, 1);73 }74 else75 {76 x = 0;77 scanf("%d%d", &a, &b);78 query(a, b, 1, n, 1);79 sum = 0;80 81 for(i = 1; i <= 30; i++)82 {83 if(x&(1<<(i-1)))84 {85 if(sum==0)86 printf("%d", i);87 else88 printf(" %d", i);89 sum++;90 }91 }92 printf("\n");93 }94 }95 }96 return 0;97 }
hdu 5023 A Corrupt Mayor's Performance Art(线段树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。