[BOJ] 1168번: 조세퍼스 문제 2

https://www.acmicpc.net/problem/1168

queue나 deque를 이용하면 O(N^2) 풀이법은 쉽게 고안해낼 수 있으나, N <= 100000인 이 문제에서는 적용할 수 없습니다. 대신 Binary indexed tree를 사용하면 되는데, 우선 해당하는 자리에 사람이 있으면 1, 제거됐으면 0이라고 해봅시다. 그러면 N=7, M=3에서 리스트는

1 1 1 1 1 1 1

1 1 0 1 1 1 1

1 1 0 1 1 0 1

1 0 0 1 1 0 1

1 0 0 1 1 0 0

1 0 0 1 0 0 0

0 0 0 1 0 0 0

0 0 0 0 0 0 0

이 될 것입니다. 배열의 시작 인덱스를 편의상 1이라고 할 때 sum(k)를 L[1]+L[2]+L[3]+..+L[k]이라고 하고, 직전에 제거된 위치가 i라고 할 때, 잘 생각해보면 그 다음에 제거될 위치는 L[j]-L[i] = M을 만족하는 가장 작은 j입니다. 저희는 이러한 sum 함수를 binary indexed tree로 O(k) 대신 O(lgN)에 계산할 수 있고, j 또한 binary search로 O(NlgN) 대신 O(lg^2N)으로 계산할 수 있습니다.

j의 범위가 선형이 아니라 원형인 점에 조금 주의해야합니다.

https://github.com/blisstoner/BOJ/blob/master/1168.cpp