HDU_3642_扫描线求覆盖3次的体积(线段树)

HDU 3642

  • 扫描线模板的基础上增加覆盖次数

    题意

  1. 至少有2个以上不同地点才存在宝藏.即3个以上的空间立体交叉覆盖出的体积,覆盖3次及以上
  2. x y z包括整个库,意思就是给出顶点,观察样例知道是左上和右下的坐标
  3. z<=500.那么扫描法求出平面的面积,在处理题目给出的每一层.求的体积

思路

  1. x用来离散化后作为横轴建线段树,z轴存下来枚举每一个层.x轴坐标离散化后要去重,z轴坐标要用来枚举所以也要去重.
  2. 开始枚举每一层的z轴高度,筛选出该层的所有点来求面积,将x轴上的横边按照y轴的高度来排序(扫描线标准做法).
  3. 建立线段树开始扫描,

3次覆盖如何用线段树维护

  1. add表示该区间被覆盖的次数
  2. len1表示该区间被覆盖次数为1的长度
  3. len2表示该区间被覆盖次数为2的长度
  4. len3表示该区间被覆盖次数>=3的长度
  • 注意当前区间被覆盖次数不仅由len1,len2,len3组成,子区间如果也被覆盖,那么该区间不一样也被覆盖了吗？
  • 根据覆盖次数的大小关系来维护
  • 当前覆盖次数的覆盖长度=真实长度-上一层被覆盖的长度,例如求被覆盖2次的长度,由于区间上面可能还覆盖一层(也就是区间被覆盖3次),那么要减去被覆盖3次的长度
  • 看代码也有解释
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    #include <iostream>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    const int N = 2005;
    struct edge {
    	int l, r;
    	int h, f;//h,y坐标的高度,f上、下边
    	edge(){}
    	edge(int left,int right,int height,int flag) {
    		l = left; r = right; h = height; f = flag;
    	}
    	bool operator<(const edge& temp)const {
    		return h < temp.h;
    	}
    }e[N<<1];
    struct node {
    	int l, r;
    	int add; //覆盖次数
    	int len1, len2, len3;
    }q[N<<3];//?
    int x[N<<1], z[N<<1];
    #define ls i<<1
    #define rs i<<1|1
    struct point {
    	int x, y, z;
    	point(){}
    	point(int tx,int ty,int tz) {
    		x = tx; y = ty; z = tz;
    	}
    }a[N<<1];
    void build(int i,int l,int r) {
    	q[i].l = l; q[i].r = r;
    	if (l == r) return;
    	int mid = (l+r) >> 1;
    	build(ls,l,mid);
    	build(rs,mid+1,r);
    }
    void pushup(int i) {
    	int r = q[i].r;
    	int l = q[i].l;
    	if (q[i].add >= 3) { //当前区间覆盖次数>=3
    		q[i].len3 = x[r + 1] - x[l]; //恢复右端+1,然后找到原始长度(总长度)
    		q[i].len1 = q[i].len2 = 0;
    	} 
    	else if (q[i].add == 2) { //当前区间的覆盖次数==2
    		// 此时覆盖次数(=2) 加上子区间的1次(或1次以上)覆盖次数也能达到覆盖3次（以上）的效果
    		q[i].len3 = (q[ls].len1 + q[rs].len1) + (q[ls].len2+q[rs].len2) + (q[ls].len3+q[rs].len3);
    		q[i].len2 = x[r+1] - x[l] - q[i].len3; //求出覆盖2次的真实长度(总长度)-覆盖3层的长度
    		q[i].len1 = 0;
    	}
    	else if (q[i].add == 1) {
    		q[i].len3 = (q[ls].len2 + q[rs].len2) + (q[ls].len3 + q[rs].len3);
    		//len3的维护和上面len3的维护同理,1+2>=3
    		q[i].len2 = q[ls].len1 + q[rs].len1; //加上q[i].len2就会到覆盖3层的范围内
    		q[i].len1 = x[r + 1] - x[l] - q[i].len3 - q[i].len2;
    	}
    	else { //没有覆盖就从下到上更新
    		q[i].len3 = q[ls].len3 + q[rs].len3;
    		q[i].len2 = q[ls].len2 + q[rs].len2;
    		q[i].len1 = q[ls].len1 + q[rs].len1;
    	}
    }
    void update(int i, int l,int r,int val) {
    	if (l <= q[i].l && q[i].r <= r) {
    		q[i].add += val;
    		pushup(i);
    		return;
    	}
    	int mid = (q[i].l + q[i].r) >> 1;
    	if (r <= mid) update(ls,l,r,val);
    	else if (l > mid) update(rs,l,r,val);
    	else {
    		update(ls,l,mid,val);
    		update(rs,mid+1,r,val);
    	}
    	pushup(i);
    }

    int main() {
    	//freopen("a.txt", "r", stdin); 
    	int times; cin >> times; int count = 0;
    	while (times--) {
    		int n; scanf("%d",&n);
    		int totx = 0, totz = 0, tot = 0;
    		int x1, y1, z1, x2, y2, z2;
    		for (int i = 1; i <= n; i++) {
    			scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
    			x[totx++] = x1; x[totx++] = x2;
    			z[totz++] = z1; z[totz++] = z2;
    			point t(x1, y1, z1); a[tot++] = t; // 第一个是左边点
    			t = point(x2, y2, z2); a[tot++] = t;// 第二个是右边点
    		}
    		printf("Case %d: ",++count);
    		if (n < 3) {
    			printf("0\n");
    			continue;
    		}
    		sort(x,x+totx);
    		sort(z,z+totz); // x和z坐标从小到大排个序
    		// 去重,让每一个坐标都对应一个值
    		totx = unique(x, x + totx) - x;
    		totz = unique(z, z + totz) - z;
    		long long ansxyz = 0;
    		for (int i = 0; i < totz-1; i++) {//访问至倒数第2层
    			//先将每一层的面积求出来,然后在*z轴高度求体积就行了
    			int k = 0;
    			for (int j = 0; j < tot; j += 2) { //遍历所有的点.每次扫描2个
    				if (a[j].z <= z[i] && z[i] < a[j + 1].z) {
    					// 上下边1,-1随便填,等下会按照高度排序,
    					// 题目数据先给左边的点,然后才给右边的点.所以a[j].x<a[j+1].x
    					e[k++] = edge(a[j].x,a[j+1].x,a[j].y,1);
    					e[k++] = edge(a[j].x,a[j+1].x,a[j+1].y,-1);
    				}
    			}
    			sort(e,e+k); // 根据y轴的值来排序,xy平面上的高度
    			memset(q,0,sizeof q); //清空线段树
    			build(1,0,totx-1);// x的范围[0,totx-1]
    			long long ansxy = 0;
    			// 扫描线开始扫描
    			for (int j = 0; j < k - 1; j++) {//[0,k-1]是该层上 的所有横边
    				//找到e[j].l e[j].r (离散化)也就是在线段树中对应的点
    				int l = lower_bound(x,x+totx,e[j].l) - x; 
    				int r = lower_bound(x,x+totx,e[j].r) - x - 1; //扫描线规定.右端-1
    				update(1,l,r,e[j].f);
    				ansxy += (long long)q[1].len3 * (long long)(e[j + 1].h - e[j].h);
    			}
    			ansxyz += (long long)ansxy * (long long)(z[i+1] - z[i]); //面积*z轴高度=体积
    		}
    		printf("%I64d\n",ansxyz);
    	}
    	return 0;
    }