picture(线段树离散两次).cpp

杭电acm解题报告2001---2099.

//线段树维护
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct node {
    int l,r;
    node * pl, * pr;
    int len;//测度
    int cover;//完全覆盖数
}mem[50000];
int mem_pos;

struct line {
    int x,y1,y2;
    int flag;
    bool operator < (const line & tt ) const {
        if(x != tt.x) {
            return x < tt.x;
        }
        return flag > tt.flag;
    }
}list[10100];
struct line2 {
    int x1,x2,y;
    int flag;
    bool operator < (const line2 & tt ) const {
        if(y != tt.y) {
            return y < tt.y;
        }
        return flag > tt.flag;
    }
}list2[10100];

node *
new_node()
{
    node * pt = &mem[mem_pos ++];
    memset(pt,0,sizeof(node));
    return pt;
}

void
cal_len(node * root)
{
    root ->len = 0;
    if(root ->cover > 0) {
        root ->len = root ->r - root ->l;
    }
    else {
        if(root ->pl) {
            root ->len += root ->pl ->len;
        }
        if(root ->pr) {
            root ->len += root ->pr ->len;
        }
    }
}

node *
make_tree(int il, int ir)
{
    node * root = new_node();
    root ->l = il;
    root ->r = ir;
    if(ir - il > 1) {
        int mid = (il+ir)/2;
        root ->pl = make_tree(il, mid);
        root ->pr = make_tree(mid, ir);
    }
    return root;
}

void
update(node * root, line e)
{
    if(root ->l == e.y1 && root ->r == e.y2) {
        root ->cover += e.flag;
        cal_len(root);
        return ;
    }

    if(root ->pl ->r > e.y1) {
        if(root ->pl ->r >= e.y2) {
            update(root ->pl, e);
        }
        else {
            line e2 = e;
            e2.y2 = root ->pl ->r;
            update(root ->pl, e2);
            e2 = e;
            e2.y1 = root ->pr ->l;
            update(root ->pr, e2);
        }
    }
    else {
        update(root ->pr, e);
    }
    cal_len(root);
}

void
update2(node * root, line2 e)
{
    if(root ->l == e.x1 && root ->r == e.x2) {
        root ->cover += e.flag;
        cal_len(root);
        return ;
    }
    if(root ->pl ->r > e.x1) {
        if(root ->pl ->r >= e.x2) {
            update2(root ->pl, e);
        }
        else {
            line2 e2 = e;
            e2.x2 = root ->pl ->r;
            update2(root ->pl, e2);
            e2 = e;
            e2.x1 = root ->pr ->l;
            update2(root ->pr, e2);
        }
    }
    else {
        update2(root ->pr, e);
    }
    cal_len(root);
}

int main()
{
    int t,n,i;
    int ls;
    int x1,x2,y1,y2;
    int sum1,sum2;
    //freopen("1828.in","r",stdin);
    //freopen("1828m.txt","w",stdout);

    mem_pos = 0;
    node * root = make_tree(0,20000);
    while(scanf("%d", &n)==1) {
        ls = 0;
        sum1 = sum2 = 0;

        for(i=0;i<n;i++) {
            scanf("%d %d %d %d", &x1,&y1,&x2,&y2);
            x1 += 10000;
            y1 += 10000;
            x2 += 10000;
            y2 += 10000;
            list[ls].x = x1;
            list[ls].y1 = y1;    list[ls].y2 = y2;
            list[ls].flag = 1;
            list[ls+1].x = x2;
            list[ls+1].y1 = y1;    list[ls+1].y2 = y2;
            list[ls+1].flag = -1;

            list2[ls].y = y1;
            list2[ls].x1 = x1;    list2[ls].x2 = x2;
            list2[ls].flag = 1;
            list2[ls+1].y = y2;
            list2[ls+1].x1 = x1;    list2[ls+1].x2 = x2;
            list2[ls+1].flag = -1;

            ls += 2;
        }
        sort(list, list+ls);
        sort(list2, list2+ls);

        int preLen = 0, preLen2 = 0;
        for(i=0;i<mem_pos;i++) {
            mem[i].len = mem[i].cover = 0;
        }
        for(i=0;i<ls;i++) {
            update(root, list[i]);
            sum1 += abs(root ->len - preLen);
            preLen = root ->len;
        }

        for(i=0;i<mem_pos;i++) {
            mem[i].len = mem[i].cover = 0;
        }
        for(i=0;i<ls;i++) {
            update2(root, list2[i]);
            sum2 += abs(root ->len - preLen2);
            preLen2 = root ->len;
        }

        printf("%d\n", sum1+sum2);
    }
}