Рубрики

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

Учитывая массив размера N, изначально состоит только из нулей. Задача состоит в том, чтобы применить данную операцию q раз и найти количество различных чисел в массиве, кроме нулей.

Формат операции: update (l, r, x) :: update a [i] = x для всех (l <= i <= r).

Примеры:

Input : N = 5, Q = 3,
update(1, 3, 1)
update(0, 1, 2)
update(3, 3, 3)
Output : 3
Explanation : Initially array is {0, 0, 0, 0, 0}. After
applying the operation for the first time array becomes {0, 1, 1, 1, 0}.
After applying the operation for the second time the array becomes
{2, 2, 1, 1, 0}. After applying the operation for the third time the array
becomes {2, 2, 1, 3, 0}. So, a number of different numbers expect zero are 3.

Input : N = 5, Q = 3,
update(1, 1, 4)
update(0, 1, 2)
update(1, 4, 5)
Output : 2

Подходить :
Каждая операция предлагает обновление диапазона, поэтому попробуйте обновить массив, используя ленивое распространение . После применения операции Q раз с использованием ленивого распространения вызовите функцию, которая находит количество различных чисел в массиве. Эта функция использует set, чтобы найти количество разных чисел.
Операции обновления и запроса аналогичны операциям в дереве сегментов с некоторыми изменениями. Всякий раз, когда запрос на обновление выполняется в дереве сегментов, все узлы, связанные с текущим узлом, также обновляются, тогда как при отложенном распространении эти узлы будут обновляться только при необходимости, т.е. мы создаем массив lazy [] размера, равного данному массиву. элементы которого будут инициализированы равными 0, что означает, что для какого-либо узла изначально нет обновлений, а любое ненулевое значение в lazy [i] указывает на то, что у узла i имеется ожидающее обновление, которое будет обновляться только при запросах (когда это необходимо).

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

C ++

// Реализация CPP для вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
#define N 100005

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

int lazy[4 * N];

  
// Для хранения разных номеров

set<int> se;

  
// Функция для обновления в диапазоне [x, y) с заданным значением

void update(int x, int y, int value, int id, int l, int r)

{

    // проверить вне границы

    if (x >= r or l >= y)

        return;

  

    // проверка на полное перекрытие

    if (x <= l && r <= y) {

        lazy[id] = value;

        return;

    }

  

    // найти среднее число

    int mid = (l + r) / 2;

  

    // проверка на наличие ожидающих обновлений

    if (lazy[id])

        lazy[2 * id] = lazy[2 * id + 1] = lazy[id];

  

    // make lazy [id] = 0, чтобы не было ожидающих обновлений

    lazy[id] = 0;

  

    // вызов двух дочерних узлов

    update(x, y, value, 2 * id, l, mid);

    update(x, y, value, 2 * id + 1, mid, r);

}

  
// Функция для поиска ненулевых целых чисел в диапазоне [l, r)

void query(int id, int l, int r)

{

    // если идентификатор содержит положительное число

    if (lazy[id]) {

        se.insert(lazy[id]);

        // Нет необходимости видеть детей,

        // потому что все интервалы имеют одинаковый номер

        return;

    }

  

    // проверка на выход за пределы

    if (r - l < 2)

        return;

  

    // найти среднее число

    int mid = (l + r) / 2;

  

    // вызов двух дочерних узлов

    query(2 * id, l, mid);

    query(2 * id + 1, mid, r);

}

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

int main()

{

    // размер массива и количество запросов

    int n = 5, q = 3;

  

    // Обновить операцию для l, r, x, id, 0, n

    update(1, 4, 1, 1, 0, n);

    update(0, 2, 2, 1, 0, n);

    update(3, 4, 3, 1, 0, n);

  

    // Операция запроса для получения ответа в диапазоне [0, n-1]

    query(1, 0, n);

  

    // Вывести количество ненулевых элементов

    cout << se.size() << endl;

  

    return 0;

}

Джава

// Java реализация для вышеуказанного подхода

import java.util.*;

  

class geeks

{

      

    static int N = 100005;

  

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

    static int[] lazy = new int[4*N];

  

    // Для хранения разных номеров

    static Set<Integer> se = new HashSet<Integer>();

  

    // Функция для обновления в диапазоне [x, y) с заданным значением

    public static void update(int x, int y, int value,

                            int id, int l, int r)

    {

  

        // проверить вне границы

        if (x >= r || l >= y) 

            return

      

        // проверка на полное перекрытие

        if (x <= l && r <= y)

        

            lazy[id] = value; 

            return

        

      

        // найти среднее число

        int mid = (l + r) / 2

      

        // проверка на наличие ожидающих обновлений

        if (lazy[id] != 0

            lazy[2 * id] = lazy[2 * id + 1] = lazy[id]; 

      

        // make lazy [id] = 0, чтобы не было ожидающих обновлений

        lazy[id] = 0

      

        // вызов двух дочерних узлов

        update(x, y, value, 2 * id, l, mid); 

        update(x, y, value, 2 * id + 1, mid, r); 

    }

  

    // Функция для поиска ненулевых целых чисел в диапазоне [l, r)

    public static void query(int id, int l, int r)

    {

          

        // если идентификатор содержит положительное число

        if (lazy[id] != 0)

        {

            se.add(lazy[id]);

              

            // Нет необходимости видеть детей,

            // потому что все интервалы имеют одинаковый номер

            return;

        }

  

        // проверка на выход за пределы

        if (r - l < 2)

            return;

  

        // найти среднее число

        int mid = (l + r) / 2;

  

        // вызов двух дочерних узлов

        query(2 * id, l, mid);

        query(2 * id + 1, mid, r);

    }

  

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

    public static void main(String[] args)

    {

          

        // размер массива и количество запросов

        int n = 5, q = 3;

  

        // Обновить операцию для l, r, x, id, 0, n

        update(1, 4, 1, 1, 0, n);

        update(0, 2, 2, 1, 0, n);

        update(3, 4, 3, 1, 0, n);

  

        // Операция запроса для получения ответа в диапазоне [0, n-1]

        query(1, 0, n);

  

        // Вывести количество ненулевых элементов

        System.out.println(se.size());

    }

}

  
// Этот код поддерживается
// sanjeev2552

python3

# Реализация Python3 для вышеуказанного подхода

N = 100005

  
# Хранить дерево в ленивом распространении

lazy = [0] * (4 * N); 

  
# Для хранения разных номеров

se = set() 

  
# Функция для обновления в диапазоне [x, y)
# с заданным значением

def update(x, y, value, id, l, r) :

      

    # проверить вне границы

    if (x >= r or l >= y): 

        return

  

    # проверка на полное перекрытие

    if (x <= l and r <= y) : 

        lazy[id] = value; 

        return

  

    # найти средний номер

    mid = (l + r) // 2

  

    # проверить наличие обновлений

    if (lazy[id]) :

        lazy[2 * id] = lazy[2 * id + 1] = lazy[id]; 

  

    # сделать ленивым [id] = 0,

    # чтобы не было ожидающих обновлений

    lazy[id] = 0

  

    # вызов двух дочерних узлов

    update(x, y, value, 2 * id, l, mid); 

    update(x, y, value, 2 * id + 1, mid, r); 

  
# Функция для поиска ненулевых целых чисел
# в диапазоне [l, r)

def query(id, l, r) : 

      

    # если идентификатор содержит положительное число

    if (lazy[id]) :

          

        se.add(lazy[id]); 

          

        # Нет необходимости видеть детей,

        # потому что все интервалы имеют одинаковый номер

        return

      

    # проверить на выход

    if (r - l < 2) :

        return

  

    # найти среднее число

    mid = (l + r) // 2

  

    # вызов двух дочерних узлов

    query(2 * id, l, mid); 

    query(2 * id + 1, mid, r); 

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

if __name__ == "__main__" :

  

    # размер массива и количество запросов

    n = 5; q = 3

  

    # Операция обновления для l, r, x, id, 0, n

    update(1, 4, 1, 1, 0, n); 

    update(0, 2, 2, 1, 0, n); 

    update(3, 4, 3, 1, 0, n); 

  

    # Операция запроса для получения ответа

    # в диапазоне [0, n-1]

    query(1, 0, n); 

  

    # Вывести количество ненулевых элементов

    print(len(se)); 

      
# Этот код предоставлен AnkitRai01

C #

// реализация C # для вышеуказанного подхода

using System;

using System.Collections.Generic;

      

public class geeks

{

      

    static int N = 100005;

  

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

    static int[] lazy = new int[4*N];

  

    // Для хранения разных номеров

    static HashSet<int> se = new HashSet<int>();

  

    // Функция для обновления в диапазоне [x, y) с заданным значением

    public static void update(int x, int y, int value,

                            int id, int l, int r)

    {

  

        // проверить вне границы

        if (x >= r || l >= y) 

            return

      

        // проверка на полное перекрытие

        if (x <= l && r <= y)

        

            lazy[id] = value; 

            return

        

      

        // найти среднее число

        int mid = (l + r) / 2; 

      

        // проверка на наличие ожидающих обновлений

        if (lazy[id] != 0) 

            lazy[2 * id] = lazy[2 * id + 1] = lazy[id]; 

      

        // make lazy [id] = 0, чтобы не было ожидающих обновлений

        lazy[id] = 0; 

      

        // вызов двух дочерних узлов

        update(x, y, value, 2 * id, l, mid); 

        update(x, y, value, 2 * id + 1, mid, r); 

    }

  

    // Функция для поиска ненулевых целых чисел в диапазоне [l, r)

    public static void query(int id, int l, int r)

    {

          

        // если идентификатор содержит положительное число

        if (lazy[id] != 0)

        {

            se.Add(lazy[id]);

              

            // Нет необходимости видеть детей,

            // потому что все интервалы имеют одинаковый номер

            return;

        }

  

        // проверка на выход за пределы

        if (r - l < 2)

            return;

  

        // найти среднее число

        int mid = (l + r) / 2;

  

        // вызов двух дочерних узлов

        query(2 * id, l, mid);

        query(2 * id + 1, mid, r);

    }

  

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

    public static void Main(String[] args)

    {

          

        // размер массива и количество запросов

        int n = 5, q = 3;

  

        // Обновить операцию для l, r, x, id, 0, n

        update(1, 4, 1, 1, 0, n);

        update(0, 2, 2, 1, 0, n);

        update(3, 4, 3, 1, 0, n);

  

        // Операция запроса для получения ответа в диапазоне [0, n-1]

        query(1, 0, n);

  

        // Вывести количество ненулевых элементов

        Console.WriteLine(se.Count);

    }

}

  
// Этот код предоставлен Rajput-Ji

Выход:

3

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

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

0.00 (0%) 0 votes