Masala #0665

Xotira 16 MB Vaqt 1000 ms
14

Gilos #2

Ikki do’st Hoshimjon va Orif ta’tilning keyingi n kuni davomida gilos terishmoqchi. Ammo do’stlar har doim ham o’zlari xohlaganchalik giloslarni tera olishmaydi va shunga qarab ularning kayfiyati o’zgarishi mumkin. Boshqacha qilib aytkanda do’stlar \(i\)-kuni gilos tersa Hoshimjonni kayfiyatiga \(a_i\), Orifnikiga esa \(b_i\) qo’shiladi \((-10^6 ≤ a_i, b_i ≤ 10^6)\).

Sizga \(l\) va \(r\) ko’rinishidagi \(q\) ta so’rov beriladi. Agar do’stlar \([l..r]\) oralig’idagi kunlarning har birida gilos teradigan bo’lsa, shu oraliqdagi do’stlarning umumiy xursandchilik koeffitsientini toping. Umumiy xursandchilik koeffitsienti quyidagicha hisoblanadi:

  • Dastlab, \(l\)-kundan oldin, har bir bolaning kayfiyati 0 ga teng bo’ladi
  • \(i\) - kuni \((l ≤ i ≤ r)\) Hoshimjonning kayfiyati \(a_i\) ga, Orifni kayfiyati \(b_i\) ga o’zgaradi
  • \(i\) - kun \((l ≤ i ≤ r)\) uchun do’stlarning xursandchilik koeffitsienti Hoshimjon va Orifni shu kundagi kayfiyatlarini kattasiga teng bo’ladi
  • umumiy xursandchilik koeffitsienti barcha \(r - l + 1\) kunlardagi xursandchilik koeffitsientlari yig’indisiga teng.

To’liqroq tushunish uchun quyida keltirilgan misolga qarang.


Kiruvchi ma'lumotlar:

Birinchi qatorda kunlar soni \(n\) va so’rovlar soni \(q\) kiritiladi \((1 ≤ n, q ≤ 10^5)\). Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, ..., a_n\) va 3-qatorda ham \(n\) ta butun son \(b_1, b_2, ..., b_n\) kiritiladi \((-10^6 ≤ a_i, b_i ≤ 10^6)\).

Keyingi \(q\) ta qatorda so’rovlar \(l\) va \(r\) butun sonlari ko’rinishida beriladi \((1 ≤ l ≤ r ≤ n)\).

1-subtask(9 ball): \(n, q ≤ 1000\).
2-subtask(7 ball): \(a_i = 1, b_i = 0, n, q ≤ 10^5\)
3-subtask(13 ball): \(a_i ≥ 0, b_i = 0, n, q ≤ 10^5\)
4-subtask(29 ball): \(b_i = 0, n, q ≤ 10^5\)
5-subtask(42 ball): \(n, q ≤ 10^5\)


Chiquvchi ma'lumotlar:

Har bir so’rov uchun umumiy xursandchilik koeffitsientini chiqaring.


Misollar
# input.txt output.txt
1
6 7
3 -5 8 -10 3 7
-4 20 9 -100 105 20
1 6
1 5
2 4
3 3
3 6
2 5
4 5
120
70
42
9
55
76
-5
Izoh:

Birinchi misoldagi uchinchi so’rovni ko’raylik, do’stlar 2..4 kunlar oralig’ida gilos terishadi.

Dastlab, Hoshimjonning ham Orifning ham kayfiyati 0 ga teng.
2-kundan so’ng: Hoshimjonni kayfiyati = -5, Orifni kayfiyati = 20, xursandlik koeffitsienti 20 (chunki 20 > -5).
3-kundan so’ng: Hoshimjonni kayfiyati = -5 + 8 = 3, Orifni kayfiyati = 20 + 9 = 29, xursandlik koeffitsienti 29 (chunki 29 > 3).
4-kundan so’ng: Hoshimjonni kayfiyati = -5 + 8 + (-10) = -7, Orifni kayfiyati = 20 + 9 + (-100) = -71, xursandlik koeffitsienti -7 (chunki -7 > -100).
Shunday qilib, umumiy xursandlik koeffitsienti = 20 + 29 + (-7) = 42.