ACM-ICPC 2018 徐州赛区网络预赛 G. Trace —— 想法+upper_bound

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

The next nn lines，each contains two numbers xx yy
(0<x0<x,10000000y≤10000000)，$(0<x0<x,10000000y\le 10000000)，$the ii-th line means the ii-th second there comes a wave of ( xx , yy ), it’s guaranteed that when 1≤i ,j≤n ，jx i​ ≤x j​ and y i​ ≤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=103+3+1+1+1+1=10

样例输入 复制
3
1 4
4 1
3 3
样例输出 复制
10

可以反着来想，反正他是不会覆盖的，所以放进去的时候一定会有一个x比他小，y比他小的值（至少是0），那么ans加上那些值就好了。

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
set<int> sex,sey;
set<int>::iterator itx,ity;
int x[80005],y[80005];
int main(){
    int n;
    ll ans=0;
    scanf("%d",&n);
    sex.insert(0),sey.insert(0);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y[i]);
    }
    for(int i=n;i>=1;i--){
        itx=sex.upper_bound(x[i]); itx--;
        ity=sey.upper_bound(y[i]); ity--;
        //cout<<*itx<<" "<<*ity<<" "<<endl;
        //cout<<(x[i]-(*itx))<<" "<< (y[i]-(*ity))<<endl;
        ans+=(x[i]-(*itx))+(y[i]-(*ity));
        sex.insert(x[i]);sey.insert(y[i]);
    }
    printf("%lld\n",ans);
    return 0;
}