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

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 \le 50000)n(n≤50000).

The next nn lines，each contains two numbers xx yy ,( 0 < x0<x , y \le 10000000y≤10000000 )，the ii-th line means the ii-th second there comes a wave of ( xx , yy ), it's guaranteed that when 1 \le i1≤i , j \le nj≤n ，x_i \le x_jxi ≤xj  and y_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=10

样例输入复制

3
1 4
4 1
3 3

样例输出复制

10

---

题解：因为题意告知当xi<xj时yi>yj，所以我们可以分开x和y从后往前判断只要小于当前值得当前值就一定被覆盖所以当前值得贡献就是减去离他最近的那个小于值

---

#include<cstring>
#include<cstdio>
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<functional>
using namespace std;
#define clr(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&-x
#define rep(a,b,c) for(ll a=b;a<c;a++)
#define dec(a,b,c) for(int a=b;a>c;a--)
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define ps(x) push(x)
#define _INIT ios::sync_with_stdio(false);cin.tie(nullptr);cout.precision(10);cout<<fixed
#define MAX_N 100000+5
#define MAX_M 100
typedef long long ll;
typedef unsigned long long ull;
typedef priority_queue<ll,vector<ll>,greater<ll> >pqg;
const ll maxn=1e3;
const ll inf=1e7;
using namespace std;
vector<int> vx,vy;
long long gao(vector<int> vec) {
	int sz = vec.size();
	set<int>st;
	long long ans = 0;
	for (int i = sz-1; i >= 0; i--) {
		set<int>::iterator it = st.lower_bound(vec[i]);
		if (it == st.begin()) {
			ans += vec[i];
		} else {
			it--;
			ans += vec[i] - *it;
		}
		st.insert(vec[i]);
	}
	return ans;
}
int main() {
	int n;
	while(scanf("%d", &n) == 1) {
		vector<int>vec1, vec2;
		int x,y;
		while(n--) {
			scanf("%d%d", &x, &y);
			vx.eb(x);
			vy.eb(y);
		}
		cout<<gao(vx) + gao(vy)<<endl;
	}
}