굉장히 오랜만에 돌아왔다. 그동안 굉장히 바쁜 일이 있었다...기보다는 그냥 기본기만 단련하느라 새로운 알고리즘을 공부하는걸 소홀히 한 것 같다. 뭐 덕분에 그 사이에 찐렌지를 찍었다거나 루비를 찍었다거나 하는 등의 변화는 있긴 하다. 어쨌든, 앞으로는 최대한 자주 글을 써보도록 노력할 것이다. 이 포스팅 앞에 있는 무수히 많은 설명하지 않은 알고리즘들도 아.....마도 조만간 채워지지 않을까싶다. 어쨌든, 오늘 쓸 것은 크게 "제곱근 분할법"이라는 범주 안에 들어가는 것들에 대한 설명이다. 나도 제곱근분할법이랑 모스밖에 아직은 모르긴 하는데, 나머지 뒤에 있는 것들도 배워봐야겠다.
1. 제곱근 분할법
뭐어... 제곱근 분할법은 이 포스팅을 제외하고도 굉장히 많은 설명글이 있기 때문에 다른 글을 참고할 수도 있겠지만, 기왕이면 이 블로그만으로 아래에 있는 모든 내용을 이해하면 좋을테니 간단히 설명하겠다. 우선, 다음과 같은 문제를 보자.
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
어느정도 자료구조에 조예가 있는 독자들이라면 이 문제가 세그먼트 트리등을 비롯한 자료구조를 통해 \(O(n\log n)\)에 해결될 수 있음을 알 것이다. 그러나, 이번에는 이 문제를 조금 색다른 방식으로 접근해볼 수도 있다.
전체 수열을 X개의 구간들로 나누고, 해당 구간들에 있는 모든 수들의 합을 관리한다.
위의 조건을 만족하는 채로 문제의 쿼리들을 처리하는 효율에 대해 생각해보자.
우선, 첫번째로 어떤 수를 변경할 경우에는, \(O(1)\)만에 갱신이 가능하다. 어쨌든 해당 수를 포함하는 구간은 정확히 하나밖에 없을 것이기 때문이다.
두번재로, 어떤 구간의 모든 수들의 합을 구하는 쿼리는 어떻게 처리할 것인가? 우선, 주어진 구간 안에 포함되는 블럭(즉, 처음에 나누었던 구간들이다. 그러나 쿼리의 "구간"과 의미가 혼동될 수 있으므로 앞으로는 블럭이라고 설명하겠다.)들이 있다면, 해당 블럭들의 전체 수들의 합을 따로 더해줄 수 있을 것이다. 이제 주어진 구간과 "어중간하게 겹치는" 블럭은 많아야 2개이고, 이들의 경우에는 나이브하게 구간 안에 포함되는 수들을 따로 더해준다. 이 경우 시간복잡도는 블럭 자체의 전체 개수인 X, 한 블럭의 크기인 \(n/X\)에 의존하는 \(O(X+n/X)\)가 된다.
그리고, 위의 식은 간단한 수학적 분석을 통해서 \(X=\sqrt n\)일때 비로소 최소가 됨을 알 수 있으며, 심지어 그때의 시간복잡도는 \(O(\sqrt n)\)이 된다. 즉, 쿼리 하나를 \(O(\sqrt n)\)에 풀 수 있는 것이다!
사실, 이 예시만 본다면 왜 제곱근 분할법이 ps계에서 가장 중요한 알고리즘중 하나인지 이해하기 힘들 수도 있다. 결국 세그먼트 트리를 활용한 풀이보다 훨씬 시간복잡도가 느리기 때문이다. 특히 n이 커지면 커질수록 두 풀이의 효율성 차이는 커질 것이다...
하지만 이 포스팅의 주제 전반이 전부 제곱근 분할법을 기본적인 동작원리로 삼는만큼, 아래의 알고리즘들을 이해해가다보면 제곱근 분할법이 얼마나 인상적인 아이디어인지 이해할 수 있을 것이다. 일단 "제곱근 분할법만이 풀 수 있는" 문제를 하나 가져와본다면, 다음과 같다: 17687번: Bitaro’s Party (acmicpc.net)
17687번: Bitaro’s Party
Among the friends attending the first party (the friends living in town 2, 3 or 4), the friends living in town 2 or 3 go to town 4, where the party is held, via the largest number of canals. This number is 1, so output 1. Among the friends attending the se
www.acmicpc.net
문제를 간략하게 요약하자면, DAG가 주어지고, 쿼리가 주어진다. 이제 하나의 쿼리에서는 도착정점 하나를 주고, 몇개의 다른 정점들을 제시한다. 이제 당신은, 주어진 몇개의 정점을 제외한 나머지 정점들에서 도착정점까지 가는 최장거리들중 최댓값을 답해야 한다.
단순히 읽어보기만 하면, 무려 "그래프" 문제인데 대체 무엇을 분할하는 것인지 감이 잡히지 않을 수 있다. 이 문제를 풀기 위해, 우리는 각각의 "쿼리"들을 분류할 것이다.
X라는 어떤 값을 하나 잡자. 한 쿼리에서 제외할 정점의 개수가 X보다 크다면, 그냥 단순한 다이나믹 프로그래밍으로 계산한다(DAG이며, 각 정점들의 순위도 주어져있으므로 가장 뒤의 정점들부터 차례대로 dp테이블을 채워나가면 된다.).
한 쿼리에서 제외할 정점의 개수가 X보다 작은 경우를 처리하는게 핵심이다. 이를 위해, 우리는 다음과 같은 값들을 계산할 것이다:
각 정점 v에 대해, v로 도달하는 최장경로가 가장 긴 X+1개의 시작점들
이것은 사실 위에서 설명한 DP를 조금 확장하기만 하면 \(O(nX)\)만에 해결할 수 있다.
어쨌든, 이 시작점들과 그 최장경로의 길이를 알고만 있다면, 결국 X개 이하의 시작정점들을 지워봤자 V로 도달하는 최장경로가 가장 긴 정점은 분명히 위에서 이미 구한 X+1개의 시작점들중에 존재할 것이다.
이제 시간복잡도를 생각해보자.
첫번째로, X보다 작거나 같은 양의 시작정점들이 제외되는 경우를 생각해보자. 각 도착정점들에 대해 X+1개의 후보들중 무엇이 최대인지를 체크하는 것은, 자명히 \(O(X)\)만에 가능하다.
이제 X보다 큰 양의 시작정점들이 제외되는 경우가 핵심이다. 나이브하게 계산한다고 했으므로, 분명히 \(O(n)\)이 걸린다. 쿼리의 개수는 Q개이다. 실패한걸까?
사실은, 굉장히 중요한 관찰을 하나 해볼 수 있다. 제외되는 시작정점의 개수가 X보다 큰 쿼리는 많아야 \(O(Q/X)\)개 있다.
따라서, 전체 시간복잡도는 \(O(nQ/X+QX)\)가 된다! 이제 \(X=\sqrt n\)으로 잡고나면, 전체 시간복잡도는 \(O(Q\sqrt n))\)가 되어, 문제를 해결할 수 있다!
이렇듯, 단순히 수열에서 블럭을 잘 잡는것 뿐만이 아니라, 굉장히 다양한 객체들(위의 예시에서는 쿼리)에 유사한 논리를 적용해서 문제를 풀어낼 수가 있다. 그리고 아래의 논의들이 바로 그러한 응용의 극한이다.
2. MOs Algorithm
ㅁㄴㅇㄹ
3. 3D MO
현재 이 문단을 쓰고 있는 시점을 기준으로, 아직 두번째 알고리즘, 즉 MOs Algorithm을 소개하지 않은 상태이다. 그러나, 분명히 미래의 내가 귀찮음을 감수하고 잘 써줄 것이라 믿기 때문에, 새로운 것을 먼저 배우고자 3D MO를 먼저 소개하고자 한다.
어떤 쿼리를 처리하는 문제에서 MOs Algorithm이 적용되기 위한 최소한의 조건은 갱신 연산이 없다는 것으로 보인다. 갱신 쿼리까지 처리를 하기 위해서는 어떤 질의를 온라인으로 답해야 할 것 같기 때문이다. 그게 바로 "오프라인 쿼리"이며, 그렇기에 쿼리의 순서를 마음대로 섞을 수 있기 때문이다.
하지만, 단지 갱신이 없는 문제만을 풀기 위해 MOs Algorithm을 사용하기에는 이 훌륭한 논리가 다소 아깝게 느껴지지 않는가? 만약 갱신이 있는 문제에서도 모스를 적용할 수 있을려면, 어떤 방법을 써야할까? 이 3D MO가 바로 그런 측면에서 모스 알고리즘을 더욱 응용한 알고리즘이라고 볼 수 있다. 업데이트가 있는 쿼리 문제에서의 MO라고도 하여, MOs with update라고도 불리는 모양이지만, 이 논의를 듣고나면 3D MO가 더욱 본질적인 의미로 와닿을 것이라고 생각한다.
어떤 알고리즘의 아름다움을 느끼기 위한 가장 간단한 방법은, 내가 모든 포스팅에서 항상 그래왔듯이 예시를 드는 것이다. 우리는 MO로 풀리는 기본문제를 위에서 분석해보았다. 그렇다면, 이번에는 다음과 같은 문제를 생각해볼 수 있다.
n개의 정수로 이루어진 수열이 주어진다. 당신은 다음의 두 쿼리를 처리해야 한다.:
1. 어떤 구간 내에 있는 서로 다른 수가 총 몇 개인지 출력한다.
2. 한 정수의 값을 갱신한다.
당연히, 이 문제는 기존의 모스만으로는 풀 수가 없다. 1번 쿼리들이 임의의 기준에 의해 정렬되고 나면 지금까지 시행된 2번 쿼리의 분포에 대한 바운드가 없기 때문에 굉장히 비효율적인 알고리즘으로 변한다. 여기에서 어떻게 시간복잡도를 줄일 수 있을까?
모스 알고리즘이 어떤 방식으로 시간복잡도를 bound했는지 생각하자. 1번 쿼리의 L,R들이 움직이는 횟수 자체를 바운드하는 것이 풀이의 핵심이었다. 그렇다면, 이번에는 1번쿼리의 L,R 거기에다가 한 1번 쿼리 이전에 시행된 2번 쿼리의 개수 t가 움직이는 횟수까지 bound할 수 있는 어떤 순서를 찾아내면 될 것이라 유추할 수 있다. 일단은 모스에서 했던 것처럼, 수열을 크기가 B인 블럭들로 분할해야 할 것 같다. 모스에서는 쿼리를 2개의 인자에 대해 정렬했었으니까, "3D MO"에서는 쿼리를 세 개의 인자를 기반으로 정렬해보면 되지 않을까? 이 세 개의 인자가 무엇인지 잠시나마 고민해보는 것을 추천한다.
결과적으로 설명을 하자면, 다음과 같은 인자들에 대해 정렬을 하면 된다:
{L이 속한 블럭의 인덱스, R이 속한 블럭의 인덱스, 해당 쿼리 이전에 있었던 2번 쿼리의 개수}
이 기준으로 정렬을 하면 어떻게 되는지 연산횟수를 분석해보자.
1. L이 속한 블럭의 인덱스가 증가하지 않는다면, L의 변화는 많아야 B이다. L이 속한 블럭의 인덱스는 많아야 \(N/B\)번 증가하며, 대략적으로 1의 인덱스가 증가할때마다 L이 변화할 수 있는 양이 B만큼 증가한다고 생각할 수 있다. 따라서, 도합 \(O(QB+N)\)이라고 생각할 수 있다.
2. R이 속한 블럭의 경우는 어떠한가? L이 속한 블럭의 인덱스와 R이 속한 블럭의 인덱스가 변하지 않는다면, \(O(B)\)만큼의 변화가 일어난다. 전체 쿼리는 Q개이므로, 일단은 \(O(QB)\)만큼의 인자가 더해진다. L이 속한 인덱스가 변화하진 않았는데, R이 속한 인덱스가 변화하는 경우를 생각해보자. 이는 첫 번째 블럭에서부터, 마지막 블럭까지 전부를 취할 수 있기 때문에 여기에서 \(O(N)\)만큼의 변화가 나타난다. 하나의 L이 속한 인덱스에 대해, \(O(N)\)만큼의 변화가 일어나므로, 여기에서 나타나는 변화횟수는 \(O(N^2/B)\)라고 할 수 있다. 요약하자면, \(O(QB+N^2/B)\)이다.
3. 2번 쿼리를 얼마나 롤백하고 재시행해야 하는가? 일단 아-무리 2번 쿼리를 많이 바꾼다 하더라도, 한번 바꿀때는 \(O(Q)\)번을 넘어가진 않는다. 그리고 잘 생각해보면, L이 속한 인덱스와 R이 속한 인덱스가 고정되어있다면 2번쿼리의 수(t)는 단조증가하므로, 하나의 {L인덱스, R인덱스}에 대해서 \(O(Q)\)만큼 변화한다. {L인덱스,R인덱스}의 가짓수는 \(O(N^2/B^2)\)개 존재하므로, 전체 변화량은 \(O(QN^2/B^2)\)이다.
종합해보면, 전체 변화량은 \(O(QB+QN^2/B^2)\)라고 할 수 있다. 이번에도 마찬가지로 \(B=N^{2/3}\)으로 잡고나면, 결국 전체 변화량은 \(O(QN^{2/3})\)이 된다! N,Q가 너무 크면 풀 수 없지만, 분명히 나이브보단 효과적일 것이고, N=Q=10만 정도라면 충분히 풀 수 있을 법한 수준이다! 백준에서는 문제를 찾지 못했지만, 아마 이 문제의 트리를 ETT로 펴바른 다음에, Tree MO와 위의 풀이를 합치면 풀 수 있을 것이다.
Practice Coding Problem - CodeChef
Practice Coding Problem - CodeChef
www.codechef.com
더욱 재미있는 것은, 굳이 "3D"에만 머무르리란 법이 없다는 것이다. 예컨대, 이런 해괴한 문제를 생각해보자.
수열이 주어지고, 두 쿼리를 처리해야 한다.
1. l1,r1,l2,r2가 주어진다. [l1,r1],[l2,r2]를 생각하자. 다음 조건을 만족하는 {x,y}의 개수를 셀 것이다:
l1<=x<=r1,l2<=y<r2, a[x]==a[y]
2. 어떤 위치의 원소를 갱신한다.
눈치가 빠른 사람이라면 알 수 있겠지만, 이 문제는 \(O(QN^{4/5|)\)에 해결할 수 있다. 블럭의 크기를 B로 잡고, l1이 속한 인덱스, r1이 속한 인덱스, l2가 속한 인덱스, r2가 속한 인덱스, 시행된 2번 쿼리의 개수를 하나의 튜플로 잡고, 해당 튜플을 정렬한다. 위에서 속한 논의를 다시 설명하기에는 굉장히 장황하고 지루해질 것이기 때문에, 간단히 설명하면,
앞의 세 인자의 변화량은 r2가 속한 인덱스의 변화량에 지배당한다. 그리고 r2가 속한 인덱스의 변화는 대략적으로 \(O(N*(N/B)*(N/B)*(N/B)+BQ)=O(N^4/B^3+BQ)\)이라고 할 수 있다.
2번 쿼리의 변화량을 분석해보면, \(O(Q(N/B)(N/B)(N/B)(N/B))=O(QN^4/B^4)\)이다. 가장 중요한 인자들만 추출해서 생각해보면, \(O(BQ+QN^4/B^4)\)라고 할 수 있다. 아하! 이제 \(B=N^{4/5}\)로 잡고나면, 전체 시간복잡도는 \(O(QN^{4/5})\)가 된다. 따라서 문제를 풀...수 있는지는 모른다. 왜냐하면 \(N^{1/5}\)를 최적화하는걸 강제하는 문제를 만드는 것 자체가 말도 안되게 어려울 것으로 추정되기 때문이다...
애초에 \(O(QN^{4/5})\)같은게 잘 돌아갈려면 N=10만, Q=10만정도로 줘야 나이브와 효율의 차이가 10배가 되는데, 10배라는 차이가 언어 이슈, 구현 이슈에 따라 안뒤집히는 값도 아니기 때문이다.
그럼에도 불구하고, 이 아이디어가 놀라운 아이디어임은 분명하며, 모스 알고리즘이 얼마나 응용될 수 있는지를 알려주는 좋은 알고리즘인 것 같다. 백준에서 이 알고리즘을 써먹어서 풀만한 문제는 흠...찾아보고 있긴 한데 생각보다 별로 안보이긴 한다. 뭐 \(N^{5/3}\)같은게 그렇게 내기 쉬운 알고리즘인건 아니기 때문에 그럴만하다고 생각하긴 한다...
4. Regions Trick
ㅁㄴㅇㄹ
5. Sweepline MO
사실 이 기법을 배울려고 결심한 시점은 굉장히 예전이지만, 실제로 공부한 것은 비교적 최근의 일이다. 왜냐하면, 생각보다 \(O(N \sqrt N logN)\)을 \(O(N\sqrt N)\)으로 줄이는 것은 들리는 만큼 굉장히 효율적인 무언가로 보이지 않을수도 있고, 실제로 나 또한 후자가 안정적으로 도는 제한이라면 전자도 충분히 돌려볼만한 시복이라고 간주해왔기 때문이다. 그러나 최근에 나는 로그를 하나 뗀다는 것이 얼마나 강력한 최적화인지 여러 문제를 풀며 느꼈다...아무튼 이제 본론으로 들어가겠다.
우선, 앞서 말했듯이 이 테크닉은 \(O(N\sqrt N logN)\) 과 같은 시간복잡도를 가지는 모스 알고리즘을 특수한 경우에 \ \(O(N\sqrt N)\) 으로 줄이는 테크닉이라고 요약할 수 있다. 우선, 다음과 같은 문제를 고려하자:
당신에게 길이 N의 수열이 주어진다. 이제, Q개의 쿼리 l,r이 주어지는데, 이는 구간 [l,r]의 반전수를 계산하라는 쿼리이다.(추후에 \(O(N\sqrt N)\) 과 같은 표기를 자주 사용할 것인데, 실제로는 아닐수도 있지만 N과 Q의 크기가 비슷하기 때문에 편의상 스케일만을 묘사하기 위해 이렇게 표기한다.)
Library Checker
judge.yosupo.jp
아마 모스 알고리즘을 배웠다면, 해당 문제를 모스 알고리즘으로 \(O(N\sqrt N logN)\) 의 시복을 통해 해결할 수 있다는 사실을 몇 가지 시도를 통해 확인 가능할 것이다. 해당 과정을 단순하게 요약하면,
우리가 현재 [x,y]라는 구간의 반전수와 그 내부에 분포해 있는 값들을 세그먼트 트리에 저장한 상황이라면, 어떤 수 하나를 추가하면서 반전수를 갱신하고 세그먼트 트리를 업데이트할 수 있고, 반대로 어떤 수를 제거할 때에도 이러한 것이 가능하기 때문에 모스의 아이디어를 적용 가능하다. 물론, 세그의 업데이트와 쿼리를 한 번의 움직임마다 해야하기 때문에 log N이라는 인자가 추가로 붙게 된다.
물론 당신이 만약 극한의 뚫기에 자신이 있거나, 혹은 \(O(N\sqrt N logN)\) 이 충분히 빠른 시간복잡도라고 생각할 수도 있다. 이 경우에 당신은 이 글을 볼 필요가 없...는건 아니고 어쨌든 축하한다. 하지만 많은 사람들은 이 시간복잡도에 불만족할것이라 생각하고, 실제로 이보다 더욱 빠른 방법을 찾아볼 필요가 있다.
여기에서, sweepline MO가 이 문제를 어떻게 해결 가능한지 설명을 시작하겠다.
우선, 우리가 현재 [l,r]에 대한 정보를 가지고 있다고 하자. 그렇다면 인덱스를 한 칸 옮기는 것은 [l,r+1], [l,r-1], [l-1,r], [l+1,r] 이렇게 네 가지의 가짓수가 있음을 알 수 있다. 이러한 변화가 일어날 때 반전수의 동향을 계산하기 위해, 다음과 같은 함수 f,g를 도입한다:
f(l,r,x): [l,r] 내에서 x보다 큰 값들의 개수, g(l,r,x): [l,r] 내에서 x보다 작은 값들의 개수.
이제 위의 네 가지의 가짓수들에 대해서 그 반전수의 변화량이 f 혹은 g들에 의해 나타내어질 수 있음은 굉장히 자명해보이며, 실제로 [l,r]->[l,r+1]등은 \(f(l,r+1,a_{r+1})\)과 같이 표기가능함을 알 수 있다.
여기까지는 일반적인 모스가 적용되는 문제들 또한 다를 바가 없지만, 이제부터 sweepline MO가 요구하는 조건이 등장한다.
우리가 관찰할 수 있는 굉장히 좋은 성질은, 만약 우리가 F(r,x)=f(1,r,x)라고 정의하면, f(l,r,x)=F(r,x)-F(l-1,x)와 같이 쓸 수 있다는 것이다(물론, g에 대해서도 그렇다.).
현재 우리가 직면한 가장 큰 문제는, f 하나를 계산하는데에 \(O(log n)\)의 시간복잡도를 요구한다는 점이다.
그렇다면, 만약 우리가 F 하나의 값을 O(1)만에 계산 가능하다면? 그렇다면 f 또한 자명하게도 계산가능하다는 사실을 알 수 있고, 따라서 전체 문제가 풀릴 것이다. 물론, r과 x를 바로 주고 F를 O(1)만에 계산하라고 하는 것은 굉장히 터무니없는 일이다. 그러나...
굳이 우리가 F의 계산을 온라인으로 할 필요가 있는가? 우리는 일단 평소에 하던 대로 쿼리를 적당히 정렬한 뒤, 변화값을 계산하지는 않고 변화값 계산에 필요한 F들을 저장해둔다. 이제 이렇게 쌓인 \(O(N\sqrt N)\) 개의 F값 계산 쿼리를 빠르게 처리해야 한다.
이제 여기에서 "sweepline"이라는 이름의 의미를 이해할 수 있을 것이다. 우리가 원하는 것은, 각 r,x들에 대해서 F(r,x)들의 값을 계산하는 것이다. 일반적인 세그먼트 트리를 이용해서 이 문제를 푼다고 하면, r을 하나씩 높여가면서 세그먼트 트리를 업데이트해주고, 각 x들에 대해 쿼리를 날려서 F의 값을 구할 것이다. 물론 이 방법을 사용하면 F 하나를 계산하는 데에 로그의 시간복잡도가 필요하기 때문에, 이 방법으로는 F를 효과적으로 구할 수 없다.
진짜로 중요한 점은, 업데이트의 횟수가 쿼리의 횟수보다 비약적으로 적다는 점이다. 쿼리는 최대 \(O(N\sqrt N)\) 존재할 수 있는 반면, 업데이트는 O(n)개 존재한다. 이런 경우에 쓸 수 있는 조금 더 나은 자료구조가 없을까? 그렇다, 바로 버킷질을 진행하면 업데이트를 \(O(N\sqrt N)\) 만에, 쿼리를 O(1)만에 처리 가능하다! 구체적으로, 우리가 사용할 자료구조가 만약 수열 하나를 B개의 구간으로 나누었다면, 우선 각 구간 내부에서 누적합을 관리하고, 그리고 길이 B의 수열에서는 각 구간의 전체합의 누적합을 관리한다. 이 경우, 원소 하나가 바뀌는 것은 많아야 루트개의 변수의 갱신을 요구하고, 어떤 쿼리를 처리하는데에는 단 두 개의 값의 합을 요구하므로 우리가 원하는 자료구조임을 알 수 있다.
따라서, 위의 방법대로 F를 r에 대해 "스위핑"하면서 계산하고, 이렇게 계산된 F를 토대로 모스의 변화량을 계산해주면 일단 우리가 원하는 \(O(N\sqrt N)\) 이라는 시간복잡도를 달성하긴 했다. 그러나, 아마 가장 중대한 문제를 눈치챈 사람 또한 있을 것이다....
우리는 \(O(N\sqrt N)\) 개의 F값들을 계산한다고 했는데, 그렇다면 반드시 이들을 저장해야 한다. 즉, 해당 알고리즘의 공간복잡도는 \(O(N\sqrt N)\) 이라고 할 수 있다...당장 n=100000만 되어도 5000만개에 가까운 정수들을 보관해야 하고, 이는 꽤 뼈아픈 문제점이다.
하지만, 사실 조금 더 잘 생각해보면 해당 공간복잡도를 \(O(n)\)으로 최적화하는 방법이 존재함을 알 수 있다. 근데 이건 귀찮아서 다음시간에 서술하겠다.
아무튼, 실제로 ps를 하면서 \(O(N\sqrt N log N)\) 이라는 시간복잡도가 대단히 빠듯하다는 느낌을 자주 받을 수 있기 때문에, 이러한 sweepline MO를 아는 것은 굉장한 이득이 될 수 있지 않을까라고 생각한다.
다음과 같은 문제 또한 sweepline MO를 통해 해결될 수 있음을 알 수 있다. 문제의 형태가 위의 예제와 크게 다를 것이 없기 때문에, 계산하는 값들만 약간 추가해주면 충분하다. 27937번: 간단한 쿼리 문제 (acmicpc.net)
소감
ㅁㄴㅇㄹ
