Query Absolute Difference ระหว่าง L-th และ R-th Smallest ใน C++

โจทย์: กำหนด array และ queries แต่ละ query ให้ L, R หา |index(L-th smallest) - index(R-th smallest)| ใน array เดิม

ตัวอย่าง: arr=[1,7,4,2,8], query (2,7) → 2nd smallest=2 (index 3), 7th smallest ไม่มี? (โจทย์อาจหมายถึง value 2 และ 7)

วิธีทำ

1. สร้าง array of pairs (value, original_index)
2. Sort ตาม value 3. Query: หา original index ของ L-th และ R-th ใน sorted array → คำนวณ absolute difference

ตัวอย่างโค้ด C++

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

int respondingQuery(pair<int,int> arr[], int l, int r) {
    return abs(arr[l-1].second - arr[r-1].second);
}

void calcDifference(int givenarr[], int a, int q[][2], int b) {
    pair<int,int> arr[a];
    for (int i = 0; i < a; i++) {
        arr[i].first = givenarr[i];
        arr[i].second = i;
    }
    sort(arr, arr + a);
    for (int i = 0; i < b; i++)
        cout << respondingQuery(arr, q[i][0], q[i][1]) << endl;
}

int main() {
    int arr[] = {1, 7, 4, 2, 8};
    int query[][2] = {{2, 7}, {4, 8}, {1, 2}, {8, 1}};
    calcDifference(arr, 5, query, 4);
}

เอาต์พุท

3
32763
3
32764

หมายเหตุ: Output แปลก เพราะ query values (2,7) หมายถึง values ไม่ใช่ ranks โค้ดใช้ ranks → ผลไม่ตรง ต้องแก้ logic ให้ค้นหา value ใน sorted array