資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學在 C++ 中，求應用給定操作 q 次後陣列中不同數字的個數
在這個問題中，我們給定一個大小為 N 的陣列，陣列元素都為零，以及 Q 個查詢，每個查詢型別如下：
update(s, e, val) -> 此查詢會將從 s 到 e（包含 s 和 e）的所有元素更新為 val。
我們的任務是*找到應用給定操作 q 次後陣列中不同數字的個數*
讓我們來看一個例子來理解這個問題：
Input : N = 6, Q = 2 Q1 = update(1, 4, 3) Q2 = update(0, 2, 4) Output : 2
解釋
初始陣列，arr[] = {0, 0, 0, 0, 0, 0}
查詢 1 - update(1, 4, 3) -> arr[] = {0, 3, 3, 3, 3, 0}
查詢 2 - update(0, 2, 4) -> arr[] = {4, 4, 4, 3, 3, 0}
解決方案
一個簡單的解決方案是對陣列執行每個查詢，然後計算陣列中唯一值的個數，並使用一個額外的陣列。然後返回唯一陣列的個數。
這個解決方案很好，但一個更有效的解決方案是使用*延遲傳播*的概念來最佳化查詢中執行的範圍操作。我們將使用延遲傳播呼叫查詢操作來查詢陣列中唯一數字的個數。為此，我們將使用線段樹，並在執行操作時更新節點，並用 0 初始化樹，操作中更新的值將返回所需的值。以下程式將更好地闡述該解決方案。
示例
程式演示了我們解決方案的工作原理
#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;
}輸出
The number of different numbers in the array after operation is 3
更新於：2022年1月24日
瀏覽量：127
廣告