eolymp
Yarışlar

Дерево Фенвика

Dima və böyük ölçülü massiv

Dimanın anası oğluna n uzunluqlu massiv hədiyyə etdi. Bu massiv heç də sadə deyil, o qeyri adidir. Dima massivdən iki ədəd seçə bilər : id (1in, -1000d1000) və bu halda i indeksli bütün elementlər möcüzəli şəkildə d-ə bərabər olacaq. Beləliklə, Dima öz massivi ilə oynayır, anası isə vaxtaşırı ona suallar verir : massivdə indeksi f-dən t-dək olan ədədlərin cəmi nəyə bərabərdir? Lakin, anası çox məşğul olduğundan həmişəki kimi tez-tez suallar verə bilmir. O, 1000-dən artıq sual verə bilmədi. Dima bu sualların öhdəsindən asanlıqla gəldi. Bəs siz bacararsız?

Giriş verilənləri

Birinci sətirdə nq (1n106, 1q5 ·105) tam ədədləri verilmişdir ki, bunlar uyğun olaraq - massivdəki elementlərin sayını və əməliyyatlar ilə sorğularının sayının cəmini göstərir. Növbəti sətirdə, massivin başlanğıc şəkli olan a1, a2, ..., an (-1000ai1000) hədlərini göstərən n ədəd verilir. Növbəti q sətirdə əməliyyatlar və sorğular verilir. Sətrin birinci simvolu + və ya ? ola bilər. Əgər sətir + işarəsi ilə başlayırsa, bu əlavə etmə əməliyyatıdır. Sonra yuxarıda verilən məhdudiyyətlər daxilində id ədədləri gəlir. Əgər sətir ? işarəsi ilə başlayırsa, bu sorğudur. Ardınca ft (1f, tn) ədədləri gəlir.

Çıxış verilənləri

Hər bir sorğu üçün massivdə indeksi f-dən t-dək olan ədədlərin cəmi hər sətirdə bir nəticə olmaqla ekrana verin.

Zaman məhdudiyyəti 7 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3 3
1 2 3
? 1 3
+ 3 -1
? 1 3
Çıxış verilənləri #1
6
5
Müəllif Егор Куликов
Mənbə Зимняя Школа Харьков 2012