HYSBZ - 1503 郁闷的出纳员——splay

HYSBZ - 1503 郁闷的出纳员——splay

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;int n, m, ans;struct Splay { int sz, root, fa[maxn], ch[maxn][2], key[maxn], cnt[maxn], size[maxn]; void clear() { sz = root = 0; } void newnode(int x, int f, int v) { fa[x] = f, ch[x][0] = ch[x][1] = 0, key[x] = v, cnt[x] = size[x] = 1; } void delnode(int x) { fa[x] = ch[x][0] = ch[x][1] = key[x] = cnt[x] = size[x] = 0; } void pushup(int x) { if (!x) return; size[x] = cnt[x]; if (ch[x][0]) size[x] += size[ch[x][0]]; if (ch[x][1]) size[x] += size[ch[x][1]]; } int pos(int x) { return ch[fa[x]][1] == x; } void rotate(int x) { int y = fa[x], z = fa[y], posx = pos(x), posy = pos(y); fa[ch[x][posx^1]] = y; ch[y][posx] = ch[x][posx^1]; fa[y] = x; ch[x][posx^1] = y; fa[x] = z; if (z) ch[z][posy] = x; pushup(y); pushup(x); } void splay(int x) { for (int f; (f = fa[x]); rotate(x)) { if (fa[f]) rotate(pos(x) == pos(f)?f:x); } root = x; } int kth(int k) { int x = root; while (true) { if (!x) return -1; if (ch[x][0] && k <= size[ch[x][0]]) x = ch[x][0]; else { int t = (ch[x][0]?size[ch[x][0]]:0)+cnt[x]; if (k <= t) return key[x]; k -= t; x = ch[x][1]; } } } void insert(int v) { if (v < m) return; if (!root) { newnode(++sz, 0, v); root = sz; return; } int f = 0, x = root; while (true) { if (!x) { newnode(++sz, f, v); ch[f][key[f]>v] = sz; splay(sz); break; } if (key[x] == v) { cnt[x]++; size[x]++; splay(x); break; } f = x; x = ch[x][key[x]>v]; } } void delet() { if (ch[root][1]) ans += size[ch[root][1]]; if (cnt[root] > 1) { cnt[root]--; ch[root][1] = 0; pushup(root); } else { root = ch[root][0]; fa[root] = 0; } } void update(int x, int v) { if (!x) return; key[x] += v; update(ch[x][0], v); update(ch[x][1], v); }}ac;int main() { scanf("%d %d", &n, &m); ans = 0; ac.clear(); char opt; int x; for (int i = 1; i <= n; i++) { getchar(); scanf("%c %d", &opt, &x); switch (opt) { case 'I': ac.insert(x); break; case 'A': ac.update(ac.root, x); break; case 'S': ac.update(ac.root, -x); ac.insert(m); ac.delet(); break; case 'F': printf("%d\n", ac.kth(x)); break; } } printf("%d\n", ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。