2018ICPC徐州赛区网络预赛G：Trace

题目来源
ACM-ICPC 2018 徐州赛区网络预赛G题(计蒜客)
There’s a beach in the first quadrant. And from time to time, there are sea waves. A wave (x,y)$(x,y)$ means the wave is a rectangle whose vertexes are (0,0)$(0,0)$,(x,0)$(x,0)$, (0,y)$(0,y)$,(x,y)$(x,y)$. Every time the wave will wash out the trace of former wave in its range and remain its own trace of (x,0)−>(x,y)$(x,0)->(x,y)$ and (0,y)−>(x,y)$(0,y)->(x,y)$. Now the toad on the coast wants to know the total length of trace on the coast after n waves. It’s guaranteed that a wave will not cover the other completely.

Input
The first line is the number of waves n(n≤50000)$n(n\le 50000)$.

The next n$n$ lines，each contains two numbers x$x$ y$y$ ,(0<x,y≤10000000)$(0<x,y\le 10000000)$，the i$i$-th line means the i$i$-th second there comes a wave of (x,y)$(x,y)$, it’s guaranteed that when 1≤i,j≤n，xi≤xj$1\le i,j\le n，x_i\le x_j$ and yi≤yj$y_i\le y_j$ don’t set up at the same time.

Output
An Integer stands for the answer.

Hint：
As for the sample input, the answer is 3+3+1+1+1+1=10.

样例输入

3
1 4
4 1
3 3

样例输出

10

题意:

海浪不断冲刷海滩，在海滩上留下矩形冲刷痕迹，并且后面的痕迹会覆盖住前面的痕迹，求最后留下的痕迹的边线总长度

解题思路：

开了两个数组，一个mapa保存输入的y的值，并从小到大排序，另一个mapb则保存当前y点到达的最大的x值，也就相当于被从y=0到对应mapa中的值的长度上已经被覆盖的x的长度，由题意得出，越靠近海的最远边线越长，即越靠近海，x或者y越大，又因为后面的痕迹一定不会被前面的痕迹所覆盖，所以从后往前计算痕迹，并不断更新mapb的值。

#include<iostream>
#include<cstdio>
#include<cstring> 
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<ctime>
#define INF 0x3f3f3f3f
#define maxn  1005
using namespace std;
typedef long long LL;

int mapa[50005];
int mapb[50005];

typedef struct part{
    int x,y;
}part;

part m[50005];

int research(int left,int right,int element)//用二分法找到对应y值在mapa中的位置
{
    while(left<=right)
    {   
        int mid = (left+right)/2;
        if(mapa[mid]>element)
        {
            right = mid - 1;
        }
        else if(mapa[mid]<element)
        {
            left = mid + 1;
        }
        else 
        {
            return mid;
        }
    }
    return -1;
}


int main(){
    int n;
    memset(mapb, 0, sizeof(mapb));
    scanf("%d",&n);
    LL sum = 0;
    for(int i=0; i<n; i++){
        scanf("%d%d",&m[i].x,&m[i].y);
        mapa[i] = m[i].y;
    }
    sort(mapa,mapa+n); 
    for(int i=n-1; i>=0; i--){
        int k = research(0,n-1,m[i].y);
        int dis = m[i].x-mapb[k], p, j;
        if(dis>0) sum+=dis;//求出未被覆盖的x海岸的边线长度
        for(j=k; j>=0&&m[i].x>mapb[j]; j--){//找到最靠近海并且未被覆盖到的点
            mapb[j] = m[i].x;//更新被覆盖住的x的长度
        }
        if(j == -1) sum += m[i].y;//当此y边边线大于靠海所有的边线长度的时候，即形成一个新的覆盖面积（平行于y轴并且到0的边线）
        else sum += (m[i].y-mapa[j]);//从i点到j点形成的新的边线（平行于y轴）
    }
    printf("%lld\n", sum);
}