又一次用到树状数组求第k小,注意边界情况
#define N 50005 int c[N]; int lowbit(int x){ return x&(-x); } void add(int x,int v){ while(x<N){ c[x]+=v; x+=lowbit(x); } } int sum(int x){ int ans = 0; while(x){ ans+=c[x]; x-=lowbit(x); } return ans; } int find_k(int k){ int ans=0,cnt=0; for(int i=log(double(N-1))/log(2.0);i>=0;i--){ ans += (1<<i); if(ans>=N || cnt+c[ans]>=k){ ans-=(1<<i); } else cnt+=c[ans]; } return ans+1; } int main(){ int n,m; while(scanf("%d%d",&n,&m)!=-1){ int i,j; memset(c,0,sizeof(c)); stack<int> st; add(1,1);//注意边界,都往后移一位 add(n+2,1);//同上 while(m--){ char str[2]; scanf("%s",str); int pos; if(str[0]=='D'){ scanf("%d",&pos); pos++; add(pos,1); st.push(pos); } else if(str[0]=='R'){ pos = st.top();st.pop(); add(pos,-1); } else { scanf("%d",&pos); pos++; int k = sum(pos); int a = find_k(k); int b = find_k(k+1); if(k-sum(pos-1)==1){ printf("0\n"); } else printf("%d\n",b-a-1); } } } return 0; }