博客

同上一题

双倍经验

我就是要不要脸的再发一遍 “_>”

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
const int N=250010,inf=0x7fffffff;
int n,m,sz,root,tot,ed;
int ch[N][2],fa[N],size[N],key[N],score[N];
map<string,int>hs;
map<int,string>ys;
string name;
inline void clear(int x){ch[x][0]=ch[x][1]=fa[x]=size[x]=key[x]=0;}
inline int get(int x){return ch[fa[x]][1]==x;}
inline void updata(int x){if (x)size[x]=(ch[x][0]?size[ch[x][0]]:0)+(ch[x][1]?size[ch[x][1]]:0)+1;}
inline void rotate(int x)
{
    int old=fa[x],oldf=fa[old],which=get(x);
    ch[old][which]=ch[x][which^1];fa[ch[x][which^1]]=old;
    ch[x][which^1]=old;fa[old]=x;fa[x]=oldf;
    if (oldf)ch[oldf][ch[oldf][1]==old]=x;
    updata(old);updata(x);
}
inline void splay(int x,int tar)
{
    for (int old;(old=fa[x])!=tar;rotate(x))
    if (fa[old]!=tar)rotate(get(old)==get(x)?old:x);
    if (!tar)root=x;
}
inline int insert(int x)
{
    if (!root){root=++sz;ch[sz][0]=ch[sz][1]=fa[sz]=0;size[sz]=1;key[sz]=x;return sz;}
    int now=root,old=0; 
    while(1)
    {
        old=now;
        now=ch[now][x>key[now]];
        if (!now)
        {
            fa[++sz]=old;
            ch[sz][0]=ch[sz][1]=0;
            ch[old][x>key[old]]=sz;
            size[sz]=1;
            key[sz]=x;
            splay(sz,0);
            break;
        }
    }
    return sz;
}
inline int pre()
{
    int now=ch[root][0];
    while(ch[now][1])now=ch[now][1];
    return now;
}
inline void del(int x)
{
    splay(x,0);
    if (!ch[root][0]&&!ch[root][1]){clear(root);root=0;return;}
    if (!ch[root][1]){int oldroot=root;root=ch[root][1];fa[root]=0;clear(oldroot);return;}
    if (!ch[root][0]){int oldroot=root;root=ch[root][0];fa[root]=0;clear(oldroot);return;}
    int leftbig=pre(),oldroot=root;
    splay(leftbig,0);
    ch[root=leftbig][1]=ch[oldroot][1];
    fa[ch[oldroot][1]]=root;
    clear(oldroot);
}
inline int findnth(int x)
{
    int now=root;
    while(1)
    {
        if (ch[now][1]&&size[ch[now][1]]>=x)now=ch[now][1];
        else 
        {
            int temp=1;
            temp+=ch[now][1]?size[ch[now][1]]:0;
            if (x<=temp){splay(now,0);return now;} 
            now=ch[now][0];
            x-=temp;
        }
    }
}
inline void print(int now)
{
    if (ch[now][1])print(ch[now][1]);
    ed--;
    string s=ys[now];
    int len=s.length();
    for (int i=0;i<len;++i)
    putchar(s[i]);if (ed) printf(" ");
    if (ch[now][0])print(ch[now][0]);
}
inline void dfs(int now)
{
    for (int now=1;now<=sz;++now)
    cout<<now<<' '<<ys[now]<<' '<<fa[now]<<' '<<size[now]<<' '<<ch[now][0]<<' '<<ch[now][1]<<' '<<key[now]<<endl;
}
inline void solve(int x)
{
    int l=x;
    int r=min(x+9,tot)+2;
    int aa=findnth(l);
    int bb=findnth(r);
    splay(bb,0);
    splay(aa,bb);
    ed=size[ch[ch[root][1]][0]];
    print(ch[ch[root][1]][0]);
    printf("\n");
}
int main()
{
//    freopen("std.in","r",stdin);
//   freopen("std.out","w",stdout);
    tot=0;
    register int val;
    hs.clear();ys.clear();
    scanf("%d",&n);
    insert(-inf);
    insert(inf);
    for (int i=1;i<=n;++i)
    {
        char c;
        while(c=getchar(),c!='+'&&c!='?');
        if (c=='+')
        {
            name="";
            char cc;
            while(1)
            {
                cc=getchar();
                if (cc>'Z'||cc<'A')break;
                name+=cc;
            }
            scanf("%d",&val);
            if (hs[name]==0)
            {
                insert(val);
                score[sz]=val;
                hs[name]=sz;
                ys[sz]=name;
                ++tot;
            }
            else 
            {
                int id=hs[name];
                del(id);
                score[id]=0;
                id=insert(val);
                score[hs[name]=id]=val;
                ys[id]=name;
           }
        }
        else 
        {
            val=0;
            char cc=getchar();
            if (cc>='0'&&cc<='9')
            {
                val=cc-'0';
                while(cc=getchar(),cc>='0'&&cc<='9')val=(val<<3)+(val<<1)+cc-'0';
               solve(val);
            }
            else 
            {
                name="";
                name+=cc;
                while(1)
                {    
                    cc=getchar();
                    if (cc>'Z'||cc<'A')break;
                    name+=cc;
                }
                int id=hs[name];
                splay(id,0);
                printf("%d\n",size[ch[id][1]]);
            }
        }
    }
}