数据结构
网络
关系型数据库管理系统 (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
广告