hdu3255 线段树扫描线求体积

题意：
      给你n个矩形，每个矩形上都有一个权值（该矩形单位面积的价值），矩形之间可能重叠，重叠部分的权值按照最大的算，最后问这n个矩形组成的图形的最大价值。

思路：

      线段树扫描线求长方体体积，对于求体积，如果理解求面积的过程，求体积也很容易理解，就是先一层一层的求面积，然后把面积当成"当前所覆盖的线段",以长方体的高的方向更新，不是很容易说清楚，看下代码就懂了，就体积的时候就是先求出一层面积，然后在用一层一层的面积更新体积，具体看代码吧，应该很容易理解，说着感觉很费劲。

#include<stdio.h> #include<string.h> #include<algorithm>#define N 65000 #define Nmax 300000 #define lson l ,mid ,t << 1 #define rson mid ,r ,t << 1 | 1 using namespace std;typedef struct {__int64 l ,r ,h ,mk; }EDGE;typedef struct {__int64 x1 ,x2 ,y1 ,y2;__int64 pri; }NODE;EDGE edge[N]; NODE node[33000]; __int64 len[Nmax] ,cnt[Nmax]; __int64 tmp[Nmax] ,num[Nmax]; __int64 price[5];bool camp(EDGE a ,EDGE b) {return a.h < b.h; }int search(int id ,__int64 now) {int low ,up ,mid ,Ans;low = 1 ,up = id;while(low <= up){mid = (low + up) >> 1;if(now <= num[mid]){Ans = mid;up = mid - 1;}else low = mid + 1;}return Ans; }void Pushup(__int64 l ,__int64 r ,__int64 t) {if(cnt[t]) len[t] = num[r] - num[l];else if(l + 1 == r) len[t] = 0;else len[t] = len[t<<1] + len[t<<1|1]; }void Update(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b ,__int64 c) {if(l == a && r == b){cnt[t] += c;Pushup(l ,r ,t);return ;}__int64 mid = (l + r) >> 1;if(b <= mid) Update(lson ,a ,b ,c);else if(a >= mid) Update(rson ,a ,b ,c);else {Update(lson ,a ,mid ,c);Update(rson ,mid ,b ,c);}Pushup(l ,r ,t); }__int64 solve(int n ,int m) {__int64 Ans = 0 ,i ,id;sort(price + 1 ,price + m + 1);price[0] = 0;for(int ii = 1 ;ii <= m ;ii ++){int nn = 0;for(id = 0 ,i = 1 ;i <= n ;i ++){if(node[i].pri < price[ii]) continue;nn += 2;edge[++id].l = node[i].x1;edge[id].r = node[i].x2 ,edge[id].h = node[i].y1 ,edge[id].mk = 1;tmp[id] = node[i].x1;edge[++id].l = node[i].x1;edge[id].r = node[i].x2 ,edge[id].h = node[i].y2 ,edge[id].mk = -1;tmp[id] = node[i].x2;} sort(tmp + 1 ,tmp + id + 1); id = 0;for(i = 1 ;i <= nn ;i ++)if(i == 1 || tmp[i] != tmp[i-1])num[++id] = tmp[i];sort(edge + 1 ,edge + nn + 1 ,camp);memset(len ,0 ,sizeof(len));memset(cnt ,0 ,sizeof(cnt));__int64 ans = 0;edge[0].h = edge[1].h;for(i = 1 ;i <= nn ;i ++){ans += len[1] * (edge[i].h - edge[i-1].h);__int64 ll = search(id ,edge[i].l);__int64 rr = search(id ,edge[i].r);Update(1 ,nn ,1 ,ll ,rr ,edge[i].mk);}Ans += ans * (price[ii] - price[ii-1]);}return Ans; }int main () {int t ,n ,m ,cas = 1;scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);for(int i = 1 ;i <= m ;i ++)scanf("%I64d" ,&price[i]);for(int i = 1 ;i <= n ;i ++){scanf("%I64d %I64d %I64d %I64d %I64d" ,&node[i].x1 ,&node[i].y2 ,&node[i].x2 ,&node[i].y1 ,&node[i].pri);node[i].pri = price[node[i].pri];}printf("Case %d: %I64d\n" ,cas ++ ,solve(n ,m));}return 0; }

总结

以上是生活随笔为你收集整理的hdu3255 线段树扫描线求体积的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。