BOJ 26559 소떡소떡 2

문제 링크입니다.

재료 자르기

가로로 늘어놓은 재료들을 적당히 잘라서, 꼬치에 재료가 예쁘게 꽂히도록 해 봅시다. 구체적으로 한 꼬치에 꽂힌 재료는 전부 같은 $x$방향 구간을 나타내야 합니다.

재료를 최소한으로 자른다면, 얻을 수 있는 서로 다른 재료의 조합은 $2N$ 가지 정도가 천장이 됩니다. 모든 재료의 끝부분에 맞춰 재료를 끊어주면 되기 때문입니다.

꼬치 밀기

가능한 모든 위치에 꼬치를 꽂아보면서 가장 재료가 많이 꽂히는 경우를 찾는 풀이를 생각해 볼 수 있습니다. 재료의 위치는 1부터 10억까지니, 아무리 많아도 10억 번만 꽂아 보면 문제를 해결할 수 있네요.

전술한 바에 따르면 그중 재료 배치가 서로 다른 꼬치는 해봐야 $2N$ 가지 정도입니다. 그러니 우리는 $2N$번만 꼬치를 꽂아봐도 문제를 해결할 수 있고, 나이브하게 구현하면 $\mathrm{O}(N^2)$짜리 풀이를 얻을 수 있습니다.

여기서 매번 꼬치를 뺐다 꽂는 게 아니라, 꼬치를 꽂은 채로 옆으로 민다고 생각해 봅시다. 그러면 각 재료를 끊어둔 위치에 도달할 때마다 재료가 빠지고 새로운 재료가 들어옵니다. 이때 끊기 전의 재료는 총 $N$개였으니, 각 재료는 1번씩 꼬치에 들어오고 나가는 이벤트를 발생시킵니다.

PS스럽게 표현하면, X좌표를 기준으로 스위핑하면 $2N$번의 재료 변경 업데이트와 쿼리를 처리함으로서 문제를 해결할 수 있다는 의미가 됩니다.

쿼리 풀기

업데이트는 어떤 점에 재료를 추가 또는 삭제, 쿼리는 전체 구간 안에서 만들 수 있는 소떡소떡의 최대 길이를 구하는 문제가 됩니다.

만들어진 두 소떡소떡을 합치는 것은 간단합니다. 서로 마주보고 있는 재료가 같다면 하나를 빼고 합치면 되고, 아니면 그냥 합치면 됩니다.

그렇다면 작은 소떡소떡을 만들어 보고, 이걸 합쳐가면서 최대 길이를 구할 수 있을 겁니다.

일명 금광 세그 내지는 연속합 세그로 알려진, 구간 안의 최대 구간을 관리하는 세그먼트 트리를 하나 만들어서 만들 수 있는 소떡소떡의 최대 길이를 관리해 주면 업데이트를 $\mathcal{O}(\lg N)$에, 쿼리를 $\mathcal{O}(1)$에 처리할 수 있습니다!

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;

struct sdsd{
	ll tot, lmax, rmax; char left, right; bool isone;
};

struct event{
	ll x; ll y; char c; ll l;
	bool operator< (const event& a){
		if(x == a.x) return l < a.l;
		return x < a.x;
	}
};

map<ll, ll> mp;
vector<event> q;
sdsd tree[1010101];

void upd(int now, int l, int r, int i, char c, ll v){
	if(i < l || r < i) return;
	if(l == r){
		tree[now] = {v, v, v, c, c, 1};
		return;
	}
	upd(now<<1, l, mid, i, c, v);
	upd(now<<1|1, mid+1, r, i, c, v);
	if(tree[now<<1].tot == 0){
		tree[now] = tree[now<<1|1]; return;
	}
	if(tree[now<<1|1].tot == 0){
		tree[now] = tree[now<<1]; return;
	}
	tree[now] = {tree[now<<1].tot+tree[now<<1|1].tot, tree[now<<1].lmax, tree[now<<1|1].rmax, tree[now<<1].left, tree[now<<1|1].right, 0};
	if(tree[now<<1].right != tree[now<<1|1].left) return;
	tree[now].tot -= min(tree[now<<1].rmax, tree[now<<1|1].lmax);
	if(tree[now<<1].isone) tree[now].lmax = max(tree[now].lmax, tree[now<<1|1].lmax);
	if(tree[now<<1|1].isone) tree[now].rmax = max(tree[now].rmax, tree[now<<1].rmax);
	if(tree[now<<1].isone && tree[now<<1|1].isone) tree[now].isone = 1;
	return;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n;
	for(int i = 1; i <= n; i++){
		ll xl, xr, y; char c; cin >> xl >> xr >> y >> c;
		q.push_back({xl, y, c, xr-xl+1});
		q.push_back({xr+1, y, '#', 0});
		mp[y] = 1;
	}
	int idx = 1;
	for(auto& [ky, val] : mp) val = idx++;
	sort(q.begin(), q.end());
	ll ans = 0;
	for(auto [x, y, c, l] : q){
		y = mp[y];
		upd(1, 1, idx, y, c, l);
		ans = max(ans, tree[1].tot);
	}
	cout << ans;
}