LOJ_1087 - Diablo

/* unlucky_13 Jul 20, 2013 11:01:42 PM
 *
 */
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#define maxn 150005
using namespace std;
int cnt_of_elements[4*maxn],q,A[maxn];

int call(int idx,int s,int e,int pos){

	cnt_of_elements[idx]-- ;
	if(s==e){
		return s ;
	}
	int mid = (s+e)>>1 ;
	int next =idx<<1 ;
	//cout<<cnt_of_elements[idx]<<endl ;
    if(cnt_of_elements[next]>=pos){
    	return call(next,s,mid,pos) ;
    }
    else{
    	return call(next+1,mid+1,e,pos-cnt_of_elements[next]) ;
    }


}

void update(int idx,int s,int e,int pos,int value){
	if(s==pos && e==pos){
		cnt_of_elements[idx]+=value ;
		return ;
	}
	int mid = (s+e)>>1 ;
	int next =idx<<1 ;
	if(mid>=pos){
		update(next,s,mid,pos,value) ; //go to left
	}

	else{
		update(next+1,mid+1,e,pos,value) ;
	}
	cnt_of_elements[idx] = cnt_of_elements[next]+cnt_of_elements[next+1] ;

}

int main() {

	//freopen("//home//unlucky_13//workspace//Hello_World//src//in.txt","r",stdin) ;
	int tc,ct=0,d,n,N;
	char c ;
	scanf("%d",&tc) ;
	while(ct!=tc){
        memset(cnt_of_elements,0,sizeof(cnt_of_elements)) ;
		scanf("%d %d\n",&n,&q) ;
		int total = n+q ;
		N = n ;
		for(int i=1;i<=n;i++) {
			scanf("%d",A+i) ;
			update(1,1,total,i,1) ;

		}
		printf("Case %d:\n",++ct) ;
		while(q--){
			scanf("  %c %d",&c,&d) ;
			if(c=='c'){
				int ret ;
				if(d>n) ret = -1 ;
				else {
					ret = call(1,1,total,d) ;
					n-- ;
				}

				if(ret==-1) printf("none\n") ;
				else printf("%d\n",A[ret]) ;
			}
			else{
				A[++N] = d ;
				n++ ;
				update(1,1,total,N,1) ;
			}
		}
	}


	return 0;
}