RT
#include<bits/stdc++.h>
#define mod 998244353
#define int long long
using namespace std;
array<int , 200001> num;
int T = 0 , ans = 0;
struct Scanner{
int maxy;
int miny;
int x;
int flag;
};
array<Scanner , 200001> scanner;
struct Tree{
int l;
int r;
int sum;
int cnt;
};
array<Tree , 8000000> tree;
void pushup(int k)
{
// if(k == 1)
// {
// cout << tree.at(k << 1).sum << ' ' << tree.at(k << 1 | 1).sum << endl;
// cout << tree.at(k << 1).l << ' ' << tree.at(k << 1).r << ' ' << tree.at(k << 1).sum << endl;
// cout << tree.at(k << 1 | 1).l << ' ' << tree.at(k << 1 | 1).r << ' ' << tree.at(k << 1 | 1).sum << endl;
// }
if(tree.at(k).cnt)
{
tree.at(k).sum = num.at(tree.at(k).r) - num.at(tree.at(k).l);
return;
}
tree.at(k).sum = tree.at(k << 1).sum + tree.at(k << 1 | 1).sum;
return;
}
void build(int l , int r , int k)
{
tree.at(k).l = l;
tree.at(k).r = r;
tree.at(k).sum = tree.at(k).cnt = 0;
if(l + 1 == r)
{
return;
}
int mid = l + (r - l) / 2;
build(l , mid , k << 1);
build(mid , r , k << 1 | 1);
pushup(k);
return;
}
void update(int l , int r , int k , int v)
{
if(l <= tree.at(k).l && tree.at(k).r <= r)
{
tree.at(k).cnt += v;
// cout << k << ' ' << tree.at(k).l << ' ' << tree.at(k).r << ' ' << tree.at(k).sum << endl;
pushup(k);
return;
}
update(l , r , k << 1 , v);
update(l , r , k << 1 | 1 , v);
pushup(k);
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
for(int i = 1;i <= T;++ i)
{
int a1 = 0,b1 = 0,a2 = 0,b2 = 0;
cin >> a1 >> b1 >> a2 >> b2;
scanner.at(i).maxy = scanner.at(i + T).maxy = b2;
scanner.at(i).miny = scanner.at(i + T).miny = b1;
scanner.at(i).flag = 1 , scanner.at(i + T).flag = -1;
scanner.at(i).x = a1 , scanner.at(i + T).x = a2;
num.at(i) = b1 , num.at(i + T) = b2;
}
sort(num.data() + 1 , num.data() + T * 2 + 1 , [&](int x , int y){return x < y;});
sort(scanner.data() + 1 , scanner.data() + T * 2 + 1 , [&](Scanner a , Scanner b){return a.x < b.x;});
int tot = unique(num.data() + 1 , num .data() + T * 2 + 1) - num.data() - 1;
// for(int i = 1;i <= tot;++ i)
// {
// cout << num.at(i) << ' ';
// }
// cout << endl;
// for(int i = 1;i <= T * 2;++ i)
// {
// cout << scanner.at(i).miny << ' ' << scanner.at(i).maxy << ' ' << scanner.at(i).x << ' ' << scanner.at(i).flag << endl;
// }
for(int i = 1;i <= T * 2;++ i)
{
scanner.at(i).maxy = lower_bound(num.data() + 1 , num.data() + T * 2 + 1 , scanner.at(i).maxy) - num.data();
scanner.at(i).miny = lower_bound(num.data() + 1 , num.data() + T * 2 + 1 , scanner.at(i).miny) - num.data();
}
// for(int i = 1;i <= T * 2;++ i)
// {
// cout << scanner.at(i).miny << ' ' << scanner.at(i).maxy << ' ' << scanner.at(i).x << ' ' << scanner.at(i).flag << endl;
// }
build(1 , tot , 1);
for(int i = 1;i < T * 2;++ i)
{
update(scanner.at(i).miny , scanner.at(i).maxy , 1 , scanner.at(i).flag);
// cout << (scanner.at(i + 1).x - scanner.at(i).x) << ' ' << tree.at(1).sum << endl;
ans = (ans + tree.at(1).sum * (scanner.at(i + 1).x - scanner.at(i).x));
}
cout << ans << endl;
return 0;
}