区间合并
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 }
所谓无底深渊，下去，也是前程万丈。
文章到此结束，我们下次再见