2892.txt

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

Problem Id:2892  User Id:fzk 
Memory:708K  Time:405MS
Language:C++  Result:Accepted

Source 

#include <functional>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>

using namespace std;

map< int, int, less<int> > s;

int query( int k ) {
	map<int, int, less<int> >::iterator it;
	it = s.lower_bound( k );
	if( it->second > k )
		return 0;
	return it->first - it->second + 1;
}

void destroy( int k ) {
	map< int, int, less<int> >::iterator it;
	it = s.lower_bound( k );
	
	if( it->second > k )
		return;

	pair<int,int> p = *it;
	s.erase( it );
	
	
	if( p.second <= k-1 )
		s.insert( pair<int,int>( k-1, p.second ) );
	if( p.first >= k+1 )
		s.insert( pair<int,int>( p.first, k+1 ) );
}

void rebuild( int k ) {
	map< int, int, less<int> >::iterator it1, it2;
	it1 = s.lower_bound( k+1 );
	it2 = s.lower_bound( k-1 );
	
	pair<int,int> p;
	
	if( it1->second == k+1 ) {
		p.first = it1->first;
		s.erase( it1 );
	}
	else
		p.first = k;
	
	if( it2->first == k-1 ) {
		p.second = it2->second;
		s.erase( it2 );
	}
	else
		p.second = k;
	s.insert( p );
}


stack<int> sk;

int main( ) {
	int n, m, k;
	char c[2];
	scanf( "%d%d", &n, &m );
	s.insert( pair<int,int>( n, 1 ) );
	while( m-- ) {
		scanf( "%1s", c );
		if( c[0] == 'D' ) {
			scanf( "%d", &k );
			sk.push( k );
			destroy( k );
		}
		else if( c[0] == 'Q' ) {
			scanf( "%d", &k );
			printf( "%d\n", query( k ) );
		}
		else {
			rebuild( sk.top() );
			sk.pop();
		}
			
	}
	return 0;
}