线段树,数组写法
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 10010;
struct segment{
int x, y1, y2; // 仅考虑所有竖向的线段,线段的x坐标,起始y坐标,终止y坐标
int k; // 线段是矩形的左边还是右边,1 / -1
bool operator < (const segment &t) const{ // 按x坐标从小到大将所有线段排序
return x < t.x;
}
}segs[N*2];
int sum[4*N]; // 覆盖度不小于1的区间长度,即线段树的维护值
int tag[4*N]; // 涉及区间修改,使用lazy标记,表示每个纵坐标区间当前的覆盖度
void push(int l, int r, int u){
if(tag[u]) sum[u] = r - l + 1;
else if(l == r) sum[u] = 0; // 根节点,且没有标记
else sum[u] = sum[2*u] + sum[2*u + 1];
}
void update(int L, int R, int l, int r, int u, int v){
if(L <= l && r <= R){
tag[u] += v;
push(l, r, u);
}
else{
int mid = l + r >> 1;
if(L <= mid) update(L, R, l, mid, 2*u, v);
if(R > mid) update(L, R, mid + 1, r, 2*u + 1, v);
push(l, r, u);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
segs[i].x = x1, segs[i].y1 = y1, segs[i].y2 = y2, segs[i].k = 1;
segs[n + i].x = x2, segs[n + i].y1 = y1, segs[n + i].y2 = y2, segs[n + i].k = -1;
}
sort(segs + 1, segs + 1 + 2*n);
int res = 0;
for(int i = 1; i <= 2*n; i++){
if(i > 1) res += (segs[i].x - segs[i - 1].x) * sum[1];
update(segs[i].y1, segs[i].y2 - 1, 0, 10000, 1, segs[i].k);
}
cout << res;
return 0;
}