# 矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结）

## Atlantis

``````#include <bits/stdc++.h>
using namespace std;
typedef double ll;
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct AreaUnion
{
struct Seg
{
ll l, r, h;
int f;
bool operator<(const Seg &rhs) const { return h < rhs.h; }
};
struct Node
{
int cnt;
ll sum;
};
vector<Seg> s;
vector<Node> v;
Ranker rk;
void add(ll l, ll b, ll r, ll t)
{
rk.push_back(l);
rk.push_back(r);
s.push_back({l, r, b, 1});
s.push_back({l, r, t, -1});
}
void upd(int ql, int qr, int c, int l, int r, int rt = 1)
{
if (ql <= l && r <= qr)
v[rt].cnt += c;
else
{
int m = l + r >> 1;
if (ql <= m)
upd(ql, qr, c, l, m, rt << 1);
if (qr > m)
upd(ql, qr, c, m + 1, r, rt << 1 | 1);
}
v[rt].sum = v[rt].cnt ? rk[r + 1] - rk[l] : l < r ? v[rt << 1].sum + v[rt << 1 | 1].sum : 0;
}
{
rk.init();
sort(s.begin(), s.end());
v.assign(rk.size() * 4, Node());
ll ans = 0;
for (int i = 0; i + 1 < s.size(); ++i)
{
upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
ans += v[1].sum * (s[i + 1].h - s[i].h);
}
return ans;
}
};
int main()
{
for (int kase = 0, n; ~scanf("%d", &n) && n;)
{
AreaUnion a;
for (int i = 0; i < n; ++i)
{
ll l, b, r, t;
scanf("%lf%lf%lf%lf", &l, &b, &r, &t);
a.add(l, b, r, t);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++kase, a.ask());
}
}
``````

## 覆盖的面积

``````#include <bits/stdc++.h>
using namespace std;
typedef double ll;
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct AreaIntersection
{
struct Seg
{
ll l, r, h;
int f;
bool operator<(const Seg &rhs) const { return h < rhs.h; }
};
struct Node
{
int cnt;
ll one, two;
};
vector<Seg> s;
vector<Node> v;
Ranker rk;
void add(ll l, ll b, ll r, ll t)
{
rk.push_back(l);
rk.push_back(r);
s.push_back({l, r, b, 1});
s.push_back({l, r, t, -1});
}
void upd(int ql, int qr, int c, int l, int r, int rt = 1)
{
if (ql <= l && r <= qr)
v[rt].cnt += c;
else
{
int m = l + r >> 1;
if (ql <= m)
upd(ql, qr, c, l, m, rt << 1);
if (qr > m)
upd(ql, qr, c, m + 1, r, rt << 1 | 1);
}
if (v[rt].cnt == 0)
{
v[rt].one = l != r ? v[rt << 1].one + v[rt << 1 | 1].one : 0;
v[rt].two = l != r ? v[rt << 1].two + v[rt << 1 | 1].two : 0;
}
else
{
v[rt].one = rk[r + 1] - rk[l];
if (v[rt].cnt > 1)
v[rt].two = rk[r + 1] - rk[l];
else
v[rt].two = l != r ? v[rt << 1].one + v[rt << 1 | 1].one : 0;
}
}
{
rk.init();
sort(s.begin(), s.end());
v.assign(rk.size() * 4, Node());
ll ans = 0;
for (int i = 0; i + 1 < s.size(); ++i)
{
upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
ans += v[1].two * (s[i + 1].h - s[i].h);
}
return ans;
}
};
int main()
{
int t, n;
for (scanf("%d", &t); t--;)
{
AreaIntersection a;
scanf("%d", &n);
for (ll l, b, r, t; n--;)
{
scanf("%lf%lf%lf%lf", &l, &b, &r, &t);
a.add(l, b, r, t);
}
}
}
``````

## Picture

### 解法一

``````#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct HalfPerimeter
{
struct Seg
{
ll l, r, h;
int f;
bool operator<(const Seg &rhs) const { return h != rhs.h ? h < rhs.h : f > rhs.f; }
};
struct Node
{
int cnt;
ll sum;
};
vector<Seg> s;
vector<Node> v;
Ranker rk;
ll add(ll l, ll b, ll r, ll t)
{
rk.push_back(l);
rk.push_back(r);
s.push_back({l, r, b, 1});
s.push_back({l, r, t, -1});
}
void upd(int L, int R, int c, int l, int r, int rt = 1)
{
if (L <= l && r <= R)
v[rt].cnt += c;
else
{
int m = l + r >> 1;
if (L <= m)
upd(L, R, c, l, m, rt << 1);
if (R > m)
upd(L, R, c, m + 1, r, rt << 1 | 1);
}
v[rt].sum = v[rt].cnt ? rk[r + 1] - rk[l] : l != r ? v[rt << 1].sum + v[rt << 1 | 1].sum : 0;
}
{
rk.init();
sort(s.begin(), s.end());
v.assign(rk.size() << 2, Node());
ll ans = 0;
for (int i = 0; i < s.size(); ++i)
{
ll last = v[1].sum;
upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
ans += abs(v[1].sum - last);
}
return ans;
}
};
int main()
{
for (int n; ~scanf("%d", &n);)
{
HalfPerimeter x, y;
for (int i = 0, l, b, r, t; i < n; ++i)
{
scanf("%d%d%d%d", &l, &b, &r, &t);
x.add(l, b, r, t);
y.add(b, l, t, r);
}
}
}
``````

### 解法二

``````#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct Ranker : vector<ll>
{
void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct Perimeter
{
struct Seg
{
ll l, r, h;
int f;
bool operator<(const Seg &rhs) const { return h < rhs.h; }
};
struct Node
{
int cnt;
ll sum, vtl, lbd, rbd;
};
vector<Seg> s;
vector<Node> v;
Ranker rk;
void add(ll l, ll b, ll r, ll t)
{
rk.push_back(l);
rk.push_back(r);
s.push_back({l, r, b, 1});
s.push_back({l, r, t, -1});
}
void upd(int ql, int qr, int c, int l, int r, int rt = 1)
{
if (ql <= l && r <= qr)
v[rt].cnt += c;
else
{
int m = l + r >> 1;
if (ql <= m)
upd(ql, qr, c, l, m, rt << 1);
if (qr > m)
upd(ql, qr, c, m + 1, r, rt << 1 | 1);
}
if (v[rt].cnt)
{
v[rt].lbd = v[rt].rbd = 1;
v[rt].sum = rk[r + 1] - rk[l];
v[rt].vtl = 2;
}
else if (l == r)
v[rt].sum = v[rt].vtl = v[rt].lbd = v[rt].rbd = 0;
else
{
v[rt].lbd = v[rt << 1].lbd;
v[rt].rbd = v[rt << 1 | 1].rbd;
v[rt].sum = v[rt << 1].sum + v[rt << 1 | 1].sum;
v[rt].vtl = v[rt << 1].vtl + v[rt << 1 | 1].vtl;
if (v[rt << 1].rbd && v[rt << 1 | 1].lbd)
v[rt].vtl -= 2;
}
}
{
rk.init();
sort(s.begin(), s.end());
v.assign(rk.size() << 2, Node());
ll ans = 0;
for (int i = 0; i + 1 < s.size(); ++i)
{
ll pre = v[1].sum;
upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
ans += v[1].vtl * (s[i + 1].h - s[i].h) + abs(v[1].sum - pre);
}
return ans + abs(v[1].sum);
}
};
int main()
{
for (int n; ~scanf("%d", &n);)
{
Perimeter p;
for (int i = 0, l, b, r, t; i < n; ++i)
{
scanf("%d%d%d%d", &l, &b, &r, &t);
p.add(l, b, r, t);
}