题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2871
这个题目与线段树区间合并的模板题(链接：点这里)非常相似，就是复杂了一点；
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include<set> 8 #include 9 #include 10 #include 11 #include<string> 12 #define ll long long 13 #define ull unsigned long long 14 #define inf 0x3f3f3f3f 15 #define inff 0x7fffffff 16 using namespace std; 17 const int N = 50000 + 10; 18 const int M = 1000000 + 10; 19 const ll mod = 1e9 + 7; 20 21 struct node { 22 int lsum; 23 int rsum; 24 int sum; 25 int lazy; 26 int len; 27 }tree[N << 2]; 28 29 void PushUp(int rt) { 30 31 if (tree[rt << 1].sum == tree[rt << 1].len) { 32 tree[rt].lsum = tree[rt << 1].sum + tree[rt << 1 | 1].lsum; 33 } 34 else { 35 tree[rt].lsum = tree[rt << 1].lsum; 36 } 37 if (tree[rt << 1 | 1].sum == tree[rt << 1 | 1].len) { 38 tree[rt].rsum = tree[rt << 1 | 1].sum + tree[rt << 1].rsum; 39 } 40 else { 41 tree[rt].rsum = tree[rt << 1 | 1].rsum; 42 } 43 tree[rt].sum = tree[rt << 1].rsum + tree[rt << 1 | 1].lsum; 44 tree[rt].sum = max(tree[rt << 1].sum, tree[rt].sum); 45 tree[rt].sum = max(tree[rt << 1 | 1].sum, tree[rt].sum); 46 47 return; 48 } 49 50 void Build(int l, int r, int rt) { 51 52 tree[rt].len = r - l + 1; 53 if (l == r) { 54 tree[rt].sum = tree[rt].lsum = tree[rt].rsum = 1; 55 return; 56 } 57 int mid = (l + r) >> 1; 58 Build(l, mid, rt << 1); 59 Build(mid + 1, r, rt << 1 | 1); 60 PushUp(rt); 61 62 return; 63 } 64 65 void PushDown(int l, int r, int rt) { 66 67 if (tree[rt].lazy == 0) return; 68 int mid = (l + r) >> 1; 69 if (tree[rt].lazy == 1) { 70 tree[rt << 1].sum = tree[rt << 1].lsum = tree[rt << 1].rsum = 0; 71 tree[rt << 1 | 1].sum = tree[rt << 1 | 1].lsum = tree[rt << 1 | 1].rsum = 0; 72 tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = 1; 73 } 74 else { 75 tree[rt << 1].sum = tree[rt << 1].lsum = tree[rt << 1].rsum = mid - l + 1; 76 tree[rt << 1 | 1].sum = tree[rt << 1 | 1].lsum = tree[rt << 1 | 1].rsum = r - (mid + 1) + 1; 77 tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = 2; 78 } 79 tree[rt].lazy = 0; 80 81 return; 82 } 83 84 void Update_in(int L, int R, int l, int r, int rt) { 85 86 if (l >= L && r <= R) { 87 tree[rt].sum = tree[rt].lsum = tree[rt].rsum = 0; 88 tree[rt].lazy = 1; 89 return; 90 } 91 PushDown(l, r, rt); 92 int mid = (l + r) >> 1; 93 if (L <= mid) Update_in(L, R, l, mid, rt << 1); 94 if (R > mid) Update_in(L, R, mid + 1, r, rt << 1 | 1); 95 PushUp(rt); 96 97 return; 98 } 99 100 void Update_out(int L, int R, int l, int r, int rt) { 101 102 if (l >= L && r <= R) { 103 tree[rt].sum = tree[rt].lsum = tree[rt].rsum = r - l + 1; 104 tree[rt].lazy = 2; 105 return; 106 } 107 PushDown(l, r, rt); 108 int mid = (l + r) >> 1; 109 if (L <= mid) Update_out(L, R, l, mid, rt << 1); 110 if (R > mid) Update_out(L, R, mid + 1, r, rt << 1 | 1); 111 PushUp(rt); 112 113 return; 114 } 115 116 //void PointUpdate(int L, int l, int r, int rt) { 117 // 118 // if (l == r) { 119 // sum[rt]++; 120 // return; 121 // } 122 // int mid = (l + r) >> 1; 123 // if (L <= mid) PointUpdate(L, l, mid, rt << 1); 124 // else PointUpdate(L, mid + 1, r, rt << 1 | 1); 125 // PushUp(rt); 126 // 127 // return; 128 //} 129 130 int Query(int len, int l, int r, int rt) { 131 132 if (l == r) return l; 133 int mid = (l + r) >> 1; 134 PushDown(l, r, rt); 135 if (tree[rt << 1].sum >= len) { 136 return Query(len, l, mid, rt << 1); 137 } 138 if (tree[rt << 1].rsum + tree[rt << 1 | 1].lsum >= len) { 139 return mid - tree[rt << 1].rsum + 1; 140 } 141 if (tree[rt << 1 | 1].sum >= len) { 142 return Query(len, mid + 1, r, rt << 1 | 1); 143 } 144 145 return 0; 146 } 147 148 //int Query(int L, int R, int l, int r, int rt) { 149 // 150 // if (l >= L && r <= R) { 151 // return sum[rt]; 152 // } 153 // int mid = (l + r) >> 1; 154 // 155 // int ans = 0; 156 // if (L <= mid) ans += Query(L, R, l, mid, rt << 1); 157 // if (R > mid) ans += Query(L, R, mid + 1, r, rt << 1 | 1); 158 // 159 // return ans; 160 //} 161 162 struct section { 163 int st, end; 164 bool operator <(const section& b)const { 165 return st < b.st; 166 } 167 }; 168 169 vectorvec; 170 171 bool cmp(section a, section b) { 172 if (a.st <= b.st) return true; 173 else return false; 174 } 175 176 int FindPos(int x, int l, int r) { 177 178 int pos = -1; 179 int lx = l, rx = r; 180 while (lx <= rx) { 181 int mid = (lx + rx) >> 1; 182 if (x >= vec[mid].st) { 183 pos = mid; 184 lx = mid + 1; 185 } 186 else { 187 rx = mid - 1; 188 } 189 } 190 if (vec[pos].st > x || vec[pos].end < x) { 191 return -1; 192 } 193 else return pos; 194 } 195 196 int main() { 197 198 /*ios::sync_with_stdio(false); 199 cin.tie(0);*/ 200 int n, m; 201 while (~scanf("%d %d", &n, &m)) { 202 Build(1, n, 1); 203 for (int i = 1; i <= m; i++) { 204 char op[10]; 205 int x; 206 scanf("%s", op); 207 if (op[0] == 'N') { 208 scanf("%d", &x); 209 int pos = Query(x, 1, n, 1); 210 if (pos != 0) { 211 //vec.push_back({ pos,pos + x - 1 }); 212 section t; 213 t.st = pos, t.end = pos + x - 1; 214 vector::iterator it; 215 it = upper_bound(vec.begin(), vec.end(), t); 216 vec.insert(it, t); 217 Update_in(pos, pos + x - 1, 1, n, 1); 218 //cout << "New at " << pos << "\n"; 219 printf("New at %d\n", pos); 220 } 221 else printf("Reject New\n"); 222 //cout << "Reject New" << "\n"; 223 } 224 else if (op[0] == 'F') { 225 scanf("%d", &x); 226 //sort(vec.begin(), vec.end(), cmp); 227 int pos = -1; 228 //int pos = upper_bound(vec.begin(), vec.end(), x) - vec.begin(); 229 int l = 0, r = vec.size() - 1; 230 pos = FindPos(x, l, r); 231 if (pos == -1) { 232 //cout << "Reject Free" << "\n"; 233 printf("Reject Free\n"); 234 } 235 else { 236 Update_out(vec[pos].st, vec[pos].end, 1, n, 1); 237 vector::iterator it; 238 it = vec.begin() + pos; 239 printf("Free from %d to %d\n", vec[pos].st, vec[pos].end); 240 //cout << "Free from " << vec[pos].st << " to " << vec[pos].end << "\n"; 241 vec.erase(it); 242 } 243 } 244 else if (op[0] == 'G') { 245 scanf("%d", &x); 246 if (x > vec.size()) { 247 //cout << "Reject Get" << "\n"; 248 printf("Reject Get\n"); 249 continue; 250 } 251 //sort(vec.begin(), vec.end(), cmp); 252 //cout << "Get at " << vec[x - 1].st << "\n"; 253 printf("Get at %d\n", vec[x - 1].st); 254 } 255 else { 256 Update_out(1, n, 1, n, 1); 257 vec.clear(); 258 //cout << "Reset Now" << "\n"; 259 printf("Reset Now\n"); 260 } 261 /*cout << "---------------------------------" << "\n"; 262 for (int i = 0; i < vec.size(); i++) { 263 cout << vec[i].st << " " << vec[i].end << "\n"; 264 } 265 cout << "---------------------------------" << "\n";*/ 266 } 267 putchar('\n'); 268 vec.clear(); 269 memset(tree, 0, sizeof(tree)); 270 } 271 272 return 0; 273 }