[875D] High Cry

문제 링크 : http://codeforces.com/contest/875/problem/D

문제 요약

N(1<=N<=200,000)개의 숫자(각 숫자는 10^9 이하의 자연수)가 주어진다. 이 때 주어진 배열의 연속한 구간(l~r번째 숫자)들 중, 해당 구간의 모든 숫자를 bitwise or한 숫자가 해당 구간의 최댓값보다 더 큰 구간의 개수를 세는 문제

한참 고민하다가 못 풀고 결국 답지를 봤는데, 스무님이 공유해주신 정답 코드 중 하나가 엄청 깔끔해서 정리해 둔다.

풀이 개념 자체는 비교적 간단한데, 특정 구간의 모든 값을 or한 값은 항상 그 구간의 max값보다 크거나 같다(or 값 자체에 구간의 max값도 포함되므로). 따라서, 만들어질 수 있는 모든 구간의 수(n * (n-1) / 2)에서 or값이 max값과 같은 구간의 수를 빼주면 원하는 답을 얻을 수 있다.

이제 or값이 max값과 같아지는 케이스를 찾으면 되는데, 이런 식으로 접근할 것이다.

1. n개의 숫자 각각에 대해, 그 수 x가 max값이면서 max=or인 구간의 개수를 센다(값이 중복될 수 있기 때문에, 해당 숫자가 그 구간의 가장 왼쪽 max 값인 개수만 센다)

2. x의 좌우에 있는 숫자들 중 x | y == x 라면 그 숫자 위치까지 확장해도 max=or 조건이 깨지지 않는다. 반면, x | y != x 인 숫자가 하나라도 구간에 포함되는 순간 max=or 조건이 깨지게 된다.

3. 따라서, 숫자 x에 대해 x보다 왼쪽에 있으면서 x | y != x인 가장 가까운 y의 위치 L과 오른쪽에서 마찬가지 조건의 가장 가까운 위치 R을 구하면,  숫자 x가 max이면서 max=or인 구간의 개수는 x의 위치를 p라고 할 때 (p-L+1) * (R-p+1)로 쉽게 구할 수 있다. p를 포함하면서 p 왼쪽이며 L 오른쪽인 위치 아무거나 하나 고르고, 마찬가지로 p 오른쪽이면서 R 왼쪽인 위치 아무거나 하나 골라서 구간을 만들면 그 구간은 항상 x==max && max==or 인 구간이 되기 때문.

4. 이러한 L과 R을 단순 반복으로 찾아서 풀면 O(N^2)으로 풀 수 있다. 하지만 그러면 시간초과가 나니 쓸 수 없는 방법.

5. 이걸 개선하기 위해 아래와 같은 방법을 쓸 것이다. i번째 위치에 대해 L[i]가 위에서 말한 조건을 만족하는 왼쪽 위치인데, 이 L[i]값을 재귀적인 방식으로 구한다.

5 - 1. L[i] = i로 초기화한다.

5 - 2. arr[L[i-1]] | arr[i] == arr[i] 라면, 현재 왼쪽에서 한 칸 더 왼쪽까지 확장해도 여전히 조건이 만족된다는 뜻이다. 그렇다면 결국 arr[L[i-1]] 위치에 있는 숫자를 기준으로 똑같이 arr[L[i-1]] 값과 or이 달라지는 위치까지 확장할 수 있다. 즉 이 경우 L[i] = L[L[i]-1]로 변경해준다. 이 과정을 arr[L[i-1]] | arr[i] != arr[i]일 때까지 반복해준다.

6. R[i]도 마찬가지 방법으로 구할 수 있다. 이 때, L[i] 값의 경우 max값이 여러 개 있을 때 중복해서 세지 않기 위해 i번째 값이 그 구간의 맨 왼쪽 max값이라는 조건을 달았으므로, arr[L[i-1]] < arr[i] 인지도 확인해줘야 한다.

이렇게 L[i], R[i]를 구하면 N개 원소를 순회하며 개수를 빼주기만 해도 답을 구할 수 있다. or값이 달라지기 위해서는 최소한 비트값이 하나라도 달라져야 하고, 10^9아래 값이므로 비트는 최대 30번 정도 까지만 달라질 수 있다. 즉, L[i] 와 R[i]를 반복해서 갱신해들어가는 반복문은 많아야 30번 정도만 실행될 수 있다. 따라서 전체 시간복잡도는 O(NlogC) 이다(C는 원소의 최댓값(10^9)). 실제로 실행해보면 굉장히 빨라서 거의 O(N)처럼 동작한다.