Kuriyama toshlari

Kuriyamada $n$ ta tosh bor, $i$-toshning narxi $v_i$. U ikki turdagi savol beradi:

1. 1 l r — $v_l + v_{l+1} + \ldots + v_r$ yig'indisi.
2. 2 l r — toshlar narxi bo'yicha o'sish tartibida saralanganda, $l$-dan $r$-gacha toshlar narxlari yig'indisi.

Har bir savolga javob bering.

Birinchi qatorda $n$ ($1 \le n \le 10^5$). Ikkinchi qatorda $n$ ta butun son $v_i$ ($1 \le v_i \le 10^9$). Uchinchi qatorda $m$ ($1 \le m \le 10^5$). Keyingi $m$ ta qatorda $t$, $l$, $r$ ($t \in \{1, 2\}$, $1 \le l \le r \le n$).

Har bir savol uchun alohida qatorda bitta son.

Ikkita prefiks massivi tuzing: biri asl massiv uchun, ikkinchisi saralangan nusxa uchun. Har bir savol — tegishli massivda $p_r - p_{l-1}$. Har bir savolda qayta saralash $O(m \cdot n \log n)$ — juda sekin.

Yig'indi $10^{14}$ gacha yetadi — 64 bitli tur kerak. Birinchi misolda saralangan massiv $2, 2, 4, 6, 7, 7$, birinchi savol $4 + 6 + 7 + 7 = 24$.

Manba: Codeforces, 433B-masala.