Задан массив длины $$$2^n$$$. Элементы массива пронумерованы от $$$1$$$ до $$$2^n$$$.
Надо обработать $$$q$$$ запросов к массиву. В $$$i$$$-м запросе будет дано целое число $$$k$$$ ($$$0 \le k \le n-1$$$). Чтобы обработать запрос, надо сделать следующее:
Например, если массив $$$a$$$ равен $$$[-3, 5, -3, 2, 8, -20, 6, -1]$$$, а $$$k = 1$$$, то запрос обрабатывается так:
Тогда массив становится равен $$$[-3, 2, -3, 5, 6, -1, 8, -20]$$$. Подотрезок с максимальной суммой — это $$$[5, 6, -1, 8]$$$, и ответ на запрос равен $$$18$$$.
Обратите внимание, что запросы изменяют массив, т. е. после выполнения запроса массив не возвращается в изначальное состояние, и следующий запрос будет применен к измененному массиву.
В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 18$$$).
Во второй строке записаны $$$2^n$$$ целых чисел $$$a_1, a_2, \dots, a_{2^n}$$$ ($$$-10^9 \le a_i \le 10^9$$$).
В третьей строке записано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$).
Затем следуют $$$q$$$ строк, в $$$i$$$-й из них записано одно целое число $$$k$$$ ($$$0 \le k \le n-1$$$), описывающее $$$i$$$-й запрос.
На каждый запрос выведите одно целое число — наибольшую сумму среди всех непрерывных подотрезков массива (включая пустой подотрезок) после обработки запроса.
3 -3 5 -3 2 8 -20 6 -1 3 1 0 1
18 8 13
Преобразование массива в примере: $$$[-3, 5, -3, 2, 8, -20, 6, -1] \rightarrow [-3, 2, -3, 5, 6, -1, 8, -20] \rightarrow [2, -3, 5, -3, -1, 6, -20, 8] \rightarrow [5, -3, 2, -3, -20, 8, -1, 6]$$$.
Название |
---|