#include <bits/stdc++.h>
using namespace std;
template< class TYPE >
class nrxTreap {
private:
struct treapNode {
TYPE key, minim, maxim; int priority;
treapNode *leftNode;
treapNode *rightNode;
treapNode() {
this -> priority = INT_MIN;
this -> minim = this -> key; this -> maxim = this -> key;
this -> leftNode = NULL;
this -> rightNode = NULL;
}
treapNode( TYPE key, int priority, treapNode *leftNode, treapNode *rightNode ) {
this -> key = key; this -> priority = priority;
this -> minim = key; this -> maxim = key;
this -> leftNode = leftNode;
this -> rightNode = rightNode;
}
} *root, *emptyNode;
void updateMinMax( treapNode *&node ) {
node -> minim = ( ( node -> leftNode == emptyNode ) ? node -> key : node -> leftNode -> minim );
node -> maxim = ( ( node -> rightNode == emptyNode ) ? node -> key : node -> rightNode -> maxim );
return;
}
void rotateLeft( treapNode *&node ) {
treapNode *auxNode = node -> leftNode;
node -> leftNode = auxNode -> rightNode;
auxNode -> rightNode = node; node = auxNode;
updateMinMax( node -> rightNode );
updateMinMax( node );
return;
}
void rotateRight( treapNode *&node ) {
treapNode *auxNode = node -> rightNode;
node -> rightNode = auxNode -> leftNode;
auxNode -> leftNode = node; node = auxNode;
updateMinMax( node -> leftNode );
updateMinMax( node );
return;
}
void balanceNode( treapNode *&node ) {
if( node -> leftNode -> priority > node -> priority )
rotateLeft( node );
if( node -> rightNode -> priority > node -> priority )
rotateRight( node );
return;
}
TYPE lowerBound( treapNode *&node, TYPE key ) {
if( node == emptyNode )
return node -> key;
if( node -> key == key )
return key;
if( node -> key > key ) {
if( node -> leftNode == emptyNode || node -> leftNode -> maxim < key )
return node -> key;
else
return lowerBound( node -> leftNode, key );
} else
return lowerBound( node -> rightNode, key );
}
TYPE upperBound( treapNode *&node, TYPE key ) {
if( node == emptyNode )
return node -> key;
if( node -> key == key )
return key;
if( node -> key > key )
return upperBound( node -> leftNode, key );
else {
if( node -> rightNode == emptyNode || node -> rightNode -> minim > key )
return node -> key;
else
return upperBound( node -> rightNode, key );
}
}
int countKey( treapNode *node, TYPE key ) {
if( node == emptyNode )
return 0;
if( node -> key == key )
return 1;
if( node -> key > key )
return countKey( node -> leftNode, key );
else
return countKey( node -> rightNode, key );
}
bool findKey( treapNode *&node, TYPE key ) {
if( node == emptyNode )
return false;
if( node -> key == key )
return true;
if( node -> key > key )
return findKey( node -> leftNode, key );
else
return findKey( node -> rightNode, key );
}
bool insertKey( treapNode *&node, TYPE key, int priority ) {
bool ok;
if( node == emptyNode ) {
node = new treapNode( key, priority, emptyNode, emptyNode );
return true;
}
if( node -> key == key )
return false;
if( node -> key > key )
ok = insertKey( node -> leftNode, key, priority );
else
ok = insertKey( node -> rightNode, key, priority );
balanceNode( node );
return ok;
}
bool eraseKey( treapNode *&node, TYPE key ) {
if( node == emptyNode )
return false;
if( node -> key > key )
return eraseKey( node -> leftNode, key );
if( node -> key < key )
return eraseKey( node -> rightNode, key );
if( node -> leftNode == emptyNode && node -> rightNode == emptyNode ) {
delete node; node = emptyNode;
return true;
}
else {
if( node -> leftNode -> priority > node -> rightNode -> priority )
rotateLeft( node );
else
rotateRight( node );
return eraseKey( node, key );
}
}
public:
nrxTreap() {
srand( time(0) ); TYPE randomKey;
root = emptyNode = new treapNode;
}
bool emptyTreap( void ) { return root == emptyNode; };
TYPE findMin ( void ) { return root -> minim; }
TYPE findMax ( void ) { return root -> maxim; }
TYPE findFirst( void ) { return root -> minim; }
TYPE findLast ( void ) { return root -> maxim; }
TYPE lowerBound( TYPE key ) { return lowerBound( root, key ); }
TYPE upperBound( TYPE key ) { return upperBound( root, key ); }
int countKey( TYPE key ) { return countKey( root, key ); }
bool insertKey( TYPE key ) { return insertKey( root, key, rand() % INT_MAX ); }
bool eraseKey ( TYPE key ) { return eraseKey ( root, key ); }
bool findKey ( TYPE key ) { return findKey ( root, key ); }
void clearTreap( void ) { while( !emptyTreap() ) eraseKey( root -> minim ); return; }
void splitTreap( TYPE key, treapNode *&myTreap1, treapNode *&myTreap2 ) {
insertKey( root, key, INT_MAX );
myTreap1 = root -> leftNode;
myTreap2 = root -> rightNode;
return;
}
void joinTreap( treapNode *&myTreap1, treapNode *&myTreap2, treapNode *&myTreap ) {
TYPE randomKey;
treapNode *newRoot = new treapNode( randomKey, INT_MIN, myTreap1, myTreap2 );
eraseKey( newRoot, newRoot -> key ); myTreap = newRoot;
return;
}
};
template< class TYPE >
class nrxMultiTreap {
private:
struct treapNode {
TYPE key, minim, maxim; int priority, cntKeys;
treapNode *leftNode;
treapNode *rightNode;
treapNode() {
this -> priority = INT_MIN; this -> cntKeys = 0;
this -> minim = this -> key; this -> maxim = this -> key;
this -> leftNode = NULL;
this -> rightNode = NULL;
}
treapNode( TYPE key, int priority, int cntKeys, treapNode *leftNode, treapNode *rightNode ) {
this -> key = key; this -> priority = priority; this -> cntKeys = cntKeys;
this -> minim = key; this -> maxim = key;
this -> leftNode = leftNode;
this -> rightNode = rightNode;
}
} *root, *emptyNode;
void updateMinMax( treapNode *&node ) {
node -> minim = ( ( node -> leftNode == emptyNode ) ? node -> key : node -> leftNode -> minim );
node -> maxim = ( ( node -> rightNode == emptyNode ) ? node -> key : node -> rightNode -> maxim );
return;
}
void rotateLeft( treapNode *&node ) {
treapNode *auxNode = node -> leftNode;
node -> leftNode = auxNode -> rightNode;
auxNode -> rightNode = node; node = auxNode;
updateMinMax( node -> rightNode );
updateMinMax( node );
return;
}
void rotateRight( treapNode *&node ) {
treapNode *auxNode = node -> rightNode;
node -> rightNode = auxNode -> leftNode;
auxNode -> leftNode = node; node = auxNode;
updateMinMax( node -> leftNode );
updateMinMax( node );
return;
}
void balanceNode( treapNode *&node ) {
if( node -> leftNode -> priority > node -> priority )
rotateLeft( node );
if( node -> rightNode -> priority > node -> priority )
rotateRight( node );
return;
}
TYPE lowerBound( treapNode *&node, TYPE key ) {
if( node == emptyNode )
return node -> key;
if( node -> key == key )
return key;
if( node -> key > key ) {
if( node -> leftNode == emptyNode || node -> leftNode -> maxim < key )
return node -> key;
else
return lowerBound( node -> leftNode, key );
} else
return lowerBound( node -> rightNode, key );
}
TYPE upperBound( treapNode *&node, TYPE key ) {
if( node == emptyNode )
return node -> key;
if( node -> key == key )
return key;
if( node -> key > key )
return upperBound( node -> leftNode, key );
else {
if( node -> rightNode == emptyNode || node -> rightNode -> minim > key )
return node -> key;
else
return upperBound( node -> rightNode, key );
}
}
int countKey( treapNode *node, TYPE key ) {
if( node == emptyNode )
return 0;
if( node -> key == key )
return node -> cntKeys;
if( node -> key > key )
return countKey( node -> leftNode, key );
else
return countKey( node -> rightNode, key );
}
bool findKey( treapNode *node, TYPE key ) {
if( node == emptyNode )
return false;
if( node -> key == key )
return true;
if( node -> key > key )
return findKey( node -> leftNode, key );
else
return findKey( node -> rightNode, key );
}
bool insertKey( treapNode *&node, int key, int priority ) {
bool ok;
if( node == emptyNode ) {
node = new treapNode( key, priority, 1, emptyNode, emptyNode );
return true;
}
if( node -> key == key ) {
node -> cntKeys ++;
return true;
}
if( node -> key > key )
ok = insertKey( node -> leftNode, key, priority );
else
ok = insertKey( node -> rightNode, key, priority );
balanceNode( node );
return ok;
}
bool eraseKey( treapNode *&node, int key, bool &globalOk ) {
if( node == emptyNode )
return false;
if( node -> key > key )
return eraseKey( node -> leftNode, key, globalOk );
if( node -> key < key )
return eraseKey( node -> rightNode, key, globalOk );
if( globalOk == true ) {
globalOk = false;
node -> cntKeys --;
if( node -> cntKeys > 0 )
return true;
}
if( node -> leftNode == emptyNode && node -> rightNode == emptyNode ) {
delete node; node = emptyNode;
return true;
}
else {
if( node -> leftNode -> priority > node -> rightNode -> priority )
rotateLeft( node );
else
rotateRight( node );
return eraseKey( node, key, globalOk );
}
}
public:
nrxMultiTreap() {
srand( time(0) ); TYPE randomKey;
root = emptyNode = new treapNode;
}
bool emptyTreap( void ) { return root == emptyNode; };
TYPE findMin ( void ) { return root -> minim; }
TYPE findMax ( void ) { return root -> maxim; }
TYPE findFirst( void ) { return root -> minim; }
TYPE findLast ( void ) { return root -> maxim; }
TYPE lowerBound( TYPE key ) { return lowerBound( root, key ); }
TYPE upperBound( TYPE key ) { return upperBound( root, key ); }
int countKey( TYPE key ) { return countKey ( root, key ); }
bool insertKey( TYPE key ) { return insertKey( root, key, rand() % INT_MAX ); }
bool eraseKey ( TYPE key ) { bool globalOk = true; return eraseKey ( root, key, globalOk ); }
bool findKey ( TYPE key ) { return findKey ( root, key ); }
void clearTreap( void ) { while( !emptyTreap() ) eraseKey( root -> minim ); return; }
void splitTreap( TYPE key, treapNode *myTreap1, treapNode *myTreap2 ) {
insertKey( root, key, INT_MAX );
myTreap1 = root -> leftNode;
myTreap2 = root -> rightNode;
return;
}
void joinTreap( treapNode *myTreap1, treapNode *myTreap2, treapNode *myTreap ) {
TYPE randomKey; bool globalOk = true;
treapNode *newRoot = new treapNode( randomKey, INT_MIN, 1, myTreap1, myTreap2 );
eraseKey( newRoot, newRoot -> key, globalOk ); myTreap = newRoot;
return;
}
};
template< class TYPE >
class nrxPositionTreap {
private:
int treapSize = 0;
static const int CONST1 = 29;
static const int CONST2 = 31;
static const int MOD1 = 666013;
static const int MOD2 = 666019;
static const int MAXSIZE = 200005;
vector< pair<int, int> > myHash;
struct treapNode {
TYPE key, minim, maxim, first, last; int nodeSize, priority;
pair <int, int> nodeHash; bool reversed;
treapNode *leftNode;
treapNode *rightNode;
treapNode() {
this -> nodeSize = 0; this -> nodeHash = make_pair( 0, 0 ); this -> priority = INT_MIN; this -> reversed = false;
this -> minim = this -> key; this -> maxim = this -> key; this -> first = this -> key; this -> last = this -> key;
this -> leftNode = NULL;
this -> rightNode = NULL;
}
treapNode( TYPE key, int nodeSize, int priority, pair <int, int> nodeHash, treapNode *leftNode, treapNode *rightNode ) {
this -> key = key; this -> nodeSize = nodeSize; this -> priority = priority; this -> nodeHash = nodeHash;
this -> minim = key; this -> maxim = key; this -> first = key; this -> last = key; this -> reversed = false;
this -> leftNode = leftNode;
this -> rightNode = rightNode;
}
} *root, *emptyNode;
void updateSize( treapNode *&node ) {
node -> nodeSize = 1 + node -> leftNode -> nodeSize + node -> rightNode -> nodeSize;
return;
}
void updateHash( treapNode *&node ) {
node -> nodeHash.first = (int) ( ( node -> rightNode -> nodeHash.first +
myHash[ node -> rightNode -> nodeSize + 1 ].first +
node -> leftNode -> nodeHash.first * 1LL * myHash[ node -> rightNode -> nodeSize + 2 ].first ) % MOD1 );
node -> nodeHash.second = (int) ( ( node -> rightNode -> nodeHash.second +
myHash[ node -> rightNode -> nodeSize + 1 ].second +
node -> leftNode -> nodeHash.second * 1LL * myHash[ node -> rightNode -> nodeSize + 2 ].second ) % MOD2 );
return;
}
void updateMinMax( treapNode *&node ) {
node -> minim = node -> key;
if( node -> leftNode != emptyNode ) node -> minim = min( node -> minim, node -> leftNode -> minim );
if( node -> rightNode != emptyNode ) node -> minim = min( node -> minim, node -> rightNode -> minim );
node -> maxim = node -> key;
if( node -> leftNode != emptyNode ) node -> maxim = max( node -> maxim, node -> leftNode -> maxim );
if( node -> rightNode != emptyNode ) node -> maxim = max( node -> maxim, node -> rightNode -> maxim );
return;
}
void updateFirstLast( treapNode *&node ) {
node -> first = ( ( node -> leftNode == emptyNode ) ? node -> key : node -> leftNode -> first );
node -> last = ( ( node -> rightNode == emptyNode ) ? node -> key : node -> rightNode -> last );
return;
}
void updateReverse( treapNode *&node ) {
if( node -> reversed == true ) {
swap( node -> leftNode, node -> rightNode ); node -> reversed = false;
if( node -> leftNode != emptyNode )
node -> leftNode -> reversed = !( node -> leftNode -> reversed );
if( node -> rightNode != emptyNode )
node -> rightNode -> reversed = !( node -> rightNode -> reversed );
}
}
void updateValues( treapNode *&node ) {
updateReverse( node );
updateSize( node );
/* updateHash( node ); */ // Linia asta de cod consuma mult timp...
updateMinMax( node );
updateFirstLast( node );
}
void rotateLeft( treapNode *&node ) {
updateValues( node );
updateValues( node -> leftNode );
treapNode *auxNode = node -> leftNode;
node -> leftNode = auxNode -> rightNode;
auxNode -> rightNode = node; node = auxNode;
updateValues( node -> rightNode );
updateValues( node );
return;
}
void rotateRight( treapNode *&node ) {
updateValues( node );
updateValues( node -> rightNode );
treapNode *auxNode = node -> rightNode;
node -> rightNode = auxNode -> leftNode;
auxNode -> leftNode = node; node = auxNode;
updateValues( node -> leftNode );
updateValues( node );
return;
}
void balanceNode( treapNode *&node ) {
updateReverse( node );
if( node -> leftNode -> priority > node -> priority )
rotateLeft( node );
if( node -> rightNode -> priority > node -> priority )
rotateRight( node );
return;
}
TYPE findKey( treapNode *&node, int position ) {
updateReverse( node );
if( node == emptyNode )
return node -> key;
if( node -> leftNode -> nodeSize + 1 == position )
return node -> key;
if( node -> leftNode -> nodeSize + 1 > position )
return findKey( node -> leftNode, position );
else
return findKey( node -> rightNode, position - ( node -> leftNode -> nodeSize + 1 ) );
}
bool insertKey( treapNode *&node, int position, TYPE key, int priority ) {
bool ok; updateReverse( node );
if( node == emptyNode ) {
if( position != 1 )
return false;
node = new treapNode( key, 1, priority, myHash[1], emptyNode, emptyNode );
return true;
}
if( node -> leftNode -> nodeSize + 1 >= position )
ok = insertKey( node -> leftNode, position, key, priority );
else
ok = insertKey( node -> rightNode, position - ( node -> leftNode -> nodeSize + 1 ), key, priority );
updateValues( node ); balanceNode( node );
return ok;
}
bool eraseKey( treapNode *&node, int position ) {
bool ok; updateValues( node );
if( node == emptyNode )
return false;
if( node -> leftNode -> nodeSize + 1 > position ) {
ok = eraseKey( node -> leftNode, position );
updateValues( node ); return ok;
}
if( node -> leftNode -> nodeSize + 1 < position ) {
ok = eraseKey( node -> rightNode, position - ( node -> leftNode -> nodeSize + 1 ) );
updateValues( node ); return ok;
}
if( node -> leftNode == emptyNode && node -> rightNode == emptyNode ) {
delete node; node = emptyNode;
return true;
}
else {
if( node -> leftNode -> priority > node -> rightNode -> priority ) {
rotateLeft( node );
ok = eraseKey( node -> rightNode, node -> rightNode -> leftNode -> nodeSize + 1 );
} else {
rotateRight( node );
ok = eraseKey( node -> leftNode, node -> leftNode -> leftNode -> nodeSize + 1 );
}
updateValues( node );
return ok;
}
}
public:
nrxPositionTreap() {
srand( time(0) );
root = emptyNode = new treapNode;
myHash.resize( MAXSIZE ); myHash[0] = make_pair( 1, 1 );
for( int i = 1; i < MAXSIZE; i ++ ) {
myHash[i].first = ( myHash[i - 1].first * CONST1 ) % MOD1;
myHash[i].second = ( myHash[i - 1].second * CONST2 ) % MOD2;
}
myHash[0] = make_pair( 0, 0 );
}
nrxPositionTreap( int SIZE ) {
srand( time(0) );
root = emptyNode = new treapNode;
myHash.resize( SIZE + 1 ); myHash[0] = make_pair( 1, 1 );
for( int i = 1; i <= SIZE; i ++ ) {
myHash[i].first = ( myHash[i - 1].first * CONST1 ) % MOD1;
myHash[i].second = ( myHash[i - 1].second * CONST2 ) % MOD2;
}
myHash[0] = make_pair( 0, 0 );
}
bool emptyTreap( void ) { return root == emptyNode; }
TYPE findMin ( void ) { return root -> minim; }
TYPE findMax ( void ) { return root -> maxim; }
TYPE findFirst( void ) { return root -> first; }
TYPE findLast ( void ) { return root -> last ; }
TYPE lowerBound( int position ) { return findKey( root, position ); }
TYPE upperBound( int position ) { return findKey( root, position ); }
TYPE rangeFirst( int left, int right ) { return findKey( root, left ); }
TYPE rangeLast ( int left, int right ) { return findKey( root, right ); }
bool insertKey( int position, TYPE key ) { return insertKey( root, position, key, rand() % INT_MAX ); }
bool eraseKey ( int position ) { return eraseKey ( root, position ); }
bool findKey ( int position ) { return findKey ( root, position ); }
int accessKey ( int position ) { return findKey( root, position ); }
void clearTreap( void ) { while( !emptyTreap() ) eraseKey( 1 ); return; }
void splitTreap( treapNode *&myTreap, int position, treapNode *&myTreap1, treapNode *&myTreap2 ) {
TYPE randomKey;
insertKey( myTreap, position + 1, randomKey, INT_MAX );
myTreap1 = myTreap -> leftNode; myTreap2 = myTreap -> rightNode;
return;
}
void joinTreap( treapNode *&myTreap1, treapNode *&myTreap2, treapNode *&myTreap ) {
TYPE randomKey; pair <int, int> randomHash;
treapNode *auxRoot = new treapNode( randomKey, 1 + myTreap1 -> nodeSize + myTreap2 -> nodeSize, INT_MIN, randomHash, myTreap1, myTreap2 );
eraseKey( auxRoot, auxRoot -> leftNode -> nodeSize + 1 ); myTreap = auxRoot;
return;
}
void rangeErase( int left, int right ) {
for( int i = left; i <= right; i ++ )
eraseKey( root, left );
return;
}
void rangeReverse( int left, int right ) {
treapNode *myTreap1, *myTreap2, *myTreap3, *myTreap4;
splitTreap( root, left - 1, myTreap1, myTreap2 );
splitTreap( myTreap2, right - ( left - 1 ), myTreap3, myTreap4 );
myTreap3 -> reversed = !( myTreap3 -> reversed );
joinTreap( myTreap3, myTreap4, myTreap2 );
joinTreap( myTreap1, myTreap2, root );
return;
}
TYPE rangeMin( int left, int right ) {
treapNode *myTreap1, *myTreap2, *myTreap3, *myTreap4; TYPE minim;
splitTreap( root, left - 1, myTreap1, myTreap2 );
splitTreap( myTreap2, right - ( left - 1 ), myTreap3, myTreap4 );
minim = myTreap3 -> minim;
joinTreap( myTreap3, myTreap4, myTreap2 );
joinTreap( myTreap1, myTreap2, root );
return minim;
}
TYPE rangeMax( int left, int right ) {
treapNode *myTreap1, *myTreap2, *myTreap3, *myTreap4; TYPE maxim;
splitTreap( root, left - 1, myTreap1, myTreap2 );
splitTreap( myTreap2, right - ( left - 1 ), myTreap3, myTreap4 );
maxim = myTreap3 -> maxim;
joinTreap( myTreap3, myTreap4, myTreap2 );
joinTreap( myTreap1, myTreap2, root );
return maxim;
}
};
ifstream inputFile ( "secv8.in" );
ofstream outputFile( "secv8.out" );
int N, K, X, Y; char ch;
nrxPositionTreap <int> myTreap( 250000 );
int main( int argc, const char *argv[] ){
inputFile >> N >> K;
for( int i = 1; i <= N; i ++ ) {
inputFile >> ch;
switch( ch ) {
case 'I': {
inputFile >> X >> Y;
myTreap.insertKey( X, Y );
break;
}
case 'A': {
inputFile >> X;
outputFile << myTreap.accessKey( X ) << "\n";
break;
}
case 'R': {
inputFile >> X >> Y;
myTreap.rangeReverse( X, Y );
break;
}
case 'D': {
inputFile >> X >> Y;
myTreap.rangeErase( X, Y );
break;
}
}
}
while( !myTreap.emptyTreap() ) {
outputFile << myTreap.findFirst() << " ";
myTreap.eraseKey( 1 );
}
return 0;
}