题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=3224
题意:维护以下操作:
(1)插入x;
(2)删除x(若有多个相同的数,只删除一个)
(3)查询x的排名(若有多个相同的数,输出最小的排名)
(4)查询排名为x的数
(5)求x的前驱(前驱定义为小于x,且最大的数)
(6)求x的后继(后继定义为大于x,且最小的数)
思路:主要用到使用树状数组计算第K位置元素。
struct node
{
int x,y;
node(){}
node(int _x,int _y)
{
x=_x;
y=_y;
}
void get()
{
RD(x,y);
}
int operator<(const node &a) const
{
return y<a.y;
}
};
node a[N],b[N];
int n,p[N],c[N],m,M;
void add(int x,int det)
{
while(x<=m)
{
c[x]+=det;
x+=x&-x;
}
}
int get(int x)
{
int ans=0;
while(x)
{
ans+=c[x];
x-=x&-x;
}
return ans;
}
int getKth(int k)
{
int ans=0,cnt=0,i;
for(i=20;i>=0;i--)
{
ans+=1<<i;
if(ans>M||cnt+c[ans]>=k) ans-=1<<i;
else cnt+=c[ans];
}
return ans+1;
}
void go()
{
int i,temp;
FOR1(i,n)
{
if(a[i].x==1) add(a[i].y,1);
else if(a[i].x==2) add(a[i].y,-1);
else if(a[i].x==3) PR(get(a[i].y-1)+1);
else if(a[i].x==4) PR(b[p[getKth(a[i].y)]].y);
else if(a[i].x==5)
{
temp=get(a[i].y-1);
PR(b[p[getKth(temp)]].y);
}
else
{
temp=get(a[i].y)+1;
PR(b[p[getKth(temp)]].y);
}
}
}
int main()
{
RD(n);
int i;
FOR1(i,n)
{
a[i].get();
if(a[i].x!=4) b[++m]=node(i,a[i].y);
}
sort(b+1,b+m+1); b[0].y=19891101;
FOR1(i,m)
{
if(b[i].y==b[i-1].y) a[b[i].x].y=M;
else a[b[i].x].y=++M,p[M]=i;
}
go();
}