题目描述

Description

小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。 当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。 久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。
Input
第一行有两个数n，m，分别表示书的个数以及命令的条数；第二行为n个正整数：第i个数表示初始时从上至下第i个位置放置的书的编号；第三行到m+2行，每行一条命令。命令有5种形式： 1． Top S——表示把编号为S的书房在最上面。 2． Bottom S——表示把编号为S的书房在最下面。 3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书； 4． Ask S——询问编号为S的书的上面目前有多少本书。 5． Query S——询问从上面数起的第S本书的编号。
Output
对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。

Sample Input

10 10 
1 3 2 7 5 8 10 4 9 6
Query 3 
Top 5 
Ask 6 
Bottom 3 
Ask 3 
Top 6 
Insert 4 -1 
Query 5 
Query 2 
Ask 2 

Sample Output

2
9
9
7
5
3

HINT

数据范围
100%的数据，n,m < = 80000

题目分析

非旋转treap模板题
以每个编号作为节点即可 然后查询节点x在序列的哪个位置上 查询在位置x上是哪个节点

#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
int val[301000*3],size[301000*3],key[301000*3],lson[301000*3],rson[301000*3];
int fa[301000*3];    
int tot,root;
void update(int x)
{   
    size[x]=size[lson[x]]+size[rson[x]]+1;
}   
void pushdown(int x)
{   
    return ;
}
int merge(int x,int y)
{
    pushdown(x),pushdown(y);
    if(x==0||y==0) return x|y;
    if(key[x]<key[y])
    {
        lson[y]=merge(x,lson[y]),fa[lson[y]]=y,update(y);
        return y;
    }
    rson[x]=merge(rson[x],y),fa[rson[x]]=x,update(x);
    return x;
}
par split(int x,int k)
{
    if(k==0) return make_pair(0,x);
    pushdown(x);
    int l=lson[x],r=rson[x];
    if(k==size[lson[x]])
    {
        lson[x]=0,update(x),fa[lson[x]]=0;
        return make_pair(l,x);
    }
    if(k==size[lson[x]]+1)
    {
        rson[x]=0,update(x),fa[rson[x]]=0;
        return make_pair(x,r);
    }
    par t;
    if(k<size[lson[x]])
    {
        t=split(l,k);
        lson[x]=t.second,fa[lson[x]]=x,update(x);
        return make_pair(t.first,x);
    }
    else
    {
        t=split(r,k-size[lson[x]]-1);
        rson[x]=t.first,fa[rson[x]]=x,update(x);
        return make_pair(x,t.second);
    }
}
int getrank(int x)
{   
    if(x==root) return size[lson[x]]+1;
    int r=getrank(fa[x]);
    pushdown(x);
    if(x==lson[fa[x]]) r-=size[rson[x]]+1;
    else r+=size[lson[x]]+1;
    return r;
}
int find(int k,int x)
{
    pushdown(k);
    if(x<=size[lson[k]]) return find(lson[k],x);
    else if(x>size[lson[k]]+1) return find(rson[k],x-size[lson[k]]-1);
    else return k;
}
char s[100];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        size[x]=1,key[x]=rand(),root=merge(root,x);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",&s[0]);
        int x,y;
        scanf("%d",&x);
        if(s[0]=='T')
        {
            int id=getrank(x);
            par t1,t2;
            t2=split(root,id);
            t1=split(t2.first,id-1);
            root=merge(t1.second,merge(t1.first,t2.second));
        }
        else if(s[0]=='B')
        {
            int id=getrank(x);
            par t1,t2;
            t2=split(root,id);
            t1=split(t2.first,id-1);
            root=merge(merge(t1.first,t2.second),t1.second);
        }
        else if(s[0]=='I')
        {
            scanf("%d",&y);
            int id=getrank(x);
            par t1,t2,t3;
            if(!y) continue;
            if(y==-1)
            {
                t3=split(root,id);
                t2=split(t3.first,id-1);
                t1=split(t2.first,id-2);
                root=merge(merge(merge(t1.first,t2.second),t1.second),t3.second);
            }
            else
            {
                t3=split(root,id+1);
                t2=split(t3.first,id);
                t1=split(t2.first,id-1);
                root=merge(merge(merge(t1.first,t2.second),t1.second),t3.second);
            }
        }
        else if(s[0]=='A') printf("%d\n",getrank(x)-1);
        else printf("%d\n",find(root,x));
    }
}