本文共 2950 字，大约阅读时间需要 9 分钟。
题目大意：同（双倍经验）
题解：略
卡点：无
C++ Code：
#include #include #include #define maxn 250010std::map name;int n, namenum;struct node { int v, p; inline node(int __v = 0, int __p = 0) {v = __v, p = __p;} inline friend bool operator > (const node &lhs, const node &rhs) { if (lhs.v == rhs.v) return lhs.p < rhs.p; return lhs.v > rhs.v; } inline friend bool operator == (const node &lhs, const node &rhs) {return lhs.v == rhs.v && lhs.p == rhs.p;} inline friend bool operator >= (const node &lhs, const node &rhs) {return lhs > rhs || lhs == rhs;}};namespace Treap { int lc[maxn], rc[maxn], num[maxn], sz[maxn]; node val[maxn]; int root, idx; int ta, tb, tmp, res; int seed = 20040826; inline int rand() {return seed *= 48271;} inline int update(int rt) { sz[rt] = sz[lc[rt]] + sz[rc[rt]] + 1; return rt; } inline int nw(node x) { val[++idx] = x; num[idx] = rand(); sz[idx] = 1; return idx; } void split(int rt, node k, int &x, int &y) { if (!rt) x = y = 0; else { if (val[rt] >= k) split(rc[rt], k, rc[rt], y), x = update(rt); else split(lc[rt], k, x, lc[rt]), y = update(rt); } } void split(int rt, int k, int &x, int &y) { if (!rt) x = y = 0; else { if (sz[lc[rt]] < k) split(rc[rt], k - sz[lc[rt]] - 1, rc[rt], y), x = update(rt); else split(lc[rt], k, x, lc[rt]), y = update(rt); } } int merge(int x, int y) { if (!x || !y) return x | y; if (num[x] < num[y]) {rc[x] = merge(rc[x], y); return update(x);} else {lc[y] = merge(x, lc[y]); return update(y);} } inline int gtrnk(node x) { split(root, x, ta, tb); res = sz[ta]; root = merge(ta, tb); return res; } inline node gtkth(int k) { tmp = root; while (true) { if (sz[lc[tmp]] >= k) tmp = lc[tmp]; else { if (sz[lc[tmp]] + 1 == k) return val[tmp]; else k -= sz[lc[tmp]] + 1, tmp = rc[tmp]; } } } void insert(node x) { if (!root) root = nw(x); else { split(root, x, ta, tb); root = merge(merge(ta, nw(x)), tb); } } void erase(node x) { split(root, x, ta, tb); split(ta, sz[ta] - 1, ta, tmp); root = merge(ta, tb); }}int val[maxn];std::string retname[maxn];int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { char op; std::string s; std::cin >> op >> s; if (op == '+') { int x; std::cin >> x; if (name.count(s)) { int pos = name[s]; Treap::erase(node(val[pos], pos)); namenum--; } namenum++; name[s] = i; retname[i] = s; val[i] = x; Treap::insert(node(x, i)); } else if (isdigit(s[0])) { int pos = 0, posend; for (std::string::iterator it = s.begin(); it != s.end(); it++) pos = pos * 10 + (*it & 15); posend = std::min(pos + 9, namenum); for (int i = pos; i <= posend; i++) { std::cout << retname[Treap::gtkth(i).p]; putchar(i == posend ? '\n' : ' '); } } else { int pos = name[s]; std::cout << Treap::gtrnk(node(val[pos], pos)) << std::endl; } } return 0;}
转载于:https://www.cnblogs.com/Memory-of-winter/p/9866899.html