Codeforces Round 495 (Div. 2) |
---|
Закончено |
У Сони есть массив $$$a_1, a_2, \ldots, a_n$$$ из $$$n$$$ чисел и неотрицательное целое число $$$x$$$. Ей нужно выполнить $$$m$$$ запросов двух типов:
Сможете ли вы помочь Соне выполнить все запросы?
Побитовое ИЛИ — это бинарная операция над парой неотрицательных целых чисел. Для подсчета побитового ИЛИ двух чисел надо рассмотреть запись обоих чисел в двоичной системе счисления. Результат — это такое число, в двоичном представлении которого в каждом разряде стоит единица если единица находится в двоичной записи хотя бы одного из аргументов. Например, $$$10$$$ OR $$$19$$$ = $$$1010_2$$$ OR $$$10011_2$$$ = $$$11011_2$$$ = $$$27$$$.
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$x$$$ ($$$1\leq n, m\leq 10^5$$$, $$$0\leq x<2^{20}$$$) — количество чисел, запросов и константа для второго типа запросов соответственно.
Вторая стркоа содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i<2^{20}$$$) — числа массива.
Далее, в $$$m$$$ строках заданы запросы, по одному в строке. Строка имеет вид:
Для каждого запроса второго типа выведите количество подмассивов на отрезке, что побитовое ИЛИ их чисел не меньше $$$x$$$.
4 8 7
0 3 6 1
2 1 4
2 3 4
1 1 7
2 1 4
2 1 3
2 1 1
1 3 0
2 1 4
5
1
7
4
1
4
5 5 7
6 0 3 15 2
2 1 5
1 4 4
2 1 5
2 3 5
2 1 4
9
7
2
4
В первом примере задан массив [$$$0$$$, $$$3$$$, $$$6$$$, $$$1$$$] и запросы:
Во втором примере задан массив [$$$6$$$, $$$0$$$, $$$3$$$, $$$15$$$, $$$2$$$] и запросы:
Название |
---|