IOI1998 Picture(矩形周长并)

前言

今天初赛,差点退役啦,哈哈…
此题是IOI 1998试题。
同时也是POJ 1177和HDU 1828.
我也是会点扫描线的人啦!

题目描述

分析

首先我们可以像做面积并一样,转化为周长并的话,我们只需要对于水平和竖直的边各扫一遍就可以了。(注意每次累加的是当前总的覆盖长度和上一次总的覆盖长度差的绝对值)
不过这样效率并不高,事实上我们可以将两次操作合并到同一轮扫描。
对于每个代表线段的节点,我们记录这样几个信息:

  • 被完全覆盖的次数
  • 区间被覆盖的总长度
  • 左右端点是否被覆盖
  • 覆盖区间的线段段数
    (注意这个段数指的是对整个区间整体考虑,比如区间[1, 10],被覆盖的部分是[2,4],[5, 9],那么这个段数就是2段)

合并的时候,区间左端点继承左儿子左端点的信息,右端点记录右儿子右端点的信息,而覆盖段数需要判断一下中间点是否被覆盖到。
其他大部分操作和面积并是差不多的。

参考程序

然后今天打的时候空间又开小了…

struct Edge {
    int lx, rx, y, f;
    Edge() {}
    Edge(int lx_, int rx_, int y_, int f_) : lx(lx_), rx(rx_), y(y_), f(f_) {}
    bool operator<(const Edge & e) const {
        return y < e.y;
    }
} E[MAXN << 1];

int N, tote;

namespace Segment_Tree {
    struct Node {
        int len, crfg, crseg, lft_cvr, rgh_cvr;
/*  5个信息:
        len - 区间被覆盖的长度
        crfg - 区间被完全覆盖的次数
        crseg - 覆盖区间的线段段数
        lft_cvr, rgh_cvr - 区间左/右端点覆盖标记
*/
        void set(int md) {
        // mode of node setting: 0 - no seg cover, 1 - all covered
            if (md) { lft_cvr = rgh_cvr = crseg = 1; return; }
            lft_cvr = rgh_cvr = crseg = len = 0;
        }
        Node operator+(const Node & n) const {
        // 重载加法:节点的合并(不满足交换律)
        // This addition does NOT satisfy the exchange law.
        // Left son must be the first-operation element.
            Node res;
            res.len = this->len + n.len, res.crfg = 0;
            res.lft_cvr = this->lft_cvr, res.rgh_cvr = n.rgh_cvr;
            res.crseg = this->crseg + n.crseg - (this->rgh_cvr & n.lft_cvr);
            return res;
        }
    } T[MAXX << 2];
    int limt, QL, QR, delta;

    void modify(int rt, int l, int r);
    inline void init(int l_) {
        limt = l_;
        memset(T, sizeof T, 0);
    }
    inline int add_edge(int ql, int qr, int flg) {
        QL = ql, QR = qr, delta = flg;
        modify(1, 1, limt);
        return T[1].len;
    }
    inline int tot_seg() {
        return T[1].crseg;
    }
}
void solve();

int main() {
    while (~scanf("%d", &N)) solve();
    return 0;
}

void solve() {
    int minx = INF, maxx = -INF;
    tote = 0;
    for (int i = 0, x1, x2, y1, y2; i < N; i++) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        E[tote++] = Edge(x1, x2, y1, 1);
        E[tote++] = Edge(x1, x2, y2, -1);
        minx = std::min(minx, x1);
        maxx = std::max(maxx, x2);
    }
    std::sort(E, E + tote);
    Segment_Tree::init(maxx - minx + 1);
    // 此题规模较小,无需离散化,但是注意需要将原区间映射到x正半轴上
    int dltx = -minx + 1, lstcvr = Segment_Tree::add_edge(E[0].lx + dltx, E[0].rx + dltx, E[0].f), ans = lstcvr, tmp;
    for (int i = 1; i < tote; i++) {
        ans += Segment_Tree::tot_seg() * 2 * (E[i].y - E[i - 1].y);
        ans += std::abs((tmp = Segment_Tree::add_edge(E[i].lx + dltx, E[i].rx + dltx, E[i].f)) - lstcvr);
        lstcvr = tmp;
    }
    printf("%d\n", ans);
}

namespace Segment_Tree {
#define lson rt << 1
#define rson rt << 1 | 1
    void pushup(int rt, int l, int r) {
        if (T[rt].crfg) {
            T[rt].len = r - l;
            T[rt].set(1);
            return;
        }
        if (r - l <= 1) { T[rt].set(0); return; }
        T[rt] = T[lson] + T[rson];
    }
    void modify(int rt, int l, int r) {
        if (QR <= l || QL >= r) return;
        if (QL <= l && r <= QR) {
            T[rt].crfg += delta;
            pushup(rt, l, r);
            return;
        }
        int mid = l + r >> 1;
        modify(lson, l, mid);
        modify(rson, mid, r);
        pushup(rt, l, r);
    }
}

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注