조금 신기한 분할정복

1 ~ n 개의 좌표가 있고 

q 개의 쿼리가 들어오는데 $ 1 \leq l \leq r \leq n $ 인 $ l $ , $ r $ 이 주어진다고 하겠습니다.

우리가 구할 쿼리는 $ l $ , $ r $ 사이에 있는 값을 xor maximization 하는 겁니다.

왼쪽의 basis 랑 오른쪽 basis 를 합하는 방법을 저는 모르기때문에 seg를 못 쓴다고 하겠습니다.

그럼 분할정복으로 풀어야 되는데 분할정복으로 넘어가도 왼쪽 basis 랑 오른쪽 basis를 합해줘야 할 것 같습니다. 

하지만 선형적으로 계산하는 방법이 있습니다.

 

쿼리가 주어지면 처음 $ 1 $ ~ $ N $ 로 구간을 본다고 생각하겠습니다.

그럼 $ mid $ 값을 정해서 $ 1 $ ~ $ mid $ , $ (mid +1) $ ~ $ N $ 이렇게 나눌 수 있습니다.

쿼리가 두 구간 중 하나에 포함되는 쿼리라면 그냥 세부적으로 다시 돌려주면 됩니다.

하지만 두 구간을 걸치는 쿼리라면 어떻게 해야될까요

그냥 일렬로 처리하면 없어지는 부분을 생각해줘야 되기 때문에 안됩니다.

 

그래서 여기서 두 구간을 걸친다는 소리는 $ mid $ 값 좌우로 값이 1개 이상 있다는 것이기 때문에 $ mid $ 값에서 좌우로 한 구간을 두 개로 나눕니다.

그럼 여기서 생긴 모든 구간은 $ mid $ 부분을 끝 지점 아니면 시작 지점으로 가지게 됨으로 거기서부터 시작해서 쿼리를 업데이트 해주면 됩니다.

 

시간복잡도는 $ N*logN + Q*logQ $ 가 됩니다. 

 

연습문제

www.acmicpc.net/problem/18314

18314번: Non-Decreasing Subsequences

www.codeforces.com/contest/1100/problem/F