s179. 1. 比例分割 - 高中生程式解題系統

內容

小明有一個由 $n$ 個正整數組成的序列 $w_1, w_2, \dots, w_n$。他對序列中區間的「比例分割點」非常感興趣。

對於任何子區間 $[l, r]$，我們定義其區間和為 $S(l, r) = \sum_{i=l}^{r} w_i$。若 $l > r$，則 $S(l, r) = 0$。

現在小明有 $m$ 個詢問。每個詢問包含四個整數 $l, r, a, b$，請你找到一個唯一的分割點 $k$ ($l \le k \le r$)，使得該點滿足以下兩個條件：

$\frac{S(l, k-1)}{S(l, r)} < \frac{a}{a+b}$
$\frac{S(l, k)}{S(l, r)} \ge \frac{a}{a+b}$

由於序列中的元素皆為正整數，可以保證對於每一組詢問，符合條件的 $k$ 恰好只有一個。

例如序列為 $2, 2, 6, 3, 1, 5$，當 $a = 1, b = 1$ 時，$k = 3$ 恰好會滿足條件。
$S(1, 2) = 4, S(1, 3) = 10, S(1, 6) = 19$

4 / 19 < 1 / 2
10 / 19 < 1 / 2

輸入說明

第一行包含兩個整數 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，分別代表序列長度與詢問次數。

第二行包含 $n$ 個整數 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^4$)。

接下來的 $m$ 行，每行包含四個整數 $l, r, a, b$ ($1 \le l \le r \le n, 1 \le a \le b \le 10$)。

(40分)：$1 \le n, m \le 10^3$
(60分)：無限制

輸出說明

對於每個詢問，輸出一行包含一個整數 $k$，即滿足條件的分割點索引。

範例輸入 #1

6 1
2 2 6 3 1 5
1 6 1 1

範例輸出 #1

範例輸入 #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

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <10M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

標籤:

出處:

2026年3月 APCS 中高級 [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
54884	brian0989560 ... (陳森凱)	s179	APCS 202603 中高級	110	2026-04-08 18:23
54739	cubeman94033 ... (請輸入暱稱)	s179	解題報告	184	2026-03-09 22:35
54712	guovinn@gmai ... (郭10)	s179	C++題解（二分搜+前綴合）	232	2026-03-09 11:57