題意：

有一塊田，上面有n個矩陣，每個矩陣對應一個權值，矩陣相交的部分取權值大的，問最后能獲得多少值。

思路：

1. 權值問題可以轉換為體積問題，因為相同格子里面權值大的勝，可以把權值看成是立方體的高，于是問題轉換為立方體體積的并。

2. 和 get the treasure 題目類似，因為price變化的范圍很小，于是先對高進行離散化 + 掃描。

3. 剩下的就是求 面積 * 高 了，對于面積，采取以前的常規手段，對 x 進行離散化，然后求面積的并就OK了。

?

#include <iostream> #include <algorithm> using namespace std;#define lhs l, m, rt << 1 #define rhs m + 1, r, rt << 1 | 1const int maxn = 61000; int sum[maxn << 2], cnt[maxn << 2]; int price[10]; int xcord[maxn];struct Coord {int x1, y1, x2, y2, p; } cord[30010] ;struct Segment {int l, r, h, v;Segment () { }Segment(int _l, int _r, int _h, int _v) : l(_l), r(_r), h(_h), v(_v) { }bool operator < (const Segment& other){if (h == other.h)return v > other.v;elsereturn h < other.h;} } seg[maxn] ;void pushUp(int l, int r, int rt) {if (cnt[rt])sum[rt] = xcord[r+1] - xcord[l];else if (l == r)sum[rt] = 0;elsesum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }void update(int beg, int end, int value, int l, int r, int rt) {if (beg <= l && r <= end){cnt[rt] += value;pushUp(l, r, rt);return ;}int m = (l + r) >> 1;if (beg <= m)update(beg, end, value, lhs);if (end > m)update(beg, end, value, rhs);pushUp(l, r, rt); }__int64 solve(int nn, int mm) {__int64 ret = 0;sort(price + 1, price + mm + 1);for (int i = 1; i <= mm; ++i){int n = 0, m = 0;for (int j = 0; j < nn; ++j){if (cord[j].p >= price[i]){seg[n++] = Segment(cord[j].x1, cord[j].x2, cord[j].y1, 1);seg[n++] = Segment(cord[j].x1, cord[j].x2, cord[j].y2, -1);xcord[m++] = cord[j].x1;xcord[m++] = cord[j].x2;}}sort(seg, seg + n);sort(xcord, xcord + m);m = unique(xcord, xcord + m) - xcord;memset(sum, 0, sizeof(sum));memset(cnt, 0, sizeof(cnt));__int64 area = 0;for (int j = 0; j < n - 1; ++j){int beg = lower_bound(xcord, xcord + m, seg[j].l) - xcord;int end = lower_bound(xcord, xcord + m, seg[j].r) - xcord - 1;if (beg <= end)update(beg, end, seg[j].v, 0, m - 1, 1);area += (__int64)sum[1] * (seg[j+1].h - seg[j].h);}ret += area * (price[i] - price[i-1]);}return ret; }int main() {int cases, cc = 0;scanf("%d", &cases);while (cases--){int n, m;scanf("%d %d", &n, &m);price[0] = 0;for (int i = 1; i <= m; ++i)scanf("%d", &price[i]);for (int i = 0; i < n; ++i){scanf("%d %d %d %d %d", &cord[i].x1, &cord[i].y1, &cord[i].x2, &cord[i].y2, &cord[i].p);cord[i].p = price[cord[i].p];}printf("Case %d: %I64d\n", ++cc, solve(n, m));}return 0; }

轉載于:https://www.cnblogs.com/kedebug/archive/2013/02/04/2891264.html

總結

以上是生活随笔為你收集整理的HDOJ 3255 Farming（扫描线 + 线段树 体积的并）的全部內容，希望文章能夠幫你解決所遇到的問題。

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