[BOJ] 3392. 화성지도

문제

https://www.acmicpc.net/problem/3392

3392번: 화성 지도

 

풀이

단순히 생각하면 30000 * 30000 배열을 만들어 사각형이 입력으로 들어오면 해당 사각형의 영역에 1씩 더해준다.

그 후, 1이상의 값을 가지는 모든 칸의 값을 세주면 된다.

하지만 이와 같은 방법으로는 시간도 많이 소모하고, 공간도 많이 잡는다.

따라서 line sweeping 알고리즘을 사용하여 현재 line과 닿아있는 부분의 30000개 배열만 생각한다.

세로 선을 왼쪽 끝부터 오른쪽 끝까지 sweeping한다고 생각하자.

sweeping하면서 만나는 면적을 모두 더하면 구하고자 하는 정답이 된다.

sweeping 하면서 발생하는 event의 종류가 두 가지인데, 각각에 대해서 처리해 주면 된다.

 

case 1) 새로운 사각형의 등장

이 때는 현재 직사각형의 왼쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 증가시켜준다.

 

case 2) 사각형의 퇴장

이 때는 현재 직사각형의 오른쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 감소시켜준다.

 

위와 같은 과정을 거치면서 현재 line에 있던 1이상의 칸의 수를 모두 더해주면 된다.

하지만 이렇게 되면 $O(nC)$의 시간복잡도로 시간안에 통과할 수 없다.

따라서 전체 구간의 합을 segment tree를 이용하여 관리해주면 된다.

 

이 때, 등장하는 쿼리는 구간에 1을 더해주는 query이므로, lazy propagation의 아이디어를 사용한다.

lazy propagation처럼 게으르게 값을 관리하는데, 현재 구간이 전파될 예정이라면, 하위 노드의 값과 관계 없이 이 구간은 모두 값을 구하는데 사용되게 된다.

root 노드로 부터 내려가다가 처음으로 전파될 예정인 노드를 만나면 바로 그 하위 구간의 길이를 return해주면 되기 때문에, 전파과정은 진행하지 않아도 무방하다.

 

이러한 방법을 이용하여 segment tree를 업데이트 해주면, event마다 log 시간복잡도에 원하는 작업을 완료할 수 있다.

 

Time Complexity : $O(N(logN+logC))$

 

코드

#include<iostream>
#include<algorithm>
#define N 10005
#define C 40000
#define lc(i) ((i)<<1)
#define rc(i) ((i)<<1|1)

using namespace std;

struct ev
{
	int x, y1, y2, z;
	bool operator<(const ev & t)
	{
		return x<t.x;
	}
}evt[N<<1];

ev make_ev(int X, int Y1, int Y2, int Z)
{
	ev r;
	r.x=X;
	r.y1=Y1;
	r.y2=Y2;
	r.z=Z;
	return r;
}
struct segtree
{
	int val;
	int num;
} seg[C<<2];

int n,pr,ans;

void update(int l, int r, int v, int t, int x, int y)
{
	if(y<l || r<x) return;
	if(l<=x && y<=r) seg[t].num+=v;
	else
	{
		int mid=(x+y)>>1;
		update(l,r,v,lc(t),x,mid);
		update(l,r,v,rc(t),mid+1,y);
	}
	if(seg[t].num) seg[t].val=y-x+1;
	else seg[t].val=(x==y?0:seg[lc(t)].val+seg[rc(t)].val);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;

		evt[i]=make_ev(a,b,d-1,1);
		evt[i+n]=make_ev(c,b,d-1,-1);
	}
	sort(evt,evt+2*n);
	for(int i=0;i<2*n;i++)
	{
		if(i>0) ans+=(evt[i].x-pr)*seg[1].val;
		update(evt[i].y1, evt[i].y2, evt[i].z,1,0,C);
		pr=evt[i].x;
	}
	cout<<ans;
}