Ավելի արագ միջակայքային հարցումներ
Տրված է
a զանգվածը, որը պարունակում է n ամբողջ թիվ։ Ունենալով այդ զանգվածը, պետք է պատասխանել q հարցումների։ Բոլոր հարցումներն ունեն հետևյալ տեսքը․ «Ո՞րն է a զանգվածի [l; r] միջակայքում բոլոր տարրերի գումարը» (երբ երկու ծայրակետերն էլ ներառյալ են, իսկ համարակալումը սկսվում է 0-ից)։ Այս անգամ թե՛ զանգվածի չափը, թե՛ հարցումների քանակը զգալիորեն ավելի մեծ են։ Կկարողանա՞ք մտածել, թե ինչպես ավելի արագ պատասխանել այդ հարցումներին։Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n — զանգվածի տարրերի քանակը (1 ≤ n ≤ )։ Հաջորդ տողում տրված են n ամբողջ թվեր, որոնք կազմում են զանգվածի տարրերը ։Այնուհետև տրվում է մեկ այլ ամբողջ թիվ
q — հարցումների քանակը (1 ≤ q ≤ )։ Հաջորդ q տողերում տրված են հարցումները տեսքով ()։Ելք
Ծրագիրը պետք է տպի
q տող, որոնցից յուրաքանչյուրում պետք է արտածել a զանգվածի միջակայքի տարրերի գումարը (ծայրակետերը ներառյալ)։Օրինակներ
Մուտք | Ելք |
8
1 2 3 4 5 6 7 8
3
0 4
5 6
5 7 | 15
13
21 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 25 MB