Masala #1151
Noodatiy so'rov
Davron massivlar bilan o'yin o'ynashni juda yaxshi bo'radi. Davronda N uzunlikka ega \(c_1, c_2, ..., c_N\)massivi bor. Bir kuni u quyidagi o'yinni o'ynamoqchi bo'ldi, massivning [L, R] oralig'ini kesib oladi va summasi 0 ga teng bo'ladigan va bir biri bilan kesishmaydigan qism massivlar sonini aniqlaydi. Lekin bu ishni bajarish juda ko'p vaqt olgani uchun Davron sizlardan yordam so'ramoqda. Davronning ishini tezlashtiruvchi dastur tuzing.
Kirish faylining birinchi qatorida N natural soni mavjud \((1 \le N \le 4*10^5)\).
Keyingi qatorda N ta butun son - massiv elementlari joylashgan \((-10^9 \le c_i \le 10^9)\).
Uchinchi qatorda so'rovlar soni - Q kiritiladi \((1 \le Q \le 4*10^5)\).
Keyingi Q ta qatorning har birida ikkita butun son L va R mavjud \((1 \le L \le R \le N)\).
Chiqish fayliga har bir so'rov uchun alohida qatorda massivning [L, R] oralig'ida yig'indisi 0 ga teng bo'lgan qism massivlar sonini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
10 1 2 -3 0 1 -4 3 2 -1 1 3 1 10 1 5 2 9 |
4 2 2 |
Qism massiv - massivning o'ng va chap tomonidan 0 yoki bir nechta elementlarini qirqib tashlashdan hosil bo'lgan massiv.
Masalan bizga berilgan massiv [1, 2, 3, 4, 5] bo'lsin. Bunday holatda ushbu massivning qism massivlari deb quyidagilarni aytishimiz mumkin: [1, 2], [3, 4, 5], [2, 3, 4] ... . [1, 2, 4], [3, 5] lar esa qism massiv bo'la olmaydi.
Birinchi misolga izoh:
1-so'rovda: [{1, 2, -3}, {0}, {1, -4, 3}, 2, {-1, 1}]
2-so'rovda: [{1, 2, -3}, {0}, 1]
3-so'rovda: [2, -3, {0}, {1, -4, 3}, 2, -1, 1]
Telegram kanalimizga obuna bo'ling