수열과 쿼리 39

• 배열의 구간에 등차수열을 더하는 것은, 인접한 원소의 차이값들로 새로운 배열을 만드는 테크닉을 사용하면, 구간에 일정한 값을 더하는 변환으로 바꿀 수 있고, 이것을 한번 더 적용하면 구간의 양 끝 점만 업데이트 하는 것으로 바꿀 수 있다.
• 원래 배열을 a, a의 차로 만든 배열을 b (b[i]=a[i]-a[i+1]), b의 차로 만든 배열을 c (c[i]=b[i]-b[i+1]) 이라고 하고, 대충 a3부터 a6까지 초항이 x 공차가 y인 수열을 더한다고 해보자.
  • (보통은 b의 누적합으로 a원소를 복구할 수 있도록, b[0]=a[0], b[i]=a[i]-a[i-1],.. 형태로 만들곤 했지만, 이번에는 쿼리를 처리할때 a[0]의 값이 필요 없으므로 평소와 다르게 정의했다.)
  • A는 [a1, a2, a3+x, a4+x+y, a5+x+2y, a6+x+3y, a7, a8, a9] 이 되고
  • B는 [b1, b2-x, b3-y, b4-y, b5-y, b6+x+3y, b7, b8] 이 되고
  • C는 [c1+x, c2-x+y, c3, c4, c5-y-x-3y, c6+x+3y, c7] 이 된다.
  • 일반화하면, a[l]부터 a[r]까지 초항이 x 공차가 y인 수열을 더하는 것은, c기준에서는 다음처럼 4개의 원소를 업데이트 해주는 것이 된다
    • c[l-2] += x
    • c[l-1] += -x+y
    • c[r-1] += -x-(r-l+1)y
    • c[r] += x+(r-l)y
• 그리고, a에서 등차수열을 이루는 부분 배열은, b기준에서는 같은 값을 갖는 부분 배열이 되고, c기준에서는 0으로 이루어진 부분 배열의 길이가 된다. 따라서 등차수열을 이루는 최대 부분 배열을 찾는 쿼리는, c에서 0으로 이루어진 최대 부분 배열의 길이를 찾는 것과 동일하다.
  • 등차수열을 이루는 최대 부분 배열의 길이는 {c에서 찾은 길이 + 2} 가 된다.
• 0으로 이루어진 최대 부분 배열의 길이는 각 구간마다 구간 내에서 (max_len, l_len, r_len, size) = (0으로 이루어진 최대 부분 배열의 길이, 구간의 왼쪽 끝에서부터 연속해서 나오는 0의 갯수, 구간의 오른쪽 끝에서부터 연속해서 나온는 0의 갯수, 구간의 길이) 의 4가지 값을 유지하면 두개의 구간이 합쳐진 구간에 대해서도 이 값을 O(1)로 계산이 가능하다.
• 따라서, c배열에 대해서 저 4개의 값을 관리하는 세그먼트 트리를 만들면, 업데이트와 구간 쿼리를 모두 O(logn)에 처리할 수 있다. 업데이트는 그냥 포인트 업데이트로 처리되므로, Lazy propagation 조차도 필요 없다.
• 시간 복잡도는 c배열을 만드는데에 O(n), 트리를 만드는 데에 O(n), m개의 쿼리를 처리하는 데에 O(mlogn), 그래서 총 O(n+mlogn)이다

(다이아몬드 이상은 코드 생략)

• Dependency: teflib.segmenttree.SegmentTree