前言或声明

本部分不超过总内容

20\%

。

本题解的参考代码不仅可以通过本题，在经过极度细微的修改之后还可以通过 P5490。
本题解参考代码可能有部分累赘内容，与 P5490 有关，在这里请大家谅解。
本题解假定大家已经对扫描线有一定的了解。如果你还不知道扫描线是什么，我贴心的提供了学习链接。
本题居然还可以写题解？？？

分析与思考

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

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

-1

，下方横向边的标记值是

1

。

之后维护一个初始全部为

0

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

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

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

提示与实现

如何维护刚刚提到的序列？我提供一种比较奇怪的方式。我们可以用特殊的方式实现一个权值线段树，可以保证即能够维护边的正常标记和取消标记，也能够

O(1)

求出标记的总长度（注意，这里重合部分只计算一次）。这种方式比较玄妙，大家可以看看代码，自己领会。

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

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

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

CPP

#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;
}

题解：P3079 [USACO13MAR] Farm Painting S

文章操作

前言或声明

分析与思考

提示与实现

相关推荐

评论

题解：P3079 [USACO13MAR] Farm Painting S