自动搬运

查看原文

来自洛谷，原作者为

	Time_tears oi复健ing

搬运于2025-08-24 21:59:57，当前版本为作者最后更新于2020-11-13 21:30:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看完了原题后，有用的信息有如下这些：

1. 矩形之间只会有包含或相离的关系（这点非常重要，是解题的关键步骤）

2. 由 1 可得矩形间会构成森林

3. 对于每个点，若它在某个矩形内，则在它的父亲内

于是原题可以分为两部分：

part 1. 处理矩形的父子关系以及包含每个点的最小矩形

part 2. 父亲继承儿子的信息

首先，第 2 步非常好处理，我们只需要用 set + 启发式合并就可以做到 $O(n \log n)$ 的复杂度了。

第 1 步比较麻烦，但其实有非常类似的题目：牛客网的 “圆与圆之间的距离是不能一概而论的”

在这里有 2 种做法，我用的是比较傻的 set ，我们先对 $x$ 轴扫描线，那么每个矩形会变成上线段和下线段，对于一个矩形，若它的上线段的上方的第一个线段是上线段，那么他就被这个矩形所包含，否则就被它的父亲所包含。

然后对于点也是同理，只不过要注意下边界，就可以用 set 维护，另一种算法是线段树，这里就不赘述了。

还有一件事，注意 set 的排序顺序，要先加再查最后删

luogurank1代码

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,m,cnt,rt,fa[N];
int h[N],ans[N];
vector<set<int> >st;
struct node {
	int to,next;
} e[N<<1];
struct Line {
	int l,opt,id;
	Line(int L=0,int O=0,int Id=0) {
		l=L,opt=O,id=Id;
	}
	bool operator <(Line a) const {
		return l==a.l?opt>a.opt:l<a.l;
	}
};
set<Line>line;
struct Pair {
	int l,r,x,opt,id;
	bool operator <(Pair a) const {
		return x==a.x?opt<a.opt:x<a.x;
	}
} p[N],q[N];
const int Mxdt=100000;
inline char gc() {
	static char buf[Mxdt],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline char pc(char ch,bool bj) {
	static char buf[Mxdt],*p1=buf,*p2=buf+Mxdt;
	return (bj||(*p1++=ch)&&p1==p2)&&fwrite(p1=buf,1,p1-buf,stdout),0;
}
inline int read() {
	int res=0;
	char ch=gc();
	while(ch<'0')ch=gc();
	while(ch>='0')res=(res<<3)+(res<<1)+(ch^48),ch=gc();
	return res;
}
void print(int x) {
	if(x>9)print(x/10);
	pc(x%10^48,false);
}
inline void printnum(int x,char ch) {
	if(x<0)pc('-',false),x=-x;
	print(x),pc(ch,false);
}
void Addedge(int x,int y) {
	e[++cnt]=(node) {y,h[x]},h[x]=cnt;
}
set<Line>::iterator it;
void Merge(int x,int y) {
	if(st[x].size()<st[y].size())swap(st[x],st[y]);
	for(int a:st[y])st[x].insert(a);
	st[y].clear();
}
void Dfs(int x) {
	for(int i=h[x]; i; i=e[i].next)Dfs(e[i].to),Merge(x,e[i].to);
	ans[x]=st[x].size();
}
int main() {
	n=read(),m=read();st.resize(n+1);
	for(int i=1,a,b,c,d; i<=n; ++i) {
		a=read(),b=read(),c=read(),d=read();
		p[++cnt].id=i,p[cnt].opt=1,p[cnt].l=b,p[cnt].r=d,p[cnt].x=a;
		p[++cnt].id=i,p[cnt].opt=2,p[cnt].l=b,p[cnt].r=d,p[cnt].x=c;
	}
	for(int i=1; i<=m; ++i)q[i].x=read(),q[i].l=read(),q[i].r=read();
	sort(p+1,p+cnt+1),sort(q+1,q+m+1);
	for(int i=1,j=1; i<=m; ++i) {
		while(j<=cnt&&(q[i].x>p[j].x||(q[i].x==p[j].x&&p[j].opt==1))) {
			if(p[j].opt==1) {
				if((it=line.lower_bound(Line(p[j].l)))!=line.end())
					fa[p[j].id]=((*it).opt==2)?(*it).id:fa[(*it).id];
				line.insert(Line(p[j].l-1,1,p[j].id)),line.insert(Line(p[j].r,2,p[j].id));
			} else line.erase(Line(p[j].l-1,1,p[j].id)),line.erase(Line(p[j].r,2,p[j].id));
			++j;
		}
		if((it=line.lower_bound(Line(q[i].l,3)))!=line.end()) {
			if((*it).opt==2)st[(*it).id].insert(q[i].r);
			else st[fa[(*it).id]].insert(q[i].r);
		}
	}
	cnt=0;
	for(int i=1; i<=n; ++i)if(fa[i])Addedge(fa[i],i);
	for(int i=1; i<=n; ++i)if(!fa[i])Dfs(i);
	for(int i=1; i<=n; ++i)printnum(ans[i],'\n');
	return pc('0',1);
}