程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1542 Atlantis(線段樹求矩形面積並)

HDU 1542 Atlantis(線段樹求矩形面積並)

編輯:C++入門知識

HDU 1542 Atlantis(線段樹求矩形面積並)


題意:給你n個矩形, 求這n個矩形所覆蓋的面積(重復覆蓋算一次)

思路:我們可以考慮, 將y坐標保存並排序。 按x坐標離散化後建立線段樹。 每次遇到一個矩形的下底邊就將這個區間+1,表示這個區間已經被幾條線段覆蓋了。 遇到上邊就-1, 每次更新後累加當前x坐標總區間被覆蓋的長度乘以相鄰兩邊的高度。 具體原因可以畫圖看看就明白了。 另外很重要的一點就是, 線段樹都是維護一個點集, 但是對於邊的問題就會變得很麻煩, 我們可以按照區間左端點建立線段樹, 那麼一個點表示的就不是點了, 而是起點在這個點的一個線段。 這樣的話, 右區間就要相應的-1, 例如更新區間[1, 4], 就相當於更新標號為[1, 3]的線段。

這也是處理線段覆蓋問題的通用方法。

細節參見代碼:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 100000 + 10;
int T,n,m,kase=0,addv[maxn<<2];
double sum[maxn<<2],c[maxn];
struct node {
    double xl, xr, h;
    int id;
    node(double xl=0, double xr=0, double h=0, int id=0):xl(xl),xr(xr),h(h),id(id) {}
    bool operator < (const node& rhs) const {
        return h < rhs.h;
    }
}b[maxn];
void PushUp(int l, int r, int o) {
    if(addv[o]) sum[o] = c[r+1] - c[l];  //當前區間被線段覆蓋
    else if(l == r) sum[o] = 0; // 已經到了葉子結點且沒有被覆蓋
    else sum[o] = sum[o<<1] + sum[o<<1|1]; // 沒有完全被覆蓋, 但是還沒到葉子結點, 從其子區間中獲得信息
}
void build(int l, int r, int o) {
    int m = (l + r) >> 1;
    addv[o] = 0;
    sum[o] = 0;
    if(l == r) return ;
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
}
void update(int L, int R, int x, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) {
        addv[o] += x;
        PushUp(l, r, o);
        return ;
    }
    if(L <= m) update(L, R, x, l, m, o<<1);
    if(m < R) update(L, R, x, m+1, r, o<<1|1);
    PushUp(l, r, o);
}
double xl, xr, yl, yr;
int main() {
    while(~scanf("%d",&n) && n) {
        int cnt = 0, res = 0;
        for(int i=0;i<n;i++) int="" m="unique(c+1," -="" c="" double="" ans="0;" i="1;i<cnt;i++)" xl="lower_bound(c+1," xr="lower_bound(c+1," test="" case="" total="" explored="" area:="" return="" pre=""><p>
</p>
   
</n;i++)></queue></map></deque></list></set></cmath></cstdlib></bitset></stack></vector></string></iostream></algorithm></cstring></cstdio>

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved