2-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"E" Изучение массива
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Вася обожает массивы. Поэтому родители на день рождения подарили ему массив a, состоящий из чисел 1 и  - 1. Вася сразу же начал его изучать.

Так как Вася также очень любит нули, он решил брать разные подотрезки a[li, ..., ri] массива a и искать в них длину максимального подотрезка с суммой 0. Если такого подотрезка нет, он считает ответ равным 0. Вася написал на бумажке q отрезков [li, ri] и теперь хочет найти сумму ответов на них.

Приведем ответы на выбранные Васей подотрезки в тестовом примере:

  • подотрезок [1, 5]: максимальный подотрезок с суммой 0 — [2, 5];
  • подотрезок [1, 3]: максимальный подотрезок с суммой 0 — [2, 3];
  • подотрезок [2, 4]: максимальный подотрезок с суммой 0 — [2, 3];
  • подотрезок [3, 4]: подотрезка с суммой 0 нет;
  • подотрезок [3, 5]: максимальный подотрезок с суммой 0 — [4, 5].

Итого, суммарная длина всех искомых подотрезков в этом тесте равна 4 + 2 + 2 + 0 + 2 = 10.

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 1000).

Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержится число n — количество элементов массива (1 ≤ n ≤ 105).

В следующей строке содержится n целых чисел ai — элементы массива (ai =  - 1 или ai = 1).

В следующей строке содержится число q — количество подотрезков, выписанных Васей (1 ≤ q ≤ 105).

В каждой из следующих q строк содержится два числа li, ri — левая и правая границы i-го подотрезка соответственно (1 ≤ li ≤ ri ≤ n)

Гарантируется, что сумма n во всех тестах одних входных данных не превосходит 105, а также сумма q во всех тестах одних входных данных не превосходит 105.

Формат выходных данных

Для каждого теста выведите ответ на него — сумму ответов для всех q подотрезков.

Примеры
Входные данные
1
5
1 -1 1 1 -1
5
1 5
1 3
2 4
3 4
3 5
Выходные данные
10
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.