题解：P3079 [USACO13MAR] Farm Painting S

· · 题解

前言或声明

本部分不超过总内容 20\%。

分析与思考

本题使用扫描线。怎么想到？我们以后做这种类型题的时候，如果敏锐地注意到题目中有关“矩形”的交错、包含、链接，那大概率就是扫描线或者可以用扫描线解决。

考虑先把所有矩形的所有横向边存起来，每条边存左端点横坐标、右端点横坐标、纵坐标与一个“标记值”。这里标记值干什么的后面会解释，只需要知道对于每个矩形，它上方横向边的标记值是 -1，下方横向边的标记值是 1。

之后维护一个初始全部为 0 的序列（可以理解为平行于 X 坐标轴的一个线形结构），用一个朴素的扫描线从下往上扫。每碰到一条矩形下方的横向边，把这个边对应在序列上的区间标记。每碰到一条矩形上方的横向边，就把这个边对应在序列上的区间取消标记（因为这个区间之前一定被一条下侧边标记过）。如何实现这个功能？这就是刚刚的标记值的用处。我们用一些方法把标记值累加到序列即可。

之后，我们发现，每碰到一条下侧横向边，就把它压到那个序列里。看看整个序列被标记的总长度有没有增加。如果增加了，就说明这个边的矩形没有被其他矩形包含。

想到了之后，我们就可以开始尝试实现了。

提示与实现

如何维护刚刚提到的序列？我提供一种比较奇怪的方式。我们可以用特殊的方式实现一个权值线段树，可以保证即能够维护边的正常标记和取消标记，也能够 O(1) 求出标记的总长度（注意，这里重合部分只计算一次）。这种方式比较玄妙，大家可以看看代码，自己领会。

注意到坐标范围可能很大，所以我们把坐标进行离散化之后再进行标记边等处理。

这里需要打 LazyTag。作者很蒟，代码中的 LazyTag 不是很正规，大家略微看看就好，希望能够谅解。

代码请有需要的同学自行取用，切勿抄题解！这可能导致又一位作弊者的产生。

#include <iostream>
#include <algorithm>
using namespace std;

#define lson(x) (x) << 1
#define rson(x) (x) << 1 | 1

long long n;
long long X1, Y1, X2, Y2;

long long ans=0;
long long top1=0;
long long top2=0;

long long tre[3000005];
long long dts[3000005];

long long tag[3000005];

struct line {
    long long l, r, h, v;

    bool operator<(const line &oth) const {
        return h < oth.h;
    }
} lne[300005];

void push_up(long long rt, long long nl, long long nr) {
    if (tag[rt] > 0) {
        tre[rt] = dts[nr+1]-dts[nl];
    } else {
        tre[rt] = tre[lson(rt)]+tre[rson(rt)];
    }
}

void update(long long rt, long long nl, long long nr, long long l, long long r, long long fla) {
    if (nr + 1 <= l || nl >= r) {
        return;
    }
    if (l <= nl && nr + 1 <= r) {
        tag[rt] += fla;
        push_up(rt, nl, nr);
        return;
    }

    long long mid = (nl + nr) >>1;

    if (l <= mid) {
        update(lson(rt), nl, mid, l, r, fla);
    }
    if (r > mid) {
        update(rson(rt), mid+1, nr, l, r, fla);
    }

    push_up(rt, nl, nr);
}

int main() {
    cin >> n;

    for (long long i = 1; i <= n; i++) {
        cin >> X1 >> Y1 >> X2 >> Y2;

        lne[++top1] = (line){X1, X2, Y1, 1};
        dts[top1] = X1;
        lne[++top1] = (line){X1, X2, Y2, -1};
        dts[top1] = X2;
    }

    sort(lne+1, lne+top1+1);
    sort(dts+1, dts+top1+1);

    long long top2 = unique(dts+1, dts+top1+1)-dts-1;

    for (long long i = 1; i < top1; i++) {
        long long L = lower_bound(dts+1, dts+top2+1, lne[i].l)-dts;
        long long R = lower_bound(dts+1, dts+top2+1, lne[i].r)-dts;

        long long tmp = tre[1];
        update(1, 0, top2-1, L, R, lne[i].v);

        if (tre[1] > tmp) {
            ans++;
        }
    }

    cout << ans;
    return 0;
}