# CF #457 D. Jamie and To-do List

http://codeforces.com/problemset/problem/916/D

ポインタ型が64bitというのが厄介で、nodeにポインタ型を持たせるとMLEする。(CFは32bit環境らしい。なんでMLEしたんだ…？)

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>

using namespace std;

template<class T> struct MSnode {
int l = 0;
int r = 0;
int sz = 0;
int cnt = 0;
T key;
bool c;
};

template<class T> class MultiSet {
using node_t = int;
static int curr;
static vector<MSnode<T>> xs;

node_t root = 0;

public:
void insert(T key) {
root = insert(root, key);
xs[root].c = false;
}

void erase(T key) {
root = erase(root, key);
xs[root].c = false;
}

int countLT(T key) {
return countLT(root, key);
}

private:
node_t fix(node_t x) {
xs[x].sz = xs[xs[x].l].sz + xs[xs[x].r].sz + xs[x].cnt;
return x;
}

node_t create() {
if (xs.size() <= curr) {
xs.resize(xs.size() * 2);
}
xs[curr].sz = 1;
xs[curr].cnt = 1;
xs[curr].c = true;
return curr++;
}

node_t create(T key) {
int x = create();
xs[x].key = key;
return x;
}

node_t clone(node_t x) {
node_t y = create();
xs[y] = xs[x];
return y;
}

node_t create(node_t x, node_t l, node_t r, bool c) {
x = clone(x);
xs[x].l = l;
xs[x].r = r;
xs[x].c = c;
return fix(x);
}

node_t create(node_t x, node_t l, node_t r) {
x = clone(x);
xs[x].l = l;
xs[x].r = r;
return fix(x);
}

node_t create(node_t x, bool c) {
x = clone(x);
xs[x].c = c;
return x;
}

node_t insert(node_t x, T key) {
if (!x) return create(key);
if (key == xs[x].key) {
x = clone(x);
xs[x].cnt++;
x = fix(x);
} else if (key < xs[x].key) {
x = create(x, insert(xs[x].l, key), xs[x].r);
} else {
x = create(x, xs[x].l, insert(xs[x].r, key));
}
if (xs[xs[x].r].c) {
x = create(xs[x].r, create(x, xs[x].l, xs[xs[x].r].l, true), xs[xs[x].r].r, xs[x].c);
}
if (xs[xs[x].l].c && xs[xs[xs[x].l].l].c) {
x = create(xs[x].l, create(xs[xs[x].l].l, false), create(x, xs[xs[x].l].r, xs[x].r, false), true);
}
return x;
}

node_t erase(node_t x, T key) {
if (!x) return 0;
if (key == xs[x].key) {
x = clone(x);
xs[x].cnt--;
x = fix(x);
} else if (key < xs[x].key) {
x = create(x, erase(xs[x].l, key), xs[x].r);
} else {
x = create(x, xs[x].l, erase(xs[x].r, key));
}
return x;
}

int countLT(node_t x, T key) {
if (!x) return 0;
int res = 0;
if (xs[x].key < key) {
res += xs[xs[x].l].sz;
res += xs[x].cnt;
res += countLT(xs[x].r, key);
} else {
res += countLT(xs[x].l, key);
}
return res;
}
};
template<class T> int MultiSet<T>::curr = 1;
template<class T> vector<MSnode<T>> MultiSet<T>::xs(1);

template<class T> class Array {
public:
Array() {}

Array(int n) {
h = 0;
for (int i = 1; i < n; i *= 16) h += 4;
}

T *mut_get(int k) {
auto p = mutable_get(k, root, 0, h);
root = p.first;
return &p.second->value;
}

T get(int k) {
return immutable_get(k, root, 0, h);
}

private:
struct node {
node *ch[16] = {};
T value;

node() {}
node(T value) : value(value) {}
};

int h;
node *root = nullptr;

T immutable_get(int a, node *x, int l, int d) {
if (!x) return T();
if (d == 0) return x->value;
int id = a - l >> d - 4;
return immutable_get(a, x->ch[id], l + (id << d - 4), d - 4);
}

pair<node *, node *> mutable_get(int a, node *x, int l, int d) {
x = x ? new node(*x) : new node();
if (d == 0) return { x, x };
int id = a - l >> d - 4;
auto p = mutable_get(a, x->ch[id], l + (id << d - 4), d - 4);
x->ch[id] = p.first;
return { x, p.second };
}
};

int main() {
int q;
cin >> q;

vector<pair<MultiSet<int>, Array<int>>> his(q + 1);
MultiSet<int> st;
Array<int> ar(q);
his[0] = make_pair(st, ar);

map<string, int> stoi;

auto get_id = [&](string key) {
if (!stoi.count(key)) {
int t = stoi.size();
stoi[key] = t;
}
return stoi[key];
};

for (int ii = 1; ii <= q; ii++) {
char type[30];
char key[30];

scanf("%s", type);

if (type[0] == 's') {
int v;
scanf("%s %d", key, &v);
int k = get_id(key);
int pv = ar.get(k);
if (pv != 0) {
st.erase(pv);
}
*ar.mut_get(k) = v;
st.insert(v);
} else if (type[0] == 'r') {
scanf("%s", key);
int k = get_id(key);
int v = ar.get(k);
if (v != 0) {
st.erase(v);
*ar.mut_get(k) = 0;
}
} else if (type[0] == 'q') {
scanf("%s", key);
int k = get_id(key);
int v = ar.get(k);
if (v != 0) {
printf("%d\n", st.countLT(v));
} else {
printf("-1\n");
}
fflush(stdout);
} else {
int d;
scanf("%d", &d);

tie(st, ar) = his[ii - d - 1];
}
his[ii] = make_pair(st, ar);
}
}