http://poj.org/problem?id=2892
#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( "%dn", query( k ) );
}
else {
rebuild( sk.top() );
sk.pop();
}
}
return 0;
}