Như tên contest, ý tưởng chính của bài này là chia căn.

Ta có ~2~ solution trâu như sau:

Solution ~1~: Làm mỗi query trong ~O(n)~ bằng cách tính số điểm nằm trong mỗi đoạn sử dụng prefix sum.

Solution ~2~: Ta nhận thấy ~m~ điểm sẽ chia đoạn ~[1, n]~ ra thành ~(m + 1)~ phần, và ~2~ điểm nằm trong cùng một phần thì coi như giống nhau. Ta for qua các cặp đoạn sao cho có lẻ điểm nằm giữa chúng, và tính số đoạn có ~2~ đầu mút nằm ở ~2~ đoạn này. Chúng ta sẽ cần trả lời ~O(m^2)~ truy vấn dạng sau:

Cho 4 số ~a, b, c, d~, hãy tính số đoạn ~L_{i}, R_{i}~ thỏa mãn ~a \leq L_{i} \leq b~ và ~c \leq R_{i} \leq d~

Ta có thể tìm hết tất cả các truy vấn và xử lý offline để có được độ phức tạp ~O(log_2(n))~ trên mỗi truy vấn.

Dễ thấy cả ~2~ solution trên đều không cho ta full điểm. Tuy nhiên, với những truy vấn có ~m~ lớn, ta có thể giải bằng solution ~1~, và với những truy vấn ít điểm, ta giải bằng solution ~2~.

Cụ thể: Khi ~m \leq 100~ thì ta làm solution ~2~, còn không chúng ta làm solution ~1~

Với solution ~1~, sẽ có tối đa ~\frac{n}{100}~ truy vấn rơi vào trường hợp này, và tổng độ phức tạp là ~\frac{n^2}{100}~

Với solution ~2~, sẽ có ~\sum(\frac{m^2}{4}) \leq \sum(m * 25) \leq 25 * n~ truy vấn (người đọc tự chứng minh), mỗi truy vấn mất ~O(log_2(n))~.

Tổng độ phức tạp: ~O(\frac{n^2}{100} + n * 25 * log_2(n))~