第13回日本情報オリンピック 本選 E - 切り取り線 （Cutting） 题解
题目链接：E - 切り取り線 （Cutting）
题目大意：给定 \(w\times h\) 的矩形内的 \(n\) 条线段，保证每条线段平行于矩形边界，问这些线段将这个矩形分成了多少个联通块。
\(n\leq 10^5,w,h\leq 10^9\)
Subtask 1: \(n\leq 1000\) (10 points)
Subtask 2: 交点个数不超过 \(10^5\) 个。(20 points)
Subtask 3: 所有的边都可以和边界直接或间接地联通。(20 points)
题解：先丢一道弱化版，然而这一道题的解题方法和刚才那道题没有太大关系。
这边先丢官方题解，如果您有疑问的话可以在官方题解中寻找解答。
首先肯定要离散化，这没有问题。
我们可以先考虑一个十分暴力的做法，我们将矩形化成 \(1\times 1\) 的小方格，然后再找联通块。紧接着我们可以发现这之中的不少格子都是可以合并的，最后合并后剩下的个数就是联通块数。
如果暴力全部拆开来的话我们会得到一个非常暴力的 \(O(n^2)\) 的做法，你可以取得 日本选拔赛最高分 \(10\) 分的好成绩。
发现边界非常麻烦，我们把边界拆成四条线段来做。
如果一些线段并没有相交，我们可以将它们分开来计算，这样对于答案是没有影响的。
至于这个东西怎么处理我们可以用并查集，但是并查集比较难求线段交，所以我们可以用线段树来实现。
然后画图找规律可以发现，整张图的联通块个数就可以表示成交点个数加上联通块个数减去线段个数。
接下来唯一麻烦的就是如何求交点，这个可以直接扫描线轻松地解决。
时间复杂度 \(O(n\log n)\)。
代码：
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int Maxn=200004;
int n,w,h;
namespace DSU{
int fa[Maxn+5];
int find(int x){
if(x==fa[x]){
return x;
}
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
int fa_x=find(x),fa_y=find(y);
if(fa_x==fa_y){
return;
}
fa[fa_y]=fa_x;
}
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
}
}
}
int len;
namespace Segment_Tree{
struct Segment_Node{
int sum,lazy;
}seg[Maxn<<2|5];
void push_down(int root){
if(seg[root].lazy==0){
return;
}
if(seg[root<<1].lazy){
DSU::merge(seg[root<<1].lazy,seg[root].lazy);
}
if(seg[root<<1|1].lazy){
DSU::merge(seg[root<<1|1].lazy,seg[root].lazy);
}
if(seg[root<<1].sum){
seg[root<<1].lazy=seg[root].lazy;
}
if(seg[root<<1|1].sum){
seg[root<<1|1].lazy=seg[root].lazy;
}
seg[root].lazy=0;
}
void update_1(int x,int a,int root=1,int left=1,int right=len){
if(left==right){
seg[root].sum+=a;
return;
}
int mid=(left+right)>>1;
if(x<=mid){
update_1(x,a,root<<1,left,mid);
}
else{
update_1(x,a,root<<1|1,mid+1,right);
}
seg[root].sum=seg[root<<1].sum+seg[root<<1|1].sum;
}
void update_2(int x,int c,int root=1,int left=1,int right=len){
if(left==right){
seg[root].lazy=c;
return;
}
push_down(root);
int mid=(left+right)>>1;
if(x<=mid){
update_2(x,c,root<<1,left,mid);
}
else{
update_2(x,c,root<<1|1,mid+1,right);
}
}
void update_3(int l,int r,int c,int root=1,int left=1,int right=len){
if(seg[root].sum==0){
return;
}
if(l>right||r=right){
if(seg[root].lazy){
DSU::merge(seg[root].lazy,c);
}
seg[root].lazy=c;
return;
}
push_down(root);
int mid=(left+right)>>1;
update_3(l,r,c,root<<1,left,mid);
update_3(l,r,c,root<<1|1,mid+1,right);
}
int query(int l,int r,int root=1,int left=1,int right=len){
if(l>right||r=right){
return seg[root].sum;
}
int mid=(left+right)>>1;
return query(l,r,root<<1,left,mid)+query(l,r,root<<1|1,mid+1,right);
}
}
vector row,col;
vector,pair > > line;
vector,pair > > lis[Maxn+5];
int main(){
scanf("%d%d%d",&w,&h,&n);
row.push_back(0);
row.push_back(w);
col.push_back(0);
col.push_back(h);
line.push_back(make_pair(make_pair(0,0),make_pair(w,0)));
line.push_back(make_pair(make_pair(0,0),make_pair(0,h)));
line.push_back(make_pair(make_pair(w,0),make_pair(w,h)));
line.push_back(make_pair(make_pair(0,h),make_pair(w,h)));
for(int i=1;i<=n;i++){
int x_1,y_1,x_2,y_2;
scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
row.push_back(x_1);
col.push_back(y_1);
row.push_back(x_2);
col.push_back(y_2);
line.push_back(make_pair(make_pair(x_1,y_1),make_pair(x_2,y_2)));
}
n+=4;
sort(row.begin(),row.end());
sort(col.begin(),col.end());
row.erase(unique(row.begin(),row.end()),row.end());
col.erase(unique(col.begin(),col.end()),col.end());
len=row.size();
for(int i=0;i,pair > >());
}
ll ans=0;
for(int i=1;i<=(int)col.size();i++){
for(int j=0;j<(int)lis[i].size();j++){
int op=lis[i][j].first.first,x=lis[i][j].first.second;
int l=lis[i][j].second.first,r=lis[i][j].second.second;
if(op==1){
Segment_Tree::update_2(l,x);
Segment_Tree::update_1(l,1);
}
if(op==0){
Segment_Tree::update_3(l,r,x);
ans+=Segment_Tree::query(l,r);
}
if(op==-1){
Segment_Tree::update_2(l,0);
Segment_Tree::update_1(l,-1);
}
}
}
for(int i=1;i<=n;i++){
if(i==DSU::find(i)){
ans++;
}
}
ans-=n;
printf("%lld\n",ans);
return 0;
}