문제 링크
- http://icpc.me/
문제 출처
- Good Bye, BOJ 2019 H번
사용 알고리즘
- Segment Tree with Lazy Propagation (or Fenwick Tree)
- Bucket
- avx 혹은 bitset으로 풀리긴 합니다.
시간복잡도
- $O(QB log N + \frac {Q}{B}(N+M))$ : $B$는 버킷 사이즈
풀이
1번 쿼리는 $L ≤ i ≤ R$인 $i$에 대해 $l_i, r_i, v$ 연산을 추가로 해주는 것이라고 볼 수 있습니다.
xor 연산은 자기 자신이 역원인 연산으로, 다시 말해 같은 수를 2번 xor하면 0이 됩니다.
쿼리 1 $L R v$가 쿼리 2 $s e$에 영향을 끼친다는 것은 $L ≤ i ≤ R$인 모든 $i$에 대해 [L_i, R_i]와 [s, e]가 겹치는 원소의 개수가 홀수라는 것을 의미합니다.
이 정보는 Segment Tree with Lazy Propagation (혹은 Fenwick Tree)과 sweeping을 이용해 오프라인으로 처리할 수 있습니다. 시간 복잡도는 $O(Q^2 log N)$입니다.
시간 복잡도가 마음에 들지 않으므로 버킷질을 해봅시다. 쿼리를 $B$개씩 나눠봅시다. 버킷 사이즈는 $B$이고, 버킷의 개수는 $\lceil frac {Q}{B} \rceil$개가 됩니다.
같은 버킷 안에서만 위 방법을 적용하면 $O(\frac {Q}{B} \space * \space B^2 log N) = O(QB log N)$입니다.
서로 다른 버킷끼리의 처리 방법을 알아봅시다.
1번 쿼리를 모두 저장해두고, 2번 쿼리가 들어올 때마다 쿼리를 전부 적용하는 것을 생각해봅시다.
prefix xor을 사용하면 1번 쿼리를 $O(1)$시간에 저장할 수 있고, prefix xor을 이용해 쿼리를 모두 적용시키면 $O(N+M)$이 걸립니다.
2번 쿼리가 들어올 때마다 쿼리를 적용해주면 $O(Q(N+M))$이 걸리지만, 각 버킷이 끝날 때만 쿼리를 적용해주면 $\frac {Q}{B}(N+M)$입니다.
두 가지 방법을 모두 사용해주면 $O(QB log N + \frac {Q}{B}(N+M))$입니다.
$QB log N ≒ \frac {Q}{B}(N+M)$이 되는 $B$를 적절히 잡아주면(100, 150) 시간 안에 풀립니다.
출제자께서 특정 버킷 사이즈에 대해 저격 데이터를 준비한 것으로 알고 있는데, 버킷 사이즈를 랜덤으로 정해주면 저격을 피할 수 있습니다.