线段树；
// 离散化的线段树；
#include < stdio.h >
#include < algorithm >
#include < memory.h >
using namespace std;
const int MAX = 1100000 ;
int p[ 3 * MAX];
int b[MAX];
int c[MAX];
int q[ 3 * MAX];
int Min[MAX];
int Max[MAX];
class IntervalTree
{
public :
int n;
IntervalTree();
void set ( int x);
int InsOrDel( int x, int test);
int FMAX();
int FMIN();
int Find( int x);
} ;
IntervalTree::IntervalTree()
{
memset(p, 0 , sizeof (p));
}
void IntervalTree:: set ( int m)
{
n = m;
/**//**/ /**//* initial n to the smallest number；
int k=Insert(1,1);
for(int i=1;i<=k;i*=2)
p[i]=n;
*/
}
int IntervalTree::InsOrDel( int x, int test) // test=1,add;test=0,delete;
{
int left = 0 ,right = n;
int k = 1 ;
int mid;
while (left < right)
{
mid = (left + right) >> 1 ;
if (test > 0 )
p[k] ++ ;
else p[k] -- ;
if (x <= c[mid]) {
k <<= 1 ;
right = mid;
}
else {
k <<= 1 ;
k ++ ;
left = mid + 1 ;
}
}
if (test > 0 ) {
p[k] ++ ;
q[k] = x;
}
else {
p[k] -- ;
}
return k;
}
int IntervalTree::FMAX() // find the max;
{
int k;
k = 1 ;
while (p[ 2 * k] > 0 || p[ 2 * k + 1 ] > 0 ) {
if (p[ 2 * k + 1 ] > 0 )k = 2 * k + 1 ;
else k = 2 * k;
}
return q[k];
}
int IntervalTree::FMIN() // find the min;
{
int k;
k = 1 ;
while (p[ 2 * k] > 0 || p[ 2 * k + 1 ] > 0 ) {
if (p[ 2 * k] > 0 )k = 2 * k;
else k = 2 * k + 1 ;
}
return q[k];
}
int IntervalTree::Find( int t) // Find the index of t;
{
int left = 1 ,right = n;
int mid;
int k = 1 ;
while (left < right) {
mid = (left + right) >> 1 ;
if (t <= p[k]) {
k <<= 1 ;
right = mid;
}
else {
t -= p[k];
k <<= 1 ;
k ++ ;
left = mid + 1 ;
}
}
mid = (left + right) >> 1 ;
if (p[mid] == t) return mid;
else return - 1 ; // t isn't in the tree;
}
int main()
{
IntervalTree a;
int l,i;
int max,min;
int k,n;
int m;
while (scanf( " %d%d " , & n, & k) != EOF) {
memset(p, 0 , sizeof (p));
for (i = 0 ;i < n;i ++ ) {
scanf( " %d " ,b + i);
c[i] = b[i];
}
sort(c,c + n);
// 离散化，相同的点合并;
for (i = 0 ,m = 0 ;i < n;i ++ ,m ++ ) {
while (i < n - 1 && c[i] == c[i + 1 ])i ++ ;
c[m] = c[i];
}
a. set (m - 1 ); // initial;
return 0 ;
}