16357번: Circuits - 세그먼트 트리(lazy propagation), 스위핑, 값/좌표 압축

1.

두 개의 수평선을 그었을 때 수평선이 관통하는 직사각형의 수를 구하는 문제이다. 이 문제의 최대 난관은 두 개의 수평선이 같은 직사각형을 지나면 어떻게 할 것인가이다. lazy propagation으로 직사각형의 y좌표의 구간을 1씩 더하는 방법을 써도, 직사각형을 서로 구분할 수 없으므로 문제를 해결할 수 없다.

 

일단 수평선 하나를 임의로 그어놓고, 또 하나의 수평선을 추가로 긋는 작업을 상상해보자. 이미 그어놓은 수평선과 교차하는 직사각형들은, 수평선을 더 그을 때 중복 처리를 해야만 한다. 그렇다면 수평선과 교차하는 직사각형들을 아예 제거하는 것은 어떨까? 수평선과 교차하는 직사각형들을 제거하여, 위에서 설명한 lazy propagation으로 직사각형의 y좌표의 구간을 1씩 더하는 방법을 사용해, 세그먼트 트리의 최댓값을 구하면 문제를 해결할 수 있을 것 같다.

 

2.

위의 방법을 쓰기 위해 수평선 하나를 임의로 긋는 작업을 상상해보자. 범위가 0을 기준으로 좌우로 천만이나 되기 때문에, 수평선을 가능한 모든 정수에 대해 그어 봤다간 시간 초과를 피하기 힘들 것이다. 때문에 값/좌표 압축으로 인덱스 범위를 최소화하자.

하지만 좌표 압축을 한다 해도 수평선을 긋는 범위가 대략 십만이기에, 수평선 2개를 모든 좌표에 대해 그어도 시간 초과가 날 것이다. 때문에 직사각형의 y좌표를 전부 정렬한 후, 스위핑을 적용해 수평선을 하나씩 그어가면서, 나머지 수평선을 그을 때 교차하는 직사각형의 최댓값을 구하면 될 것이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int SIZE = 200001;
int n;
set<int> SET;
vector<int> CC;
vector<tiii> range;
vector<pii> regY[SIZE];
int segTree[SIZE*4], lazy[SIZE*4];

void setLazy(int s, int e, int idx)
{
    int val = lazy[idx];
    lazy[idx] = 0;
    
    segTree[idx] += val;
    if(s != e)
    {
        lazy[idx*2] += val;
        lazy[idx*2+1] += val;
    }
}

void update(int s, int e, int l, int r, int idx, int val)
{
    if(lazy[idx]) setLazy(s, e, idx);
    
    if(e < l || r < s) return;
    if(l <= s && e <= r)
    {
        segTree[idx] += val;
        if(s != e)
        {
            lazy[idx*2] += val;
            lazy[idx*2+1] += val;
        }
        return;
    }
    
    update(s, (s+e)/2, l, r, idx*2, val);
    update((s+e)/2+1, e, l, r, idx*2+1, val);
    segTree[idx] = max(segTree[idx*2], segTree[idx*2+1]);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n;
	for(int i=1; i<=n; i++)
	{
	    int ux, uy, vx, vy; cin >> ux >> uy >> vx >> vy;
	    range.push_back({vy, uy, 0});
	    range.push_back({uy, vy, 1});
	    SET.insert(uy), SET.insert(vy);
	}
	
	sort(range.begin(), range.end());
	for(int y : SET) CC.push_back(y);
	
	for(auto [y1, y2, b] : range)
	{
	    y1 = lower_bound(CC.begin(), CC.end(), y1) - CC.begin() + 1;
	    y2 = lower_bound(CC.begin(), CC.end(), y2) - CC.begin() + 1;
	    regY[y1].push_back({y2, b});
	    if(b == 0) update(1, SIZE, y1, y2, 1, 1); //해당 범위에 직사각형을 겹친다.
	} //좌표 압축
	
	int cross = 0;
	int ans = 0;
	for(int y1=1; y1<SIZE; y1++) //y1 : 수평선을 그을 좌표 - 스위핑
	{
	    for(auto [y2, b] : regY[y1])
	    {
	        if(b == 0)
	        {
	            update(1, SIZE, y1, y2, 1, -1); //해당 범위의 직사각형을 뺀다.
	            cross++;
	        }
	    }
	    ans = max(ans, cross + segTree[1]);
	    
	    for(auto [y2, b] : regY[y1])
	        if(b == 1) cross--;
	}
	cout << ans;
}