Найдите значение побитового 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')

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

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

	Найдите значение побитового AND всех целых чисел в интервале от L до R включительно 12.10.2022, 15:39. Показов 2190. Ответов 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