주어진 숫자보다 크거나 같은 배열의 요소 수를 쿼리하고 업데이트합니다.-C++-php.cn

주어진 숫자보다 크거나 같은 배열의 요소 수를 쿼리하고 업데이트합니다.

王林

풀어 주다： 2023-09-05 08:25:12

앞으로

908명이 탐색했습니다.

주어진 숫자보다 크거나 같은 배열의 요소 수를 쿼리하고 업데이트합니다.

세그먼트 트리의 도움으로 배열을 성공적으로 업데이트하고 범위 쿼리를 수행할 수 있습니다. 업데이트하면 알려진 데이터 구조 세그먼트 트리를 사용하여 계산할 수 있습니다. 배열의 요소 수는 no보다 크거나 같습니다.

Query - [l, r] 범위에 x보다 크거나 유사한 항목이 몇 개 있는지 알아보세요.

범위 [l, r]이 세그먼트 트리의 현재 노드가 나타내는 세그먼트를 넘어 완전히 확장되면 0이 제공됩니다.
카운트. 간격 [l, r]이 세그먼트 트리의 현재 노드가 나타내는 세그먼트 내에 완전히 있는 경우 x보다 크거나 유사한 범위 [l, r]에 있는 요소 수입니다.
그렇지 않은 경우 현재 노드의 왼쪽 및 오른쪽 하위 노드를 재귀적으로 ping하여 수집된 총 개수를 반환합니다.

Update - 인덱스 i의 요소에 v 값을 추가합니다. 이번 업데이트에는 다음 알고리즘을 적용합니다 -

세그먼트 트리의 현재 노드 표시 범위에 인덱스 i가 없으면 아무런 작업도 수행되지 않습니다.
인덱스 i의 값이 x보다 크거나 같으면 선분 트리의 현재 노드가 나타내는 간격에서 x보다 크거나 같은 요소의 개수를 업데이트합니다. 또는 x와 같고 이를 증가시킨 다음 현재 노드를 재귀적으로 업데이트합니다. 왼쪽 및 오른쪽 하위 요소 노드입니다.
세그먼트 트리의 루트 노드에서 [0, n-1] 범위의 쿼리를 실행할 수 있습니다. 여기서 n은 총 개수입니다. x보다 크거나 같은 배열의 항목 수입니다.

문법

1. 처음부터 세그먼트 트리 및 배열 생성 -

으아악

2. 업데이트(변경) 절차 수행 -

으아악

3. 다음 쿼리 작업을 수행합니다. -

으아악

4. 쿼리 작업을 사용하여 수량을 계산합니다. 지정된 값보다 크거나 같은 요소, 배열 및 세그먼트 트리를 업데이트하는 업데이트 작업 -

으아악

알고리즘

업데이트를 사용하여 숫자를 계산할 수 있는 방법은 다음과 같습니다. 지정된 값보다 크거나 같은 배열 멤버 -

1단계 - 시작 값을 저장할 n 크기의 배열 A를 만듭니다.
2단계 - 최소 범위 쿼리를 표시하려면 크기 4*n의 세그먼트 트리 T를 초기화합니다.
3단계 - build(T, A, 1, 0, n-1) 함수를 사용하여 세그먼트 트리 T를 만듭니다. 여기서 build(T, A, v, tl, tr)는 A의 값을 사용합니다. 범위 [tl, tr]를 생성하고 결과를 T의 노드 v에 넣습니다.
4단계 - 크기 n의 배열 C를 만들고 지정된 수보다 크거나 같은 항목 수로 초기화합니다.
5단계 - 개수 쿼리의 범위 합계를 나타내기 위해 시작 크기가 4*n인 세그먼트 트리 S를 만듭니다.
6단계 - build(S, C, 1, 0, n-1) 함수를 호출합니다. 여기서 build(S, C, v, tl, tr)는 [tl, tr], C의 값을 사용하고 결과를 S의 노드 v에 유지합니다.
7단계 - 각 "x보다 크거나 같은 요소 개수 계산" 쿼리에 응답합니다. -

배열 A의 [l, r] 범위에서 최소값을 찾으려면 쿼리(T, 1, 0, n-1, l, r) 함수를 호출하세요. 결과가 m이라고 가정합니다.

m이 x보다 크거나 같으면 함수 쿼리(S, 1, 0, n-1, l, r)를 사용하여 총 개수를 구합니다. x보다 크거나 같은 배열 C의 간격 [l, r]에 있는 항목 수입니다. 결과는 다음과 같습니다. c.

그렇지 않다면 c를 0으로 설정하세요.

8단계 - 유형이 변경될 때마다 "A[i]의 값을 v로 설정" -

[tl,tr] 범위에서 선분 트리 T의 노드 v를 업데이트하고 update(T,v,tl,tr,i,val) 함수를 호출합니다. 여기서 update(T,v,tl,tr,i , val) 인덱스 i의 값을 val로 설정하여 세그먼트 트리 T의 노드 v를 변경합니다.

update(S, 1, 0, n-1, i, (v >= x)) 함수를 사용하여 [tl, tr] 범위의 선분 트리 노드 v를 업데이트합니다. 여기서 update(S, v, tl , tr, i, val)은 x보다 크거나 같은 항목 수에 val을 추가하여 노드 v를 업데이트합니다.

9단계 - 7단계와 8단계를 다시 반복합니다.

따라야 할 방법

방법 1

예제에서는 배열을 나타내기 위해 int 유형의 벡터를 정의하고 계산하려는 항목 수보다 크거나 같은 int 유형의 임계값을 정의합니다. 그런 다음 counttheElements 함수를 사용하여 초기 배열과 임계값보다 크거나 같은 요소 수를 생성합니다.

updatetheElement 함수는 배열, 업데이트할 요소의 인덱스, 요소의 새 값을 매개변수로 받아들인 다음 배열의 요소를 업데이트하는 데 사용됩니다. 마지막으로, counttheElements 메소드를 다시 사용하여 수정된 배열과 임계값보다 크거나 같은 요소의 새 개수를 출력합니다.

예 1

으아악

출력

으아악

방법-2

각 쿼리의 기능은 계산입니다. query[i]보다 크거나 같은 배열(항목), 해당 값을 모두 M만큼 감소시키고 업데이트된 배열에서 문제의 나머지 부분을 실행합니다. 입력은 두 개의 배열 array[] 및 query[]이며 크기는 각각 N과 Q입니다.

먼저 배열[]을 오름차순으로 정렬합니다.

l과 같이 첫 번째 위치에서 요소가 query[i]보다 크거나 같은 요소를 찾습니다.

해당 요소가 없으면 응답으로 0을 반환합니다. 그렇지 않으면 응답은 N – l이 됩니다.

最后一步是从提供的范围内的每个元素中减去 M，并将区间 l 中的线段树更改为 N - 1。

示例 2

#include <bits/stdc++.h>
using namespace std;

void build(vector<int>& tosum, vector<int>& a, int l, int r, int rlt){
   if (l == r) {
      tosum[rlt] = a [l - 1];
      return;
   }
   int m = (l + r) >> 1;
   build (tosum, a, l, m, rlt << 1);
   build (tosum, a, m + 1, r, rlt << 1 | 1);
}
void push(vector<int>& tosum, vector<int>& toadd, int rlt, int ln, int rn){
   if (toadd[rlt]) {
      toadd [rlt<< 1] += toadd[rlt];
      toadd [rlt << 1 | 1] += toadd[rlt];
      tosum [rlt<< 1] += toadd[rlt] * ln;
      tosum [rlt << 1 | 1] += toadd[rlt] * rn;
      toadd[rlt] = 0;
   }
}
void update(vector<int>& tosum, vector<int>& toadd, int L, int R, int C, int l,int r, int rlt){
   if (L <= l && r <= R) {
      tosum[rlt] += C * (r - l + 1);
      toadd[rlt] += C;
      return;
   }
   int m = (l + r) >> 1;
   push (tosum, toadd, rlt, m - l + 1,
   r - m);
   if (L <= m)
      update (tosum, toadd, L, R, C, l, m,
      rlt << 1);
   if (R > m)
      update (tosum, toadd, L, R, C, m + 1, r,
      rlt << 1 | 1);
}
int query(vector<int>& tosum,
   vector<int>& toadd,
   int L, int R, int l,
   int r, int rlt){
   if (L <= l && r <= R) {
      return tosum[rlt];
   }
   int m = (l + r) >> 1;
   push (tosum, toadd, rlt, m - l + 1,
   r - m);
   int ans = 0;
   if (L <= m)
   ans += query (tosum, toadd, L, R, l, m,
   rlt << 1);
   if (R > m)
   ans += query (tosum, toadd, L, R, m + 1, r,
   rlt << 1 | 1);
   return ans;
}
void sequMaint(int n, int q,vector<int>& a,vector<int>& b,int m){
   sort(a.begin(), a.end());
   vector<int> tosum, toadd, ans;
   tosum.assign(n << 2, 0);
   toadd.assign(n << 2, 0);
   build (tosum, a, 1, n, 1);
   for (int i = 0; i < q; i++) {
      int l = 1, r = n, pos = -1;
      while (l <= r) {
         int m = (l + r) >> 1;
         if (query (tosum, toadd, m, m, 1, n, 1)
         >= b[i]) {
            r = m - 1;
            pos = m;
         }
         else {
            l = m + 1;
         }
      }
      if (pos == -1)
      ans.push_back(0);
      else {
         ans.push_back(n - pos + 1);
         update (tosum, toadd, pos, n, -m,
         1, n, 1);
      }
   }
   for (int i = 0; i < ans.size(); i++) {
      cout << ans[i] << " ";
   }
}
int main (){
   int A = 4;
   int B = 3;
   int C = 1;
   vector<int> array = {1, 2, 3, 4};
   vector<int> query = {4, 3, 1};
   sequMaint(A, B, array, query, C);
   return 0;
}

로그인 후 복사