1028 - 2.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

#include <iostream>
using namespace std;

const int maxX = 32000;
const int maxC = 15000;
int level[maxC + 100];
int len = 1;
class sTree
{
public:
       int left, right;
       int val;
       sTree* lc, * rc;
       void Construct(int l , int r );
       void Insert(int x);
       int Getval(int x);
}seg[maxX*4+100];

void sTree::Construct( int l ,int r )
{
     left = l , right = r;
     val = 0;
     if( left == right ){ lc=NULL, rc = NULL; return; }
     int mid = ( left + right ) >> 1; 
     lc = &seg[len++];
     lc->Construct(left,mid);
     rc = &seg[len++];
     rc->Construct(mid+1,right);
}

void sTree::Insert( int x )
{
	 val++; 
     if( left == right ){return;}
     
     int mid = (left + right) >> 1;
     
     if( x <= mid ) lc -> Insert(x);
     if( x > mid ) rc -> Insert(x);
}

int sTree::Getval(int x)
{
    if (left == right) return val;
    if (x == right) return val;

    int mid = (left + right) >> 1;
    
    if( x <= mid ) return val = lc -> Getval(x);	//原来是 return val = lc ->Getval(x);为什么不过？
    if( x >  mid ) return val = lc -> Getval(mid) + rc-> Getval(x); //important!

}
int main()
{
    int i, x, y, n;
    memset(level, 0,sizeof(level) );
    seg[0].Construct(0,maxX+2);
    cin >> n; 
    for( i = 1 ; i <= n; i++ )
	{
		cin >> x >> y;
		seg->Insert(x);
	    level[ seg->Getval(x)-1 ]++;

	}
	for( i = 0 ; i <= n-1; i++ )
		cout<< level[i ]<< endl;


    return 0;
}