Code:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define N 300002
#define mod 1000000009
#define ll long long
#define lson t[x].ch[0]
#define rson t[x].ch[1]
#define setIO(s) freopen(s".in", "r", stdin)
using namespace std;
map<int, int> id;
char S[N][12];
int sta[N], pos[N], tot , root, cc = 0, splay_cnt;
struct Node
{
int ch[2] , siz, f;
ll val;
}t[N];
inline int decode(char str[])
{
int k = strlen(str + 1), i , j ;
ll h = 1;
for(i = 1; i <= k ; ++i) h = (h * 26 + str[i] - 'A') % mod;
return (int) h ;
}
inline int get(char str[])
{
int k = strlen(str + 1), i , j = 0;
for(i = 1; i <= k ; ++i) j = j * 10 + str[i] - '0';
return j ;
}
inline void pushup(int x)
{
t[x].siz = t[lson].siz + t[rson].siz + 1;
}
inline int get(int x)
{
return t[t[x].f].ch[1] == x;
}
inline void rotate(int x)
{
int old = t[x].f, fold = t[old].f , which = get(x);
t[old].ch[which] = t[x].ch[which ^ 1], t[t[old].ch[which]].f = old;
t[x].ch[which ^ 1] = old, t[old].f = x, t[x].f = fold;
if(fold) t[fold].ch[t[fold].ch[1] == old] = x;
pushup(old), pushup(x);
}
inline void splay(int x, int &tar)
{
int u = t[tar].f;
for(int fa ; (fa = t[x].f) ^ u ; rotate(x))
if(t[fa].f ^ u)
rotate(get(fa) == get(x) ? fa : x);
tar = x;
}
inline void insert(int &x, int ff, ll v)
{
if(!x)
{
x = ++ tot;
t[x].f = ff, t[x].val = v;
pushup(x);
return ;
}
insert(t[x].ch[v <= t[x].val], x , v), pushup(x);
}
inline int get_kth(int k)
{
int x = root;
while(1)
{
if(k > t[lson].siz)
{
k -= (t[lson].siz + 1);
if(!k) return x ;
else x = rson;
}
else x = lson;
}
}
inline void print(int i)
{
int L = strlen(S[i] + 1), j ;
for(j = 1; j <= L; ++j) printf("%c", S[i][j]);
}
inline void dfs(int u)
{
if(!u) return ;
if(t[u].ch[0]) dfs(t[u].ch[0]);
print(pos[u]), printf(" ");
if(t[u].ch[1]) dfs(t[u].ch[1]);
}
inline void del(int x)
{
splay(x, root);
if(!lson) root = rson, t[root].f = 0;
else if(!rson) root = lson, t[root].f = 0;
else
{
int p = lson;
while(t[p].ch[1]) p = t[p].ch[1];
splay(p, t[root].ch[0]), t[p].ch[1] = t[root].ch[1], t[p].f = 0, t[t[root].ch[1]].f = p, pushup(p), root = p;
}
t[x].ch[0] = t[x].ch[1] = 0;
}
int main()
{
// setIO("input");
int T, i , j ;
scanf("%d", &T);
for(int cas = 1; cas <= T; ++cas)
{
char str[20];
scanf("%s", str);
if(str[0] == '+')
{
j = strlen(str + 1);
for(i = 1; i <= j ; ++i) S[cas][i] = str[i];
int h = decode(str);
ll v;
scanf("%lld", &v), ++cc, ++splay_cnt;
if(id[h]) del(id[h]), --cc;
insert(root , 0 , v), id[h] = tot, pos[tot] = cas;
if(splay_cnt % 6 == 0) splay(tot, root);
}
else
{
if(str[1] >= '0' && str[1] <= '9') // (好头疼qaq)
{
int kth = get(str);
int p = get_kth(kth);
int now, c;
splay(p, root), print(pos[p]), printf(" ");
if(kth + 10 - 1 < cc) c = get_kth(kth + 10), splay(c, t[root].ch[1]), now = t[t[root].ch[1]].ch[0];
else now = t[root].ch[1];
dfs(now), printf("
");
}
else
{
int h = decode(str);
splay(id[h], root), printf("%d
", t[t[root].ch[0]].siz + 1);
}
}
}
return 0;
}