이 문제에서는 크기가 n인 배열 arr[]이 주어지고 쿼리가 주어집니다. 각 쿼리에는 두 개의 값(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