/******************************
@GavinCQTD / 2024-12-19 16:34:24
"P1856 [IOI1998] [USACO5.5] 矩形周长Picture" From Luogu
# https://www.luogu.com.cn/problem/P1856
1000 ms / 125 MB
******************************/
/* We all make choices, but in the end our choices make us. */
// #pragma GCC optimize(1,2,3,"Ofast","inline")
// #define NDEBUG
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <unordered_map>
using namespace std;
inline void pass(){return;}
inline void hold(){while(1);}
#define endl "\n"
#define mp(a,b) make_pair(a,b)
#define ct(a) while(!a.empty()) a.pop()
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define cdb cerr<<"Debug: "
#define cwn cerr<<"Warn: "
#define debug(x) cerr<<"In Line "<<__LINE__<<": "<<#x<<" = "<<x<<"\n"
#define sp(a) fixed<<setprecision(a)
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
#define ll long long
#define ull unsigned long long
#define ld long double
// #define int ll
// #define _debug
int _t,n,_xb=0,_yb=0,tree[300005],lzy[300005],ans=0;
struct jx{
int x1,y1,x2,y2;
}js[100005];
struct bx{
int x,y1,y2,tp;
}xb[300005];
struct by{
int y,x1,x2,tp;
}yb[300005];
bool cmpx(bx x,bx y){
if(x.x==y.x) return x.tp<y.tp;
return x.x<y.x;
}
bool cmpy(by x,by y){
if(x.y==y.y) return x.tp<y.tp;
return x.y<y.y;
}
inline void pushup(int u){tree[u]=tree[u*2]+tree[u*2+1];}
inline bool inrange(int l,int r,int ql,int qr){return (ql<=l)&&(r<=qr);}
inline bool outofrange(int l,int r,int ql,int qr){return (l>qr)||(r<ql);}
inline void maketag(int u,int ul,int ur,int uk){
lzy[u] += uk;
tree[u] += (ur-ul+1)*uk;
}
inline void pushdown(int u,int ul,int ur){
int mid=(ul+ur)>>1;
maketag(u*2,ul,mid,lzy[u]);
maketag(u*2+1,mid+1,ur,lzy[u]);
lzy[u] = 0;
}
int query(int u,int l,int r,int ql,int qr){
if(inrange(l,r,ql,qr)) return tree[u];
else if(!outofrange(l,r,ql,qr)){
int mid=(l+r)>>1;
pushdown(u,l,r);
return query(u*2,l,mid,ql,qr)+query(u*2+1,mid+1,r,ql,qr);
}
else return 0;
}
void update(int u,int l,int r,int ul,int ur,int uk){
if(inrange(l,r,ul,ur)) maketag(u,l,r,uk);
else if(!outofrange(l,r,ul,ur)){
int mid=(l+r)>>1;
pushdown(u,l,r);
update(u*2,l,mid,ul,ur,uk);
update(u*2+1,mid+1,r,ul,ur,uk);
pushup(u);
}
}
void solve(int testID){
cin >> n;
for(int i=1;i<=n;i++){
cin >> js[i].x1 >> js[i].y1 >> js[i].x2 >> js[i].y2;
xb[++_xb] = {js[i].x1,js[i].y1,js[i].y2-1,0};
xb[++_xb] = {js[i].x2,js[i].y1,js[i].y2-1,0};
xb[++_xb] = {js[i].x2,js[i].y1,js[i].y2-1,1};
yb[++_yb] = {js[i].y1,js[i].x1,js[i].x2-1,0};
yb[++_yb] = {js[i].y2,js[i].x1,js[i].x2-1,0};
yb[++_yb] = {js[i].y2,js[i].x1,js[i].x2-1,1};
}
sort(xb+1,xb+_xb+1,cmpx);
int lst=0;
for(int i=1;i<=_xb;i++){
if(xb[i].tp){
update(1,-1e4,1e4,xb[i].y1,xb[i].y2,-2);
lst = query(1,-1e4,1e4,-1e4,1e4);
continue;
}
update(1,-1e4,1e4,xb[i].y1,xb[i].y2,1);
int qres=query(1,-1e4,1e4,-1e4,1e4);
ans += qres-lst;
// cerr << ">>> " << i << " " << lst << " " << qres << " " << ans << "\n";
lst = qres;
}
// debug(ans);
memset(tree,0,sizeof(tree));
memset(lzy,0,sizeof(lzy));
sort(yb+1,yb+_yb+1,cmpy);
lst = 0;
for(int i=1;i<=_yb;i++){
if(yb[i].tp){
update(1,-1e4,1e4,yb[i].x1,yb[i].x2,-2);
lst = query(1,-1e4,1e4,-1e4,1e4);
continue;
}
update(1,-1e4,1e4,yb[i].x1,yb[i].x2,1);
int qres=query(1,-1e4,1e4,-1e4,1e4);
ans += qres-lst;
// cerr << ">>> " << i << " " << lst << " " << qres << " " << ans << "\n";
lst = qres;
}
cout << ans;
// debug(ans);
// cerr << "--------------------------------\n";
// for(int i=1;i<=_xb;i++) cerr<<xb[i].x<<" "<<xb[i].y1<<" "<<xb[i].y2<<" "<<xb[i].tp<<"\n";
// cerr << "--------------------------------\n";
// for(int i=1;i<=_yb;i++) cerr<<yb[i].y<<" "<<yb[i].x1<<" "<<yb[i].x2<<" "<<xb[i].tp<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
// freopen("PublicDebug.debug", "w", stderr);
// cout << sp();
// cerr << sp();
_t = 1;
// cin >> _t;
for(int ran=0;ran<_t;ran++) solve(ran);
fflush(stdout);
return 0;
}
样例输出了 356