#include "stdio.h"
#include "string.h"
#include <time.h> 
char str[1000010],node[5000];
int  b[5000],e[5000],max,v[5000],l[5000],r[5000],root,flag[5000],next;
void insert(char ch ,int k, int ps){
	if( flag[k] == 1 ){
		   flag[k] = 0,v[k] = ps - 1;
           next ++ ;
	       node[k] = ch;
		   l[k] = next;
		   b[next] = b[k];
		   e[next] = b[k] + ps - 2;
		   flag[next] = 1;
		   next ++;
		   r[k] = next;
		   b[next] = b[k] + ps - 1;
		   e[next] = e[k];
		   flag[next] = 1;
	}else{
		if( ps <= v[k] + 1 ){
			v[k] ++ ;
			insert( ch, l[k] , ps );
		}
		else{
			ps -= v[k] ;
			ps-- ;
			insert( ch, r[k], ps );
		}
	}
}
void search( int k , int ps ){
	if( flag[k] == 1 ) {
		printf("%c\n",str[b[k] + ps -1]);
		return ;
	}else{
		if( v[k] + 1 == ps ) {
	 	    printf( "%c\n", node[k] );
		    return ;
		}else{
			if( ps <= v[k] )
				search( l[k] , ps );
			else{
				ps -= v[k];
			    ps --;
				search( r[k] , ps );
			}
		}
	}
}

int main(void){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int   k, cs;
	char  ch;
//	clock_t start, finish;
//	start = clock();
	k = 0 ;
	while( 1 ){
		scanf("%c",str+k);
		if(str[k] == '\n' )
			break;
	    k++;
	}
	max = k,next = 0;	
//	start = clock();
	b[0] = 0 , e[0] = max - 1,flag[0] = 1;
	scanf( "%d", &cs );
	while ( cs -- ){
		scanf(" %c", &ch);
		if( ch == 'I'){
			scanf(" %c %d", &ch, &k);
			if( k > max ) 
				k = max + 1;
			insert( ch , 0, k );                     
			max ++ ;
		}else{
			scanf( "%d", &k);
			search( 0, k );
		}
	}
//	finish = clock();
//	printf("time = %d\n",finish - start);
	return 0 ;
}

• 有多少组 2000 的数据啊,1000ms是所有的数据通过的总时间还是用时最长的那组数据? (0) madzero 2006-07-30 23:08:48