from 1 to N stand in a line initially. Each time you should simulate one of the following operations:
1. Top x :Take person x to the front of the queue
2. Query x: calculate the current position of person x
3. Rank x: calculate the current person at position x
Where x is in [1, N].
Ponyo is so clever that she plays the game very well while Garfield has no idea. Garfield is now turning to you for help.
In each case, the first line contains two integers N(1<=N<=10^8), Q(1<=Q<=10^5). Then there are Q lines, each line contain an operation as said above.
person at position x at a line.
3 9 5 Top 1 Rank 3 Top 7 Rank 6 Rank 8 6 2 Top 4 Top 5 7 4 Top 5 Top 2 Query 1 Rank 6
Case 1: 3 5 8 Case 2: Case 3: 3 6
//
http://www.cppblog.com/Yuan/archive/2010/08/18/123871.html
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN = 100010;
struct OP
{
char cmd[10];
int x;
}op[MAXN];
int N;
int num[MAXN];//for compress
int pos[MAXN*2],peo[MAXN];//pos[i] = who peo[i] = where
int C[2*MAXN];//,A[2*MAXN];// A[i] = number of people at pos[i]
inline int lowbit(int x)
{
return x&(-x);
}
inline void add(int p,int x)
{
while(p<=N)
{
C[p]+=x;
p+=lowbit(p);
}
}
inline int sum(int p)
{
int ans = 0;
while(p>0)
{
ans+=C[p];
p-=lowbit(p);
}
return ans;
}
//下面两个函数都行
int findK(int K)//find the first one >=K
{
int pos = 0,cnt = 0;
for(int i=17;i>=0;i--)
{
pos+=(1<<i);
if(pos>=N||cnt+C[pos]>=K)pos-=(1<<i);
else cnt+=C[pos];
}
return pos+1;
}
int findK(int n,int K)//find the first one >=K
{
int l=0,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(sum(mid)>=K) r=mid;
else l=mid+1;
}
return l;
}
int main()
{
//freopen("in","r",stdin);
int T,t=1,n,q;
for(scanf("%d",&T);T--;)
{
printf("Case %d:\n",t++);
scanf("%d%d",&n,&q);
num[0]=0;
for(int i=0;i<q;i++)
{
scanf("%s%d",op[i].cmd,&op[i].x);
num[i+1]=op[i].x;
}
sort(num+1,num+1+q);
n=unique(num+1,num+1+q)-(num+1);
N = q+n;
fill(C,C+N+1,0);
//fill(A,A+N+1,0);
for(int i=1;i<=n;i++)
{
// A[q+i]=num[i]-num[i-1];
add(q+i,num[i]-num[i-1]);
pos[q+i]=num[i];
peo[i]=q+i;
}
int top=q;
for(int i=0;i<q;i++)
{
if(strcmp(op[i].cmd,"Top")==0)
{
int x=lower_bound(num+1,num+1+n,op[i].x)-num;
add(peo[x],-1);
pos[peo[x]]--;
peo[x]=top;
add(peo[x],+1);
pos[top]=op[i].x;
top--;
}
if(strcmp(op[i].cmd,"Rank")==0)
{
int K=op[i].x;
int p=findK(N,K);//
int sp=sum(p);
printf("%d\n",pos[p]-(sp-K));
}
if(strcmp(op[i].cmd,"Query")==0)
{
int x=lower_bound(num+1,num+1+n,op[i].x)-num;
printf("%d\n",sum(peo[x]));
}
}
}
return 0;
}