題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2173F. Isla’s Memory Thresholds

Problem Statement

題目簡述

給定一個長度為 $n$ 的非遞增數列 $a$ ( $a_1 \ge a_2 \ge \dots \ge a_n$ )。
有 $q$ 次查詢，每次給定 $(l, r, x)$ ，模擬以下過程：
從 $a_l$ 開始逐一累加數值，一旦當前累積總和 $\ge x$ ，則記錄一次「清空」（計數器 +1），並將累積總和歸零，繼續處理後續元素直到 $a_r$ 。

對於每個查詢，輸出清空次數及最後剩餘的累積總和。

Constraints

約束條件

$1 \le n, q \le 150,000$
$\sum n, \sum q \le 150,000$
$1 \le a_i, x \le 10^9$
$a_1 \ge a_2 \ge \dots \ge a_n$ (非遞增)

思路：根號分治 (Square-root Decomposition) + 二分搜尋 (Binary Search)

這道題目的關鍵在於利用 $a$ 是非遞增的性質。這意味著：隨著起始位置向右移動，湊滿閾值 $x$ 所需的最少元素個數（長度 ln）單調不減。

基於此性質，我們可以維護一個變數 ln 表示「上一次清空所需的長度」，並在推進過程中猜測下一次的長度。

核心策略

由於長度 ln 只會變大，且通常變化緩慢，我們可以按以下優先順序檢查：

當前長度 ln 是否仍足夠？ 如果足夠，則盡可能連續跳躍。
長度 ln + 1 是否足夠？
長度 ln + 2 是否足夠？
二分搜尋： 如果以上皆非，說明長度劇烈增加，使用 lower_bound 尋找新的 ln。

為了進一步優化「當前長度 ln 足夠」的情況，我們引入根號分治的思想：

小片段 (ln < B)：
- 當 ln 很小時，簡單的線性跳躍可能會導致次數過多（例如 $x$ 很小，ln=1，需要跳 $10^5$ 次）。
- 此時利用 二分搜尋 找出「能連續用長度 ln 跳躍的最大次數」，一次性更新位置。
大片段 (ln >= B)：
- 當 ln 很大時，剩餘的跳躍次數必然很少（最多 $\frac{N}{B}$ 次）。
- 直接線性模擬（一步一步跳）即可，省去二分搜尋的開銷。

這裡的塊大小 $B$ 取值約為 $\sqrt{\frac{N}{\log N}}$ 以平衡二分搜尋與線性模擬的成本。

深入解析：兩次二分搜尋的單調性基礎

這道題巧妙地在兩個不同的維度上使用了二分搜尋，且各自依賴不同的單調性：

針對「長度 ln」的二分搜尋 (策略 4)
- 目的：當 ln 劇烈變化時，尋找新的滿足條件的最小長度。
- 依賴單調性：前綴和的單調遞增。
- 給定起點 $l$ ，函數 $f(i) = s[i] - s[l]$ 隨 $i$ 單調遞增。因此可用 lower_bound 找到第一個 $f(i) \ge x$ 的位置，確定新的長度。
針對「跳躍次數」的二分搜尋 (策略 1 - 小片段)
- 目的：當 ln 很小且固定時，找出能連續跳躍的最大次數。
- 依賴單調性：滑動窗口和的單調遞減。
- 考慮起始於 $l$ 、長度皆為 ln 的連續 $k$ 個片段，其總和分別為 $S_1, S_2, \dots, S_k$ 。
- 由於數列 $a$ 非遞增 ( $a_i \ge a_{i+1}$ )，對於任意偏移量 $j$ ，都有 $a_{l+j} \ge a_{l+ln+j}$ 。這導致 $S_1 \ge S_2 \ge \dots \ge S_k$ 。
- 這種「越後面的片段總和越小」的性質，保證了若第 $k$ 個片段滿足 $\ge x$ ，則前 $k-1$ 個片段必然也滿足，從而允許我們對次數進行二分搜尋。

複雜度分析

複雜度推導

主要開銷在找尋新的 ln 以及跳躍時發生的二分搜尋：

1. 找尋新的 ln 時，最壞情況是長度變化劇烈，每次都需要二分搜尋：

設二分搜尋發生次數為 $k$ ，每次找到的新長度分別為 $len_1, len_2, \dots, len_k$ 。
由於啟發式檢查處理了 $+0, +1, +2$ 的情況，觸發二分搜尋意味著長度至少增加了 $3$ 。
因此長度序列大致為 $1, 4, 7, \dots, 1+3(k-1)$ 。
總長度限制： $\sum len_i \le N$ 。
近似解 $3k^2 \approx 2N \implies k \approx \sqrt{\frac{2N}{3}}$ 。
這部分的總複雜度約為 $O(Q \cdot \sqrt{N} \cdot \log N)$ 。

2. 跳躍時發生的二分搜尋：

當 $ln < B$ 時，我們花費 $O(\log \frac{N}{ln})$ 進行二分跳躍。
當 $ln \ge B$ 時，我們花費 $O(1)$ 進行線性跳躍，最多跳 $N/B$ 次。

總複雜度約為 $O(Q \cdot (B \cdot \log N + \frac{N}{B}))$ 。
為了平衡 $B \cdot \log N$ (小片段二分成本) 與 $\frac{N}{B}$ (大片段線性成本)，取 $B \cdot \log N \approx \frac{N}{B}$ ，即 $B \approx \sqrt{\frac{N}{\log N}}$ 。
最終時間複雜度約為 $O(Q \cdot \sqrt{N \cdot \log N})$ 。

時間複雜度： $\mathcal{O}(Q \cdot (\sqrt{N \cdot \log N} + \sqrt{N} \cdot \log N))$
空間複雜度： $\mathcal{O}(N)$ (僅需前綴和陣列)

import math
from bisect import bisect_left
from itertools import accumulate

def solve():
    n, q = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == n
    
    # 根據複雜度分析，選擇適當的 B 值
    B = int(math.sqrt(n / math.log2(n))) + 1 if n > 1 else 1

    s = list(accumulate(A, initial=0))
        
    for _ in range(q):
        l, r, x = map(int, input().split())
        l -= 1  # 0-based index [l, r)
        cnt = rem = 0
        ln = 1
        while l < r:
            # 剩餘長度不足 ln 或 剩餘總和不足 x
            if r - l < ln or s[r] - s[l] < x:
                rem = s[r] - s[l]
                break
            
            # 1. 當前長度 ln 足夠
            if s[l + ln] - s[l] >= x:
                # ln >= B 時，直接跳躍
                if ln >= B:
                    while l + ln <= r and s[l + ln] - s[l] >= x:
                        l += ln
                        cnt += 1
                # ln < B 時，二分搜尋找到最大的跳躍次數
                else:
                    left, right = 1, (r - l) // ln
                    while left <= right:
                        mid = (left + right) // 2
                        if s[l + mid * ln] - s[l + (mid - 1) * ln] >= x:
                            left = mid + 1
                        else:
                            right = mid - 1
                    cnt += right
                    l += right * ln
                ln += 1
            #2. 嘗試 ln + 1
            elif l + ln + 1 <= r and s[l + ln + 1] - s[l] >= x:
                ln += 1
            # 3. 嘗試 ln + 2
            elif l + ln + 2 <= r and s[l + ln + 2] - s[l] >= x:
                ln += 2
            # 4. 二分搜尋找新的長度
            else:
                # 尋找最小的 idx 使得 s[idx] - s[l] >= x 即 s[idx] >= s[l] + x
                target = s[l] + x
                idx = bisect_left(s, target, lo=l + 1, hi=r + 1)
                
                cnt += 1
                ln = idx - l
                l = idx
        print(cnt, rem)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

這裡什麼都沒有。