АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Бүхэл тоон элементүүдээс тогтох массив өгөгдсөн бөгөөд чи дараах үйлдлүүдийг гүйцэтгэх X бүхэл тооноос тогтсон

q ширхэг асуулгуудад хариулах ёстой.

  1. Уг X тоог массивын элемент бүр дээр нэмж, дараагийн асуулгуудад бэлдэж массивыг шинэчлэх

  2. Массивын элемент бүрийн абсолют (Модуль) утгыг олж, тэдгээрийн нийлбэрийг шинэ мөрөнд хэвлэх

Санамж: Бодлогын оролт гаралтын хэмжээ маш том учраас асуулга бүрт хариулж амжих зөв шийдлийг олох шаардлагатай болно. 

Оролтын хэлбэр

Эхний мөрөнд массивын элементийн тоог илэрхийлэх n тоо өгөгдөнө.

Хоёрдугаар мөрөнд n ширхэг массивын элементүүд зайгаар тусгаарлагдан өгөгдөнө.

Гуравдугаар мөрөнд асуулгын тоо болох q тоо өгөгдөнө.

Дөрөвдүгээр мөрөнд хоорондоо зайгаар тусгаарлагдсан q ширхэг асуулгыг илэрхийлэх X тоонууд өгөгдөнө.

Хязгаарлалт

 1 < = n <= 5*10^5

 1 < = q <= 5*10^5

 -2000 <= Arr[i] <= 2000 Энд 0 <= i < n

-2000 <= queries[j] <= 2000  Энд 0 <= j < q

Гаралтын хэлбэр 

Асуулга бүрийн хувьд массивын бүх элементүүдийн абсолют утгуудын нийлбэрийг шинэ мөрөнд хэвлэнэ.

Жишээ оролт

3

-1 2 -3

3

1 -2 3

Жишээ гаралт

5

7

6

Тайлбар

Асуулга 0: X=1 

Массив: [-1, 2, -3] -> [0, 3, -2] болно.
Массив : [0, 3, -2] -> [-2, 1, -4]

Шинэчлэгдсэн массивын абсолют утгуудын нийлбэрийг олбол: |0|+|3|+|-2|=0+3+2=5

Асуулга 1: X=-2

Шинэчлэгдсэн массивын абсолют утгуудын нийлбэрийг олбол: |-2|+|1|+|-4|=2+1+4=7

Асуулга 2: X=3

Массив : [-2, 1, -4] -> [1, 4, -1]

Шинэчлэгдсэн массивын абсолют утгуудын нийлбэрийг олбол: |1|+|4|+|-1|=1+4+1=6

Орчуулсан : Хөвсгөл аймгийн Ирээдүй сургуулийн багш Д.Батмөнх