BOJ 20874 Guitar Hero

문제 링크입니다.

문제 요약

연주해야 하는 음들을 $M$ 이하의 양의 정수로 표현해야 합니다. 각 음에 수를 매길 때는 이 문제에서와 같은 조건을 지켜야 합니다.

• 직전에 연주한 음이 현재 연주할 음보다 낮으면 직전에 쓴 수보다 큰 수를 씁니다.
• 직전에 연주한 음이 현재 연주할 음보다 높으면 직전에 쓴 수보다 작은 수를 씁니다.
• 직전에 연주한 음과 현재 연주할 음이 같으면 직전에 쓴 수를 씁니다.

구간 [L, R]이 주어질 때마다, 그 구간 안의 수들을 규칙에 맞게 수로 표현할 수 있는지 판별해야 합니다.

쿼리 하나 처리하기

구간 [1, N]이 주어졌을 때 답을 구하는 방법을 생각해 봅시다.

음의 추세에 집중합시다. 전체 구간을 올라가고 내려가는 조각들로 분해해서 생각하면, 각각의 조각 안에서는 쓸 수 있는 음이 계속 증가하거나 감소합니다. 그러면 각각의 조각 안에서 최대 $M$종류의 음만이 표현 가능하고, 그를 넘어가면 표현이 불가능해집니다.

조각이라고 표현하긴 했지만, 방향이 꺾이는 음은 양 조각에 모두 포함되어야 합니다. 그러니까 전체 구간 안에 연속한 증가하지 않는/감소하지 않는 부분 수열의 최대 길이가 각각 $M$ 이하여야 한다는 의미가 됩니다.

전처리하기

이를 거꾸로 생각하면, 표현이 불가능한 경사를 찾아둔 뒤에 경사들 중 하나라도 구간 안에 포함되는 것이 있으면 그 구간이 표현 불가능하다는 뜻이 됩니다.

경사를 모두 찾는 것은 투 포인터를 활용하면 어렵지 않게 할 수 있습니다.

• 오른쪽 원소를 현재 조각에 추가합니다.
• 현재 조각의 추세와 반대 방향으로 음이 꺾였다면, 마지막 두 음만 남기고 전부 버립니다.
• 음의 종류가 $M$을 초과하는 경사가 완성되었다면, 그 조각을 저장해 둡니다.
  • 맨 앞에 겹치는 음이 여러 개라면, 그중 맨 오른쪽 음을 기준으로 경사를 잡습니다.
  • 그 뒤 음의 종류가 $M$종류가 될 때까지 조각의 맨 왼쪽 음을 제거합니다.

쿼리 빠르게 처리하기

모든 경사 [l, r]들을 찾았다고 해 봅시다. 그러고서 쿼리로 구간 [L, R]이 주어졌을 때 답을 판별하는 방법을 생각해봅시다.

경사 [l, r]이 구간 [L, R]에 포함되려면 $L \le l \le r \le R$이어야 합니다. 일단 l이 [L, R]에 포함되어 있어야 합니다. l ≤ r은 이미 확정되어 있으니 그중에서 r ≤ R인 게 하나라도 있는지만 판별하면 됩니다.

arr[l]에 r을 넣어주면 이 작업을 구간 [L, R]에서의 최솟값을 찾는 것과 같이 생각할 수 있습니다. 여기까지만 생각해도 세그먼트 트리를 이용해 구간 최솟값을 찾아 문제를 해결할 수 있습니다. 어떤 경사가 다른 경사보다 l이 크면 r도 크다는 점을 이용하면 모든 L에 대한 R 값을 전처리해 더 빠르게 해결할 수도 있습니다.

코드

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

int a[123456];
int tree[404040];

void upd(int now, int l, int r, int i, int v){
	if(l > i || i > r) return;
	if(l == r){
		tree[now] = v; return;
	}
	int mid = l+r>>1;
	upd(now<<1, l, mid, i, v); upd(now<<1|1, mid+1, r, i, v);
	tree[now] = min(tree[now<<1], tree[now<<1|1]);
}

int qry(int now, int l, int r, int L, int R){
	if(r < L || R < l) return 101010101;
	if(L <= l && r <= R) return tree[now];
	int mid = l+r>>1;
	return min(qry(now<<1, l, mid, L, R), qry(now<<1|1, mid+1, r, L, R));
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	memset(tree, 0x3F, sizeof(tree));
	int n, m, q; cin >> n >> m >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	int L = 1, inc = 1, dec = 1;
	for(int R = 2; R <= n; R++){
		if(a[R] == a[R-1]) continue;
		else if(a[R] > a[R-1]){
			if(dec > 1) L = R-1;
			dec = 1; inc++;
			if(inc > m){
				while(a[L] == a[L+1]) L++;
				upd(1, 1, n, L, R);
				L++;
				inc--;
			}
		}
		else{
			if(inc > 1) L = R-1;
			inc = 1; dec++;
			if(dec > m){
				while(a[L] == a[L+1]) L++;
				upd(1, 1, n, L, R);
				L++;
				dec--;
			}
		}
	}
	
	while(q--){
		int L, R; cin >> L >> R;
		if(qry(1, 1, n, L, R) <= R) cout << "nej\n";
		else cout << "ja\n";
	}
}