2887.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2887  User Id:fzk 
Memory:1060K  Time:428MS
Language:C++  Result:Accepted

Source 

#include <functional>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <iterator>
#include <memory.h>

using namespace std;

char w[1000100];
vector<pair<int,char> > v;

int main( ) {
	int i, len, m, k;
	char c[2];
		
	scanf( "%s", w );
	len = strlen( w );
	
	scanf( "%d", &m );
	while( m-- ) {
		scanf( "%1s", c );
		if( c[0] == 'I' ) {
			scanf( "%1s%d", c, &k );
			v.push_back( pair<int,char>( 0, 'a' ) );
			
			for( i=v.size()-2; i>=0 && v[i].first >= k; i-- ){
				v[i+1].first = v[i].first+1;
				v[i+1].second = v[i].second;
			}
			v[i+1].first = k;
			v[i+1].second = c[0];
		}
		else {
			int h;
			scanf( "%d", &k );
			h = k;
			for( i=0; i<v.size()&&v[i].first<k; i++ )
				h--;
			if( i<v.size() && v[i].first == k )
				printf( "%c\n", v[i].second );
			else
				printf( "%c\n", w[h-1] );
		}
	}
	return 0;
}