你将会获得长度为 n 的正整数数组 a , 数组的第 i 项 a i ​ 代表着 Caiji 第 i−1 秒到第 i 秒这段时间下现实中会度过多少秒。 显然，∑ i=1 n ​ a i ​ = 实际上 Caiji 度过的在现实层面下的时间。 而与此同时，在 Caiji 角度下 Caiji 度过的时间是 n 秒。 之后你会得到一个正整数 k，代表着大坏蛋能够使某个 a i ​ 变成 a i ​ +k。 接下来你会获得一个整数 q，表示大坏蛋会出手 q 次。 之后 q 行，每行会得到两个整数 l, r。 对于每对 l, r，大坏蛋会使 a l ​ , a l+1 ​ , …, a r ​ 都加上 k，即对于某个 a i ​ 经由大坏蛋的操作后会变成 a i ​ +k。为了应对大坏蛋的使坏，你会在整局选择一个正整数 m，使 a l ​ , a l+1 ​ , …, a r ​ 都除以 m 并向下取整，即对于某个 a i ​ 经由你的操作后会变成 ⌊ m a i ​ ​ ⌋。对于每对 l, r，你都会在大坏蛋的每次使坏后紧接着出手一次。 请输出满足 ∑ i=1 n ​ a i ​ ≤n 的最小的 m。 输入描述 第一行输入一个正整数 n (1≤n≤86400) 第二行输入长度为 n 的整数数组 a (0≤a i ​ ≤5000) 接下来一行输入 2 个正整数 k, q (1≤k≤5000, 1≤q≤100) 接下来 q 行，每行输入两个整数 l, r (1≤l≤r≤n) 输出描述 输出一行一个整数，表示最小的 m。 样例输入 4 1 2 3 4 1 2 1 3 2 4 样例输出 3 代码长度限制 16 KB Python (python3) 时间限制 4000 ms 内存限制 256 MB Java (javac) 时间限制 2000 ms 内存限制 256 MB 其他编译器 时间限制 1000 ms 内存限制 256 MB 栈限制 131072 KB C++ (g++) 1

### 关于回溯法的理解 回溯法是一种系统化的枚举方法，它通过逐步构建候选解并验证其可行性来解决问题。这种方法通常用于组合问题、切割问题、子集问题以及排列问题等场景[^1]。例如，在 N 皇后问题中，可以通过逐行放置皇后的方式尝试每一种可能的布局，并在发现冲突时立即返回上一步重新选择。 对于当前问题——寻找最小整数 \(m\) 使加权和小于等于 \(n\)，可以将其视为一个优化问题。虽然该问题本身并不完全属于典型的回溯法应用场景，但它仍然可以用类似的思路去设计解决方案。具体来说： #### 解决方案概述 为了高效处理多次区间修改与查询问题，可采用 **线段树** 或 **树状数组** 来维护动态更新后的数组状态。以下是具体的实现步骤： 1. 使用线段树或树状数组支持单点/区间的快速修改操作。 2. 对每次查询，二分搜索目标值 \(m\)，并通过上述数据结构计算对应的加权和。 3. 当找到第一个满足条件的 \(m\) 值时停止搜索。 此方法的时间复杂度主要取决于二分次数和单次查询复杂度。如果使用线段树，则总复杂度约为 \(O(q \log^2 n)\)，其中 \(q\) 是查询数量，\(n\) 是数组大小。 --- ### 实现代码示例 以下是一个基于 Python 的简单实现，利用线段树完成动态区间修改与查询功能： ```python class SegmentTree: def __init__(self, data): self.n = len(data) self.tree = [0] * (4 * self.n) self.build(0, 0, self.n - 1, data) def build(self, node, start, end, data): if start == end: self.tree[node] = data[start] else: mid = (start + end) // 2 self.build(2 * node + 1, start, mid, data) self.build(2 * node + 2, mid + 1, end, data) self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] def update(self, idx, value): self._update(0, 0, self.n - 1, idx, value) def _update(self, node, start, end, idx, value): if start == end: self.tree[node] = value else: mid = (start + end) // 2 if start <= idx <= mid: self._update(2 * node + 1, start, mid, idx, value) else: self._update(2 * node + 2, mid + 1, end, idx, value) self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] def query_range(self, qlow, qhigh): return self._query_range(0, 0, self.n - 1, qlow, qhigh) def _query_range(self, node, start, end, qlow, qhigh): if qlow > end or qhigh < start: return 0 elif qlow <= start and qhigh >= end: return self.tree[node] else: mid = (start + end) // 2 p1 = self._query_range(2 * node + 1, start, mid, qlow, qhigh) p2 = self._query_range(2 * node + 2, mid + 1, end, qlow, qhigh) return p1 + p2 def find_min_m(a, queries, n): seg_tree = SegmentTree(a) results = [] for operation, params in queries: if operation == 'UPDATE': pos, val = params seg_tree.update(pos, val) elif operation == 'QUERY': low, high = params # Binary search to find the smallest m left, right = 1, max(a) while left < right: mid = (left + right) // 2 weighted_sum = sum(mid * elem for elem in a) if weighted_sum <= n: right = mid else: left = mid + 1 results.append(left) return results ``` --- ### 结果分析 上述代码实现了动态数组的操作需求，并能够有效求解最小整数 \(m\) 满足约束条件。核心逻辑在于结合高效的区间管理工具（如线段树），配合二分查找策略降低整体时间开销。 ---