[백준 19651] 수열과 쿼리 39

작성일 | In |

문제 링크

https://www.acmicpc.net/problem/19651

풀이

$[l, r]$ 사이의 수열이 등차수열이기 위해서는 $i \in [l,r-1]$ 인 $i$에 대해 $A_{i+1}-A_i$ 가 모두 같아야 합니다. 그렇다면 $A_i$를 관리하는 대신 $A_{i+1}-A_i$를 관리하고 이 값으로 2번 쿼리 $[i,j]$에서 값이 모두 동일한 가장 긴 연속 부분 수열의 길이를 빠르게 구하는 방법을 찾아야 합니다.

구간에서 값이 모두 동일한 가장 긴 연속 부분 수열의 길이는 금광 세그라고 불리는 테크닉을 이용해 $O(logN) $만에 구할 수 있습니다.

$A_{i+1}-A_i$를 세그먼트 트리로 관리하기로 했기 때문에 1번 쿼리로 변화하는 값들을 세그먼트 트리에서 업데이트하는 방법을 찾아야 합니다. 1번 쿼리 $[i, j]$가 주어졌을 때 $A_i - A_{i-1}$은 $x$만큼 증가하고 $A_{j+1}-A_j$는 $x + y ⋅ (j-i)$만큼 감소하고 $k \in [i,j-1]$ 인 k에 대해 $A_{k+1}-A_k$는 $y$만큼 증가합니다. 3개의 구간에 각각 동일한 값을 더 해주므로 이 값들을 lazy propagation으로 전파해 줄 수 있습니다. lazy propagation을 이용한 업데이트는 $O(\log N)$을 보장해 주기 때문에 1번 쿼리, 2번 쿼리 모두 $O(\log N)$만에 구할 수 있으므로 전체 시간복잡도는 $O(Q \log N)$입니다.

전체 코드

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l + r) >> 1)
#define MAXN 100000

struct Node{
	ll l, r, lm, rm, sz, lazy, mx;
}t[4 * MAXN + 10];

int n, q;
ll a[MAXN + 10], b[MAXN + 10];

Node merge(Node L, Node R){
	if(L.sz == 0) return R;
	if(R.sz == 0) return L;

	Node re = {L.l, R.r, L.lm, R.rm, L.sz + R.sz, 0, max(L.mx, R.mx)};
	if(L.r == R.l){
		re.mx = max(re.mx, L.rm + R.lm);
		if(L.lm == L.sz) re.lm += R.lm;
		if(R.rm == R.sz) re.rm += L.rm;
	}
	re.mx = max({re.mx, re.lm, re.rm});
	return re;
}

Node build(int node = 1, int l = 1, int r = n-1){
	if(l == r) return t[node] = {b[l], b[l], 1, 1, 1, 0, 1};
	return t[node] = merge(build(node*2, l, mid), build(node*2+1, mid+1, r));
}

void lazy_update(int node, int l, int r){
	if(t[node].lazy){
		t[node].l += t[node].lazy, t[node].r += t[node].lazy;
		if(l != r) t[node*2].lazy += t[node].lazy, t[node*2+1].lazy += t[node].lazy;
		t[node].lazy = 0;
	}
}

void update(int nl, int nr, int x, int node = 1, int l = 1, int r = n-1){
	lazy_update(node, l, r);
	if(nr < l || r < nl) return;
	if(nl <= l && r <= nr){
		t[node].lazy += x;
		lazy_update(node, l, r);
		return;
	}
	update(nl, nr, x, node*2, l, mid), update(nl, nr, x, node*2+1, mid+1, r);
	t[node] = merge(t[node*2], t[node*2+1]);
}

Node find(int nl, int nr, int node = 1, int l = 1, int r = n-1){
	lazy_update(node, l, r);
    if(nr < l || r < nl || nl > nr) return {0, 0, 0, 0, 0, 0, 0};
    if(nl <= l && r <= nr) return t[node];
	return merge(find(nl, nr, node*2, l, mid), find(nl, nr, node*2+1, mid+1, r));
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<n;i++) b[i] = a[i+1] - a[i];
	build();
	cin >> q;
	while(q--){
		int t; cin >> t;
		if(t == 1){
			int l, r; ll A, B; cin >> l >> r >> A >> B;
			if(1 < l) update(l-1, l-1, A);
			if(r < n) update(r, r, -(A + B * (r-l)));
			if(l < r) update(l, r-1, B);
		}
		if(t == 2){
			int l, r; cin >> l >> r;
			cout << find(l, r-1).mx + 1 << "\n";
		}
	}
}

여담

의외로 수열과 쿼리 시리즈 중에 금광 세그테크닉을 이용해 값이 모두 동일한 가장 긴 연속 부분 수열의 길이를 구하는 문제가 없길래 템플릿에 도움이 될 겸 수열과 쿼리로 문제를 만들었습니다. lazy propagation을 이용하지 않는 풀이도 존재하니 궁금하면 JusticeHui 블로그의 백준19651 수열과 쿼리 39를 참고하는 것을 추천합니다.