題意：就是對一個區間的四種操作，NEW x，占據最左邊的連續的x個單元，Free x 把x單元所占的連續區間清空 ， Get x 把第x次占據的區間輸出來， R 清空整個區間。 解法：很明顯的區間合並，跟hotel那題差不多，貌似多了Free，Get操作， 我們可以用一個vector保存已經申請的區間，然後要Free x就在vector裡面二分找到x所在的區間即可， Get也是二分一下即可， 其它操作可以用線段樹或者伸展樹操作。 這題主要是練了一下伸展樹，這題也算基礎， 但還是調了好久，真心難調，鍛煉調試能力。 伸展樹：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 50006;
#define L ch[x][0]
#define R ch[x][1]
#define KT ch[ ch[root][1]][0]
#define mp make_pair
typedef pair<int, int> pii;
int n;
struct splayTree {
int sz[maxn], pre[maxn], ch[maxn][2];
int top, root;
int ls[maxn], rs[maxn], ms[maxn], col[maxn], val[maxn];
void rotate(int &x, int f) {
int y = pre[x], z = pre[y];
down(y); down(x);
ch[y][!f] = ch[x][f];
pre[ch[x][f]] = y;
pre[x] = pre[y];
if(z) ch[z][ch[z][1] == y] = x;
ch[x][f] = y;
pre[y] = x;
up(y);
}
void splay(int &x, int g) {
down(x);
while(pre[x] != g) {
int y = pre[x], z = pre[y];
if(z == g) rotate(x, ch[y][0] == x);
else {
int f = (ch[z][0] == y);
ch[y][!f] == x ? rotate(y, f) : rotate(x, !f);
rotate(x, f);
}
}
up(x);
if(!g) root = x;
}
void rto(int k, int g) {
int x = root;
while(sz[L] != k) {
down(x);
if(sz[L] > k) x = L;
else {
k -= sz[L]+1;
x = R;
}
}
splay(x, g);
}
void newNode(int &x, int v, int fa) {
x = ++top;
sz[x] = 1;
pre[x] = fa;
L = R = 0;
col[x] = -1;
ls[x] = rs[x] = ms[x] = val[x] = v;
}
void down(int x) {
if(~col[x]) {
col[L] = col[R] = val[L] = val[R] = col[x];
ls[L] = rs[L] = ms[L] = col[x] * sz[L];
ls[R] = rs[R] = ms[R] = col[x] * sz[R];
col[x] = -1;
}
}
void up(int x) {
sz[x] = sz[L] + sz[R] + 1;
ls[x] = ls[L];
rs[x] = rs[R];
ms[x] = max(ms[L], ms[R]);
if(val[x]) {
ms[x] = max(ms[x], rs[L]+1+ls[R]);
if(ls[x] == sz[L]) ls[x] += ls[R]+1;
if(rs[x] == sz[R]) rs[x] += rs[L]+1;
}
}
void build(int &x, int l, int r, int fa) {
if(l > r) return;
int m = (l + r) >> 1;
newNode(x, 1, fa);
build(L, l, m-1, x);
build(R, m+1, r, x);
up(x);
}
void init(int n) {
top = 0;
newNode(root, 0, 0);
newNode(ch[root][1], 0, root);
build(KT, 0, n-1, ch[root][1]);
up(ch[root][1]); up(root);
}
void update(int l, int r, int c) {
rto(l-1, 0);
rto(r+1, root);
col[KT] = val[KT] = c;
ls[KT] = rs[KT] = ms[KT] = c*sz[KT];
up(ch[root][1]);
up(root);
}
int find(int x, int k, int pos) { //找連續的空位的首位置
down(x);
if(ms[L] >= k) return find(L, k, pos);
pos += sz[L];
if(val[x] && rs[L]+ls[R]+1 >= k) return pos - rs[L];
return find(R, k, pos+1);
}
}spt;
vector<pii> vec;
int main() {
char op[22];
int j, m, x;
while (~scanf("%d%d", &n, &m)) {
spt.init(n);
vec.clear();
while (m--) {
scanf("%s", op);
if (op[0] == 'R') {
vec.clear();
puts("Reset Now");
spt.update(1, n, 1);
continue;
}
scanf("%d", &x);
if (op[0] == 'N') {
if (spt.ms[spt.root] < x) {
puts("Reject New");
continue;
}
int l = spt.find(spt.root, x, 0);
printf("New at %d\n", l);
int r = l + x - 1;
spt.update(l, r, 0);
pii tp = mp(l, r);
j = lower_bound(vec.begin(), vec.end(), tp) - vec.begin();
vec.insert(vec.begin() + j, tp);
} else if (op[0] == 'G') {
if ((int) vec.size() < x)
puts("Reject Get");
else
printf("Get at %d\n", vec[x - 1].first);
} else if (op[0] == 'F') {
j = upper_bound(vec.begin(), vec.end(), mp(x, n + 3))
- vec.begin() - 1;
if (j == -1 || vec[j].first > x || vec[j].second < x)
puts("Reject Free");
else {
printf("Free from %d to %d\n", vec[j].first, vec[j].second);
spt.update(vec[j].first, vec[j].second, 1);
vec.erase(vec.begin() + j);
}
}
}
puts("");
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 50006;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define Mid int m = (l+r) >> 1
#define mp make_pair
typedef pair<int, int> pii;
int n;
struct segTree {
int lsum[maxn<<2], rsum[maxn<<2], msum[maxn<<2];
int col[maxn<<2];
inline void up(int l, int r, int rt) {
msum[rt] = max(msum[ls], msum[rs]);
msum[rt] = max(msum[rt], rsum[ls] + lsum[rs]);
Mid;
lsum[rt] = lsum[ls];
if (lsum[ls] == m - l + 1) lsum[rt] += lsum[rs];
rsum[rt] = rsum[rs];
if (lsum[rs] == r - m) rsum[rt] += rsum[ls];
}
inline void down(int l, int r, int rt) {
if (~col[rt]) {
col[ls] = col[rs] = col[rt];
Mid;
lsum[ls] = rsum[ls] = msum[ls] = col[rt] * (m - l + 1);
lsum[rs] = rsum[rs] = msum[rs] = col[rt]* (r - m );
col[rt] = -1;
}
}
void build(int l = 1, int r = n, int rt = 1) {
lsum[rt] = rsum[rt] = msum[rt] = r - l + 1;
col[rt] = -1;
if (l == r)
return;
Mid;
build(lson);
build(rson);
// up(l, r, rt);
}
void update(int L, int R, int v, int l = 1, int r = n, int rt = 1) {
if (L <= l && r <= R) {
col[rt] = v;
rsum[rt] = lsum[rt] = msum[rt] = v * (r - l + 1);
return;
}
Mid;
down(l, r, rt);
if (L <= m)
update(L, R, v, lson);
if (R > m)
update(L, R, v, rson);
up(l, r, rt);
}
int find(int x, int l = 1, int r = n, int rt = 1) {
if (l == r)
return l;
Mid;
down(l, r, rt);
if (msum[ls] >= x)
return find(x, lson);
else if (rsum[ls] + lsum[rs] >= x)
return m - rsum[ls] + 1;
else
return find(x, rson);
}
} tree;
vector<pii > vec;
int main() {
char op[22];
int j, m, x;
while (~scanf("%d%d", &n, &m)) {
tree.build();
vec.clear();
while (m--) {
scanf("%s", op);
if (op[0] == 'R') {
vec.clear();
puts("Reset Now");
tree.update(1, n, 1);
continue;
}
scanf("%d", &x);
if (op[0] == 'N') {
if (tree.msum[1] < x) {
puts("Reject New");
continue;
}
int l = tree.find(x);
printf("New at %d\n", l);
int r = l + x - 1;
tree.update(l, r, 0);
pii tp = mp(l, r);
j = lower_bound(vec.begin(), vec.end(), tp) - vec.begin();
vec.insert(vec.begin()+j, tp);
} else if (op[0] == 'G') {
if ((int) vec.size() < x)
puts("Reject Get");
else
printf("Get at %d\n", vec[x - 1].first);
} else if (op[0] == 'F') {
j = upper_bound(vec.begin(), vec.end(), mp(x, n + 3))
- vec.begin() - 1;
if (j == -1 || vec[j].first > x || vec[j].second < x)
//if(j == -1)
puts("Reject Free");
else {
printf("Free from %d to %d\n", vec[j].first, vec[j].second);
tree.update(vec[j].first, vec[j].second, 1);
vec.erase(vec.begin() + j);
}
}
}
puts("");
}
return 0;
}
