首页 > 代码库 > hdu - 5023 - A Corrupt Mayor's Performance Art（线段树）

hdu - 5023 - A Corrupt Mayor's Performance Art（线段树）

2024-07-24 09:41:50   211人阅读

题目原文废话太多太多太多，我就不copyandpaste到这里啦。。发个链接吧题目

题目意思就是：P  l  r  c  将区间 [l ，r]上的颜色变成c    Q  l r 就是打印出区间[l,r]中所有的颜色，并且要升序排列出来，注意最坑的就是各个区间的颜色初始化为2，这个条件竟然夹杂在那又长又臭的题目的某个角落里面！！

比赛的时候思路是有的，并且也能想到用set来撸，哎，对set的用法太挫逼了，写线段树又写得太挫逼了，后来补回这道题的时候，才发现其实是一道非常常规的线段树，所以最近给自己留了20道线段树慢慢刷，主要是能够更加熟练地写出线段树的模板，因为我发觉之前只是看得懂别人写的线段树的代码，却很少完全靠自己去敲出来，今天在补这道题的时候依然wa了很多次，最终才发现在query的那里忘记PushDown了  QAQ，废话少说 直接贴代码：

   1 #include <cstdio>

 2 #include <iostream>
 3 #include <queue>
 4 #include <set>
 5 #include <cstring>
 6 using namespace std;
 7 #define lson l,m,rt<<1
 8 #define rson m+1,r,rt<<1|1
 9 const int maxn = 1001111;
10 set<int> ans;
11 int SIZE;
12 int sum[maxn<<2];
13 void PushDown(int rt){
14     if(sum[rt]){
15         sum[rt<<1] = sum[rt];
16         sum[rt<<1|1] = sum[rt];
17         sum[rt] = 0;
18     }
19 }
20 void build(int l,int r,int rt){
21     if(l == r){
22         sum[rt] = 2;return;
23     }
24     int m = (l + r) >>1;
25     build(lson);
26     build(rson);
27     return ;
28 }
29 void update(int L,int R,int c,int l,int r,int rt){
30     if(L <= l&&r <= R){
31         sum[rt] = c;
32         return ;
33     }
34     int m = (l + r)>>1;
35     PushDown(rt);
36     if(L <= m) update(L,R,c,lson);
37 
38     if(m <  R) update(L,R,c,rson);
39     return ;
40 }
41 void query(int L,int R,int l,int r,int rt){
42     //if(rt > SIZE) return;
43     if(L <= l&&r <= R&&sum[rt]){
44         ans.insert(sum[rt]);
45         return ;
46     }
47     PushDown(rt);
48     int m = (l + r)>>1;
49     if(L <= m) query( L, R,lson);
50     if(m <  R) query( L, R,rson);
51     return;
52 }
53 void print(){
54     set<int>::iterator it;
55     it = ans.begin();
56     cout<<*it;
57     ans.erase(it);
58     for(it = ans.begin();it != ans.end();++it)
59         printf(" %d",*it);
60         puts("");
61 }
62 void print_debug(){  //此为调试代码，请忽略==|||
63     cout<<"sum: "<<endl;
64     for(int i = 1;i <= 20;i++)
65         cout<<sum[i]<<" ";
66         puts("");
67 }
68 int main(){
69     int N,Q,a,b,c;
70     char ope[3];
71     while(~scanf("%d%d",&N,&Q)&&(N+Q)){
72         SIZE = (N+1)*N/2;
73         memset(sum,0,sizeof(sum));
74         build(1,N,1);
75         while(Q--){
76             scanf("%s",ope);
77             if(ope[0] == ‘Q‘){
78                 scanf("%d%d",&a,&b);
79                 ans.clear();
80                 query(a,b,1,N,1);
81                 print();
82             }else{
83                 scanf("%d%d%d",&a,&b,&c);
84                 update(a,b,c,1,N,1);
85                 //print_debug();
86             }
87         }
88     }
89     return 0;
90 }

 

然后我又看到了另一份比较好玩的代码，是通过巧妙的位移运算来表示的，恩 感觉挺好的   http://blog.csdn.net/u012860063/article/details/39434665

 

hdu - 5023 - A Corrupt Mayor's Performance Art（线段树）


联系
我们