Codeforces 35E Parade 扫描线 + list

主题链接：点击打开链接

意甲冠军：特定n矩阵（总是接近底部x轴）

然后找到由上面的矩阵所包围的路径，的点

给定n

以下n行给定 y [x1, x2] 表示矩阵的高度和2个x轴坐标

思路：

扫描线维护每段区间的线段最大的y值

则我们訪问每一个x轴坐标，就相当于訪问x轴坐标向右最短的那个小区间上的最大y值。

则能够得到[x,y] 和 [x+1, y] 这样2个点

当我们发现存在高度差时（且x轴不同样）

那么则手动加入一个点（这个点一定是与y大的点的x同样，y小的点的y同样）

再把3个相邻点且有同样y值的中间点删除。

再在首尾各添加一个底边的点就可以。

由于涉及链表的添加和删除。所以用stl的list。

#include <cstdio>

#include <algorithm>

#include<map>

#include<vector>

#include<list>

using namespace std;

#define N 400010

#define L(x) (x<<1)

#define R(x) (x<<1|1)

struct node{

    int l,r;

    int y, mid;

}tree[N<<2];

void push_down(int id){

	if(tree[id].l + 1==tree[id].r)return;

	if(tree[id].y) {

		tree[L(id)].y = max(tree[L(id)].y, tree[id].y);

		tree[R(id)].y = max(tree[R(id)].y, tree[id].y);

	}

}

void build(int l,int r,int id){

    tree[id].l = l, tree[id].r = r; tree[id].mid = (l+r)>>1;

    tree[id].y = 0;

    if(l+1==r)return ;

    build(l, tree[id].mid, L(id));

    build(tree[id].mid, r, R(id));

}

void updata(int l,int r,int val,int id){

	push_down(id);

    if(l == tree[id].l && tree[id].r == r) {

        tree[id].y = max(tree[id].y, val);

        return ;

    }

	if(tree[R(id)].l<=l)

        updata(l, r, val, R(id));

    else if(r<=tree[L(id)].r)

        updata(l, r, val, L(id));

    else {

        updata(l, tree[L(id)].r, val, L(id));

        updata(tree[R(id)].l, r, val, R(id));

    }

}

int query(int pos, int id){

	push_down(id);

    if(tree[id].l+1 == tree[id].r)

        return tree[id].y;

    if(tree[id].mid <= pos)

        return query(pos, R(id));

    else

        return query(pos, L(id));

}

int x1[N], x2[N], y[N], n;

map<int,int>mp;

vector<int>G;

list<pair<int,int> >lis;

list<pair<int,int> >::iterator it1;

int hehex[N], hehey[N], top;

int main() {

	int i;

	freopen("input.txt","r",stdin);

	freopen("output.txt","w",stdout);

	while(~scanf("%d",&n)){

        G.clear();

        mp.clear();

        for(i = 1; i <= n; i++){

            scanf("%d %d %d",&y[i], &x1[i], &x2[i]);

            G.push_back(x1[i]);

            G.push_back(x2[i]);

        }

        sort(G.begin(), G.end());

        G.erase(unique(G.begin(),G.end()), G.end());

        for(i = 0; i <G.size(); i++) mp[G[i]] = i+1;

        build(1, G.size(), 1);

        for(i = 1; i <= n; i++)

            updata(mp[x1[i]], mp[x2[i]], y[i], 1);

        lis.clear();

        for(i = 0; i < G.size(); i++) {

			int tmp = query(i+1,1);

            lis.push_back(pair<int,int>(G[i], tmp));

			if(i+1<G.size())

			lis.push_back(pair<int,int>(G[i+1], tmp));

        }

       	for(it1 = lis.begin(); it1!=lis.end(); ) {

			int u = it1->second;

			list<pair<int,int> >::iterator it2 = it1;

			it2++; if(it2==lis.end())break;

			list<pair<int,int> >::iterator it3 = it2;

			it3++; if(it3==lis.end())break;

			int v = it3->second;

			if(u==v) {

				lis.erase(it2);

				continue;

			}

			it1++;

		}

		top = 0;

		hehex[top] = G[0];

		hehey[top++] = 0;

		for(it1 = lis.begin(); it1 != lis.end(); it1++) {

			hehex[top] = it1->first;

			hehey[top++] = it1->second;

			list<pair<int,int> >::iterator it2 = it1;

			it2++;

			if(it2 == lis.end())continue;

			if(it1->first == it2->first)continue;

			int u = it1->second, v = it2->second;

			if(u>v)

				hehex[top] = it1->first, hehey[top++] = v;

			else if(u<v)

				hehex[top] = it2->first, hehey[top++] = u;

		}

		it1 = lis.end(); it1--;

		hehex[top] = it1->first, hehey[top++] = 0;

        printf("%d\n", top);

        for(i = 0; i < top; i++)

            printf("%d %d\n",hehex[i], hehey[i]);

    }

	return 0;

}