ACL에서 1줄만 추가해서 Segment Tree Beats 구현하기

2022-08-13) 초안을 작성했습니다. 일단 글을 완성하는 것을 목적으로 하였기에 부족한 부분이 매우 많이 보입니다. 부족한 예시를 채워 넣고 가독성을 높일 방법을 찾아야겠습니다. 부족하거나 어설픈 내용 수정은 이 작업이 끝난 뒤에 해야겠네요.

 

2022-11-10) 내용을 보강하였고, 오타를 수정하였습니다. 치명적인 오류가 있지 않는 한 더 이상의 수정 예정은 없습니다.

 

 

이 글은 Segment Tree, Lazy Propagation, Beats에 관하여 이미 지식이 있는 분들을 대상으로 하는 글입니다.

따라서 처음 Segment Tree Beats를 배우시려는 분들이 읽기에는 어려울 수 있습니다.

또한 ACL의 사용법을 이 글에서 따로 설명하지 않으니 유의 바랍니다.

 

0.목차

1. Group/Monoid

2. Group/Monoid Action

3. Segment Tree with Lazy Propagation의 추상화

4. Segment Tree의 추상화의 예시

5. Segment Tree Beats

6. Segment Tree Beats의 추상화, 그리고 ACL을 이용하여 구현하는 법

7. Segment Tree Beats의 추상화의 예시

8. 기타

 

1.Group/Monoid

수학에서, Group이란 특정 연산을 잘 적용할 수 있는 Object들의 집합입니다. 굳이 Object라고 적은 이유는, 원소들이 굳이 숫자일 필요가 없기 때문입니다. 주로 숫자, 행렬, 함수등을 모아 Group으로 만듭니다. Group $G$는 다음 4가지를 만족해야합니다.

 

1) $G$의 원소 $a,b$를 연산할 경우 그 연산 결과도 $G$에 속해야 합니다. 즉, $ a \odot b \in G $ 여야 합니다. 이 특징을 수학에서는 "닫혀있다"고 표현합니다. (즉, Group $G$는 연산 $ \odot $에 의해 닫혀있습니다)
2) 결합법칙을 만족해야 합니다. 즉, $a,b,c$가 $G$의 원소일때, $a \odot (b \odot c) = (a \odot b) \odot c$를 만족해야 합니다.
3) 항등원이 존재해야 합니다. 즉, 적당한 원소 $e$가 $G$안에 존재하는데, 그 $e$는 모든 $G$의 원소 $a$에 대하여 $e \odot a = a \odot e = a$를 만족합니다.
4) 역원이 존재해야 합니다. 즉, 임의의 $G$의 원소 $a$에 대하여, $a \odot b = b \odot a = e$를 만족하는 $b$가 $G$안에 존재합니다. 이때, 이런 $b$를 \(a^{-1}\)로 표현하기도 합니다.

 

이 4가지 조건중 마지막 조건을 뺀 1~3) 조건만 만족하는 구조를 Monoid라고 부릅니다. 대표적으로 곱셈이 주어진 정수 집합이 있습니다.(곱셈은 결합법칙도 만족하고, 항등원 1이 존재하지만, 역원이 정수 집합 내에 존재하지 않습니다)

 

이 구조가 도대체 Segment Tree와 무슨 관련이 있을까요? 바로 "합치기"를 가장 잘 표현하는 수학적 구조이기 때문입니다. "합치기"라고 애매하게 표현하긴 했지만, 이 행동은 Segment Tree에서 아주 자주 보이는 행동입니다. 예를 들어, 정점 v를 루트로 하는 서브트리의 자료를 가지고 있는 $\textrm{value}[v]$라는 배열을 생각했을때, 세그먼트 트리 위에서 $\textrm{value}[v]$를 계산하려면 $\textrm{value}[2v]$와 $\textrm{value}[2v+1]$의 값을 가져와서 계산을 해야 합니다. 다시 말해, $\textrm{value}[2v]$와 $\textrm{value}[2v+1]$을 "합쳐서" 나온 결과가 $\textrm{value}[v]$가 되는 것입니다. 수식으로 적으면 $\textrm{value}[v] = \textrm{value}[2v] \odot \textrm{value}[2v+1]$이 되겠네요. 이 "합치기"가 잘 안되면 그 문제는 Segment Tree를 이용해서 풀 수 없습니다. 대표적으로 다음과 같은 문제가 있습니다.

 

구간 $[L,R]$이 주어졌을 때, $a[L,L+1,\cdots,R]$에 등장하는 서로 다른 수 갯수 세기

 

이 문제는 위에서 말한 1),2),3)을 전부 만족하는 "합치기"를 정의할 수 없기 때문에, Segment Tree로 풀 수 없습니다. 반대로 이런 문제를 생각해봅시다.

 

구간 $[L,R]$이 주어졌을 때, $a[L]+a[L+1]+\cdots+a[R]$ 계산하기

 

이 문제는 "합치기"를 잘 정의할 수 있기 때문에 Segment Tree로 풀 수 있습니다. $\textrm{value}[v] = \textrm{value}[2v] + \textrm{value}[2v+1]$로 정의하면 되기 때문입니다.

 

2. Group/Monoid Action

수학에서 Group을 배우는 이유는 무엇일까요? 많은 이유야 있겠지만 대다수의 사람들은 "Group Action"을 생각하기 위해서 라고 대답합니다. Group $G$와 집합 $X$, 그리고 $G$와 $X$사이의 연산 $\cdot : G \times X \rightarrow X$가 존재할 때, 다음을 만족하면 Group Action이라 부릅니다.

 

1) $X$의 임의의 원소 $x$에 대하여, $ e \cdot x = x $. 즉, $e \cdot x$는 항상 $x$가 된다. 여기서 $e$는 그룹 $G$의 항등원입니다.

2) 결합법칙이 성립한다. 즉, $G$의 원소 $a,b$, $X$의 원소 $x$에 대하여, $ a \cdot ( b \cdot x) = (a \odot b) \cdot x $가 성립한다.

 

만약 위 정의에서 Group $G$ 대신에 Monoid $F$를 사용하면, 그것은 Monoid Action으로 바뀝니다. 이 Monoid Action이야 말로 Segment Tree의 핵심이며, Segment Tree의 추상화를 이해하기 위하여 반드시 알아두어야 합니다. 왜 Monoid Action이 Segment Tree와 관련이 있을까요? Segment Tree는 쿼리문제에(혹은, 일반 문제를 쿼리 문제로 치환하였을때) 쓰이게 되는데요, 쿼리 중엔 거의 반드시 "값의 갱신"에 관한 쿼리가 존재합니다. 값의 갱신에 관한 쿼리를 간단하게 설명하면 다음과 같습니다.

 

$ ind \; val : a_{ind}$의 값에 $val$이라는 연산을 취한다

 

여기서 연산을 취한다는것은 여러가지가 가능합니다. $a_{ind}$에 $val$을 더하는 것일수도, 곱하는 것일수도, $a_{ind}$를 $val$값으로 바꾸는 연산일 수도 있습니다. 아무튼 이 과정이 바로 Monoid Action입니다. $a_{ind}$라는 값에 $val$이라는 값을 "act"해주는 것이죠. 위에 적었던 수식으로 표현하자면, $a_{ind}$의 값을 $ val \cdot a_{ind} $로 바꾸는 것이죠. 그렇기 때문에, 만약 Monoid Action이 잘 정의되지 않는다면, 그 문제는 Segment Tree의 "값 갱신"을 올바르게 할 수 없다는 것을 의미하고, 결국 Segment Tree로 풀 수 없다는 의미가 됩니다.(이 문장에는 예외가 있습니다. 그것이 Segment Tree Beats인데요, 추후에 설명하겠습니다.). Monoid Action이 잘 정의된다는 것은 무슨 뜻일까요? 위에서 보듯 $X$는 그냥 집합이기만 하면 되고 아무런 조건이 없습니다. 신경써야하는 것은 집합 $F$를 정의하고, $F$사이에 정의된 Monoid 연산 $\odot$이 존재하고, $F$와 $X$사이에 정의된 Action 연산 $\cdot$이 존재하면 잘 정의된 것입니다.

 

3. Segment Tree with Lazy Propagation의 추상화

본격적으로 Segment Tree를 추상화 해봅시다. 많은 분들이 Segment Tree를 "특정 구간을 일정 값으로 만드는 것" "특정 구간에 일정 값을 더하는 것"으로 생각하시지만, Segment Tree는 더 많은 일을 할 수 있습니다. 구체적으론, Segment Tree는 다음과 같은 행동을 하는 자료구조입니다.

 

Monoid 수열 $a_1 , a_2 , \cdots , a_n $ 이 존재할때, 특정 구간에 Monoid Action을 해주는 자료구조

 

이 Monoid Action에는 여러분들이 알고 있는 "값 더하기" "값으로 만들기" " 값 곱하기"등이 있기 때문에 여러분들이 Segment Tree로 문제를 풀 수 있는 것입니다. 주의해야 할것은 위 Monoid Action에서 action을 받는 집합 $X$는 아무 조건없이 그냥 집합이면 된다고 설명하였지만, Segment Tree 문제를 풀기 위해서는 이 $X$ 역시 Monoid 여야 한다는 조건이 붙습니다.

 

결과적으로, Segment Tree with Lazy Propagation을 정의하기 위해서는 다음과 같은 것들이 정확하게 정의되어야 합니다.

1) $\textrm{value}$들을 저장할 Monoid S, $\textrm{lazy}$들을 저장할 Monoid F

2) $S$ 사이에 정의된 Monoid 연산 $ \odot_S $, $F$ 사이에 정의 된 Monoid 연산 $ \odot_F $

3) $S$의 항등원 $e_S$, $F$의 항등원 $e_F$

4) $F$와 $S$ 사이에 정의된 Action 연산 $\cdot$

 

위 사항들이 모두 잘 정의되었다면, 저희는 다음 2가지 연산을 매우 빠르게 시행할 수 있습니다.

1) $L \; R \; val : $ $ L \leq i \leq R $을 만족하는 모든 $i$에 대하여, $a_i$ 값을 $val \cdot a_i$로 바꾸기. 즉, $val$값을 act하기

2) $L \; R : $ $ a_L \odot_S a_{L+1} \odot_S \cdots \odot_S a_R$을 계산하기

 

각 연산과 항등원들에 대해 간단하게 설명하면

1) $ \odot_S $ : Segment Tree의 특정 정점 $v$를 볼때, $v$의 왼쪽 자식과 오른쪽 자식에서의 값을 보고 "합쳐서" $v$에서의 값을 만들어야 합니다. 그때 사용됩니다. 즉, $\textrm{value}[v] = \textrm{value}[2v] \odot_S \textrm{value}[2v+1]$ 연산을 하는데 필요합니다.

 

2) $ \odot_F $ : $\textrm{lazy}$들을 합치는데 필요합니다. 예를 들어, 어떤 값에 $a$를 더하고 $b$를 더하라는 연산이 주어질때, 이것은 $a+b$를 더하라는 연산으로 합칠 수 있는데, 이렇게 $\textrm{lazy}$들을 합치는 연산이 필요합니다. 즉, 정점 $v$를 루트로 하는 서브트리 전체에 $val$이라는 연산을 하라는 연산이 주어질때, $ \textrm{lazy}[v] = val \odot_F \textrm{lazy}[v]$ 연산을 하는데 필요합니다.

 

3) $e_S$ : Segment Tree 구현에 따라 필요할 수도, 필요 없을 수도 있습니다만, 대부분 필요합니다. 만약 $[L,R]$에서의 연산값을 계산하려는데, 현재 참조하고 있는 구간 $[l,r]$이 $[L,R]$과 겹치지 않는다면(즉, $r<L$이거나 $R<l$인 경우), 무슨 값을 return해야 할까요? 항등원, 즉 $e_S$를 return해야 합니다.

 

4) $e_F$ : $\textrm{lazy}$를 초기화 시키는데 필요합니다. 예를 들어, $[L,R]$ 값에 $val$값을 act하려고 하는데, 저희가 지금 참조하는 $[l,r]$구간이 $[L,R]$구간과 애매하게 겹쳐있다면 어떻게 할까요? $[l,r]$구간을 $[l,m]$ $[m+1,r]$ 구간으로 쪼개서 쪼갠 구간에서 다시 탐색하게 됩니다. 이때, 구간을 쪼개서 탐색할때 $\textrm{lazy}$값을 밑으로 흘려준 뒤 초기화 하는 과정이 필요합니다. 이때 초기화 할 $\textrm{lazy}$ 값으로 $e_F$를 사용합니다.

 

5) $\cdot$ : $\textrm{lazy}$ 값을 이용하여 $\textrm{value}$ 값을 직접적으로 갱신할때 필요합니다. 예를 들어, $[L,R]$ 구간을 갱신 시키려고 하고 있고, 현재 보고 있는 구간 $[l,r]$이 $[L,R]$에 정확히 포함된다면, 그 즉시 밑으로 내려가는 것을 멈추고 그 자리에서 값 갱신 연산을 진행해야합니다. 이때 $\textrm{value}[v] = \textrm{lazy}[v] \cdot \textrm{value}[v]$ 연산을 하게 됩니다.

 

ACL에서 Segment Tree with Lazy Propagation 구현에 필요한 Constructor

실제로 ACL에서도 Segment Tree를 구현하기 위하여 위에서 언급한 $S, \odot_S, e_S, F, \odot_F, e_F,\cdot$를 전부 작성하라고 명시되어 있습니다. 다만 용어의 차이는 있는데요, ACL에서 op는 $\odot_S$를, e는 $e_S$를, composition은 $\odot_F$를, id는 $e_F$를, mapping은 $\cdot$을 의미합니다.

 

말로 하면 어렵기 때문에 몇가지 예시를 들겠습니다.

 

4. Segment Tree의 추상화의 예시

 

1. 다음 문제를 생각해봅시다.

1) $L \; R \; val : $ 수열 $a$의 $L$번째부터 $R$까지의 값을 $val$로 바꾼다.($val$은 0 이상의 정수)

2) $L \; R : $ 수열 $a$의 $L$번째부터 $R$까지의 값의 최대값을 출력한다.

 

안타깝게도, $S$,$F$가 어떤 형태인지 바로 눈치채는건 매우 어렵습니다. 몇번씩 될법한 것들을 생각해보면서 $S$와 $F$를 만들어내야합니다. 먼저 $F$를 생각해볼까요?

$F$는 $\textrm{lazy}$를 저장해야합니다. 즉, $\textrm{lazy}[v]$가 담아야하는 정보 그 자체가 $F$가 됩니다. $val$이 정수값만 들어오기 때문에 $\textrm{lazy}[v]$는 정수값만 담을 수 있으면 충분하며, 따라서 $F = $ 0 이상의 정수 집합으로 정의하면 됩니다. PS적으로 얘기하면 $F = int$ 혹은 $long \; long \; int$면 됩니다.

$\odot_F$는 어떻게 될까요? 이를 알기 위해서는 $\cdot$을 여러번 했을때 어떤 꼴이 되는 지 보면 됩니다. 값 $x$를 $b$로 바꾸는 연산을 한 뒤, $a$로 바꾸는 연산을 하면 어떨까요? 이것은 그냥 값 $x$를 $a$로 바꾸는 연산을 한 것과 같습니다. 즉, $ a \cdot ( b \cdot x) = (a) \cdot x $가 된다는 뜻인데, Monoid Action에서의 정의를 생각해보면 $ a \cdot ( b \cdot x) = (a \odot_F b) \cdot x $가 됩니다. 따라서, $ a \odot_F b = a $ 로 정의하면 되겠네요.

$e_F$는 어떻게 될까요? 안타깝게도 문제가 생깁니다. $\odot_F$ 정의상 $ a \odot_F e_F = a$가 항상 만족하지만, $ e_F \odot_F a = a$를 만족하게 하는 $e_F$가 존재하지 않기 때문입니다. 어떻게 해야 할까요? 이제부터 여기서 기존에 정의한 $F$, $\odot_F$를 변형해가며 최대한 끼워맞출겁니다.

 

기존 $F$에 $dummy$를 하나 추가해봅시다. 이 $dummy$는 입력으로 들어오는 $val$과 중복되면 안됩니다. $-1$이면 되겠네요. 즉, $F$를 -1이상의 정수 집합으로 정의하겠습니다. 그러면 이에 맞춰  $\odot_F$도 조작해야합니다. $ a \odot_F b$를 만약 $a$가 $-1$이면 $b$, 아니면 $a$로 정의하겠습니다. 이 경우, $\odot_F$가 결합법칙을 만족해야하는지 체크해야하지만 넘어가겠습니다. 만족한다고 대충 넘어가고, 항등원 $e_F$를 $-1$로 설정하면, 네, 됐습니다. 이제 $F$는 Monoid가 됩니다!

 

이제 $S$를 생각해봅시다. $S$는 $\textrm{value}$를 저장해야합니다. 최대값을 저장하면 충분하므로, $S = $ 0 이상의 정수 집합으로 정의하면 됩니다.

$\odot_S$는 어떻게 될까요? $\textrm{value}[v]$ 를 $\textrm{value}[2v]$와 $\textrm{value}[2v+1]$을 이용하여 계산하려면 $\textrm{value} = \max(\textrm{value}[2v],\textrm{value}[2v+1])$ 과정을 거쳐야 합니다. 따라서, $\odot_S$는 $ a \odot_S b = \max(a,b)$로 정의하면 되겠네요.

$e_S$는 어떻게 될까요? $ \max(a,e_S) = \max(e_S,a) = a$를 항상 만족시키게 설정하면 되겠네요. $-\infty$가 좋겠습니다.

마지막으로 $\cdot$ 연산을 정의해봅시다. $a \cdot b = $ $a$가 $-1$이면 $b$, 아니면 $a$로 정의합시다. 그러면 $\cdot$은 Monoid Action이 된다는 것을 알 수 있고, 이제 Segment Tree를 잘 정의할 수 있습니다.

 

보다 시피 쉽게 $S$와 $F$를 정의할 수 없고, 주먹구구식으로 될때까지 어떤 값들이 필요한지 추가해보고 연산을 만드는 과정이 필요합니다. 굉장히 이상해보이지만 추상화 없이 Segment Tree를 정의할때도 충분히 겪는 과정입니다.(예를 들어 추상화 없이 구현한다고 하였을때도 $\textrm{lazy}$를 $-1$로 초기화 하는 과정이 필요합니다. 이 과정이 왜 필요한가 생각해 보면, 위에 서술한 추상화때와 동일한 이유로 $-1$이 필요한 것을 알 수 있습니다)

 

위에 계산한 Monoid들과 AtCoder Library를 이용하여 Segment Tree를 구현하면 다음과 같습니다.

#include <atcoder/lazysegtree>
#define MIN -1234567890

int op(int a, int b)
{
	return a>b?a:b;
}
int e()
{
	return MIN;
}
int composition(int a, int b)
{
	if(a==-1) return b;
	else return a;
}
int id()
{
	return -1;
}
int mapping(int a, int b)
{
	if(a==-1) return b;
	else return a;
}

using segTree = atcoder::lazy_segtree<int,op,e,int,mapping,composition,id>;

이 Segment Tree 위에서 1), 2) 연산을 어떻게 사용하면 되는지에 관해서는 AtCoder Library Github을 참고해주세요

 

5. Segment Tree Beats

Segment Tree with Lazy Propagation의 추상화는 3가지로 요약할 수 있습니다. $\textrm{value}$를 저장할 Monoid $S$가 잘 정의되어야 하고, $\textrm{lazy}$를 저장할 Monoid $F$가 잘 정의되어야 하고, $F$와 $S$ 사이의 Monoid Action $\cdot$이 잘 정의되어야 합니다. Segment Tree Beats는, $S$와 $F$를 잘 정의할 수 있지만, Monoid Action $\cdot$을 잘 정의할 수 없을때 제한적으로 사용이 가능합니다.

 

예를 들어, 일반 Segment Tree에서 $\cdot$ 연산은 다음처럼 표현할 수 있습니다.

$\textrm{lazy} \cdot \textrm{value} : $ $\textrm{value}$에 $\textrm{lazy}$를 act 합니다.

 

하지만 Segment Tree Beats에서의 $\cdot$ 연산은 다음처럼 표현됩니다.

$\textrm{lazy} \cdot \textrm{value} : $ $\textrm{value}$에 $\textrm{lazy}$를 act 할 수 있다면 act 합니다. 만약 act가 불가능할 경우에는, 특수한 방법을 사용합니다.

 

이 특수한 방법이란 "처음부터 다시 계산하기" 입니다. 예를 들어 배열 $a_1, a_2, \cdots, a_n$이 주어지고, 정점 $v$에 해당하는 구간이 $[L,R]$이라고 할 때, $\textrm{lazy}$를 $\textrm{value}[v]$에 act 할 수 없다면, $L \leq i \leq R$을 만족하는 모든 $i$에 대하여, $\textrm{lazy} \cdot a_i$를 일일히 계산해 갱신해주고, $a_L \odot_S a_{L+1} \odot_S \cdots \odot_S a_R$을 일일히 계산하여 $\textrm{lazy} \cdot \textrm{value}[v] = a_L \odot_S a_{L+1} \odot_S \cdots \odot_S a_R$로 정의해주는 방법입니다. 보다시피 이 특수한 방법은 $v$의 서브트리 크기에 비례한 시간이 걸리기 때문에 Segment Tree Beats를 사용할때는 반드시 이 특수한 방법이 자주 쓰이지 않는다는 것을 증명한 뒤에 사용해야합니다.

 

6. Segment Tree Beats의 추상화, 그리고 ACL을 이용하여 구현하는 법

Beats의 추상화는 일반 Segment Tree의 추상화와 똑같이 $S, \odot_S, e_S, F, \odot_F, e_F,\cdot$를 잘 정의하면 충분합니다. 단, 몇가지 추가사항이 존재합니다.

 

1) Monoid $S$의 변수타입중에는 반드시 $\textrm{fail}$이라는 변수타입이 들어가야 합니다. $\textrm{fail}$은 $bool$형이어야 하고, 거의 언제나 $\textrm{false}$값을 가져야 합니다. $\textrm{fail}$이 $\textrm{true}$가 될 때는 오직 Monoid Action이 실패할 때 뿐입니다.

2) $\odot_S$ 연산 결과로 나오는 $S$값의 $\textrm{fail}$은 무조건 $\textrm{false}$여야합니다. 이유는 1)에서 말했듯 $\textrm{fail}$이 $\textrm{true}$가 될 때는 오직 Monoid Action이 실패할 때 뿐이기 때문입니다.

3) $e_S$의 $\textrm{fail}$값은 무조건 $\textrm{false}$입니다. 이유는 위와 같습니다.

4) $F,\odot_F,e_F$에는 특별한 제약이 없습니다.

5) $\cdot$은 다음과 같이 정의됩니다: $\textrm{lazy} \cdot \textrm{value}$는 만약 이 값을 직접적으로 계산하는게 가능하다면 그 값을 return 합니다. 계산 할 수 없다면, $\textrm{value}$의 $\textrm{fail}$값을 $\textrm{true}$로 변경한 뒤 $\textrm{value}$를 return 합니다.

 

이제 ACL이 이 추상화된 Beats를 동작하게 조작해야합니다. #include <atcoder/lazysegtree>를 코드에 넣은 뒤 일반 OJ에서도 실행이 되도록 그 코드를 convert하면, 209번째 줄 근처에서 all_apply라는 함수를 찾으실 수 있을것입니다.

 

수정 전 ACL

void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }

이 함수에 딱 한줄만 추가해줍시다.

수정 후 ACL

void all_apply(int k, F f) {
    	d[k] = mapping(f, d[k]);
    	if (k < size) {
    	    lz[k] = composition(f, lz[k]);
    	    if (d[k].fail) push(k), update(k);
    	}
	}

네, 됐습니다. 이제 이 ACL은 Beats를 지원합니다. 추가한 문장에 대해서 간단히 설명하면, 만약 $\textrm{fail}$이 $\textrm{true}$가 될 경우, 위에서 언급한 특수한 방법을 사용하라는 문장입니다.

남은것은 $S, \odot_S, e_S, F, \odot_F, e_F,\cdot$를 잘 정의한 다음 Segment Tree with Lazy Propagation에서 했던것처럼 Segment Tree를 정의해주면 끝납니다.

 

7. Segment Tree Beats의 추상화의 예시

BOJ 17474: 수열과 쿼리 26

17474번: 수열과 쿼리 26

 

추상화 부분에서 지겹도록 설명한 $S, \odot_S, e_S, F, \odot_F, e_F,\cdot$들을 잘 정의하면 바로 풀리는 문제입니다. 물론 실제로 이 문제가 바로 풀리지는 않을것입니다 - Monoid $S$와 $F$가 어떤 값을 가지고 있어야 하는지 분석하는게 어렵기 때문입니다. 그래도 침착하게 조건들을 하나하나 따져보면, $S$와 $F$가 다음 값을 가지고 있으면 Monoid 연산을 충분히 잘 정의할 수 있다는 것을 알 수 있습니다.

 

$S$의 경우

• 그 구간에 속한 값들중 최대값 max1
• 그 구간에 속한 값들중 max1이라는 값을 가지는 원소의 개수 countMax1
• 그 구간에 속한 값들 중 두번째로 큰 값 max2
• 그 구간에 속한 값들의 합 sum
• beats를 사용하기 위하여 임의로 선언한 변수 fail

$F$의 경우

• lazy를 나타내는 변수. 결국 $F$는 값 1개로 정의되니 그냥 long long int라고 생각합니다.

그리고 Monoid 연산들과 Monoid Action을 잘 정의해주면 끝입니다. 이 문제는 Monoid Action이 잘 정의되지 않으니, 6.에서 설명한것처럼 적절하게 fail을 사용하여야 합니다.

#include <stdio.h>
#include <atcoder/lazysegtree>
#define MAX (long long int)1e18
#define MIN -(long long int)1e18

struct S{
	long long int max1;
	int countMax1;
	long long int max2;
	long long int sum;
	int fail;
};
S op(S a, S b)
{
	int countMax1;
	long long int max1,max2,sum;
	sum = a.sum + b.sum;
	if(a.max1<b.max1)
	{
		max1 = b.max1;
		countMax1 = b.countMax1;
		max2 = b.max2>a.max1?b.max2:a.max1;
	}
	else if(a.max1>b.max1)
	{
		max1 = a.max1;
		countMax1 = a.countMax1;
		max2 = a.max2>b.max1?a.max2:b.max1;
	}
	else
	{
		max1 = a.max1;
		countMax1 = a.countMax1 + b.countMax1;
		max2 = a.max2>b.max2?a.max2:b.max2;
	}
	return {max1,countMax1,max2,sum,0};
}
S e() { return {MIN,0,MIN,0,0}; }
S mapping(long long int f, S x)
{
	S y = x;
	if(f>=x.max1) return y;
	else if(f>x.max2)
	{
		y.max1 = f;
		y.sum = x.sum -= (x.max1-f)*x.countMax1;
		return y;
	}
	else // fail condition!!
	{
		y.fail = 1;
		return y;
	}
}
long long int composition(long long int f, long long int g) { return f<g?f:g; }
long long int id(){ return MAX; }
using segtree = atcoder::lazy_segtree<S,op,e,long long int,mapping,composition,id>;

int main()
{
	int a;
	scanf("%d",&a);
	segtree T(a+1); // 0 index to a index
	for(int i=1;i<=a;i++)
	{
		int b;
		scanf("%d",&b);
		T.set(i,{b,1,MIN,b,0});
	}
	int b;
	scanf("%d",&b);
	while(b--)
	{
		int c;
		scanf("%d",&c);
		if(c==1)
		{
			int d,e,f;
			scanf("%d%d%d",&d,&e,&f);
			T.apply(d,e,f);
		}
		if(c==2)
		{
			int d,e;
			scanf("%d%d",&d,&e);
			printf("%lld\n",T.prod(d,e+1).max1);
		}
		if(c==3)
		{
			int d,e;
			scanf("%d%d",&d,&e);
			printf("%lld\n",T.prod(d,e+1).sum);
		}
	}
}

어려워 보이는 코드지만 사실 정말 별거 없습니다. main문 위에 있는 많은 구조체와 함수는 단순히 Monoid를 정의해 놓은것 뿐이며, main문은 단순히 쿼리 계산하는것 뿐입니다. 당연하지만 이 코드 그대로 BOJ에 제출하면 컴파일 에러가 나는것을 볼 수 있습니다. 이 코드를 BOJ에서 돌아가도록 convert 한 뒤에, 위에서 말한대로 ACL에 한 줄을 추가해야합니다. 그 후에는 AC가 나오는 것을 확인할 수 있을 것입니다.

또한, 이 코드가 잘 돌아가기 위하여 기본적인 증명이 필요합니다. 5.에서 말하였듯 fail이 일어나는 상황이 매우 적다는 것을 증명해야 하기 때문입니다. 다른 블로그등에서 충분히 자세히 설명되어 있을테니 여기서는 간단하게만 설명하겠습니다. fail이 일어나는 조건과 동치인것이 lazy가 max2보다 작아져서 최대값과 2번째로 큰 최대값이 같게되는 그런 쿼리가 들어올때입니다. 그런데, 최대값과 2번째로 큰 최대값이 같아지는 경우가 각 리프노드당 1번씩, 총 $N$번만 일어나게 되며, 그렇게 어떤 리프노드에서 fail이 일어날 경우 segment tree 위에서 그 노드의 부모 노드에 전부 fail이 일어나게 됩니다. 따라서,  전체 일어나는 fail 횟수는 약 $ 2N$이며, fail로 인하여 소모되는 연산은 각 segment tree의 level별로 정확히 $N$번이 되기 때문에, 전체 fail로 인한 소모되는 연산은 정확히 $N \log N$이 됩니다. 이는 $N \leq 10^6$ 범위 내에서 충분히 허용할만한 연산량이기 때문에, fail이 충분히 많이 일어나지 않는다고 볼 수 있습니다. 즉, Segment Tree Beats를 사용할 수 있습니다.

 

8. 기타

이 글의 원문은 Codeforces 닉네임 hitonanode님이 적으신 https://rsm9.hatenablog.com/entry/2021/02/01/220408입니다. hitonanode님에게 번역 허가를 받아서 한국어로 번역할 겸, Segment Tree의 추상화에 관한 내용도 넣었습니다. 자료를 제공해준 hitonanode님에게 무한한 감사를 드립니다.

ひとなのでさんありがとうございます！

 

덤으로 번역하면서 원문에 있는 오타쿠 내용들은 전부 제거했습니다(...) 모두 러브라이브 보세요