题目地址
题意：操作系统内存分配，拥有4个操作：
- Reset:释放所有内存
- New x :从内存编号1开始分配一个x的空间，能发下则输出这个区间的头地址，如果放不下则输出Reject New
- Free x:释放包含x的那个区间，并且输出那个区间的头地址与尾地址,x这个地方不能被释放则输出Reject Free
- Get x:得到第x个区间的头地址,如果这个区间不存在,输出Reject Get
思路：我一开始的代码的线段树结构体特复杂然后再写update的时候发现还是不能少掉先查找空间在进行更新，就让我前面设定的很多变量浪费了，所以重新开始写，然后看了网上大佬的写法，发现可以用vector去存已用空间起点和终点，通过二分去查找插入，发现这样的确更加的方便，所以对应的操作就转变成了：
- updata的所有区间置为0，把vector清空
- 先按照所需长度x来查询起点pos，如果没有那么长的就输出Reject New，否则就updata(pos,pos+x,1,1);
- 先通过二分来查找所属区间，如果没有就输出Reject Free，否则就把这个区间置为0
- 直接查询vector的第x个区间，然后没有就输出Reject Get，否则直接输出
除了这里比较难想到，其他的应该就是线段树的知识了
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define N 50010
#define LL long long
#define inf 0x3f3f3f3f
#define gol ans<<1
#define gor ans<<1|1
#define lson l,mid,ans<<1
#define rson mid+1,r,ans<<1|1
using namespace std;
const LL mod = 1e9 + 7;
const double eps = 1e-9;
struct node {
int l, r, lazy;
int llen, rlen, maxlen;
}tree[N<<2];
struct nope {
int l, r;
bool operator<(const nope &a) const {
return l < a.l;
}
}now;
vector<nope> v;
void pushDown(int ans, int num) {
if (tree[ans].lazy != -1) {
tree[gol].lazy = tree[ans].lazy;
tree[gor].lazy = tree[ans].lazy;
tree[gol].llen = tree[gol].rlen = tree[gol].maxlen = (tree[ans].lazy ? 0 : num - (num >> 1));
tree[gor].llen = tree[gor].rlen = tree[gor].maxlen = (tree[ans].lazy ? 0 : (num >> 1));
tree[ans].lazy = -1;
}
}
void pushUp(int ans, int num) {
tree[ans].llen = tree[gol].llen;
tree[ans].rlen = tree[gor].rlen;
tree[ans].maxlen = max(tree[gol].maxlen, tree[gor].maxlen);
if (tree[ans].llen == num - (num >> 1)) {
tree[ans].llen += tree[gor].llen;
}
if (tree[ans].rlen == num >> 1) {
tree[ans].rlen += tree[gol].rlen;
}
tree[ans].maxlen = max(tree[ans].maxlen, tree[gol].rlen + tree[gor].llen);
}
void build(int l, int r, int ans) {
tree[ans].l = l;
tree[ans].r = r;
tree[ans].lazy = -1;
tree[ans].llen = tree[ans].rlen = tree[ans].maxlen = r - l + 1;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
}
void updata(int l,int r,int ans,int num) {//更新区间
if (l <= tree[ans].l&&r >= tree[ans].r) {
tree[ans].lazy = num;
tree[ans].llen = tree[ans].rlen = tree[ans].maxlen = (num ? 0 : tree[ans].r - tree[ans].l + 1);
return;
}
pushDown(ans, tree[ans].r - tree[ans].l + 1);
int mid = (tree[ans].l + tree[ans].r) >> 1;
if (l <= mid) {
updata(l, r, gol, num);
}
if (mid < r) {
updata(l, r, gor, num);
}
pushUp(ans, tree[ans].r - tree[ans].l + 1);
}
int query(int ans, int num) {//查询长度为num的空闲区间
if (tree[ans].l == tree[ans].r) {
return tree[ans].l;
}
pushDown(ans, tree[ans].r - tree[ans].l + 1);
int mid = (tree[ans].l + tree[ans].r) >> 1;
if (tree[gol].maxlen >= num) {
return query(gol, num);
}
if (tree[gol].rlen + tree[gor].llen >= num) {
return mid - tree[gol].rlen + 1;
}
return query(gor, num);
}
int main() {
cin.sync_with_stdio(false);
int n, m;
string str;
int x;
vector<nope>::iterator it;
while (cin >> n >> m) {
build(1, n, 1);
v.clear();
while (m--) {
cin >> str;
if (str == "Reset") {
updata(1, n, 1, 0);
v.clear();
cout << "Reset Now" << endl;
}
else if (str == "New") {
cin >> x;
if (tree[1].maxlen < x) {
cout << "Reject New" << endl;
}
else {
int pos = query(1, x);
cout << "New at " << pos << endl;
updata(pos, pos + x - 1, 1, 1);
now.l = pos;
now.r = pos + x - 1;
it = upper_bound(v.begin(), v.end(), now);//upper_bound()返回的是大于now的第一个值
v.insert(it, now);
}
}
else if (str == "Free") {
cin >> x;
now.l = now.r = x;
it = upper_bound(v.begin(), v.end(), now);//upper_bound()返回的是大于now的第一个值
int pos = it - v.begin() - 1;
if (pos == -1 || v[pos].r < x) {
cout << "Reject Free" << endl;
}
else {
cout << "Free from " << v[pos].l << " to " << v[pos].r << endl;
updata(v[pos].l, v[pos].r, 1, 0);
v.erase(v.begin() + pos);
}
}
else {
cin >> x;
if (x > v.size()) {
cout << "Reject Get" << endl;
}
else {
cout << "Get at " << v[x - 1].l << endl;
}
}
}
cout << endl;
}
return 0;
}