這題就是給出了好多個長方體， 求出那些被覆寫了 3次及以上的體積
我們注意到z的範圍很小，而且就給了1000個長方體
那麼可以把z坐标離散化
然後在相鄰的z坐标空間内，就變成了求面積覆寫
記錄三個變量，代表一次覆寫，兩次覆寫，三次覆寫及以上
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define lch(x) x<<1
#define rch(x) x<<1|1
const int maxn = 2222;
int cnt[maxn << 2];//邊重複的次數
int sum[maxn << 2];//1次及以上
int sum2[maxn << 2];//2次及以上
int sum3[maxn << 2];
int X[maxn],Z[maxn];
struct Seg {
int h, l, r;
int s;//1為入邊，-1為出邊
Seg() {}
Seg(int a, int b, int c, int d) : l(a), r(b), h(c), s(d) {}
bool operator < (const Seg &cmp) const {
return h < cmp.h;
}
}ss[maxn];
struct Spot
{
int lx, rx, ly, ry, lz, rz;
}p[maxn];
void PushUp(int rt, int l, int r) {
if (cnt[rt] >= 3) sum[rt] = sum2[rt] = 0, sum3[rt] = X[r + 1] - X[l];
else if (cnt[rt] == 2)
{
if (l == r) sum2[rt] = X[r + 1] - X[l], sum3[rt] = 0, sum[rt] = 0;
else
{
sum3[rt] = sum[lch(rt)] + sum[rch(rt)] + sum2[lch(rt)] + sum2[rch(rt)] + sum3[lch(rt)] + sum3[rch(rt)];
sum2[rt] = X[r + 1] - X[l] - sum3[rt];
sum[rt] = 0;
}
}
else if (cnt[rt] == 1)
{
if (l == r) sum[rt] = X[r + 1] - X[l], sum2[rt] = 0, sum3[rt] = 0;
else
{
sum3[rt] = sum2[lch(rt)] + sum2[rch(rt)] + sum3[lch(rt)] + sum3[rch(rt)];
sum2[rt] = sum[lch(rt)] + sum[rch(rt)];
sum[rt] = X[r + 1] - X[l] - sum2[rt] - sum3[rt];
}
}
else
{
if (l == r) sum[rt] = sum2[rt] = sum3[rt] = 0;
else
{
sum3[rt] = sum3[lch(rt)] + sum3[rch(rt)];
sum2[rt] = sum2[lch(rt)] + sum2[rch(rt)];
sum[rt] = sum[lch(rt)] + sum[rch(rt)];
}
}
}
void update(int L, int R, int c, int l, int r, int rt) {
if (L <= l && r <= R) {
cnt[rt] += c;
PushUp(rt, l, r);
return;
}
int m = (l + r) >> 1;
if (L <= m) update(L, R, c, lson);
if (m < R) update(L, R, c, rson);
PushUp(rt, l, r);
}
int main() {
int t,cas = 0;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
int m = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d%d%d%d", &p[i].lx, &p[i].ly, &p[i].lz, &p[i].rx, &p[i].ry, &p[i].rz);
Z[m++] = p[i].lz;
Z[m++] = p[i].rz;
}//離散化
sort(Z, Z + m);
int cntz = unique(Z, Z + m) - Z;
long long ans = 0;
for (int i = 0; i < cntz - 1; i++)
{
memset(cnt, 0, sizeof(cnt));
memset(sum, 0, sizeof(sum));
memset(sum2, 0, sizeof(sum2));
memset(sum3, 0, sizeof(sum3));
m = 0;
for (int j = 1; j <= n; j++)
if (p[j].lz <= Z[i] && p[j].rz > Z[i])
{
X[m] = p[j].lx;
ss[m++] = Seg(p[j].lx, p[j].rx, p[j].ly, 1);
X[m] = p[j].rx;
ss[m++] = Seg(p[j].lx, p[j].rx, p[j].ry, -1);
}
sort(X, X + m);
sort(ss, ss + m);
int cntx = unique(X, X + m) - X;
for (int j = 0; j < m - 1; j++)
{
int l = lower_bound(X, X + cntx, ss[j].l) - X;
int r = lower_bound(X, X + cntx, ss[j].r) - X - 1;
if (l <= r) update(l, r, ss[j].s, 0, cntx - 1, 1);
ans += (long long)sum3[1] * (long long)(ss[j + 1].h - ss[j].h) * (long long)(Z[i + 1] - Z[i]);
}
}
printf("Case %d: %lld\n", ++cas, ans);
}
return 0;
}