用线段树解pku2352--西电

《用线段树解pku2352--西电》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include #include const int LEN = 15005;//坐标处理struct NODE{    int x; //X坐标    int y; //Y坐标    int addr; //第几个点}node[LEN];int cmp ( const void *a, const void *b ){    int ans = ( (NODE *)a )->x-( (NODE *)b )->x;    if ( !ans )    {   

2、     ans = ( (NODE *)a )->y-( (NODE *)b )->y;    }    return ans;}//记录答案的数组int answer[LEN];//线段树struct{    int num; //区间中点的个数    int b, e; //左右区间    int lson, rson; //左右孩子}tree[LEN*25];int next_tree;void creat ( int b, int e ) //建树{    int  p = next_tr

3、ee;    next_tree ++;    tree[p].b = b;    tree[p].e = e;    tree[p].lson = -1;    tree[p].rson = -1;    tree[p].num = 0;    if ( b!=e )    {        tree[p].lson = next_tree;        creat ( b, (b+e)/2 );        tree[p].rson = next_tree;        creat ( (

4、b+e)/2+1, e );    }}void ins ( int p, int key ) //插入一个结点{    if ( tree[p].b==tree[p].e )    {        tree[p].num ++;    }    else    {        int mid = ( tree[p].b+tree[p].e )/2;        if ( key>mid )        {            ins ( tree[p].rson, key );     

5、   }        else        {            ins ( tree[p].lson, key );        }        tree[p].num = tree[ tree[p].lson ].num+tree[ tree[p].rson ].num;    }}int ser ( int p, int key ) //查找函数{    if ( tree[p].b==tree[p].e )    {        return tree[p].num;    }

6、    else    {        int mid = ( tree[p].b+tree[p].e )/2;        if ( key>mid )        {            return tree[ tree[p].lson ].num + ser ( tree[p].rson, key );        }        else        {            return ser ( tree[p].lson, key );        }    }}vo

7、id work ( int n, int max ) //主要的工作函数{    next_tree = 0;    for ( int i=0; i

8、i].y );        answer[addr] ++ ;        ins ( 0, node[i].y );    }}int main (){    int n;    int max = -1;;    scanf ( "%d", &n );    for ( int i=0; i