郁闷的出纳员（伸展树） C语言

#include <stdio.h> #include <math.h> #include <string.h> #define maxn 100005 #define nil 0 #define oo 1000000000 int n, minp, root, tot, w; int d[maxn], son[maxn][2], fa[maxn], s[maxn]; inline void update(int rot) { s[rot] = s[son[rot][0]] + s[son[rot][1]] + 1; } void rotate(int x, int w) { int y = fa[x]; son[y][w ^ 1] = son[x][w]; if(son[x][w] != nil) fa[son[x][w]] = y; fa[x] = fa[y]; if(fa[y] != nil) { if(y == son[fa[y]][0]) son[fa[y]][0] = x; else son[fa[y]][1] = x; } son[x][w] = y; fa[y] = x; update(y); update(x); } void splay(int x, int poi) { if(x == nil) return; while(fa[x] != poi) { if(fa[fa[x]] == poi) { if(x == son[fa[x]][0]) rotate(x, 1); else rotate(x, 0); } else { if(fa[x] == son[fa[fa[x]]][0]) { if(x == son[fa[x]][0]) { rotate(fa[x], 1); rotate(x, 1); } else { rotate(x, 0); rotate(x, 1); } } else { if(x == son[fa[x]][0]) { rotate(x, 1); rotate(x, 0); } else { rotate(fa[x], 0); rotate(x, 0); } } } } if(poi == nil) root = x; } void insert(int rot, int x) { ++s[rot]; if(d[rot] <= x) { if(son[rot][1] == nil) { d[++tot] = x; s[tot] = 1; fa[tot] = rot; son[rot][1] = tot; son[tot][0] = son[tot][1] = nil; splay(rot, nil); } else { insert(son[rot][1], x); } } else { if(son[rot][0] == nil) { d[++tot] = x; s[tot] = 1; fa[tot] = rot; son[rot][0] = tot; son[tot][0] = son[tot][1] = nil; splay(rot, nil); } else { insert(son[rot][0], x); } } } int succ(int rot, int k) { if(rot == nil) return nil; if(d[rot] >= k) { int t = succ(son[rot][0], k); if(t == nil) return rot; else return t; } else { return succ(son[rot][1], k); } } int select(int rot, int k) { if(rot == nil || k < 0) return -1; if(s[son[rot][1]] + 1 == k) return d[rot] + w; if(s[son[rot][1]] >= k) return select(son[rot][1], k); return select(son[rot][0], k - s[son[rot][1]] - 1); } int main() { char opt; int k, sum = 0; printf("请输入下面命令条数和工资下界："); scanf("%d%d", &n, &minp); d[root = ++tot] = (oo << 1); s[tot] = 1; fa[tot] = son[tot][0] = son[tot][1] = nil; while(n--) { printf("请输入命令："); scanf("\n%c %d", &opt, &k); switch(opt) { case 'I': if(k >= minp) { insert(root, k - w); ++sum; } break; case 'A': w += k; break; case 'S': w -= k; splay(succ(root, minp - w), nil); s[root] -= s[son[root][0]]; son[root][0] = nil; break; case 'F': printf("当前工资第%d的员工所拿的工资数：%d\n", k,select(root, k + 1)); break; default : break; } } printf("命令结束。\n离开公司的员工的总数：%d\n", sum - s[root] + 1); printf("\n请输入任意键退出"); getch(); return 0; }