BOJ 30512 조용히 완전히 영원히

문제 링크입니다.

업데이트 처리하기

구간 안의 모든 원소 $A_i$에 $\min (A_i, x)$를 적용합니다. 느리게 갱신되는 세그먼트 트리를 이용해 처리할 수 있습니다. 세그먼트 트리의 각 노드에 현재 해당 구간에 min 연산을 넣어주어야 하는 값을 저장하는 방식을 이용합니다. 실제로 min 연산을 할 필요가 없다면 적당히 큰 값을 넣어주는 것으로 표현 가능합니다.

기억하기

어떤 구간의 값이 실제로 변경될 때마다, 그 구간의 마지막으로 변경된 시점을 업데이트해 줍니다. 모든 업데이트가 끝난 뒤에, 각 원소에 중간에 걸려 있는 업데이트들을 전파하고 마지막으로 변경된 시점을 가져오기 위해, 적당히 큰 값으로 각 단일 원소마다 업데이트를 쏴 줍시다.

이렇게 총 시간복잡도 $\mathcal{O} ((N+Q) \log N)$ 에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
int seg[400000], A[123456], u[500000], T[123456], ans[123456];
void upd(int now, int l, int r, int L, int R, int k, int t){
	if(R < l || r < L) return;
	if(L <= l && r <= R){
		if(seg[now] > k){
			seg[now] = k;
			u[now] = max(u[now], t);
		}
		A[L] = seg[now];
		T[L] = u[now];
		return;
	}
	if(seg[now<<1] > seg[now]){
		seg[now<<1] = seg[now];
		u[now<<1] = max(u[now<<1], u[now]);
	}
	if(seg[now<<1|1] > seg[now]){
		seg[now<<1|1] = seg[now];
		u[now<<1|1] = max(u[now<<1|1], u[now]);
	}
	seg[now] = 1234567;
	u[now] = 0;
	upd(now<<1, l, mid, L, R, k, t);
	upd(now<<1|1, mid+1, r, L, R, k, t);
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n; cin >> n;
	fill(seg, seg+n*4, 1234567);
	for(int i = 1; i <= n; i++){
		cin >> A[i];
		upd(1, 1, n, i, i, A[i], 0);
	}
	int q; cin >> q; for(int t = 1; t <= q; t++){
		int l, r, k; cin >> l >> r >> k;
		upd(1, 1, n, l, r, k, t);
	}
	for(int i = 1; i <= n; i++){
		upd(1, 1, n, i, i, 1234567, 0);
		cout << A[i] << ' ';
		ans[T[i]]++;
	}
	cout << '\n';
	for(int i = 1; i <= q; i++){
		ans[i] += ans[i-1];
		cout << ans[i] << ' ';
	}
}