【差分】It Rains Again

我果然是个初学者级别的five
但是今天level++啦（滑稽）

Description

Suppose that in a Cartesian coordinate system on an infinite plane, the x-axis represents the ground and there are n rainscreens (We don't consider their thickness.) in the sky.

Every rainscreen can be described as a segment which starts from theand (x1,y1)ends at (x2.y2). Now if it starts to rain from the infinite high sky, I want you to tell me how many units of the x-axis will not get rained on.

To simplify the problem,the rain can only move vertically whenever it falls.

Note that two rainscreens can overlap and intersect with each other, and there is no rainscreen which is placed vertically.

这个其实是差分
差分数组的前缀和是a[i]
它的性质很有意思，单点修改，影响整个区间的值，而且可以对别的区间无影响
我们在div[x1]++,div[x2]--
改变一个区间的值
在遍历差分数组的时候就可以摸到这个区间
如果有一个地方大于零（没有被雨淋上）那就ans++
（别的地方不用管，因为div[x2]--存在）

Input

The first line contains one positive integer n (1 \leq n \leq 100000)n(1≤n≤100000).

Each of the next n lines contains four positive integers x_1, y_1, x_2, y_2 (1 < x_1 < x_2 < 100000, 1 < y_1,y_2 < 100000), representing a rainscreen which starts from the (x_1, y_1)and ends at (x_2, y_2).

Output

The only one integer - the number of units of the x-axis which will not get rained on.

Example

Input
5
1 2 2 1
1 1 2 2
3 3 4 3
5 1 6 3
6 3 7 2
Output
4

Note

Consider the example, we can draw a picture like below:

It's easy to calculate the answer is 4.

#include
#include
#include
using namespace std;
int main(){
    int n,div[100050];
    cin>>n;
    memset(div,0,sizeof(div));
    for(int i=1;i<=n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        div[a]++;
        div[c]--;
    }
    int cnt=0,ans=0;
    for(int i=0;i<=100000;i++){
        cnt+=div[i];
        if(cnt>0) ans++;
    }
    cout<