Найти количество различных чисел в диапазоне

28.12.2019Конкурентное программирование, Массивы, Немного магии, Разделяй и властвуй

Дан массив размера N, содержащий только числа от 0 до 63, и вам задают Q запросов относительно него.

Запросы следующие:

1 XY т.е. изменить элемент с индексом X на Y
2 LR т.е. напечатать количество различных элементов, присутствующих между L и R включительно

Примеры:

Input:
N = 7
ar = {1, 2, 1, 3, 1, 2, 1}
Q = 5
{ {2, 1, 4},
  {1, 4, 2},
  {1, 5, 2},
  {2, 4, 6},
  {2, 1, 7} }
Output:
3
1
2

Input:
N = 15
ar = {4, 6, 3, 2, 2, 3, 6, 5, 5, 5, 4, 2, 1, 5, 1}
Q = 5
{ {1, 6, 5},
  {1, 4, 2},
  {2, 6, 14},
  {2, 6, 8},
  {2, 1, 6} };

Output:
5
2
5

Предварительные условия: дерево сегментов и управление битами
Подходить:

Сформированная в вопросе bitMask будет обозначать наличие i-го числа или нет, мы выясним, что, проверяя i-й бит нашей bitMask, если i-й бит включен, это означает, что i-й элемент присутствует, в противном случае его нет.
Создайте классическое дерево сегментов, и каждый из его узлов будет содержать битовую маску, которая используется для декодирования количества отдельных элементов в этом конкретном сегменте, которое определяется конкретным узлом.
Постройте дерево сегментов снизу вверх, поэтому битовую маску для текущего узла дерева сегментов можно легко рассчитать, выполнив операцию побитового ИЛИ для битовых масок правого и левого дочерних узлов этого узла. Листовые узлы будут обрабатываться отдельно. Обновление также будет сделано таким же образом.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ Программа для поиска
// элементы в диапазоне
#include <bits/stdc++.h>

using namespace std;

// Функция для выполнения запросов в диапазоне

long long query(int start, int end, int left, int right,

int node, long long seg[])

{

// Нет перекрытия

if (end < left || start > right) {

return 0;

}

// Полное перекрытие

else if (start >= left && end <= right) {

return seg[node];

}

// Parital Overlap

else {

int mid = (start + end) / 2;

// Находим ответ

// для левого ребенка

long long leftChild = query(start, mid, left,

right, 2 * node, seg);

// Находим ответ

// для правильного ребенка

long long rightChild = query(mid + 1, end, left,

right, 2 * node + 1, seg);

// Объединяем битовые маски

return (leftChild | rightChild);

}

// Функция для выполнения операции обновления
// в сегменте seg

void update(int left, int right, int index, int Value,

int node, int ar[], long long seg[])

{

if (left == right) {

ar[index] = Value;

// Формирование битовой маски

seg[node] = (1LL << Value);

return;

}

int mid = (left + right) / 2;

if (index > mid) {

// Обновление левого ребенка

update(mid + 1, right, index, Value, 2 * node + 1, ar, seg);

}

else {

// Обновление правильного ребенка

update(left, mid, index, Value, 2 * node, ar, seg);

}

// Обновление BitMask

seg[node] = (seg[2 * node] | seg[2 * node + 1]);

}

// Построение дерева сегментов

void build(int left, int right, int node, int ar[],

long long seg[])

{

if (left == right) {

// Построение начальной битовой маски

seg[node] = (1LL << ar[left]);

return;

}

int mid = (left + right) / 2;

// Создание левого сегмента

build(left, mid, 2 * node, ar, seg);

// Строим правильное дерево сегментов

build(mid + 1, right, 2 * node + 1, ar, seg);

// Формирование битовой маски

seg[node] = (seg[2 * node] | seg[2 * node + 1]);

}

// Сервисная функция для ответа на запросы

void getDistinctCount(vector<vector<int> >& queries,

int ar[], long long seg[], int n)

{

for (int i = 0; i < queries.size(); i++) {

int op = queries[i][0];

if (op == 2) {

int l = queries[i][1], r = queries[i][2];

long long tempMask = query(0, n - 1, l - 1,

r - 1, 1, seg);

int countOfBits = 0;

// Подсчет установленных битов, которые обозначают

// отдельные элементы

for (int i = 63; i >= 0; i--) {

if (tempMask & (1LL << i)) {

countOfBits++;

}

cout << countOfBits << '\n';

}

else {

int index = queries[i][1];

int val = queries[i][2];

// Обновление значения

update(0, n - 1, index - 1, val, 1, ar, seg);

}

// Код драйвера

int main()

{

int n = 7;

int ar[] = { 1, 2, 1, 3, 1, 2, 1 };

long long seg[4 * n] = { 0 };

build(0, n - 1, 1, ar, seg);

int q = 5;

vector<vector<int> > queries = {

{ 2, 1, 4 },

{ 1, 4, 2 },

{ 1, 5, 2 },

{ 2, 4, 6 },

{ 2, 1, 7 }

};

getDistinctCount(queries, ar, seg, n);

return 0;

}

python3

# Python3 Программа для поиска
# элементов в диапазоне

# Функция для выполнения запросов в диапазоне

def query(start, end, left,

right, node, seg):

# Нет перекрытия

if (end < left or start > right):

return 0

# Полное перекрытие

elif (start >= left and

end <= right):

return seg[node]

# Parital Overlap

else:

mid = (start + end) // 2

# Нахождение ответа

# для левого ребенка

leftChild = query(start, mid, left,

right, 2 * node, seg)

# Нахождение ответа

№ для правильного ребенка

rightChild = query(mid + 1, end, left,

right, 2 * node + 1, seg)

# Объединение битовых масок

return (leftChild | rightChild)

# Функция для выполнения операции обновления
# в сегменте seg

def update(left, right, index,

Value, node, ar, seg):

if (left == right):

ar[index] = Value

# Формирование битовой маски

seg[node] = (1 << Value)

return

mid = (left + right) // 2

if (index > mid):

# Обновление левого ребенка

update(mid + 1, right, index,

Value, 2 * node + 1, ar, seg)

else:

# Обновление правильного ребенка

update(left, mid, index,

Value, 2 * node, ar, seg)

# Обновление BitMask

seg[node] = (seg[2 * node] |

seg[2 * node + 1])

# Построение дерева сегментов

def build(left, right, node, ar, eg):

if (left == right):

# Построение начальной битовой маски

seg[node] = (1 << ar[left])

return

mid = (left + right) // 2

# Построение левого сегмента

build(left, mid, 2 * node, ar, seg)

# Построение правильного сег-дерева

build(mid + 1, right,

2 * node + 1, ar, seg)

# Формирование битовой маски

seg[node] = (seg[2 * node] |

seg[2 * node + 1])

# Сервисная функция для ответа на запросы

def getDistinctCount(queries, ar, seg, n):

for i in range(len(queries)):

op = queries[i][0]

if (op == 2):

l = queries[i][1]

r = queries[i][2]

tempMask = query(0, n - 1, l - 1,

r - 1, 1, seg)

countOfBits = 0

# Подсчет установленных битов, которые обозначают

# отдельные элементы

for i in range(63, -1, -1):

if (tempMask & (1 << i)):

countOfBits += 1

print(countOfBits)

else:

index = queries[i][1]

val = queries[i][2]

# Обновление значения

update(0, n - 1, index - 1,

val, 1, ar, seg)

Код водителя

if __name__ == '__main__':

n = 7

ar = [1, 2, 1, 3, 1, 2, 1]

seg = [0] * 4 * n

build(0, n - 1, 1, ar, seg)

q = 5

queries = [[ 2, 1, 4 ],

[ 1, 4, 2 ],

[ 1, 5, 2 ],

[ 2, 4, 6 ],

[ 2, 1, 7 ]]

getDistinctCount(queries, ar, seg, n)

# Этот код предоставлен Мохитом Кумаром

Выход:

3
1
2

Временная сложность: O (N + Q * Log (N))

Рекомендуемые посты:

Найти количество различных чисел в диапазоне

0.00 (0%) 0 votes