ค้นหาคู่ที่มีผลคูณสูงสุดในช่วงพร้อมอัปเดตใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์และ Q คำถาม 2 ประเภท:

• Type 1: หาคู่ที่มีผลคูณสูงสุดในช่วง [L, R]
• Type 2: อัปเดตค่าที่ดัชนี i

ตัวอย่าง

arr = {4, 2, 6, 9, 1}
Q1: [1, 1, 4] -> range {2,6,9,1} -> max product = 6×9 = 54
Q2: [2, 2, 3] -> update index 2 to 3 -> arr = {4,2,3,9,1}
Q3: [1, 0, 2] -> range {4,2,3} -> max product = 4×3 = 12

วิธีแก้ปัญหา

วิธีง่าย - O(n²) ต่อคำถาม

วนลูปหาคู่อย่างครบ

วิธี Segment Tree - O(log n) ต่อคำถาม

• เก็บค่าสูงสุด 2 อันดับ (max, second max) ในแต่ละโหนด
• ผลคูณสูงสุด = max × second_max
• รองรับการอัปเดตได้อย่างมีประสิทธิภาพ

ตัวอย่างโค้ด C++ (Segment Tree)

#include <iostream>
using namespace std;

struct Segment {
    int maxEle, secMax;
};

Segment seg[4*MAX];

Segment merge(Segment a, Segment b) {
    Segment res;
    res.maxEle = max(a.maxEle, b.maxEle);
    res.secMax = min(max(a.maxEle, b.secMax), max(b.maxEle, a.secMax));
    return res;
}

// build, update, query functions...

int main() {
    // Segment tree implementation for max product pair queries
    return 0;
}

ผลลัพธ์

The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12