poj 1177 Picture（线段树周长并）

题意：给你n个矩形问你重叠后外边缘总共多长。

周长并与面积并很像只不过是处理的时候是增加的周长=abs（上一次的线段的长度-更新后线段的长度）

然后分别处理一下竖着的边和横着的边就好了即建两次树就好。

就是一道典型的周长并问题，可以拿来练练周长并的写法。

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdio>

using namespace std;

typedef long long ll;

const int M = 1e5 + 10;

struct ss {

    int l , r , h , flag;

}s1[M << 1] , s2[M << 1];

struct TnT {

    int l , r , add , len;

}T[M << 4];

bool cmp(ss a , ss b) {

    if(a.h == b.h)

        return a.flag > b.flag;

    return a.h < b.h;

}

void build(int l , int r , int p) {

    int mid = (l + r) >> 1;

    T[p].l = l , T[p].r = r , T[p].add = T[p].len = 0;

    if(l == r)

        return ;

    build(l , mid , p << 1);

    build(mid + 1 , r , (p << 1) | 1);

}

void pushup(int p) {

    if(T[p].add) {

        T[p].len = T[p].r - T[p].l + 1;

    }

    else if(T[p].l == T[p].r) {

        T[p].len = 0;

    }

    else {

        T[p].len = T[p << 1].len + T[(p << 1) | 1].len;

    }

}

void updata(int l , int r , int p , int ad) {

    int mid = (T[p].l + T[p].r) >> 1;

    if(T[p].l == l && T[p].r == r) {

        T[p].add += ad;

        pushup(p);

        return ;

    }

    if(mid >= r) {

        updata(l , r , p << 1 , ad);

    }

    else if(mid < l) {

        updata(l , r , (p << 1) | 1 , ad);

    }

    else {

        updata(l , mid , p << 1 , ad);

        updata(mid + 1 , r , (p << 1) | 1 , ad);

    }

    pushup(p);

}

int main() {

    int n;

    scanf("%d" , &n);

    for(int i = 1 ; i <= n ; i++) {

        int x1 , y1 , x2 , y2;

        scanf("%d%d%d%d" , &x1 , &y1 , &x2 , &y2);

        x1 += M , x2 += M , y1 += M , y2 += M;

        s1[i].flag = 1;

        s1[i].l = x1;

        s1[i].r = x2;

        s1[i].h = y1;

        s1[i + n].flag = -1;

        s1[i + n].l = x1;

        s1[i + n].r = x2;

        s1[i + n].h = y2;

        s2[i].flag = 1;

        s2[i].l = y1;

        s2[i].r = y2;

        s2[i].h = x1;

        s2[i + n].flag = -1;

        s2[i + n].l = y1;

        s2[i + n].r = y2;

        s2[i + n].h = x2;

    }

    sort(s1 + 1 , s1 + 1 + 2 * n , cmp);

    sort(s2 + 1 , s2 + 1 + 2 * n , cmp);

    int l , r;

    build(1 , 2 * M , 1);

    ll ans = 0;

    for(int i = 1 ; i <= 2 * n ; i++) {

        int last = T[1].len;

        l = s1[i].l;

        r = s1[i].r - 1;

        updata(l , r , 1 , s1[i].flag);

        ans += abs(last - T[1].len);

    }

    build(1 , 2 * M , 1);

    for(int i = 1 ; i <= 2 * n ; i++) {

        int last = T[1].len;

        l = s2[i].l;

        r = s2[i].r - 1;

        updata(l , r , 1 , s2[i].flag);

        ans += abs(last - T[1].len);

    }

    printf("%lld\n" , ans);

    return 0;

}

巴特西

poj 1177 Picture（线段树周长并）

最新文章

热门文章