Yig'indisi x ga teng qism-massivlar

$n$ ta butun sondan iborat massiv va $x$ soni berilgan. Yig'indisi aynan $x$ ga teng bo'lgan bo'sh bo'lmagan qism-massivlar sonini toping.

Birinchi qatorda $n$ va $x$ ($1 \le n \le 2 \cdot 10^5$, $|x| \le 10^9$). Ikkinchi qatorda $n$ ta butun son ($|a_i| \le 10^9$).

Bitta son — qism-massivlar soni.

$[l, r]$ yig'indisi $x$ ga teng $\iff$ $p_{l-1} = p_r - x$. Chapdan o'ngga yurib, har bir $r$ uchun avval uchragan prefikslar orasida $p_r - x$ nechta ekanini qo'shing, keyin $p_r$ ni sanoqqa kiriting. Sanoq uchun lug'at (map/dict) yoki prefikslarni saralab, teng qiymatlarni binar qidiruv bilan sanash mumkin.

Manfiy sonlar bor, shuning uchun ikki ko'rsatkich usuli ishlamaydi. Prefikslar $2 \cdot 10^{14}$ gacha, javob $2 \cdot 10^{10}$ gacha yetadi.

Manba: CSES, 1661-masala.