Задача №3313. Количество нулей на интервале

@Senoki · Регистрация: 24.09.2021

Студворк — интернет-сервис помощи студентам

Реализуйте структуру данных для эффективного вычисления количества нулей в отрезке массива.

Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление количества нулей.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).'

Выходные данные
Для каждого запроса выведите количество нулей на соответствующем участке массива. Числа выводите в одну строку через пробел.
Примеры
входные данные
5
0 0 0 0 2
2
2 3
2 5
выходные данные
2 3
Пыталась решать в лоб, спомощью срезов и функции list.count(0), но код не прошел по времени. Можно ли написать программу с использованием префиксных сумм? Если да, то как?

@eaa · 15.09.2022, 19:22

Python
1
2
3
4
5
6
7
from itertools import accumulate
 
input()
*pref, = accumulate((not x for x in map(int, input().split())), initial=0)
for _ in range(int(input())):
    lo, hi = map(int, input().split())
    print(pref[hi] - pref[lo - 1], end=' ')

Новые блоги и статьи Все статьи Все блоги /
Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .

@Senoki 6 / 6 / 0 Регистрация: 24.09.2021 Сообщений: 125

	Задача №3313. Количество нулей на интервале 15.09.2022, 18:55. Показов 3369. Ответов 1 Метки нет (Все метки) Реализуйте структуру данных для эффективного вычисления количества нулей в отрезке массива. Входные данные В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве. Во второй строке вводятся N чисел от 0 до 100000 — элементы массива. В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление количества нулей. В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).' Выходные данные Для каждого запроса выведите количество нулей на соответствующем участке массива. Числа выводите в одну строку через пробел. Примеры входные данные 5 0 0 0 0 2 2 2 3 2 5 выходные данные 2 3 Пыталась решать в лоб, спомощью срезов и функции list.count(0), но код не прошел по времени. Можно ли написать программу с использованием префиксных сумм? Если да, то как? 0

Задача №3313. Количество нулей на интервале

Решение