HDU 3642 （扫描线、三维体积相交）

题意

在三维空间中给你n个长方体，求空间中被这些长方体覆盖至少3次以上的区域的总体积。

思路

这题没给数据组数T的范围，大致看了一下其他人的都是枚举z来做的，所以我这边也是同样的做法转换成二维的扫描线来做，数组ci表示被覆盖i次的区间标记，具体扫描线怎么实现可以看我上篇博客。

  1 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  2 #define bug2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl
  3 #define bug(x) cout<<#x<<" is "<<x<<endl;
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<cstdio>
  7 #include<vector>
  8 #include<tuple> 
  9 #define rs o*2+1
 10 #define ls o*2
 11 using namespace std;
 12 typedef long long ll;
 13 const int N=2e3+5;
 14 int T, kase, n, c[N*4];
 15 ll sum[4][N*4];
 16 vector<tuple<int, int, int, int, int, int>> v, g;
 17 vector<int> id;
 18 vector<int> idz;
 19 void push_up(int o, int l, int r){
 20     if (c[o] >= 3) {
 21         for (int i = 1; i <= 3 ;i++) sum[i][o] = id[r] - id[l-1];
 22     }
 23     else if (c[o] == 2) {
 24         for (int i = 1; i <= 2 ;i++) sum[i][o] = id[r] - id[l-1];
 25         if (l < r) sum[3][o] = sum[1][ls] + sum[1][rs];
 26         else sum[3][o] = 0; 
 27     }
 28     else if (c[o] == 1) {
 29         sum[1][o] = id[r] - id[l-1];
 30         if (l < r) {
 31             for(int i = 2; i <= 3 ;i++) sum[i][o] = sum[i-1][ls] + sum[i-1][rs];
 32         }
 33         else sum[2][o] = sum[3][o] = 0;
 34     }
 35     else{
 36         if (l < r) {
 37             for(int i = 1; i <= 3 ;i++) sum[i][o] = sum[i][ls] + sum[i][rs];
 38         }
 39         else sum[1][o] = sum[2][o] = sum[3][o] = 0;
 40     }
 41 } 
 42 void up(int o, int l, int r, int ql, int qr, int val){
 43     if (l >= ql && r <= qr) {
 44         c[o] += val;
 45         push_up(o, l, r);
 46         return;
 47     }
 48     int m = (l+r)/2;
 49     if (ql <= m) up(ls, l, m, ql, qr, val);
 50     if (qr > m) up(rs, m+1, r, ql, qr, val);
 51     push_up(o, l, r);
 52 }
 53 int gao(int x){
 54     return lower_bound(id.begin(), id.end(), x)-id.begin();
 55 }
 56 void init(int n){
 57     for (int i = 1; i <= 8 * n; i++) {
 58         c[i] = 0;
 59         for (int j = 1; j <= 3; j++) {
 60             sum[j][i] = 0;
 61         }
 62     }
 63 }
 64 int main(){
 65     IO;
 66     cin >> T;
 67     while (T--){
 68         cin >> n;
 69         id.clear();
 70         v.clear();
 71         int l, r, d, u, h, k;
 72         for (int i = 0; i < n; i++){
 73             cin >> l >> d >> k >> r >> u >> h;
 74             id.push_back(d);
 75             id.push_back(u);
 76             idz.push_back(h);
 77             idz.push_back(k);
 78             v.push_back(make_tuple(l, d, u, 1, k, h));
 79             v.push_back(make_tuple(r, d, u, -1, k, h));
 80         }
 81         sort(v.begin(), v.end()); 
 82         sort(id.begin(), id.end());
 83         id.erase(unique(id.begin(), id.end()), id.end());
 84         sort(idz.begin(), idz.end());
 85         idz.erase(unique(idz.begin(), idz.end()), idz.end());
 86         ll ans = 0;
 87         for (int i = 1; i < idz.size(); i++) {
 88             int pre = 0;
 89             init(n);
 90             ll res = 0;
 91             g.clear();
 92             for (auto j : v) {
 93                 int k = get<4>(j), h = get<5>(j);
 94                 if (idz[i-1] >= k && idz[i] <= h) g.push_back(j);
 95             }
 96             for (auto j : g) {
 97                 int pos = get<0>(j), d = get<1>(j), u = get<2>(j), val = get<3>(j);
 98                 res += 1ll * (pos - pre) * sum[3][1];
 99                 pre = pos;
100                 up(1, 1, id.size()-1, gao(d)+1, gao(u), val);
101             }
102             ans += res * (idz[i] - idz[i-1]);
103         }
104         printf("Case %d: %I64d\n",++kase,ans);
105     }
106 }