比例分割 (APCS 2026-03 中高級)
2.0s 256M給定正整數序列 \(w\)。每次詢問指定 \(l,r,a,b\),請找出最小的索引 \(k\in[l,r]\),使 \(w_l+\cdots+w_k\) 至少是整段區間和的 \(a/(a+b)\)。索引從 \(1\) 開始。
輸入格式
第一行為 \(n,m\)。第二行為 \(n\) 個權重。接著 \(m\) 行各為 \(l,r,a,b\)。
限制
\(1\le n,m\le10^5\);\(1\le w_i\le10^4\);\(1\le l\le r\le n\);\(1\le a\le b\le10\)。
輸出格式
每個詢問輸出一行 \(k\)。
評分說明
每筆計分測資獨立計分,每筆 5 分,共 100 分;範例不計分。
- 1: 40% — \(n,m\le1000\)
- 2: 60% — 無額外限制。
範例輸入 1
6 1
2 2 6 3 1 5
1 6 1 1
範例輸出 1
3
範例輸入 2
12 3
1 4 2 3 6 7 1 9 9 8 10 6
4 10 1 6
1 6 1 10
3 11 6 8
範例輸出 2
5
2
8
題目來源
APCS 2026 年 3 月中高級實作題第 1 題。
題敘參考 ZeroJudge s179「比例分割」 整理,細節可能與正式試題有出入。