หาผลรวมมัธยฐานของทุก sublist ความยาวคี่ใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหา ผลรวมของมัธยฐาน (median) ของทุก sublist (subarray) ที่มีความยาวเป็นเลขคี่

ตัวอย่าง

nums = [2, 4, 6, 3]
Odd-length sublists: [2], [4], [6], [3], [2,4,6], [4,6,3]
Medians: 2, 4, 6, 3, 4, 4
Sum = 2+4+6+3+4+4 = 23

อัลกอริทึม: Two Heaps สำหรับแต่ละ Starting Index

สำหรับแต่ละ i (starting index):

• ใช้ 2 heaps: max-heap (que_max) เก็บครึ่งล่าง, min-heap (que_min) เก็บครึ่งบน
• ขยาย subarray โดยเพิ่ม j จาก i ถึง n-1
• รักษา: |size(max) - size(min)| ≤ 1, max.top() ≤ min.top()
• ถ้าความยาว subarray คี่ (i%2 == j%2) → median = max.top() → บวกเข้าผลรวม

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

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

int solve(vector& nums) {
    int ret = 0;
    for (int i = 0; i < nums.size(); i++) {
        priority_queue que_max;  // max-heap
        priority_queue, greater> que_min;  // min-heap
        
        for (int j = i; j < nums.size(); j++) {
            que_max.push(nums[j]);
            
            // Balance: max-heap มีมากกว่าได้สูงสุด 1
            while (que_max.size() - que_min.size() >= 2) {
                que_min.push(que_max.top());
                que_max.pop();
            }
            
            // Maintain order: max.top() <= min.top()
            while (que_min.size() && que_max.top() > que_min.top()) {
                int a = que_max.top(); que_max.pop();
                int b = que_min.top(); que_min.pop();
                que_max.push(b);
                que_min.push(a);
            }
            
            // Odd length: i and j same parity
            if (i % 2 == j % 2) {
                ret += que_max.top();
            }
        }
    }
    return ret;
}

int main() {
    vector v = {2, 4, 6, 3};
    cout << solve(v);
    return 0;
}

ผลลัพธ์

23

ความซับซ้อน

• เวลา: O(n² log n) - n² subarrays, แต่ละอัน heap operations log n
• พื้นที่: O(n) - heaps สูงสุด n elements

การปรับปรุง

สามารถทำได้ O(n log n) หรือ O(n) ด้วยเทคนิคขั้นสูง (Order Statistics Tree, หรือคำนวณ contribution ของแต่ละ element) แต่ O(n² log n) พอสำหรับ n ≤ 1000

สรุป

ใช้ Two Heaps คำนวณ median แบบ streaming สำหรับทุก subarray เริ่มที่ i หาผลรวมเฉพาะความยาวคี่ หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ