# 数据结构 1.0(Data structure 1.0)-其他

## 数据结构 1.0(Data structure 1.0)

### 扫描线

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N  200009
#define ll long long
#define pb push_back
#define ls now << 1
#define rs now << 1 | 1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
struct Line {
int x1, x2, y, d;
Line(int x1 = 0, int x2 = 0, int y = 0, int d = 0):x1(x1), x2(x2), y(y), d(d) {}
}a[N];
int n , cnt , len[N << 2], A[N << 2], tot ;
struct data {
int sum, tag, l, r;
data() { sum = tag = l = r = 0; }
}s[N << 2];
void build(int l, int r, int now) {
s[now].l = l, s[now].r = r;
if(l == r) return ;
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs);
}
void pushup(int now) {
if(s[now].tag)
len[now] = A[s[now].r + 1] - A[s[now].l];
else {
if(s[now].l != s[now].r)
len[now] = len[ls] + len[rs];
else len[now] = 0;
}
}
void update(int l, int r, int now, int L, int R, int v) {
if(l >= L && r <= R) {
s[now].tag += v;
pushup(now);
return ;
}
int mid = (l + r) >> 1;
if(L <= mid)  update(l, mid, ls, L, R, v);
if(R > mid)   update(mid + 1, r, rs, L, R, v);
pushup(now);
}
bool cmp(Line i, Line j) { return i.y < j.y; }
int main() {
// setIO("input");
scanf("%d", &n);
for(int i = 1; i <= n ; ++ i) {
int x[2], y[2];
scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);
a[++ cnt] = Line(x[0], x[1], y[0], 1);
a[++ cnt] = Line(x[0], x[1], y[1], -1);
// 离散化横坐标即可.
A[++ tot] = x[0], A[++ tot] = x[1];
}
sort(A + 1, A + 1 + tot);
tot = unique(A + 1, A + 1 + tot) - A - 1;
for(int i = 1; i <= cnt ; ++ i) {
a[i].x1 = lower_bound(A + 1, A + 1 + tot, a[i].x1) - A;
a[i].x2 = lower_bound(A + 1, A + 1 + tot, a[i].x2) - A;
}
sort(a + 1, a + 1 + cnt, cmp);
// int pre = a[1].y;
build(1, tot , 1);
ll ans = 0;
for(int i = 1; i <= cnt ; ++ i) {
update(1, tot, 1, a[i].x1, a[i].x2 - 1, a[i].d);
ans += 1ll * len[1] * (a[i + 1].y - a[i].y);
}
printf("%lld", ans);
return 0;
}

————————

### Scan line

Rectangular area and:

Multiply the length intercepted by the horizontal line by the longitudinal difference

In particular, the bottom layer of the line segment tree represents a point, but the line segment needs to be maintained in the length

So let the $\ mathrm {[l, R]}$interval in the segment tree actually maintain the segment $\ mathrm {[l, R + 1)}$

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N  200009
#define ll long long
#define pb push_back
#define ls now << 1
#define rs now << 1 | 1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
struct Line {
int x1, x2, y, d;
Line(int x1 = 0, int x2 = 0, int y = 0, int d = 0):x1(x1), x2(x2), y(y), d(d) {}
}a[N];
int n , cnt , len[N << 2], A[N << 2], tot ;
struct data {
int sum, tag, l, r;
data() { sum = tag = l = r = 0; }
}s[N << 2];
void build(int l, int r, int now) {
s[now].l = l, s[now].r = r;
if(l == r) return ;
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs);
}
void pushup(int now) {
if(s[now].tag)
len[now] = A[s[now].r + 1] - A[s[now].l];
else {
if(s[now].l != s[now].r)
len[now] = len[ls] + len[rs];
else len[now] = 0;
}
}
void update(int l, int r, int now, int L, int R, int v) {
if(l >= L && r <= R) {
s[now].tag += v;
pushup(now);
return ;
}
int mid = (l + r) >> 1;
if(L <= mid)  update(l, mid, ls, L, R, v);
if(R > mid)   update(mid + 1, r, rs, L, R, v);
pushup(now);
}
bool cmp(Line i, Line j) { return i.y < j.y; }
int main() {
// setIO("input");
scanf("%d", &n);
for(int i = 1; i <= n ; ++ i) {
int x[2], y[2];
scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);
a[++ cnt] = Line(x[0], x[1], y[0], 1);
a[++ cnt] = Line(x[0], x[1], y[1], -1);
// 离散化横坐标即可.
A[++ tot] = x[0], A[++ tot] = x[1];
}
sort(A + 1, A + 1 + tot);
tot = unique(A + 1, A + 1 + tot) - A - 1;
for(int i = 1; i <= cnt ; ++ i) {
a[i].x1 = lower_bound(A + 1, A + 1 + tot, a[i].x1) - A;
a[i].x2 = lower_bound(A + 1, A + 1 + tot, a[i].x2) - A;
}
sort(a + 1, a + 1 + cnt, cmp);
// int pre = a[1].y;
build(1, tot , 1);
ll ans = 0;
for(int i = 1; i <= cnt ; ++ i) {
update(1, tot, 1, a[i].x1, a[i].x2 - 1, a[i].d);
ans += 1ll * len[1] * (a[i + 1].y - a[i].y);
}
printf("%lld", ans);
return 0;
}