Tìm số lượng các số khác nhau trong mảng sau khi áp dụng thao tác đã cho q lần trong C ++

Trong bài toán này, chúng ta được cung cấp một số N là kích thước của một mảng bao gồm tất cả các số 0 và truy vấn Q, mỗi loại sau -

update (s, e, val) -> truy vấn này sẽ cập nhật tất cả các phần tử từ s đến e (cả hai) thành val.

Nhiệm vụ của chúng ta là tìm số lượng các số khác nhau trong mảng sau khi áp dụng thao tác đã cho q lần

Hãy lấy một ví dụ để hiểu vấn đề,

Input : N = 6, Q = 2
Q1 = update(1, 4, 3)
Q2 = update(0, 2, 4)

Output : 2

Giải thích

Mảng ban đầu, arr [] ={0, 0, 0, 0, 0, 0}

Truy vấn 1 - cập nhật (1, 4, 3) -> arr [] ={0, 3, 3, 3, 3, 0}

Truy vấn 2 - update (0, 2, 4) -> arr [] ={4, 4, 4, 3, 3, 0}

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là thực hiện từng truy vấn trên mảng, sau đó đếm số giá trị duy nhất trong mảng và sử dụng thêm một mảng. Và sau đó trả về tổng số mảng duy nhất.

Giải pháp này là tốt nhưng giải pháp hiệu quả hơn cho vấn đề là sử dụng khái niệm lan truyền lười biếng để tối ưu hóa hoạt động phạm vi được thực hiện trong truy vấn. Chúng tôi sẽ sử dụng lệnh gọi truyền dẫn lười biếng cho hoạt động truy vấn để tìm số lượng các số duy nhất trong mảng. Đối với điều này, chúng tôi sẽ lấy một cây phân đoạn và các nút cập nhật khi hoạt động được thực thi và khởi tạo cây bằng 0, các giá trị đang cập nhật trên hoạt động trả về giá trị mong muốn. Đây là chương trình sẽ xây dựng giải pháp tốt hơn.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int lazyST[4 * N];
set<int> diffNo;
void update(int s, int e, int val, int idx, int l, int r){
   if (s >= r or l >= e)
      return;
   if (s <= l && r <= e) {
      lazyST[idx] = val;
      return;
   }
   int mid = (l + r) / 2;
   if (lazyST[idx])
      lazyST[2 * idx] = lazyST[2 * idx + 1] = lazyST[idx];
   lazyST[idx] = 0;
   update(s, e, val, 2 * idx, l, mid);
   update(s, e, val, 2 * idx + 1, mid, r);
}
void query(int idx, int l, int r){
   if (lazyST[idx]) {
      diffNo.insert(lazyST[idx]);
      return;
   }
   if (r - l < 2)
      return;
   int mid = (l + r) / 2;
   query(2 * idx, l, mid);
   query(2 * idx + 1, mid, r);
}
int main() {
   int n = 6, q = 3;
   update(1, 3, 5, 1, 0, n);
   update(4, 5, 1, 1, 0, n);
   update(0, 2, 9, 1, 0, n);
   query(1, 0, n);
   cout<<"The number of different numbers in the array after operation is "<<diffNo.size();
   return 0;
}

Đầu ra

The number of different numbers in the array after operation is 3