HDu 1255で覆われた面積(矩形面積交差+走査線)

http://acm.hdu.edu.cn/showproblem.php?pid=1255
标题:n個の矩形をあげて、彼らの面積を求めて渡します.
考え方:hdu 1542と基本的に同じですが、この問題は面積を求めています.
len 1はセグメントを1回、len 2はセグメントを2回上書きする.
キーはノードの長さの更新にあります.ここで面積を求める長さは1回以上上書きしなければならないので、線分ツリーノードに変数len 2を増やして、1回以上上書きされた区間の長さを記録する.更新時に、1回以上上書きすると、len 1、len 2の長さが直接求められます.
以下に重点を置きます.
一度上書きすると、len 1が直接求め、len 2がどのように求めるか、これは非常に重要な点であり、理解しなければならない.cnt==1の場合,この点の状態は比較的微妙で,彼が一度上書きされたことは知られているが,再び上書きされたかどうかは分からない.セグメントを下から上へスキャンすると、エッジをスキャンするたびにcnt値が更新され、セグメント情報が更新され、更新するときは下へ更新され、求めたサブノードの長さが戻って各親ノードが更新されるからです.このとき親ノードに戻る情報は子ノードから提供されますが、len 2の値はどのように求めますか?cnt=1はどういう意味かを考えてみましょう.この区間がセグメントで完全に覆われていることを説明します.サブノードのlen 1に値がある限り、親ノードのlen 2値が加算されます.
また、0回オーバーライドすると、子ノードのみで価値が伝達され、親ノードはあまりにも役に立たない==
残りは古いやり方ですが、double変換は柔軟な点を覚えているだけで、このためコンパイルできないことが多いです.

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 50010;
const int INF = 1e8;

struct line//     
{
    int l, r;//    
    int cnt;//cnt       ，0        ，1       
    double len1, len2;//len1             ，len2             
}tree[4*N];

struct node//    
{
    double l, r, h;
    int f;
    bool operator < (const struct node & tmp) const
    {
        return h < tmp.h;
    }
}seg[4*N];

double x[N];

void build(int i, int l, int r)
{
    tree[i].l = l;
    tree[i].r = r;
    tree[i].len1 = tree[i].len2 = 0;
    tree[i].cnt = 0;
    if(l == r)
    {
        return;
    }
    int mid = (l+r) >> 1;
    build(i*2, l, mid);
    build(i*2+1, mid+1, r);
}

int binsearch(double key, int k)
{
    int high = k;
    int low = 1;
    while(high >= low)
    {
        int mid = (high+low) >> 1;
        if(x[mid] == key)
        {
            return mid;
        }
        else if(x[mid] < key)
        {
            low = mid+1;
        }
        else high = mid-1;
    }
    return -1;
}

void maintain(int i)
{
    if(tree[i].cnt > 1)//         ， len1 len2         
    {
        tree[i].len2 = tree[i].len1 = x[tree[i].r+1]-x[tree[i].l];
        return;
    }
    if(tree[i].cnt == 1)
    {
        tree[i].len1 = x[tree[i].r+1]-x[tree[i].l];
        if(tree[i].l == tree[i].r)
            tree[i].len2 = 0;
        else
            tree[i].len2 = tree[i*2].len1+tree[i*2+1].len1;
        return;
    }
    if(tree[i].cnt == 0)
    {
        if(tree[i].l == tree[i].r)
            tree[i].len2 = tree[i].len1 = 0;
        else
        {
            tree[i].len1 = tree[i*2].len1+tree[i*2+1].len1;
            tree[i].len2 = tree[i*2].len2+tree[i*2+1].len2;
        }
        return;
    }
}


void update(int i, int l, int r, int f)
{
    if(tree[i].l == l && tree[i].r == r)
    {
        tree[i].cnt += f;
        maintain(i);
        return;
    }
    int mid = (tree[i].l+tree[i].r) >> 1;
    if(mid >= r)
        update(i*2, l, r, f);
    else if(mid < l)
        update(i*2+1, l, r, f);
    else
    {
        update(i*2, l, mid, f);
        update(i*2+1, mid+1, r, f);
    }
    maintain(i);
}

int main()
{
 //   freopen("in.txt", "r", stdin);
    int t, n;
    double x1, y1, x2, y2;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        memset(x,0,sizeof(x));
        int num = 1;
        for(int i = 1; i <= n; i++)
        {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            seg[num] = (struct node){x1, x2, y1, 1};
            x[num++] = x1;

            seg[num] = (struct node){x1, x2, y2, -1};
            x[num++] = x2;
        }
        sort(seg+1, seg+num);
        sort(x+1, x+num);
        int k = 1;
        for(int i = 2; i < num; i++)
        {
            if(x[i-1] != x[i])
            {
                x[++k] = x[i];
            }
        }
        build(1, 1, k);
        double ans = 0;
        for(int i = 1; i < num; i++)
        {
            int l = binsearch(seg[i].l, k);
            int r = binsearch(seg[i].r, k)-1;
            update(1, l, r, seg[i].f);
            ans += (seg[i+1].h-seg[i].h)*tree[1].len2;
        }
        printf("%.2lf
", ans);
    }
    return 0;
}