虽然一直TLE..

但是主要是因为Splay的巨大常数..

也算是写成了一颗Splay?

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int val[250005];
map<string,int> ma;
string maps[250005];
struct node
{
    int val;
    int id;
    int size;
    node * father;
    node * ch[2];
};
node * null;
node * new_node(int x,int y)
{
    static node a[2500005];
    static int top=0;
    node * t=&a[top++];
    t->val=x;
    t->id=y;
    t->size=1;
    t->father=null;
    t->ch[0]=null;
    t->ch[1]=null;
    return t;
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]->father=x;
    y->ch[!c]=x;
    y->father=x->father;
    x->father=y;
    y->size=x->size;
    x->size=x->ch[0]->size+x->ch[1]->size+1;
    x=y;
}
int up(node * x)
{
    if (x->father->ch[0]==x) return 0;
    if (x->father->ch[1]==x) return 1;
    return -1;
}
node * root;
void splay(node * x)
{
    for (;;)
    {
        int t1=up(x);
        if (t1==-1) return;
        int t2=up(x->father);
        if (t2==-1)
        {
            rotate(root,t1);
            return;
        }
        int t3=up(x->father->father);
        if (t3==-1)
        {
            if (t1==t2)
            {
                rotate(root,t2);
                rotate(root,t1);
            }
            else
            {
                rotate(root->ch[t2],t1);
                rotate(root,t2);
            }
        }
        else
        {
            if (t1==t2)
            {
                x=x->father;
                x=x->father;
                x=x->father;
                rotate(x->ch[t3],t2);
                rotate(x->ch[t3],t1);
                x=x->ch[t3];
            }
            else
            {
                x=x->father;
                x=x->father;
                rotate(x->ch[t2],t1);
                x=x->father;
                rotate(x->ch[t3],t2);
                x=x->ch[t3];
            }
        }
    }
}
void insert_node(node * &now,node * x)
{
    if (now==null)
    {
        now=x;
        if (rand()%2) splay(x);
        return;
    }
    now->size++;
    int c;
    if ((x->val<now->val)||((x->val==now->val)&&(x->id>now->id)))
    {
        c=0;
    }
    else
    {
        c=1;
    }
    insert_node(now->ch[c],x);
}
void delete_node(node * &now,int val,int x)
{
    now->size--;
    if ((now->val==val)&&(now->id==x))
    {
        int c=rand()%2;
        if (now->ch[c]==null) c=!c;
        if (now->ch[c]==null)
        {
            node * t=now->father;
            now=null;
            if (rand()%2) splay(t);
            return;
        }
        rotate(now,c);
        delete_node(now->ch[!c],val,x);
    }
    else
    {
        if (((now->val==val)&&(now->id>x))||(now->val<val))
        {
            delete_node(now->ch[1],val,x);
        }
        else
        {
            delete_node(now->ch[0],val,x);
        }
    }
}
int find_kth(node * x,int k)
{
    if (k==x->ch[0]->size+1)
    {
        int ans=x->id;
        splay(x);
        return ans;
    }
    if (k<x->ch[0]->size+1)
    {
        return find_kth(x->ch[0],k);
    }
    else
    {
        return find_kth(x->ch[1],k-x->ch[0]->size-1);
    }
}
int find_min(node * x,int val,int id)
{
    if ((x->val==val)&&(x->id==id))
    {
        int ans=x->ch[0]->size+1;
        splay(x);
        return ans;
    }
    if (((x->val==val)&&(x->id>id))||(x->val<val))
    {
        return x->ch[0]->size+1+find_min(x->ch[1],val,id);
    }
    else
    {
        return find_min(x->ch[0],val,id);
    }
}
char a[1005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    null=new_node(-1,-1);
    null->ch[0]=null;
    null->ch[1]=null;
    null->father=null;
    null->size=0;
    root=null;
    ios::sync_with_stdio(false);
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        char x;
        for (;;)
        {
            x=getchar();
            if (x=='\n') continue;
            if (x==' ') continue;
            break;
        }
        if (x=='+')
        {
            string name;
            scanf("%s",a);
            name=a;
            if (ma.find(name)!=ma.end())
            {
                delete_node(root,val[ma[name]],ma[name]);
            }
            int x;
            scanf("%d",&x);
            ma[name]=i;
            maps[i]=name;
            val[i]=x;
            insert_node(root,new_node(x,i));
        }
        else
        {
            scanf("%s",a);
            if (a[0]<'A')
            {
                int x;
                sscanf(a,"%d",&x);
                int i;
                for (i=x;i<x+10;i++)
                {
                    if (root->size+1-i<=0) break;
                    int t=find_kth(root,root->size+1-i);
                    if (t==-1) break;
                    printf("%s ",maps[t].c_str());
                }
                printf("\n");
            }
            else
            {
                string x;
                x=a;
                int t=ma[x];
                int s=val[t];
                printf("%d\n",root->size+1-find_min(root,s,t));
            }
        }
    }
    return 0;
}