#28434 Same Range 뇌풀이

뇌풀이인 이유는 구현에 실패했기 때문이다.

대략 140줄 정도 짜고 ide 껐다.

 

정해는 특수한 형태의 세그먼트 트리를 사용하면 풀 수 있다고 한다.

문제를 분할정복으로 해결해보자.

 

각 분할하는 문제마다 결국 mid를 넘는 배열들에 대해서만 문제를 풀어주면 된다.

 

예제

4
1 2 1 3
3 1 2 1

로 문제를 설명해보면

 

이렇게 mid로 나눠버린다.

 

그러고 양쪽 방향으로 prefix max,min suffix max,min을 구한다.

 

그럼 문제는 이렇게 환원되는데

 

왼쪽 (Amax, Amin,Bmax,Bmin)원소와 오른쪽 (Amax,Amin,Bmax,Bmin)원소를 적절히 골라서 합쳤을 때,

max=min이 되어야 한다.

 

물론 모든 쌍을 순회화면 O(n^2)이므로 빠르게 할 방법을 생각해봐야하는데,

max의 suffix와 prefix들은 증가하고

min의 suffix와 prefix들은 감소한다.

 

이 단조성을 이용해서 빠르게 밀어서 더해주면 된다.

근데 이 과정이 매우 고통스럽다.

 

 

일단 배열에서 l~r까지를 분할정복한다고 했을때

mid+1번째 원소부터 r까지 v[mid+1]~v[r]까지를 오른쪽 원소를 고정하고, 가능한 왼쪽원소의 개수를 더한다.

이때 현재보는 i번째 v[i]를 보고 있다고 해보자.

premax_A[i]와 premax_B[i]를 살펴보자.

 

예제를 예시로 들어서 i=3을 살펴보면 premax_A[i]=1이고, premax_B[i]=3이다.

 

그럼 왼쪽 구간 즉 l~mid까지 임의의 원소 j에서 sufmax_A[j]가 1이하인 원소들은 합쳤을때 max가 1이되고, 

1초과인 원소들은 max가 sufmax_A[j]가 된다.

 

즉 max(sufmax_A[j],premax_A[i])를 풀어쓴 것이다.

 

마찬가지로 B도 성립한다.

그럼 우리는 단조성이 보장되기 때문에 다음과 같은 사실을 알 수있다.

 

이렇게 세구간으로 나눠짐을 볼 수 있다.

 

그럼 다음과 같을 때 Amax=Bmax이다.

 

1번 구간 = 이 구간에서는 premax_A[j]와 premax_B[j]를 따라간다. 따라서 premax_A[j]=premax_B[j]면 조건을 만족한다.

2번 구간 = 이 구간에서는 A는 premax_A[j]를 따라가고 B는 premax_B[i] (j가 아니고 i임에 유의하자)를 따라간다.

따라서 pre_A[j]=premax_B[i]인 구간이 만족한다. 

3번 구간 A,B모두 premax_A[i]와 premax_B[i]를 따라간다 따라서 premax_A[i]=premax_B[i]일때만 전체구간으로 ok.

 

1번 구간은 띄엄띄엄 나오고, 2번 구간에서 가능한 값은 연속되게 나오고, 3번 구간은 전체가 되거나 안된다.

즉 우리는 1번 구간에서 중요한 것이 premax_A[j]=premax_B[j]인 여러 원소들. 2번 구간은 구간 하나만 구하면 되니까 구현할 수 있다.

 

따라서 우리는  premax_A[j]=premax_B[j]인 것을 또 다른 누적합으로 전처리해두면 O(1)에 구할수 있다.(...)

 

마찬가지로 Amin=Bmin인 구간도 구할수 있을 것이다.

그럼 max 에서 1 2 3 세가지 구간으로 나누어졌고,

min에서 1 2 3 세가지 구간으로 나누어졌다...

 

그럼 총 9가지 구간으로 나누어질 텐데,

이걸 잘 나누고, 누적합으로 잘 더하고 하면 이론상(짜다 포기하긴 했는데... ) O(n)에 문제가 풀린다.

 

 

따라서 O(nlogn).

 

그냥 정해로 풀자.

구현 난이도가 말이 안되는 풀이이다...