// problem zju 1610
// Segment Tree
#define NoColor -1
#define MulColor -2
#include <stdio.h>
#include <string.h>
int Len;
struct TNode {
int left , right;
int col;
TNode *LeftChild , *RightChild;
void Construct ( int , int );
void Insert ( int , int , int );
void Calculate ();
} Tree [16000] , *Root = &Tree [0];
int CalColor [8001] , Many [8001];
void TNode :: Construct ( int l , int r )
{
left = l; right = r;
if ( l + 1 == r ) { LeftChild = NULL; RightChild = NULL; return; }
int mid = ( l + r ) >> 1;
LeftChild = &Tree [Len ++];
RightChild = &Tree [Len ++];
LeftChild->Construct( l , mid );
RightChild->Construct( mid , r );
}
void TNode :: Insert ( int l , int r , int c )
{
if ( col == c ) return;
if ( l == left && r == right ) { col = c; return; }
int mid = ( left + right ) >> 1;
if ( col != MulColor ) { LeftChild -> col = col; RightChild -> col = col; }
col = MulColor;
if ( r <= mid ) { LeftChild -> Insert ( l , r , c ); return; }
if ( l >= mid ) { RightChild -> Insert ( l , r , c ); return; }
LeftChild -> Insert ( l , mid , c );
RightChild -> Insert ( mid , r , c );
}
void TNode :: Calculate ()
{
if ( col != MulColor && col != NoColor ) {
int i;
for ( i = left; i < right; i ++ ) CalColor [i] = col;
}
if ( col == MulColor ) { LeftChild -> Calculate (); RightChild -> Calculate (); }
}
main ()
{
int Total , a , b , c , i , t;
Len = 1; Tree [0].Construct( 0 , 8000 );
// printf ( "After Construct the Tree , Len = %d\n" , Len );
while ( scanf ( "%d" , &Total ) != EOF ) {
Tree [0].col = NoColor;
while ( Total ) {
scanf ( "%d %d %d" , &a , &b , &c );
Root -> Insert( a , b , c );
Total --;
}
memset ( CalColor , 0xff , sizeof ( CalColor ) );
memset ( Many , 0 , sizeof ( Many ));
Root -> Calculate ();
t = -1;
for ( i = 0; i <= 8000; i ++ ) {
if ( CalColor [i] == t ) continue;
t = CalColor [i];
if ( t != -1 ) Many [t] ++;
}
for ( i = 0; i <= 8000; i ++ ) if ( Many [i] )
printf ( "%d %d\n" , i , Many [i] );
printf ( "\n" );
}
}
// Problem zju2451
// DP with Segment Tree
#include <stdio.h>
#define MAX 50000
int Len;
struct TNode {
int left , right;
int minstep;
TNode *LeftChild , *RightChild;
void Construct ( int , int );
void Insert ( int , int );
int GetRank ( int , int );
} STree [MAX * 2 + 2] , *Root = &STree [0];
int N , M;
void TNode :: Construct ( int l , int r )
{
left = l; right = r; minstep = 999999;
if ( l == r ) { LeftChild = NULL; RightChild = NULL; return; }
int mid = ( l + r ) >> 1;
LeftChild = &STree [Len ++];
RightChild = &STree [Len ++];
LeftChild->Construct ( l , mid );
RightChild->Construct( mid + 1 , r );
}
void TNode :: Insert ( int p , int x )
{
if ( x < minstep ) minstep = x;
if ( left == right ) return;
if ( p <= ( left + right ) >> 1 ) LeftChild->Insert( p , x );
else RightChild->Insert( p , x );
}
int TNode :: GetRank ( int l , int r )
{
if ( l == left && r == right ) return minstep;
int mid = ( left + right ) >> 1;
if ( r <= mid ) return LeftChild->GetRank( l , r );
if ( l > mid ) return RightChild->GetRank( l , r );
int ret1 , ret2;
ret1 = LeftChild->GetRank( l , mid );
ret2 = RightChild->GetRank( mid + 1 , r );
return ret1 < ret2 ? ret1 : ret2;
}
main ()
{
int i , a , b , p;
while ( scanf ( "%d %d" , &N , &M ) != EOF ) {
Len = 1; Root->Construct( 1 , N );
Root->Insert ( 1 , 0 );
for ( i = 0; i < M; i ++ ) {
scanf ( "%d%d" , &a , &b );
if ( a < b ) {
p = Root->GetRank ( a , b - 1 );
Root->Insert ( b , p + 1 );
}
}
printf ( "%d\n" , Root->GetRank( N , N ) );
}
}
// PKU 2104
// Segment Tree && Binnary Search
#include <stdio.h>
#define MAX 100000
int len;
struct TNode {
int left , right;
char depth;
TNode *LeftChild , *RightChild;
void construct ( int , int , int );
int GetRank ();
} Node [2 * MAX + 2];
int SortArray [18] [MAX + 2];
int Key , ls , rs;
void TNode :: construct ( int l , int r , int dep )
{
left = l; right = r; depth = dep;
if ( left == right ) {
scanf ( "%d" , &SortArray [dep] [l] );
return;
}
int mid = ( l + r ) >> 1;
LeftChild = &Node [len ++];
LeftChild->construct( l , mid , dep + 1 );
RightChild = &Node [len ++];
RightChild->construct( mid + 1 , right , dep + 1 );
int i = left , j = mid + 1 , k = left;
while ( i <= mid && j <= r ) {
if ( SortArray [dep + 1] [i] < SortArray [dep + 1] [j] )
SortArray [dep] [k ++] = SortArray [dep + 1] [i ++];
else
SortArray [dep] [k ++] = SortArray [dep + 1] [j ++];
}
while ( i <= mid ) SortArray [dep] [k ++] = SortArray [dep + 1] [i ++];
while ( j <= right ) SortArray [dep] [k ++] = SortArray [dep + 1] [j ++];
}
int TNode :: GetRank ()
{
if ( ls <= left && right <= rs ) {
if ( SortArray [depth] [left] >= Key ) return 0;
if ( SortArray [depth] [right] < Key ) return right - left + 1;
if ( SortArray [depth] [right] == Key ) return right - left;
int low = left , high = right , mid;
while ( low + 1 < high ) {
mid = ( low + high ) >> 1;
if ( SortArray [depth] [mid] < Key ) low = mid;
else high = mid;
}
return low - left + 1;
}
int ret = 0;
if ( ls <= LeftChild->right ) ret += LeftChild->GetRank();
if ( RightChild->left <= rs ) ret += RightChild->GetRank();
return ret;
}
main ()
{
int N , Q , i;
int low , high , mid , Index;
scanf ( "%d%d" , &N , &Q );
len = 1; Node [0].construct( 0 , N - 1 , 0 );
for ( i = 0; i < Q; i ++ ) {
scanf ( "%d%d%d" , &ls , &rs , &Index );
ls --; rs --;
low = 0; high = N;
while ( low + 1 < high ) {
mid = ( low + high ) >> 1;
Key = SortArray [0] [mid];
if ( Node [0].GetRank() >= Index ) high = mid;
else low = mid;
}
printf ( "%d\n" , SortArray [0] [low] );
}
}