我们考虑给每一个编号附上一个伪权值,然后用平衡树维护这个伪权值,同时用 map 记录伪权值,使得编号和伪权值双向映射,然后几种修改操作可以考虑如下实施:
可以见得这个方法的常数非常之大,但是蒟蒻交了一发之后 1AC,8WA,1TLE 。在此请求大佬帮助!!!!
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct fhq_treap
{
int rt;
struct Node
{
int data,rnd;
int son[2];
int size;
}tr[N];
int top,num,rub[N];
int newnode()
{
if(top)
return rub[top--];
return ++num;
}
void up(int p)
{
if(p==0)
return ;
tr[p].size=tr[tr[p].son[0]].size+tr[tr[p].son[1]].size+1;
return ;
}
void split(int p,int &x,int &y,int val)
{
if(p==0)
x=y=0;
else if(tr[p].data<val)
x=p,split(tr[p].son[1],tr[p].son[1],y,val);
else
y=p,split(tr[p].son[0],x,tr[p].son[0],val);
up(p);
return ;
}
int merge(int x,int y)
{
if(!x)
return y;
if(!y)
return x;
if(tr[x].rnd<tr[y].rnd)
{
tr[x].son[1]=merge(tr[x].son[1],y);
up(x);
return x;
}
else
{
tr[y].son[0]=merge(x,tr[y].son[0]);
up(y);
return y;
}
}
void insert(int x)
{
int a,b;
split(rt,a,b,x);
int tmp=newnode();
tr[tmp].data=x;
tr[tmp].rnd=rand();
tr[tmp].son[0]=tr[tmp].son[1]=0;
tr[tmp].size=1;
tmp=merge(tmp,b);
rt=merge(a,tmp);
return ;
}
void erase(int x)
{
int a,tmp,b;
split(rt,a,tmp,x);
split(tmp,tmp,b,x+1);
rub[++top]=tmp;
rt=merge(a,b);
return ;
}
int get_rk(int p,int x)
{
if(tr[p].data==x)
return tr[tr[p].son[0]].size+1;
if(tr[p].data>x)
return get_rk(tr[p].son[0],x);
if(tr[p].data<x)
return tr[tr[p].son[0]].size+1+get_rk(tr[p].son[1],x);
}
int get_x(int p,int rk)
{
if(tr[tr[p].son[0]].size+1==rk)
return tr[p].data;
if(tr[tr[p].son[0]].size+1>rk)
return get_x(tr[p].son[0],rk);
if(tr[tr[p].son[0]].size+1<rk)
return get_x(tr[p].son[1],rk-tr[tr[p].son[0]].size-1);
}
int find(int p,int x)
{
if(tr[p].data==x)
return p;
if(tr[p].data>x)
return find(tr[p].son[0],x);
if(tr[p].data<x)
return find(tr[p].son[1],x);
}
int get_pre(int x)
{
return get_x(rt,get_rk(rt,x)-1);
}
int get_nxt(int x)
{
return get_x(rt,get_rk(rt,x)+1);
}
void init()
{
rt=top=num=0;
memset(tr,0,sizeof(tr));
memset(rub,0,sizeof(rub));
}
}FHQ;
int n,m,x,t;
string opt;
map<int,int> mp1,mp2;
int maxn,minn;
int main()
{
srand(time(NULL));
FHQ.init();
cin>>n>>m;
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
mp1[x]=i;
mp2[i]=x;
FHQ.insert(i);
}
minn=1,maxn=n;
for(int i=1;i<=m;++i)
{
cin>>opt;
if(opt=="Top")
{
scanf("%d",&x);
mp2.erase(mp2.find(mp1[x]));
FHQ.erase(mp1[x]);
mp1[x]=--minn;
mp2[minn]=x;
FHQ.insert(minn);
}
if(opt=="Bottom")
{
scanf("%d",&x);
mp2.erase(mp2.find(mp1[x]));
FHQ.erase(mp1[x]);
mp1[x]=++maxn;
mp2[maxn]=x;
FHQ.insert(maxn);
}
if(opt=="Insert")
{
scanf("%d%d",&x,&t);
int tmp;
if(t==1)
tmp=mp2[FHQ.get_nxt(mp1[x])];
else
tmp=mp2[FHQ.get_pre(mp1[x])];
swap(mp2[mp1[x]],mp2[mp1[tmp]]);
swap(mp1[x],mp1[tmp]);
}
if(opt=="Ask")
scanf("%d",&x),printf("%d\n",FHQ.get_rk(FHQ.rt,mp1[x])-1);
if(opt=="Query")
scanf("%d",&x),printf("%d\n",mp2[FHQ.get_x(FHQ.rt,x)]);
}
}