#215027. [NHSPC 2024] 區間最大獨立集詢問

小雲最近在學習「最大權重獨立集（Maximum-Weight Independent Set, MWIS）」的演算法。

根據定義，一張無向圖裡的頂點子集合 要被稱作「獨立集」的話，需要滿足 集合中任兩個頂點在原圖上皆互不相鄰的條件。而「最大權重獨立集」則是所有可能的「獨立集」中，點權重總和最大的一組。

今天小雲發現，假如這張無向圖是一條直鏈（Chain）的話，那要找到「最大權重獨立集」變得超級簡單！他向小成分享這件事之後，小成卻反問:「那你知道怎麼有效率的回答一條直鏈上面的『區間最大權重獨立集詢問』嗎？」

經過一番研究後，小雲發現，即使在不知道直鏈上每個節點的具體權重下，也能找到它的最大權重獨立集，甚至能用來解決區間詢問。於是，他列了以下這道難題給小成：

「給定一條包含 個頂點編號為 的直鏈（chain），其中對於任何的 ，頂點 與頂點 之間皆有一條無向邊，且對於任何 ，頂點 的權重為一個正整數 ，請回答 筆『區間最大權重獨立集詢問 (Range MWIS Query)』。」

「在區間最大權重獨立集詢問中, 對於滿足 的任意區間，你必須回答我頂點 之間的最大權重獨立集為何。」

小雲接著補充。

「當然，在一無所知的情況下不可能解決這個問題，所以我允許你執行數次『權重和比較詢問』：任選兩個頂點的子集合，我會告訴你哪一個子集合的頂點權重和比較大。」

請協助小成, 在執行儘量少次『頂點子集合權重比較』的情況下，回答所有待詢問區間裡的最大權重獨立集！

實作細節

你需要實作兩個函式 init() 與 range_MWIS_query()：

void init(int n);

• 對於每一筆測試資料，正式評分程式會呼叫你實作的 init() 函式恰好 次。
• 代表頂點的數量。

std::vector<int> range_MWIS_query(int l, int r);

• 對於每一筆測試資料，正式評分程式會呼叫你實作的 range_MWIS_query() 函式恰好 次。
• 保證在呼叫完 init() 後才會呼叫此函式。
• range_MWIS_query() 需要回傳一個陣列 。
• 陣列 代表了該詢問區間的最大權重獨立集包含的頂點編號。
• 對於所有 ，皆須保證 。
• 對於所有 ，皆須保證 。

此外，在實作時可以呼叫 compare_subsets() 這個函式。

bool compare_subsets(const std::vector<int>& a, const std::vector<int>& b);

• 是一個陣列，其描述了 的子集合。
• 是一個陣列，其描述了 的子集合。
• 內不能有重複的數字。
• 內不能有重複的數字。
• 若集合 內的頂點的權重和比集合 小，則該函式會回傳布林值 true，否則會回傳布林值 false。
• 範例評分程式內的 compare_subsets() 實作與實際評分程式內的實作完全相同。

互動範例

一個可能被評為 Accepted 的互動例子顯示如下：

範例評分程式採用以下格式輸入：

請注意，正式的評分程式一定不會採用以上格式輸入。請不要自行處理輸入輸出。

範例評分程式⾸先呼叫 init()，接著範例評分程式會呼叫 次 range_MWIS_query()。接著，若範例評分程式偵測到從 init 或 range_MWIS_query 對 compare_subsets 的呼叫有任何不合法，此程式將輸出

Wrong Answer: msg

後並終⽌程式執⾏，其中 為下列其中之⼀錯誤訊息：

• Invalid vertex number: v: 你的程式傳入 compare_subsets 的集合中有不介在 之間的數字 。
• Duplicate vertex numbers: v: 你的程式傳入 compare_subsets 的集合中有重複的數字 。

否則，範例評分程式將會以下列格式印在標準輸出中：

其中，

• 為第 次呼叫 range_MWIS_query() 時你回傳的陣列長度。
• 為第 次呼叫 range_MWIS_query() 時你回傳的陣列的第 項。
• 與 為根據你的程式呼叫 compare_subsets 的次數得來的數值，詳細定義請見評分說明欄位。

样例输入 1

样例输出 1

評分說明

對於每一筆測試資料，若你的程式在函式 init() 中呼叫 compare_subsets 的次數為 、在第 次 range_MWIS_query() 中呼叫 compare_subsets 的次數為 ，則定義 與 為：

根據 與 ，你將得到兩個分數比重 與 ：

你的最終比重 會是兩者相乘，也就是：

本題共有 3 組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，你在該子任務的得分為所有測試資料中分數比重 的最小值，乘以該子任務的總分。