HDU 1255 Covered area(Segment Tree Scanning Lines)

Description

多个矩形相交，求至少被覆盖过两次的面积

Analyze

相对于求矩形面积并集，此题所求的特点在于cnt[o] >= 2 才有 len[o] = X[R + 1] - X[L];。另外这要求每段的cnt及时更新，而之前那种方法不down，数据没有被正确表示，而现在就需要用上lazy数组down下去了。

另外加一个query函数释放所有的lazy以更新数据

对于之前写过的线段树们，下面节点的状态没被更新不影响上面节点状态的正确性，而这一题下面节点不被lazy更新会导致上面节点呈现着错误的状态，所以每次从线段树取值时都需要释放所有lazy更新这棵树。

现在这种方案：需要用到线段树维护的值时，释放全部lazy

相比较于：不用lazy，每次update都更新到底

还是省时间的

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2100;

int n;

int num;
double X[N];
int cnt[N << 2 | 1], lazy[N << 2 | 1];
double len[N << 2 | 1];

struct edge
{
    double l, r, h;
    int flag;
    edge(double a, double b, double c, int d):l(a), r(b), h(c), flag(d){}
    edge(){}
    bool operator < (const edge & t)const
    {
        return h < t.h;
    }
}e[N];

void down(int o, int L, int R)
{
    if(lazy[o] != 0)
    {
        cnt[o << 1] += lazy[o];
        cnt[o << 1 | 1] += lazy[o];
        lazy[o << 1] += lazy[o];
        lazy[o << 1 | 1] += lazy[o];
        lazy[o] = 0;
    }
}

void up(int o, int L, int R)
{
    if(cnt[o] >= 2)
        len[o] = X[R + 1] - X[L];
    else if(L == R)
        len[o] = 0;
    else
        len[o] = len[o << 1] + len[o << 1 | 1];
}

void update(int o, int L, int R, int l, int r, int val)
{
    if(L > r || R < l)
        return ;
    if(l <= L && R <= r)
    {
        cnt[o] += val;
        lazy[o] += val;
        up(o, L, R);
        return ;
    }
    if(L == R)
        return ;

    down(o, L, R);
    int mid = (L + R) >> 1;
    update(o << 1, L, mid, l, r, val);
    update(o << 1 | 1, mid + 1, R, l, r, val);
    up(o, L, R);
}

void query(int o, int L, int R)
{
    if(L == R)
    {
        up(o, L, R);
        return ;
    }

    down(o, L, R);
    int mid = (L + R) >> 1;
    query(o << 1, L, mid);
    query(o << 1 | 1, mid + 1, R);
    up(o, L, R);
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        num = 0;
        memset(len, 0, sizeof(len));
        memset(cnt, 0, sizeof(cnt));
        memset(lazy, 0, sizeof(lazy));
        double a, b, c, d;
        for(int i = 0; i < n; ++i)
        {
            scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
            X[num] = a;
            e[num++] = edge(a, c, b, 1);
            X[num] = c;
            e[num++] = edge(a, c, d, -1);
        }

        sort(e, e + num);
        sort(X, X + num);
        int m = unique(X, X + num) - X;

        double ans = 0;
        for(int i = 0; i < num; ++i)
        {
            int l = lower_bound(X, X + m, e[i].l) - X;///Segment Tree begins with 0
            int r = lower_bound(X, X + m, e[i].r) - X - 1;
            update(1, 0, m - 2, l, r, e[i].flag);
            query(1, 0, m - 2);
            ans += len[1] * (e[i + 1].h - e[i].h);
        }
        printf("%.2f\n", ans);
    }
    return 0;
}

方案2:就是不down

区分len1(区间被覆盖次数>=1)与len2(区间覆盖次数>=2)

up函数

void up(int o, int L, int R)
{
    if(cnt[o])
        len1[o] = X[R + 1] - X[L];
    else if(L == R)
        len1[o] = 0;
    else
        len1[o] = len1[o << 1] + len1[o << 1 | 1];

    if(cnt[o] >= 2)
        len2[o] = X[R + 1] - X[L];
    else if(L == R)
        len2[o] = 0;
    else
    {
        if(cnt[o] == 1)
            len2[o] = len1[o << 1] + len1[o << 1 | 1];
        else
            len2[o] = len2[o << 1] + len2[o << 1 | 1];
    }
}

由于更新len2需要用到len1，所以先更新len1

len1[o] >= len2[o]一个区间被覆盖一次以上的长度不少于它被覆盖两次以上的长度，所以当cnt[o] < 2时，如果cnt[o] == 1那就先用len1更新len2，否则再用len2更新len2.

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2100;

int n;

int num;
double X[N];
int cnt[N << 2 | 1];
double len1[N << 2 | 1], len2[N << 2 | 1];

struct edge
{
    double l, r, h;
    int flag;
    edge(double a, double b, double c, int d):l(a), r(b), h(c), flag(d){}
    edge(){}
    bool operator < (const edge & t)const
    {
        return h < t.h;
    }
}e[N];

void up(int o, int L, int R)
{
    if(cnt[o])
        len1[o] = X[R + 1] - X[L];
    else if(L == R)
        len1[o] = 0;
    else
        len1[o] = len1[o << 1] + len1[o << 1 | 1];

    if(cnt[o] >= 2)
        len2[o] = X[R + 1] - X[L];
    else if(L == R)
        len2[o] = 0;
    else
    {
        if(cnt[o] == 1)
            len2[o] = len1[o << 1] + len1[o << 1 | 1];
        else
            len2[o] = len2[o << 1] + len2[o << 1 | 1];
    }
}

void update(int o, int L, int R, int l, int r, int val)
{
    if(L > r || R < l)
        return ;
    if(l <= L && R <= r)
    {
        cnt[o] += val;
        up(o, L, R);
        return ;
    }
    if(L == R)
        return ;

    int mid = (L + R) >> 1;
    update(o << 1, L, mid, l, r, val);
    update(o << 1 | 1, mid + 1, R, l, r, val);
    up(o, L, R);
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        num = 0;
        memset(cnt, 0, sizeof(cnt));
        memset(len1, 0, sizeof(len1));
        memset(len2, 0, sizeof(len2));
        double a, b, c, d;
        for(int i = 0; i < n; ++i)
        {
            scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
            X[num] = a;
            e[num++] = edge(a, c, b, 1);
            X[num] = c;
            e[num++] = edge(a, c, d, -1);
        }

        sort(e, e + num);
        sort(X, X + num);
        int m = unique(X, X + num) - X;

        double ans = 0;
        for(int i = 0; i < num; ++i)
        {
            int l = lower_bound(X, X + m, e[i].l) - X;///Segment Tree begins with 0
            int r = lower_bound(X, X + m, e[i].r) - X - 1;
            update(1, 0, m - 2, l, r, e[i].flag);
            ans += len2[1] * (e[i + 1].h - e[i].h);
        }
        printf("%.2f\n", ans);
    }
    return 0;
}