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 ( 0 , 0 ), ( x , 0 ), ( 0 , 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 ) and (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).
The next nn lines,each contains two numbers x y ,( 0<x , y≤10000000 ),the ii-th line means the i-th second there comes a wave of ( xx , yy ), it's guaranteed that when 1≤i , j≤n ,xi≤xj and 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
题目来源
1 //分成横纵坐标来考虑 2 //如 :纵坐标,因为题目已明确会覆盖,但不会完全覆盖 3 //那么,(会影响我的)比我高的一定在我左边(不然完全覆盖),比我矮的 4 //一定在我右边,(不然就完全不覆盖了)。 5 #include<bits/stdc++.h> 6 using namespace std; 7 #define ll long long 8 #define N 50009 9 int n; 10 ll x[N],y[N]; 11 ll solve(ll a[]) 12 { 13 set<ll>se; 14 set<ll>::iterator it; 15 ll ans=0; 16 for(int i=n;i>=1;i--) 17 { 18 it=se.lower_bound(a[i]); 19 if(it==se.begin()) {//不存在,或者都比我大 20 ans+=a[i]; 21 } 22 else{ 23 it--;//不可能有2 2 1 3 24 ans+=a[i]-(*it); 25 } 26 se.insert(a[i]); 27 } 28 return ans; 29 } 30 int main() 31 { 32 while(~scanf("%d",&n)) 33 { 34 for(int i=1;i<=n;i++) 35 { 36 scanf("%lld%lld",&x[i],&y[i]); 37 } 38 printf("%lld ",solve(x)+solve(y)); 39 } 40 return 0; 41 }