Smiling & Weeping

　　　　　　　　　　　　　　　　　　　---- 我多想痛哭一场。

　　　　　　　　　　　　　　　　　　　　　然而我觉得这颗心，

　　　　　　　　　　　　　　　　　　　 　　比沙漠还要干燥。

题目链接：Problem - 4553 (hdu.edu.cn)

题目大意：就是一道区间合并的模板

Talk is cheap , show me the code

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<cstdio>
  5 #include<algorithm>
  6 using namespace std;
  7 const int maxn = 100010;
  8 #define ls(p) p<<1
  9 #define rs(p) p<<1|1
 10 #define lson L,R,pl,mid,ls(p)
 11 #define rson L,R,mid+1,pr,rs(p) 
 12 int tree1[maxn<<2] , pre1[maxn<<2] , suf1[maxn<<2];
 13 int tree2[maxn<<2] , pre2[maxn<<2] , suf2[maxn<<2];
 14 int tag1[maxn<<2] , tag2[maxn<<2];
 15 int max(int x , int y){
 16     return x>y ? x : y;
 17 }
 18 void push_up1(int p , int len){
 19     pre1[p] = pre1[ls(p)];
 20     suf1[p] = suf1[rs(p)];
 21     if(pre1[ls(p)] == (len-(len>>1))) pre1[p] = pre1[ls(p)]+pre1[rs(p)];
 22     if(suf1[rs(p)] == (len>>1)) suf1[p] = suf1[rs(p)]+suf1[ls(p)];
 23     tree1[p] = max(suf1[ls(p)]+pre1[rs(p)] , max(tree1[ls(p)] , tree1[rs(p)]));
 24 }
 25 void push_up2(int p , int len){
 26     pre2[p] = pre2[ls(p)];
 27     suf2[p] = suf2[rs(p)];
 28     if(pre2[ls(p)] == (len-(len>>1))) pre2[p] = pre2[ls(p)]+pre2[rs(p)];
 29     if(suf2[rs(p)] == (len>>1)) suf2[p] = suf2[rs(p)]+suf2[ls(p)];
 30     tree2[p] = max(suf2[ls(p)]+pre2[rs(p)] , max(tree2[ls(p)] , tree2[rs(p)]));
 31 }
 32 void build(int p , int pl , int pr){
 33     tag1[p] = tag2[p] = -1; 
 34     if(pl == pr){tree1[p] = tree2[p] = pre1[p] = pre2[p] = suf1[p] = suf2[p] = 1; return ; }
 35     int mid = pl+pr >> 1;
 36     int len = pr-pl+1;
 37     build(ls(p) , pl , mid);
 38     build(rs(p) , mid+1 , pr);
 39     push_up1(p,len);
 40     push_up2(p,len);
 41 }
 42 void change1(int p , int pl , int pr, int d){
 43     tree1[p] = suf1[p] = pre1[p] = d*(pr-pl+1);
 44     tag1[p] = d;
 45 }
 46 void change2(int p , int pl , int pr, int d){
 47     tree2[p] = suf2[p] = pre2[p] = d*(pr-pl+1);
 48     tag2[p] = d;
 49 }
 50 void push_down1(int p , int pl ,int pr){
 51     if(tag1[p] != -1){
 52         int mid = pl+pr >> 1;
 53         change1(ls(p) , pl , mid , tag1[p]);
 54         change1(rs(p) , mid+1 , pr , tag1[p]);
 55         tag1[p] = -1;
 56     }
 57 }
 58 void push_down2(int p , int pl , int pr){
 59     if(tag2[p]!=-1){
 60         int mid = pl+pr >> 1;
 61         change2(ls(p) , pl , mid , tag2[p]);
 62         change2(rs(p) , mid+1 , pr, tag2[p]);
 63         tag2[p] = -1;
 64     }
 65 }
 66 // 1代表有空，0代表占位
 67 void update1(int L , int R , int pl , int pr, int p , int d){
 68     if(L <= pl && pr <= R){
 69         tag1[p] = d;
 70         tree1[p] = pre1[p] = suf1[p] = d*(pr-pl+1);
 71         return ;
 72     }
 73     push_down1(p,pl,pr);
 74     int mid = pl+pr >> 1;
 75     int len = pr-pl+1;
 76     if(L <= mid) update1(L,R,pl,mid,ls(p),d);
 77     if(R > mid)  update1(L,R,mid+1,pr,rs(p),d);
 78     push_up1(p,len);
 79 }
 80 void update2(int L , int R , int pl , int pr, int p , int d){
 81     if(L <= pl && pr <= R){
 82         tag2[p] = d;
 83         tree2[p] = pre2[p] = suf2[p] = d*(pr-pl+1);
 84         return ;
 85     }
 86     push_down2(p,pl,pr);
 87     int mid = pl+pr >> 1;
 88     int len = pr-pl+1;
 89     if(L <= mid) update2(L,R,pl,mid,ls(p),d);
 90     if(R > mid)  update2(L,R,mid+1,pr,rs(p),d);
 91     push_up2(p,len);
 92 }
 93 int query1(int p , int pl , int pr , int qt){
 94     if(tree1[p] < qt){
 95         return -1;
 96     }
 97     if(pl == pr){
 98         return pl;
 99     }
100     push_down1(p,pl,pr);
101     int mid = pl+pr >> 1;
102     if(tree1[ls(p)] >= qt) return query1(ls(p) , pl , mid , qt);
103     else if(suf1[ls(p)]+pre1[rs(p)] >= qt) return mid-suf1[ls(p)]+1;
104     else return query1(rs(p) , mid+1 , pr , qt);
105 }
106 int query2(int p , int pl , int pr , int qt){
107     if(tree2[p] < qt){
108         return -1;
109     }
110     if(pl == pr && qt==1){
111         return pl;
112     }
113     push_down2(p,pl,pr);
114     int mid = pl+pr >> 1;
115     if(tree2[ls(p)] >= qt) return query2(ls(p) , pl , mid , qt);
116     else if(suf2[ls(p)]+pre2[rs(p)] >= qt) return mid-suf2[ls(p)]+1;
117     else return query2(rs(p) , mid+1 , pr , qt);
118 }
119 int T , n , t , cnt;
120 int main()
121 {
122     scanf("%d",&T);
123     while(T--){
124         printf("Case %d:\n",++cnt);
125         scanf("%d%d",&t,&n);
126         build(1,1,t);
127         char op[10];
128         int qt , L , R;
129         for(int i = 1; i <= n; i++){
130             scanf("%s",op);
131             if(op[0] == 'D'){
132                 scanf("%d",&qt);
133                 int ind;
134                 if(qt > t || tree2[1] < qt) ind = -1;
135                 else ind = query2(1,1,t,qt);
136                 if(ind == -1){
137                     printf("fly with yourself\n");
138                     continue;
139                 }
140                 update2(ind,ind+qt-1,1,t,1,0);
141                 printf("%d,let's fly\n",ind);
142             }
143             else if(op[0] == 'N'){
144                 scanf("%d",&qt);
145                 int ind;
146                 if(qt > t || tree2[1] < qt) ind = -1;
147                 else ind = query2(1,1,t,qt);
148                 if(ind != -1){
149                     update1(ind,ind+qt-1,1,t,1,0);
150                     update2(ind,ind+qt-1,1,t,1,0);
151                     printf("%d,don't put my gezi\n",ind);
152                 }
153                 else{
154                     if(qt > t || tree1[1] < qt) ind = -1;
155                     else
156                         ind = query1(1,1,t,qt);
157                     if(ind == -1){
158                         printf("wait for me\n");
159                     }
160                     else{
161                         update1(ind,ind+qt-1,1,t,1,0);
162                         update2(ind,ind+qt-1,1,t,1,0);
163                         printf("%d,don't put my gezi\n",ind);
164                     }
165                 }
166             }
167             else if(op[0] == 'S'){
168                 scanf("%d%d",&L,&R);
169                 update1(L,R,1,t,1,1);
170                 update2(L,R,1,t,1,1);
171                 printf("I am the hope of chinese chengxuyuan!!\n");
172             }
173         }
174     }
175     return 0;
176 }

所谓无底深渊，下去，也是前程万丈。

文章到此结束，我们下次再见