← 返回题目列表

Codeforces · 1141/F2

F2. 相同的总和块(硬)

中文机器翻译题面 查看原题

这个问题有两个版本,唯一的区别在于对数字 $$$n$$$ 的约束。

给定一个整数数组 $$$a[1], a[2], \dots, a[n].$$$ 块是连续(连续)元素 $$$a[l], a[l+1], \dots, a[r]$$$ ($$$1 \le l \le r \le n$$$) 的序列。因此,一个块由一对索引 $$$(l, r)$$$ 定义。

找到一组块 $$$(l_1, r_1), (l_2, r_2), \dots, (l_k, r_k)$$$ 使得:

- 它们不相交(即它们不相交)。形式上,对于每对块 $$$(l_i, r_i)$$$ 和 $$$(l_j, r_j$$$),其中 $$$i \neq j$$$ 要么 $$$r_i < l_j$$$ 要么 $$$r_j < l_i$$$。
- 对于每个块,其元素的总和是相同的。形式上, $$$$$$a[l_1]+a[l_1+1]+\dots+a[r_1]=a[l_2]+a[l_2+1]+\dots+a[r_2]=$$$$$$ $$$$$$\dots =$$$$$$ $$$$$$a[l_k]+a[l_k+1]+\点+a[r_k].$$$$$$
- 集合中块的数量为最大。形式上,不存在满足上述两个要求且 $$$k' > k$$$ 的块集合 $$$(l_1', r_1'), (l_2', r_2'), \dots, (l_{k'}', r_{k'}')$$$。

该图片对应于第一个示例。蓝色框表示块。

编写一个程序来查找这样一组块。

输入

第一行包含整数 $$$n$$$ ($$$1 \le n \le 1500$$$) — 给定数组的长度。第二行包含元素序列 $$$a[1], a[2], \dots, a[n]$$$ ($$$-10^5 \le a_i \le 10^5$$$)。

输出

在第一行打印整数 $$$k$$$ ($$$1 \le k \le n$$$)。以下 $$$k$$$ 行应包含块,每行一个。在每行中打印一对索引 $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 第 $$$i$$$ 个块的边界。您可以按任何顺序打印块。如果有多个答案,请打印其中任何一个。

示例

输入 #1

7
4 1 2 2 1 5 3

输出 #1

3
7 7
2 3
4 5

输入 #2

11
-5 -4 -3 -2 -1 0 1 2 3 4 5

输出 #2

2
3 4
1 1

输入 #3

4
1 1 1 1

输出 #3

4
4 4
1 1
2 2
3 3