サブアレイ内の個別の要素の数のクエリ| C++で2を設定します

この問題では、サイズnの配列arr []が与えられ、aqueryが与えられます。各クエリには2つの値（L、R）が含まれています。私たちのタスクは、サブアレイ内の多数の個別の要素のクエリを解決するプログラムを作成することです

問題の説明 −ここでは、インデックス（L-1）から（R-1）までのサブアレイに存在する個別の整数の総数を見つける必要があります。

問題を理解するために例を見てみましょう

入力

arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4]

出力

4

説明

クエリ1の場合：L =1＆R =4、インデックス0から3までの個別の要素の数（4）を見つける必要があります。

クエリ2の場合：L =2＆R =6、インデックス1から5までの個別の要素の数（3）を見つける必要があります。

ソリューションアプローチ

各クエリを解決する簡単な方法は、配列をLからRandに移動し、要素をセットに格納します。そのサイズによって、クエリの結果が得られます。前のセットで説明したのと同じです。

この問題を解決するためのより効果的な方法は、セグメントツリーのデータ構造を使用することです。指定された範囲の個別の要素数が保存されます。

セグメントツリー は特殊なタイプのツリーであり、情報をセグメントの形式で格納します。

セグメントツリーのリーフノードは、配列の要素を示します。また、非リーフノードは必要な値を持つセグメントを示します。ここでは、個別の要素が格納されます。このデータ構造の実装には、Setを使用します。

上記のソリューションの動作を実装するためのプログラム-

例

#include <bits/stdc++.h>
using namespace std;
set<int>* segmentTree;

void CreateSegmentTree(int i, int s, int e, int arr[]) {

   if (s == e) {
      segmentTree[i].insert(arr[s]);
      return;
   }
   CreateSegmentTree(2 * i, s, (s + e) / 2, arr);
   CreateSegmentTree(1 + 2 * i, 1 + (s + e) / 2, e, arr);
   segmentTree[i].insert( segmentTree[2 * i].begin(), segmentTree[2 * i].end());
   segmentTree[i].insert(segmentTree[2 * i + 1].begin(), segmentTree[2 * i + 1].end());
}

set<int> findDistSubarray(int node, int l, int r, int a, int b) {

   set<int> left, right, distinctSubarray;
   if (b < l || a > r)
   return distinctSubarray;
   if (a <= l && r <= b)
   return segmentTree[node];
   left = findDistSubarray(2 * node, l, (l + r) / 2, a, b);
   distinctSubarray.insert(left.begin(), left.end());
   right = findDistSubarray(1 + 2 * node, 1 + (l + r) / 2, r, a, b);
   return distinctSubarray;
}

int main() {

   int arr[] = {4, 6, 1, 3, 1, 6, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   int query[] = {1, 4};
   int i = (int)ceil(log2(n));
   i = (2 * (pow(2, i))) - 1;
   segmentTree = new set<int>[i];
   CreateSegmentTree(1, 0, n - 1, arr);
   set<int> distCount = findDistSubarray(1, 0, n - 1, (query[0]-1), (query[1]-1));
   cout<<"The number of distinct elements in the subarray is "<<distCount.size();
   return 0;
}

出力

The number of distinct elements in the subarray is 4