线段树
#include<bits/stdc++.h>
using namespace std;
struct Seg{
const vector<int>&data;
vector<int> seg;
vector<int> sum;
Seg(const vector<int>& vec):data(vec),seg(vec.size()*4+10,0),sum(vec.size()*4+10){
}
void push_up(int rt,int left,int right){
if(seg[rt]){
sum[rt]=data[right]-data[left-1];
}else if(left==right){
sum[rt]=0;
}else{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
}
void update(int rt,int left,int right,int qleft,int qright,int val){
if(left>=qleft&&right<=qright){
seg[rt]+=val;
push_up(rt,left,right);
return;
}
int mid=left+(right-left)/2;
if(qleft<=mid)
update(rt<<1,left,mid,qleft,qright,val);
if(qright>mid)
update(rt<<1|1,mid+1,right,qleft,qright,val);
push_up(rt,left,right);
}
int acquire(){
return sum[1];
}
};
int rectangleArea(vector<vector<int>>& rectangles) {
vector<int> xvec;
for(int i=0;i<rectangles.size();i++){
xvec.push_back(rectangles[i][0]);
xvec.push_back(rectangles[i][2]);
}
sort(xvec.begin(),xvec.end());
unordered_map<int,int> m;
m[xvec[0]]=1;
vector<int> data{0,xvec[0]};
for(int i=1,id=2;i<xvec.size();i++){
if(xvec[i]!=xvec[i-1]){
data.push_back(xvec[i]);
m[xvec[i]]=id++;
}
}
vector<pair<int,int>> order;
for(int i=0;i<rectangles.size();i++){
//用正负表示下边界与上边界,第二个参数表示按y坐标排序后第i个框,从第1个开始
order.push_back({rectangles[i][1],(i+1)});
order.push_back({rectangles[i][3],-(i+1)});
}
sort(order.begin(),order.end());
Seg seg(data);
int res=0;
int len=data.size()-1;
int length=0,lasty=0;
for(int i=0;i<order.size();i++){
int cury=order[i].first;
res=(res+long(cury-lasty)*length);
if(order[i].second<0){
int id=-order[i].second-1;
//一个点管理一个区间,例如[i,i+1]该区间由点i+1管理
seg.update(1,1,len,m[rectangles[id][0]]+1,m[rectangles[id][2]],-1);
length=seg.acquire();
}else{
int id=order[i].second-1;
seg.update(1,1,len,m[rectangles[id][0]]+1,m[rectangles[id][2]],1);
length=seg.acquire();
}
lasty=cury;
}
return res;
}
int main(){
int n,a,b,c,d;
cin >> n;
vector<vector<int>>rectangles(n,vector<int>(4));
for(int i = 0;i < n;i ++){
cin >> a >> b >> c >> d;
rectangles[i][0] = a;
rectangles[i][1] = b;
rectangles[i][2] = c;
rectangles[i][3] = d;
}
cout << rectangleArea(rectangles);
return 0;
}