문제 요약 및 풀이
다른 풀이 보러가기(풀고 나서, 더 생각하니 이 풀이는 너무나 닭 잡는데 소칼을 쓴 격이 되었다. )
오랜만에 세그먼트 트리를 복습하고자 본 문제였지만, 결국 제일 좋아하는 알고리즘이 된(?!) sqrt decomposition을 이용해 풀게 되었다.
sqrt decomposition은 되게 어려워보이지만, 정말 간단한 아이디어로 어려운 상황을 해결할 수 있게 해준다.
먼저 문제를 요약해보자.
1
2
3
4
5
최대 길이가 10만인 수열 A가 주어지고 최대 10만인 M개의 쿼리에 대해서 수행해야 한다.
주어지는 쿼리는 아래 2개다.
1. i번쨰에 있는 숫자를 v로 변경해라.
2. 전체 수열의 최솟값의 인덱스를 출력하라.
한번 모든 쿼리를 나이브하게 처리한다고 생각해보자.
10만개의 숫자 중 최솟값을 최대 10만번 알아내야 하기 때문에, 10만 x 10만으로 100억이 된다. 무조건 시간초과가 뜬다. (질문 목록을 보니 예전에는 나이브하게 풀리는 허점이 있었던 것 같긴 하다. 테케 추가되었으니 안 될듯?)
그럼 여기에 sqrt decomposition 아이디어를 접목해보자.
평방 분할의 큰 아이디어는 여러 값들의 대표값을 sqrt(N)개 만큼 뽑아놓고 그값들을 갱신하고, 활용하자 라고 할 수 있다.
N개의 값이 있고, \(\sqrt N\) 개만큼을 묶어서, \(\sqrt N\) 개 만큼의 대표값을 만든다.
여기서 대표값은 \(\sqrt N\) 개 수의 최소값 및 최소값의 인덱스일 것이다.
한번 쿼리를 처리해보자.
1번 쿼리를 복잡하게 생각할 필요없이 그냥 \(\sqrt N\) 개의 숫자를 순회하면서 대표값을 갱신하면 된다. (단, 해당 대표값은 바꿔야 하는 i번째 숫자가 포함된 구간의 대표값을 말하는것이다.)
2번 쿼리는 정말 간단하게 모든 구간의 대표값을 순회하면서, 최소값과 최소값을 찾으면 된다.
두 쿼리의 시간 복잡도는 \(\sqrt N\) 일 것이고, \(N * \sqrt N\) 는 최대 대략 10만 x 300 정도이고, 3000만은 충분히 1초내에 연산된다.
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define for1(s,n) for(int i = s; i<n; i++)
#define INF (ll)1e11
using namespace std;
typedef long long ll;
ll mo[110000];
ll mo_idx[110000];
ll ar[110000];
ll N, sq, Q, q, a, b;
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> N;
fill(mo, mo+N, INF);
fill(mo_idx, mo_idx+N, -1);
for(sq = 0; sq*sq < N; sq++);
for1(0, N) {
cin >> ar[i];
if(mo[i/sq] > ar[i]) {
mo[i/sq] = ar[i];
mo_idx[i/sq] = i;
}
}
cin >> Q;
while(Q--) {
cin >> q;
if (q == 1) {
cin >> a >> b;
a--;
ar[a] = b;
ll partition = a/sq;
mo[partition] = INF;
mo_idx[partition] = -1;
for1(partition * sq, min((partition + 1) * sq, N)) {
if(mo[i/sq] > ar[i]) {
mo[i/sq] = ar[i];
mo_idx[i/sq] = i;
}
}
} else {
ll mn = INF;
ll ret = -1;
for1(0, sq) {
if(mo[i] < mn && mo_idx[i] != -1) {
mn = mo[i];
ret = mo_idx[i];
}
}
cout << ret + 1 << "\n";
}
}
}