2018 ACM-ICPC徐州站网络赛 G题

There's a beach in the first quadrant. And from time to time, there are sea waves. A wave ( xxx , yyy ) means the wave is a rectangle whose vertexes are ( 000 , 000 ), ( xxx , 000 ), ( 000 , yyy ), ( xxx , yyy ). Every time the wave will wash out the trace of former wave in its range and remain its own trace of ( xxx , 000 ) -> ( xxx , yyy ) and ( 000 , yyy ) -> ( xxx , yyy ). 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)n(n≤50000).

The next nnn lines，each contains two numbers xxx yyy ,( 0<x0 < x0<x , y≤10000000y \le 10000000y≤10000000 )，the iii-th line means the iii-th second there comes a wave of ( xxx , yyy ), it's guaranteed that when 1≤i1 \le i1≤i , j≤nj \le nj≤n ，xi≤xjx_i \le x_jxi≤xj and yi≤yjy_i \le y_jyi≤yj 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=103+3+1+1+1+1=103+3+1+1+1+1=10

样例输入

样例输出

题目来源

ACM-ICPC 2018 徐州赛区网络预赛

题意：

有n个矩形按顺序出现在坐标轴上，后出现的矩形会覆盖之前出现的矩形，问最后没被覆盖的边的长度（不含在坐标轴上的边）。

分析::

首先看到这题最先想到的就应该是按矩形加入的顺序从后往前开始计算边长。又因为题目有要求：不存在一个矩形被另一个矩形完全包含，所以说每一个矩形都有突出来的部分可以被计算在答案内。我们从后往前枚举矩形，被枚举过的矩形的边长加入到set中，新加入的矩形的计算方法就是根据当前矩形的边长在set中找到小于当前边长的最长边长（二分），然后更新答案：ans+=(当前边 - set中找到的小于当前边的最大边)。

有一个注意点是二分的时候用的upper_bound()需要使用set内置的，而不是直接调用STL，直接调用STL的话时间大概是(1100ms左右 TLE)，使用set内封装的upper_bound的话只要（90ms）。。。。（震惊）

AC code:

#include<bits/stdc++.h>

using namespace std;

set<int> x;

set<int> y;

set<int>::iterator tx,ty;

int X[],Y[];

int main()

{

    int n;

    scanf("%d",&n);

    x.insert();

    y.insert();

    for(register int i=;i<n;++i)

    {

        scanf("%d%d",&X[i],&Y[i]);

    }

    long long ans=;

    for(int i=n-;i>=;--i)

    {

        tx=x.upper_bound(X[i]);//使用set内封装的二分

        tx--;

        ty=y.upper_bound(Y[i]);//使用set内封装的二分

                //*ty=(upper_bound(y.begin(),y.end(),Y[i]))超时！！！！

        ty--;

        ans+=(X[i]-*tx);

        ans+=(Y[i]-*ty);

        x.insert(X[i]);

        y.insert(Y[i]);

    }

    printf("%lld\n",ans);

    return ;

}

巴特西