[BOJ 13982] Shopping

13982번: Shopping

2000번째 문제로 뭘 풀까 고민하다가 IBory님께 추천을 받았다. 깔끔하고 재밌는 문제였다.

 

풀이

 

쉽게 할 수 있는 관찰은 현재 가지고 있는 돈보다 가격이 높은 구간은 모두 통과할 수 있다는 것이다.

현재 가지고 있는 돈이 바뀌는 부분에 주목해보자.

$v$ $\%$ $a_i = w$ 에서 $w$ 는 $\frac{v}{2}$ 보다 작거나 같다. 이는 $a_i$ 의 범위에 따라 케이스 분류를 해봄으로써 보일 수 있다.

따라서 돈은 최대 $O(logN)$ 번 바뀔 수 있고, 돈이 바뀌는 모든 지점을 빠르게 찾아 직접 계산해주는 것으로 문제가 해결된다.

그리고, 이는 희소 배열을 가지고 Binary Lifting을 시행하는 것으로 충분하다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 2;
int nxt[N][18]; ll a[N], mn[N][18];
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n, q; cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		nxt[i][0] = i + 1, mn[i - 1][0] = a[i];
	}
	nxt[n + 1][0] = n + 1, mn[n][0] = mn[n + 1][0] = 2e18;
	for(int j = 1; j < 18; j++) for(int i = 1; i <= n; i++) {
		nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
		mn[i][j] = min(mn[i][j - 1], mn[nxt[i][j - 1]][j - 1]);
	}
	while(q--) {
		ll v; int l, r; cin >> v >> l >> r;
		v %= a[l];
		while(l < r) {
			for(int i = 17; i >= 0; i--) if(mn[l][i] > v) l = nxt[l][i];
			if(l < r) v %= a[++l]; 
		}
		cout << v << '\n';
	}
}