HDU 1255 覆寫的面積（線段樹+離散化+掃描線）

題目分析

上次做了一道隻用計算覆寫一次的面積，這次需要計算覆寫2次的面積，其實就是在上面的基礎上加一點東西，sum1[]表示覆寫一次的長度,sum2[]覆寫2次的長度，具體怎麼操作看pushup函數即可，寫的非常清楚。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define mid (L+R)/2
#define lson o<<1, L, mid
#define rson o<<1|1, mid+1, R
const int maxn = ;

double pos[maxn<<];
double sum1[maxn<<], sum2[maxn<<];  //sum1表示覆寫一次的長度,sum2表示覆寫2次的長度
int flag[maxn<<];

struct Edge{
    double l, r, h;
    int f;
    Edge(){}
    Edge(double a, double b, double c, int d):l(a), r(b), h(c), f(d){}
    bool operator < (const Edge& e)const{
        return h < e.h;
    }
}line[maxn];

void pushup(int o,int L,int R){   //這裡代碼已經寫得很清楚了
    if(flag[o]) sum1[o] = pos[R+] - pos[L];    
    else if(L == R) sum1[o] = ;
    else sum1[o] = sum1[o<<] + sum1[o<<|];

    if(flag[o] > ) sum2[o] = pos[R+] - pos[L];
    else if(L == R) sum2[o] = ;
    else if(flag[o] == ) sum2[o] = sum1[o<<] + sum1[o<<|];
    else sum2[o] = sum2[o<<] + sum2[o<<|];
}

void update(int o,int L,int R,int l,int r,int val){ //更新
    if(l <= L && R <= r){
        flag[o] += val;
        pushup(o, L, R);
        return;
    }
    if(l <= mid) update(lson, l, r, val);
    if(r > mid) update(rson, l, r, val);
    pushup(o, L, R);
}

int BS(double k, double a[], int len){  //二分查找
    int L = , R = len-;
    while(L <= R){
        if(a[mid] == k) return mid;
        else if(a[mid] < k) L = mid+;
        else R = mid-;
    }
    return -;
}

int main(){
    int T, n;
    scanf("%d", &T);
    while(T--){
        memset(sum1, , sizeof(sum1));
        memset(sum2, , sizeof(sum2));
        memset(flag, , sizeof(flag));
        memset(pos, , sizeof(pos));
        double x1, y1, x2, y2;
        scanf("%d", &n);
        int k = ;
        for(int i = ; i < n; i++){
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            pos[k] = x1;
            line[k++] = Edge(x1, x2, y1, );
            pos[k] = x2;
            line[k++] = Edge(x1, x2, y2, -);
        }
        sort(pos, pos+k);
        sort(line, line+k);
        int m = ;
        for(int i = ; i < k; i++)
            if(pos[i] != pos[i-]) pos[m++] = pos[i];
        double ans = ;
        for(int i = ; i < k-; i++){
            int l = BS(line[i].l, pos, m);
            int r = BS(line[i].r, pos, m)-;
            update(, , k-, l, r, line[i].f);
            ans += sum2[]*(line[i+].h - line[i].h);
        }
        printf("%.2lf\n", ans);
    }
    return ;
}