เพิ่มผลรวมอาร์เรย์สูงสุดใน K การเคลื่อนที่ช่วง [L, R] ใน C++

ได้รับอาร์เรย์ Arr[] และคิวรี 2D Q แต่ละคิวรีมี lpos, rpos, K สามารถเคลื่อนจาก index i ไป i+1 ใน 1 ขั้น หรืออยู่ที่เดิมได้ ต้องเคลื่อนจาก lpos ถึง rpos ภายใน K ขั้น สะสมค่าทุกขั้นรวมตำแหน่งเริ่มต้น หาผลรวมสูงสุด หากเคลื่อนไม่ได้พิมพ์ "NO"

ตัวอย่าง

Input: Arr[] = {1, 2, 4, -1}, Q[][3] = {{0,2,2}, {0,2,1}, {3,3,1}, {0,2,3}}

Output: Query 1: 7, Query 2: NO, Query 3: NO, Query 4: 11

คำอธิบาย:

• Query 1: 0→1 (1+2=3), 1→2 (3+4=7) ใช้ 2 ขั้น
• Query 2: 0→2 ต้องใช้ ≥2 ขั้น แต่ K=1 → NO
• Query 3: 3→3 ต้อง 0 ขั้น แต่ K=1 (ต้องเคลื่อนอย่างน้อย 1?) → NO
• Query 4: 0→1 (3), 1→2 (7), อยู่ 2 (7+4=11) ใช้ 3 ขั้น

Input: Arr[] = {1, 2, 3, 3, 2}, Q = {{0,3,2}, {1,4,3}}

Output: Query 1: NO, Query 2: 10

อัลกอริทึม: Segment Tree + Prefix Sum

• สร้าง Segment Tree หา max ในช่วง [lpos, rpos]
• Prefix Sum pSum สำหรับผลรวมช่วง
• solQuery(lpos, rpos, k): ถ้า rpos-lpos > k → -1 (NO)
• หา maxVal ในช่วง [lpos, rpos] จาก Segment Tree
• sum = pSum[rpos] - (lpos>0 ? pSum[lpos-1] : 0)
• ผลลัพธ์ = sum + (k - (rpos - lpos)) * maxVal (อยู่ที่ค่าสูงสุดในขั้นที่เหลือ)

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

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

void createTree(int min, int max, int pos, int sgT[], int arr[], int len) {
    if (min == max) { sgT[pos] = arr[max]; return; }
    int midd = (min + max) / 2;
    int loc1 = 2*pos+1, loc2 = 2*pos+2;
    createTree(min, midd, loc1, sgT, arr, len);
    createTree(midd+1, max, loc2, sgT, arr, len);
    sgT[pos] = max(sgT[loc1], sgT[loc2]);
}

int findMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1) {
    if (min1 <= start && max1 >= end) return sgT1[pos1];
    if (end < min1 || start > max1) return INT_MIN;
    int middle = (start + end) / 2;
    int loc1 = 2*pos1+1, loc2 = 2*pos1+2;
    int lmax = findMax(start, middle, min1, max1, loc1, sgT1, arr1, len1);
    int rmax = findMax(middle+1, end, min1, max1, loc2, sgT1, arr1, len1);
    return max(lmax, rmax);
}

int solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) {
    if (rpos - lpos > k) return -1;
    int maxVal = findMax(0, len2-1, lpos, rpos, 0, sgT2, arr2, len2);
    if (maxVal < 0) maxVal = 0;
    int sum = pSum2[rpos];
    if (lpos > 0) sum -= pSum2[lpos-1];
    return sum + (k - (rpos - lpos)) * maxVal;
}

void resQuery(int len3, int arr3[], int sgT3[], int pSum3[], int q1[][3], int qlen1) {
    for (int i = 0; i < qlen1; i++) {
        int result = solQuery(q1[i][0], q1[i][1], q1[i][2], len3, arr3, sgT3, pSum3);
        if (result == -1) cout << endl << "Query " << i+1 << ": NO";
        else cout << endl << "Query " << i+1 << ": " << result;
    }
}

void preSum(int pSum4[], int arr4[], int len4) {
    pSum4[0] = arr4[0];
    for (int j = 1; j < len4; j++) pSum4[j] = pSum4[j-1] + arr4[j];
}

int main() {
    int Arr[] = {1, 2, 4, -1};
    int length = sizeof(Arr) / sizeof(Arr[0]);
    int sgTreee[5 * length];
    createTree(0, length-1, 0, sgTreee, Arr, length);
    int pSum[length];
    preSum(pSum, Arr, length);
    int Q[][3] = {{0,2,2}, {0,2,1}, {3,3,1}, {0,2,3}};
    int qlen = sizeof(Q) / sizeof(Q[0]);
    resQuery(length, Arr, sgTreee, pSum, Q, qlen);
    return 0;
}

ผลลัพธ์

Query 1: 7 Query 2: NO Query 3: NO Query 4: 11