Найдите значение побитового AND всех целых чисел в интервале от L до R включительно

@AtomnuyWalker · Регистрация: 12.10.2022

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

Условия
Дан массив a длины n, состоящий из чисел от 0 до 10⁶. Требуется отвечать на запросы типа «найдите значение побитового AND всех целых чисел в интервале от l до r включительно».

Напоминаем, что результат побитового AND нескольких чисел — это число, в котором бит равен единице тогда и только тогда, когда во всех этих числах соответствующий бит равен единице.

Система оценки
Всего в задаче 20 тестов (не считая примера). Каждый тест оценивается в 5 баллов.

Гарантируется, что не менее, чем в 30% тестов n,q ≤ 1000 и не менее, чем в 30% тестов ai равны 0 или 1.

Формат входных данных
Первая строка входных данных содержит два целых числа n и q (1 ≤ n ≤ 2·10⁵; 1 ≤ q ≤ 2·10⁵) — количество чисел и количество запросов соответственно.
Вторая строка содержит массив a, перечисленный слева направо, и содержит n целых чисел ai (0 ≤ ai ≤ 10⁶).
Каждая из последующих q строк содержит по два целых числа l и r — границы интервала для очередного запроса (1 ≤ l ≤ r ≤ n).

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

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

@eaa · 12.10.2022, 15:53

Python
1
2
3
4
5
6
7
8
9
10
from operator import __and__
from functools import reduce
 
n, q = map(int, input().split())
*a, = map(int, input().split())
res = []
for _ in range(q):
    left, right = map(int, input().split())
    res.append(reduce(__and__, a[left-1:right]))
print(*res, sep='\n')

@KesX · 12.10.2022, 16:29

Не проходит по времени

@eaa · 12.10.2022, 16:37

Сообщение от KesX

Не проходит по времени

а должно?

@KesX · 12.10.2022, 16:39

Ну,спасибо и за это,но вообще желательно) 7 из 20 тестов только проходит

@eaa · 12.10.2022, 16:49

KesX, какие деревья вы знаете?

@u235 · 12.10.2022, 16:50

Предлагаю рассмотреть вложенность интервалов, и/или также делать break, а не считать далее, если результат 0.

@Aael · 12.10.2022, 18:12

думаю, нужно при вводе чисел префиксные суммы считать для каждого бита - сколько раз встретился ноль до этого числа. Например для чисел: 3,7,3,2:

Code
1
2
3
4
5
6
n| x  двоичный вид | T - сколько раз встретился ноль в каждом бите
0|                 | 0,0,0
1| 3    011        | 1,0,0
2| 7    111        | 1,0,0
3| 3    011        | 2,0,0
4| 2    010        | 3,0,1

теперь запрос, например, (l,r)=(2,4) смотрим на разность T[4]-T[1]=(3,0,1) - (1,0,0)=(2,0,1) и видим что в крайних битах нулей стало больше на интервале, а в среднем - не поменялось, значит AND интервала равен 0b010=2

что-то такое

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# откуда читаем
from sys import stdin as reader
reader = open('input.txt')
from io import StringIO
reader = StringIO('5 4\n3 7 3 4 1\n1 3\n4 5\n2 5\n2 3')
 
bits = 20
n, q = map(int, reader.readline().split())
xs = map(int, reader.readline().split()[:n])
xb = [[0] * bits]
for i, x in enumerate(xs):
    print(f'{i}: {x} -> {x:0{bits}b}')
    y = x ^ ((1<<bits) - 1)
    xb.append(xb[i].copy())
    for b in range(bits):
        xb[i+1][-b-1] += y&1
        if not (y:=y>>1): break
 
print("сколько раз встретился ноль")
print(*xb, sep='\n')
 
print(f'запросы:\nl r {"bits":{bits}} x')
for _ in range(q):
    l, r, x = *map(int, reader.readline().split()), 0
    for b in range(bits):
        x = x << 1 | (xb[l-1][b] == xb[r][b])
    print(l, r, f"{x:0{bits}b}", x)
 
print('done')

Новые блоги и статьи Все статьи Все блоги /
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .

@AtomnuyWalker 0 / 0 / 0 Регистрация: 12.10.2022 Сообщений: 8

	Найдите значение побитового AND всех целых чисел в интервале от L до R включительно 12.10.2022, 15:39. Показов 2193. Ответов 7 Метки python (Все метки) Условия Дан массив a длины n, состоящий из чисел от 0 до 10⁶. Требуется отвечать на запросы типа «найдите значение побитового AND всех целых чисел в интервале от l до r включительно». Напоминаем, что результат побитового AND нескольких чисел — это число, в котором бит равен единице тогда и только тогда, когда во всех этих числах соответствующий бит равен единице. Система оценки Всего в задаче 20 тестов (не считая примера). Каждый тест оценивается в 5 баллов. Гарантируется, что не менее, чем в 30% тестов n,q ≤ 1000 и не менее, чем в 30% тестов ai равны 0 или 1. Формат входных данных Первая строка входных данных содержит два целых числа n и q (1 ≤ n ≤ 2·10⁵; 1 ≤ q ≤ 2·10⁵) — количество чисел и количество запросов соответственно. Вторая строка содержит массив a, перечисленный слева направо, и содержит n целых чисел ai (0 ≤ ai ≤ 10⁶). Каждая из последующих q строк содержит по два целых числа l и r — границы интервала для очередного запроса (1 ≤ l ≤ r ≤ n). Формат выходных данных Для каждого запроса в отдельной строке выведите одно целое число — результат ответа на очередной запрос. Примеры Входные данные: 5 4 2 5 3 4 1 1 3 4 5 2 5 2 3 Выходные данные: 0 0 0 1 0

@KesX 0 / 0 / 0 Регистрация: 12.10.2022 Сообщений: 5
	12.10.2022, 16:29
	Не проходит по времени 0

@KesX 0 / 0 / 0 Регистрация: 12.10.2022 Сообщений: 5
	12.10.2022, 16:39
	Ну,спасибо и за это,но вообще желательно) 7 из 20 тестов только проходит 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	12.10.2022, 16:49
	KesX, какие деревья вы знаете? 1

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	12.10.2022, 16:50
	Предлагаю рассмотреть вложенность интервалов, и/или также делать break, а не считать далее, если результат 0. 0