SP4828 ZSEQ - ZSequence

你将获得一个由 **N** 个正整数组成的序列 **A**，其中包含 **a $_{1}$**, **a $_{2}$**, ..., **a $_{N}$**。 我们定义一个区间和 **S(i, j)** 为从 **a $_{i}$** 到 **a $_{j}$**（包括两者）的所有元素之和，即 **S(i, j)** = **a $_{i}$** + **a $_{i+1}$** + ... + **a $_{j}$**，前提是 **i ≤ j**。 你的任务是找出 **K - 1** 个递增的下标 **m $_{1}$ < m $_{2}$ < ... < m $_{K-1}$**，使得每个子区间的和满足相应的给定条件：即 **lb $_{1}$** ≤ **S(1, m $_{1}$)** ≤ **ub $_{1}$**， ...， **lb $_{i}$** ≤ **S(m $_{i-1}$ + 1, m $_{i}$)** ≤ **ub $_{i}$**， 最后一个区间满足 **lb $_{K}$** ≤ **S(m $_{K-1}$ + 1, N)** ≤ **ub $_{K}$**。 如果存在多个解，要求输出字典序最小的那个解。

第一行包含两个整数 **N** 和 **K**，用空格分隔，表示序列的长度和待选取的分割点个数（**N** 满足 2 ≤ **N** ≤ 5 000，**K-1** 满足 1 ≤ **K-1** ≤ **N-1**）。 接下来 **N** 行，每行包含一个正整数，表示序列中的元素，满足 1 ≤ **a $_{i}$** ≤ 100,000。 接下来的 **K** 行中，每行包含两个整数 **lb $_{i}$** 和 **ub $_{i}$**，表示第 **i** 个区间的和应该在这个范围内（1 ≤ **lb $_{i}$** ≤ **ub $_{i}$** ≤ 1,000,000,000）。

如果有合法的解，在第一行以空格分隔输出 **K-1** 个下标。若无解则输出 -1。

- 对于 N 的范围，确保序列不会极度巨大，便于计算。 - 对于 K-1 的限制，确保至少存在一个分割点。 **本翻译由 AI 自动生成**