題意：
? ? ? 給你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 线段树扫描线求体积的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。