Qahva retseptlari

Karenda $n$ ta qahva retsepti bor: $i$-retsept qahvani $l_i$ dan $r_i$ gradusgacha (ikkala chegara ham kiradi) qaynatishni tavsiya qiladi. Butun son harorat kamida $k$ ta retsept tavsiya qilsa, qulay deyiladi.

Karen $q$ ta savol beradi: $a$ dan $b$ gradusgacha (ikkala chegara ham kiradi) nechta qulay butun harorat bor?

Birinchi qatorda $n$, $k$, $q$ ($1 \le k \le n \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$). Keyingi $n$ ta qatorda $l_i$ va $r_i$, keyin $q$ ta qatorda $a$ va $b$ ($1 \le l_i \le r_i \le 200000$, $1 \le a \le b \le 200000$).

Har bir savol uchun alohida qatorda bitta son.

Ikki bosqichli prefiks. Farq massivi: har bir retsept uchun $d_{l_i} \mathrel{+}= 1$, $d_{r_i + 1} \mathrel{-}= 1$; $d$ ning prefiks yig'indisi har bir haroratni nechta retsept tavsiya qilishini beradi. Keyin $g_t = 1$, agar shu son $\ge k$ bo'lsa, va $g$ ning prefiks yig'indisi bilan har bir savol $O(1)$.

Birinchi misolda qulay haroratlar $92, 93, 94, 97$.

Manba: Codeforces, 816B-masala.