BOJ 32033 민들레

문제 링크입니다.

관찰

각 쿼리를 나이브하게 처리한다고 하면, L, R 쿼리가 들어올 때마다 모든 민들레를 순회해야 하기 때문에 시간이 너무 오래 걸립니다.

L 쿼리가 들어왔을 때 자기 왼쪽에 다른 민들레가 있다면 그 민들레는 넘어가도 좋습니다. 이 점에서 착안해, 서로 인접한 민들레들을 하나의 무리로 관리합니다. 그러면 L, R 쿼리가 들어올 때마다 각 민들레 무리의 옆 칸에만 민들레가 새로 심깁니다. 이를 각 민들레 무리가 한쪽으로 팽창한다고 생각해 볼 수 있습니다.

L, R 쿼리가 들어올 때마다 민들레의 총 개수는 그때의 민들레 무리 수만큼 증가함을 알 수 있습니다.

민들레 무리 관리하기

새로운 민들레 무리는 오로지 C x에 의해서만 생길 수 있습니다. 바람은 이미 존재하는 민들레 무리를 팽창시키기만 하니까요.

그래서 일단 쿼리를 전부 입력받고, C x로 주어지는 각 화분의 위치를 이용해 민들레 무리를 표현할 수 있습니다.

L, R 쿼리 처리하기

바람이 불 때마다 모든 민들레 무리를 순회하면서 양 끝 위치를 업데이트하는 것은 비효율적입니다. 대신 중심 화분에서부터 양 끝까지의 거리를, 현재 각 방향으로 바람이 분 총 횟수 - 민들레 무리가 처음 생겼을 때의 각 방향으로 바람이 분 횟수로 표현할 수 있습니다. 현재 각 방향으로 바람이 분 총 횟수는 모든 민들레 무리가 공유하는 값이고, 민들레 무리가 처음 생겼을 때의 각 방향으로 바람이 분 횟수는 L, R 쿼리가 들어온다고 해서 변하는 값이 아닙니다. 바람 분 횟수를 세기만 하면 L, R 쿼리를 O(1)에 처리할 수 있겠네요.

C x 쿼리 처리하기

민들레 무리들의 위치를 중심 화분 기준으로 정렬된 채로 관리합시다. std::set과 같은 자료 구조로 쉽게 할 수 있습니다.

어떤 민들레를 새로 심으면, 그 민들레 양 옆의 무리를 이분 탐색으로 $\mathcal{O}(\log Q)$에 찾을 수 있습니다. 이미 어떤 민들레 무리에 포함되어 있다면 무시하고, 아니면 새로운 민들레 무리를 만들어 줍시다.

민들레 무리 합치기

쿼리를 처리하는 도중에 두 민들레 무리가 서로 붙는 경우가 최대 $\mathcal{O}(Q)$번 생길 수 있습니다. 어느 방향으로 바람이 불든 두 민들레 무리 사이의 간격은 1 줄어듭니다. 이 점을 이용해, 처음부터 총 몇 번 바람이 불었어야 두 민들레가 서로 붙는 지를 하나의 값으로 관리해 줍시다. 이 값 역시 C x 쿼리가 들어오지 않는 한은 바뀌지 않습니다.

이 값을 기준으로 우선순위 큐 등의 자료 구조를 활용해 민들레 무리들 사이의 간격을 가까운 것부터 관리해 줍니다. 각 쿼리를 처리한 후에, 이 우선순위 큐를 확인하면서 두 민들레 무리가 붙어있는 지 확인하고 합쳐 줍니다.

민들레 무리를 합치는 것은 분리 집합 등의 자료 구조를 이용하면 쉽게 처리할 수 있습니다. 이때, 민들레 무리를 합친 뒤 민들레 무리가 처음 생겼을 때의 각 방향으로 바람이 분 횟수를 잘 업데이트해 주어야 합니다.

이상의 내용을 구현하면 총 시간 복잡도 $\mathcal{O}(Q \log Q)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using query = pair<char, int>;

struct dandelion{
	int mid;
	int loffset;
	int roffset;
	int par;
};

vector<query> queries;
vector<dandelion> d;
set<int> hwadan;
priority_queue<pair<int, pair<int, int>>> dist;
map<int, int> comp;
int l = 0, r = 0;
ll ans = 1;

int f(int x){
	return d[x].par < 0 ? x : d[x].par = f(d[x].par);
}

void u(int x, int y){
	x = f(x); y = f(y);
	if(x == y) return;
	if(x > y) swap(x, y);
	d[y].par = x;
	int leftmost = min(d[x].mid+d[x].loffset, d[y].mid+d[y].loffset)+l;
	int rightmost = max(d[x].mid+d[x].roffset, d[y].mid+d[y].roffset)+r;
	d[x].loffset = leftmost-d[x].mid-l;
	d[x].roffset = rightmost-d[x].mid-r;
	hwadan.erase(y);
	return;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int N; cin >> N; comp[0] = 1;
	while(N--){
		char c; int x = 0; cin >> c;
		if(c == 'C'){
			cin >> x;
			comp[x] = 1;
		}
		queries.push_back({c, x});
	}
	int idx = 0;
	for(auto& [x, t] : comp){
		d.push_back({x,0,0,-1});
		t = idx++;
	}
	hwadan.insert(comp[0]);
	
	for(auto [c, x] : queries){
		if(c == 'Q'){
			cout << ans << '\n';
			continue;
		}
		else if(c == 'C'){
			x = comp[x];
			int lmid = -1, rmid = -1;
			if(*(hwadan.begin()) <= x){
				lmid = *(--hwadan.lower_bound(x+1));
				if(d[lmid].mid+d[lmid].roffset+r >= d[x].mid) continue;
			}
			if(*(hwadan.rbegin()) >= x){
				rmid = *(hwadan.lower_bound(x));
				if(d[rmid].mid+d[rmid].loffset+l <= d[x].mid) continue;
			}
			ans++;
			d[x].loffset = -l;
			d[x].roffset = -r;
			hwadan.insert(x);
			if(lmid >= 0) dist.push({-(d[x].mid+d[x].loffset-d[lmid].mid-d[lmid].roffset-1),{lmid, x}});
			if(rmid >= 0) dist.push({-(d[rmid].mid+d[rmid].loffset-d[x].mid-d[x].roffset-1),{x, rmid}});
		}
		else{
			if(c == 'L') l--;
			if(c == 'R') r++;
			ans += hwadan.size();
		}
		while(dist.size()){
			int D = -dist.top().first;
			int lidx = f(dist.top().second.first);
			int ridx = f(dist.top().second.second);
			if(lidx == ridx){dist.pop(); continue;}
			if(r-l < D) break;
			dist.pop();
			u(lidx, ridx);
		}
	}
}