luogu P1382 楼房

二次联通门 : luogu P1382 楼房

/*

    luogu P1382 楼房

    线段树 + 扫描线 + 离散化

    正解貌似是堆。。。

       MMP。。。二段式线段树各种错误。。。

    离散化一下横坐标

    扫描线扫一下就好。。

    注意判断一个横坐标上对应两个y值的情况。。。

*/

#include <algorithm>

#include <cstdio>

#define Max 1000002

void read (int &now)

{

    now = ;

    bool temp = false;

    register char word = getchar ();

    while (word < '' || word > '')

    {

        if (word == '-')

            temp = true;

        word = getchar ();

    }

    while (word >= '' && word <= '')

    {

        now = now *  + word - '';

        word = getchar ();

    }

    if (temp)

        now = -now;

}

inline int min (int _Curs_, int ROcs_)

{

    return _Curs_ < ROcs_ ? _Curs_ : ROcs_;

}

inline int max (int _Curs_, int ROcs_)

{

    return _Curs_ > ROcs_ ? _Curs_ : ROcs_;

}

struct Segment_Tree_Data

{

    Segment_Tree_Data *Left, *Right;

    int l, r;

    int key;

    int Flandre;

    int Mid;

    Segment_Tree_Data ()

    {

        Left = NULL;

        Right = NULL;

        key = ;

        Flandre = ;

    }

};

struct Data_Type

{

    int l, r;

    int h;

    bool operator < (const Data_Type &now) const

    {

        return now.l < l;

    }

};

struct Point_Data

{

    int x, y;

};

Segment_Tree_Data *Root;

class Segment_Tree_Type

{

    public :

        void Build (Segment_Tree_Data *&now, int l, int r)

        {

            now = new Segment_Tree_Data ();

            now->l = l;

            now->r = r;

            if (l == r)

                return ;

            now->Mid = l + r >> ;

            Build (now->Left, l, now->Mid);

            Build (now->Right, now->Mid + , r);

        }

        void Change_Section (Segment_Tree_Data *&now, int l, int r, int to)

        {

            if (l <= now->l && r >= now->r)

            {

                now->key = max (now->key, to);

                now->Flandre = max (now->Flandre, to);

                return ;

            }

            if (now->Flandre)

            {

                now->Left->key = max (now->Flandre, now->Left->key);

                now->Right->key = max (now->Flandre, now->Right->key);

                now->Left->Flandre = max (now->Flandre, now->Left->Flandre);

                now->Right->Flandre = max (now->Flandre, now->Right->Flandre);

                now->Flandre = ;

            }

            if (l <= now->Mid)

                Change_Section (now->Left, l, min (now->Mid, r), to);

            if (r > now->Mid)

                Change_Section (now->Right, max (now->Mid + , l), r, to);

            now->key = max (now->Left->key, now->Right->key);

        }

        int Query (Segment_Tree_Data *&now, int pos)

        {

            if (now->l == now->r)

                return now->key;

            if (now->Flandre)

            {

                now->Left->key = max (now->Flandre, now->Left->key);

                now->Right->key = max (now->Flandre, now->Right->key);

                now->Left->Flandre = max (now->Flandre, now->Left->Flandre);

                now->Right->Flandre = max (now->Flandre, now->Right->Flandre);

                now->Flandre = ;

            }

            now->key = max (now->Left->key, now->Right->key);

            if (pos <= now->Mid)

                return Query (now->Left, pos);

            else

                return Query (now->Right, pos);

        }

};

Segment_Tree_Type Tree;

Data_Type data[Max];

int Answer;

int rank[Max << ];

int N;

int Size, Count;

Point_Data point[Max];

int main (int argc, char *argv[])

{

    read (N);

    for (int i = ; i <= N; i++)

    {

        read (data[i].h);

        read (data[i].l);

        read (data[i].r);

        rank[++Size] = data[i].l;

        rank[++Size] = data[i].r;

    }

    std :: sort (rank + , rank +  + Size);

    Size = std :: unique (rank + , rank +  + Size) - rank - ;

    Root = NULL;

    Tree.Build (Root, , Size);

    for (int i = ; i <= N; i++)

    {

        data[i].l = std :: lower_bound (rank + , rank +  + Size, data[i].l) - rank;

        data[i].r = std :: lower_bound (rank + , rank +  + Size, data[i].r) - rank;

        Tree.Change_Section (Root, data[i].l, data[i].r - , data[i].h);

    }

    for (int i = ; i <= Size; i++)

    {

        point[i].x = rank[i];

        point[i].y = Tree.Query (Root, i);

        if (point[i].y != point[i - ].y)

            Answer++;

    }

    printf ("%d\n", Answer << );

    for (int i = ; i <= Size; i++)

        if (point[i].y != point[i - ].y)

        {

            printf ("%d %d\n", point[i].x, point[i - ].y);

            printf ("%d %d\n", point[i].x, point[i].y);

        }

    return ;

}