Truy vấn hiệu tuyệt đối giữa vị trí phần tử nhỏ thứ L và nhỏ thứ R trong C++

Mô tả bài toán

Cho mảng arr[] kích thước n và Q truy vấn mỗi truy vấn hai số L, R. Tìm hiệu tuyệt đối giữa chỉ số của phần tử nhỏ thứ L và nhỏ thứ R trong mảng gốc.

Ví dụ: arr = [8,4,1,5,2], truy vấn {{2,4},{1,5}} → kết quả 1 và 2.

Giải pháp

Tạo mảng cặp (giá trị, chỉ số gốc), sắp xếp theo giá trị. Với mỗi truy vấn, lấy chỉ số gốc của phần tử tại vị trí L-1 và R-1 trong mảng đã sắp xếp, tính hiệu tuyệt đối.

Ví dụ minh họa (C++)

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

void solveAllQueries(int arr[], int n, int Q, int queries[][2]) {
    pair<int,int> arrayIndex[n];
    for (int i = 0; i < n; i++) {
        arrayIndex[i].first = arr[i];
        arrayIndex[i].second = i;
    }
    sort(arrayIndex, arrayIndex + n);
    for (int i = 0; i < Q; i++) {
        int result = abs(arrayIndex[queries[i][0]-1].second - arrayIndex[queries[i][1]-1].second);
        cout << "For Query " << (i+1) << ": Difference is " << result << endl;
    }
}

int main() {
    int arr[] = {8,4,1,5,2};
    int n = 5, Q = 2;
    int queries[][2] = {{2,4},{1,5}};
    solveAllQueries(arr, n, Q, queries);
    return 0;
}

Đầu ra

For Query 1: Difference is 1
For Query 2: Difference is 2