hdu 2871 Memory Control 伸展树区间合并
题意:就是对一个区间的四种操作,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') {补充:软件开发 , C++ ,
- 更多C/C++疑问解答:
- 关于c++的cout输出的问题。
- 在学校里学过C和C++,不过学的很一般,现在自学C#,会不会很难?
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点,3个3度结点,4个4度结点,问有几个叶子结点?
- c++数据结构内部排序问题,整数排序
- 2012九月计算机二级C语言全国题库,,急求急求
- 如果assert只有一个字符串作为参数,是什么意思呢?
- C语言中,哪些运算符具有左结合性,哪些具有右结合性,帮忙总结下,谢谢了!
- 为什么用结构体编写的程序输入是,0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型,用C或C++都行,多谢各位大侠啊,非常感谢!
- 为什么这个程序求不出公式?
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊