C++에서 주어진 연산을 q번 적용한 후 배열에서 다른 숫자의 수를 찾습니다.

이 문제에서 우리는 모두 0으로 구성된 배열의 크기인 숫자 N이 주어지고 Q는 다음 유형의 각각을 쿼리합니다 -

update(s, e, val ) -> 이 쿼리는 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 - 업데이트(1, 4, 3) -> arr[] ={0, 3, 3, 3, 3, 0}

쿼리 2 - 업데이트(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