Рубрики

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

Дан массив размера 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