주어진 부분 배열에서 주어진 수보다 작거나 같은 요소의 수


난이도 하드
자주 묻는 질문 CodeNation DE Shaw 구글 운영 페이팔 클립
배열 나무

문제 정책

"주어진 하위 배열에서 주어진 수보다 작거나 같은 요소 수"문제는 정수 배열과 q 개의 쿼리가 제공된다는 것을 나타냅니다. 두 가지 유형의 쿼리가 있습니다 à

  • queryUpdate (i, v) : 배열 [i] = v를 업데이트하는 두 개의 정수 i와 v가 있습니다.
  • queryPrint (left, right, k) : k보다 작은 범위 내의 정수 수를 인쇄합니다.

arr[]={2, 4, 6, 1, 5)
queryPrint(0, 2, 2)
queryUpdate(2, 8)
queryPrint(1, 3, 5)
queryUpdate(4, 3)
queryUpdate(1, 3)
queryPrint(1, 2, 4)
1 2 1

설명

queryPrint (0, 2, 2)는 인덱스 2에서 0, 즉 2까지 1보다 작거나 같은 요소 수를 인쇄합니다.

queryUpdate (2, 8)은 인덱스 2의 요소를 값 8로 업데이트합니다. 즉, arr은 {2, 4, 8, 1, 5}입니다.

queryPrint (1, 3, 5)는 인덱스 5에서 1, 즉 3까지 2보다 작거나 같은 요소 수를 인쇄합니다.

queryUpdate (4, 3)는 인덱스 4의 요소를 3으로 업데이트합니다. 즉, arr은 {2, 4, 8, 1, 3}입니다.

queryUpdate (1, 3)는 인덱스 1의 요소를 3으로 업데이트합니다. 즉, arr은 {2, 3, 8, 1, 3}입니다.

queryPrint (1, 2, 4)는 인덱스 4에서 1, 즉 2까지 1보다 작거나 같은 요소 수를 인쇄합니다.

주어진 부분 배열에서 주어진 수보다 작거나 같은 요소의 수

 

하위 배열에서 주어진 값 <= 숫자를 찾는 알고리즘

  1. 나누기 정렬 n의 제곱근과 같은 크기의 블록으로, 여기서 n은 입력 배열의 크기입니다.
  2. 특정 블록의 배열에있는 최대 요소보다 하나 더 큰 이진 인덱스 트리를 만듭니다.
  3. 배열의 각 요소가 속한 블록을 찾아서 arr [i]에서 1로 블록의 BIT 배열을 업데이트합니다.
  4. 각 업데이트 쿼리에 대해. 인덱스에 대한 배열의 원래 값에있는 블록을 기준으로 BIT 배열의 값을 -1로 업데이트합니다.
  5. 특정 인덱스의 새 요소에서 값 1로 동일한 블록의 BIT 배열을 업데이트합니다.
  6. 각 인쇄 쿼리에 대해. k보다 작거나 같은 요소 값을 계산하기 위해 BIT 배열에 대한 쿼리를 작성하십시오. 전체 블록 또는 불완전 또는 부분 블록의 경우 모든 요소를 ​​통과합니다.

설명

정수 배열과 두 가지 유형의 쿼리가 제공됩니다. 한 가지 쿼리는 주어진 특정 인덱스에서 값을 업데이트하는 것입니다. 그리고 또 다른 쿼리는 k보다 작은 요소의 수를 얻는 것입니다. 업데이트 쿼리의 경우 인덱스와 값이 제공됩니다. 값을 업데이트하겠습니다. v 배열 [i]의 주어진 인덱스에서. 인쇄 쿼리 또는 개수 쿼리의 경우 k보다 작거나 같은 정수의 수를 인쇄해야합니다.

배열을 몇 개의 블록으로 나눌 것입니다. 이 블록은 배열 길이의 제곱근 크기입니다. 모든 블록에 대해 우리는 이진 인덱스 트리. 이진 인덱스 트리의 크기는 배열 요소의 특정 블록에 대한 최대 요소보다 하나 더 커집니다. 각 블록에 대해 BIT 배열이 있으므로 배열 [i]의 각 위치에서 값 1로 값 비트 배열을 업데이트하고 배열의 각 요소에 대한 블록을 찾아 위와 동일한 절차를 따릅니다. arr [i]에서 해당 블록의 비트 배열을 1로 업데이트합니다.

각 업데이트 쿼리에 대해 BIT 배열을 업데이트하십시오. 각 배열 요소에 대한 블록이 있기 때문에. 특정 인덱스의 배열 값을 -1 값으로 업데이트하고 필요한 블록의 BIT 배열을 지정된 인덱스에있는 배열의 새 요소에서 값 1로 업데이트합니다. 인쇄 또는 값 계산 쿼리의 경우 루프를 통과하면됩니다. 전체 블록 또는 부분 전체 블록에 대한 두 가지 경우가 있습니다. 마침내 값을 반환합니다.

암호

숫자 <= 주어진 값을 찾기위한 C ++ 코드

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>

using namespace std;

const int MAX = 10001;

void update(int index, int block, int val, int bit[][MAX])
{
    for (; index < MAX ; index += (index&-index))
        bit[block][index] += val;
}
int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][MAX])
{
    int sum = 0;
    while (left<right && left%blockSize!=0 && left!=0)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }

    while (left + blockSize <= right)
    {
        int index = k;
        for (; index > 0 ; index -= index&-index)
            sum += bit[left/blockSize][index];
        left += blockSize;
    }

    while (left <= right)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }
    return sum;
}
void preprocess(int arr[], int blockSize, int n, int bit[][MAX])
{
    for (int i=0; i<n; i++)
        update(arr[i], i/blockSize, 1, bit);
}

void queryUpdate(int i, int v, int blockSize,int arr[], int bit[][MAX])
{
    update(arr[i], i/blockSize, -1, bit);
    update(v, i/blockSize, 1, bit);
    arr[i] = v;
}
int main()
{
    int arr[] = {2,4,6,1,5};
    int n = sizeof(arr)/sizeof(arr[0]);

    int blockSize = sqrt(n);

    int bit[blockSize+1][MAX];

    memset(bit, 0, sizeof(bit));

    preprocess(arr, blockSize, n, bit);

    cout << queryPrint (0, 2, 2, arr, blockSize, bit) << endl;

    queryUpdate(2, 8, blockSize, arr, bit);

    cout << queryPrint(1, 3, 5, arr, blockSize, bit) << endl;

    queryUpdate(4, 3, blockSize, arr, bit);

    queryUpdate(1, 3, blockSize, arr, bit);

    cout << queryPrint (1, 2, 4, arr, blockSize, bit) << endl;
    return 0;
}
1
2
1

숫자 <= 주어진 값을 찾기위한 Java 코드

class NumberElements
{
    static final int MAX = 10001;

    static void update(int index, int block, int val, int bit[][])
    {
        for ( ; index < MAX ; index += (index&-index))
            bit[block][index] += val;
    }
    static int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][])
    {
        int sum = 0;
        while (left < right && left % blockSize != 0 && left != 0)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        while (left + blockSize <= right)
        {
            int index = k;
            for (; index > 0 ; index -= index&-index)
                sum += bit[left/blockSize][index];
            left += blockSize;
        }
        while (left <= right)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        return sum;
    }
    static void buildArray(int arr[], int blockSize, int n, int bit[][])
    {
        for (int i=0; i<n; i++)
            update(arr[i], i/blockSize, 1, bit);
    }

    static void queryUpdate(int i, int v, int blockSize, int arr[], int bit[][])
    {
        update(arr[i], i/blockSize, -1, bit);
        update(v, i/blockSize, 1, bit);
        arr[i] = v;
    }

    public static void main(String args[])
    {
        int arr[] = {2,4,6,1,5};

        int blockSize = (int) Math.sqrt(arr.length);

        int bit[][] = new int[blockSize+1][MAX];
        buildArray(arr, blockSize, arr.length, bit);

        System.out.println(queryPrint(0, 2, 2, arr, blockSize, bit));

        queryUpdate(2, 8, blockSize, arr, bit);

        System.out.println(queryPrint(1, 3, 5, arr, blockSize, bit));

        queryUpdate(4, 3, blockSize, arr, bit);

        queryUpdate(1, 3, blockSize, arr, bit);

        System.out.println(queryPrint (1, 2, 4, arr, blockSize, bit));

    }
}
1
2
1

복잡성 분석

시간 복잡성

O (1) 어레이 업데이트 및 O (N) 어레이 인쇄용.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. “주어진 부분 배열에서 주어진 수보다 작거나 같은 요소의 수”문제는 선형 공간을 가지고 있습니다.