<\/p>\n
…<\/p>\n
\r\n\/* .................................................................................................................................. *\/\r\n \r\n\/** Header **\/\r\n \r\n#include <cstdio>\r\n#include <cstring>\r\n#define DO(N) while(N--)\r\n \r\ntemplate<class T> inline void RD(T &x){ \/\/ ... :" I am I\/O Accelerator ... Use me at your own risk ;) ... " ..\r\n \/\/scanf("%d", &x);\r\n char c; c = getchar(); x = c - '0';\r\n for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';\r\n}\r\ntemplate<class T> inline void RD(T &x0, T &x1){RD(x0), RD(x1);}\r\ntemplate<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}\r\ntemplate<class T> inline void RST(T &A0, T &A1){RST(A0), RST(A1);}\r\ntemplate<class T> inline void RST(T &A0, T &A1, T &A2){RST(A0), RST(A1), RST(A2);}\r\ntemplate<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}\r\n \r\nconst int INF = 0x7fffffff;\r\nconst int N = 100001;\r\n \r\nint l[N], r[N], p[N], ky[N], sz[N];\r\nint root, total;\r\nint n, b, d, ans;\r\n \r\n \r\ninline void Rotate(int x){\r\n int y = p[x], z = p[y], lc = l[x], rc = r[x];\r\n if (y == l[z]) l[z] = x; else r[z] = x;\r\n if (x == l[y]) {\r\n p[p[p[rc] = y] = x] = z, l[r[x] = y] = rc;\r\n sz[x] = sz[y], sz[y] -= sz[lc] + 1;\r\n }\r\n else {\r\n p[p[p[lc] = y] = x] = z, r[l[x] = y] = lc;\r\n sz[x] = sz[y], sz[y] -= sz[rc] + 1;\r\n }\r\n}\r\n \r\ninline void Splay(int x){\r\n while (p[x]) Rotate(x);\r\n root = x;\r\n}\r\n \r\nvoid Insert(int val){\r\n val -= b - d; if (val < d) return;\r\n int x = root, y = 0; while (x != 0){\r\n ++sz[y = x];\r\n if (val < ky[x]) x = l[x];\r\n else x = r[x];\r\n }\r\n \r\n x = ++total, ky[x] = val, sz[x] = 1, p[x] = y;\r\n if (val < ky[y]) l[y] = x; else r[y] = x;\r\n \r\n Splay(x);\r\n}\r\n \r\nint Search(){\r\n int val = d, res = 0, x = root; while (x != 0){\r\n if (val > ky[x]) x = r[x];\r\n else {\r\n if (ky[x] <= ky[res]) res = x;\r\n x = l[x];\r\n }\r\n }\r\n return res;\r\n}\r\n \r\nint Select(int k){\r\n int x = root; while (sz[l[x]] + 1 != k){\r\n if (sz[l[x]] + 1 < k) k -= sz[l[x]] + 1, x = r[x];\r\n else x = l[x];\r\n }\r\n Splay(x); return x;\r\n}\r\n \r\nint main(){\r\n \r\n \/\/freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n \r\n#define gc getchar()\r\n \r\n while (scanf("%d %d", &n, &b) != EOF){\r\n \r\n gc; RST(p, l, r); RST(ky, sz); root = total = ans = d = 0;\r\n Insert(INF), ky[0] = INF; int t; DO(n){\r\n \r\n char cmd = gc; gc; \/\/scanf(" %c", &cmd);\r\n RD(t); switch (cmd) {\r\n case 'I':\r\n Insert(t);\r\n break;\r\n case 'A':\r\n d -= t;\r\n break;\r\n case 'S':\r\n d += t, Splay(Search());\r\n ans += sz[l[root]], sz[root] -= sz[l[root]], l[root] = 0;\r\n break;\r\n default:\r\n if (t >= sz[root]) puts("-1");\r\n else printf("%d\\n", ky[Select(sz[root] - t)] + b - d);\r\n }\r\n }\r\n printf("%d\\n", ans);\r\n }\r\n}\r\n<\/pre>\nExternal link: <\/h3>\n