题目描述

难度分:$2000$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

你需要把一段非空连续子数组替换成这段子数组的元素之积，替换后，需要让$a$的元素和尽量大。

例如$a=[5,4,3,2,1]$，选择其中的$[4,3,2]$，替换后$a=[5,24,1]$。

该替换操作必须恰好执行一次。

输出被替换的子数组的左右端点（下标从$1$开始）。如果有多种方案，输出任意一种均可。

输入样例

9
4
1 3 1 3
4
1 1 2 3
5
1 1 1 1 1
5
10 1 10 1 10
1
1
2
2 2
3
2 1 2
4
2 1 1 3
6
2 1 2 1 1 3

输出样例

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

算法

贪心+有技巧地枚举

这个题看着就感觉有数学规律在里面，因为随着替换的子数组长度越来越大，很可能这个乘积是非常大的，写高精度肯定要超时。

我们可以发现一点，在一般情况下，被替换的子数组端点$a[l]$和$a[r]$肯定是两个大于$1$的数，因为再往两边囊括$1$是没有意义的，$1$不会增大乘积但是会减少和。这样一来搜索空间就减小很多了，我们可以先将满足$a[i] \gt 1$的索引$i$加入到一个数组$pos$中。但考虑到$pos$可能长度很大，也不能直接$O(n^2)$枚举端点$l$和$r$。

还可以发现一点，由于$2^{18} \gt n$，所以如果$a$中大于$1$的$a[i]$不小于$18$个，那一定是把子数组$[pos[0],pos.back()]$替换掉最好，因为这些大于$1$的数相乘最少都有$2^{18}$，不替换肯定不如替换为乘积后得到的数组和。因此，分为以下两种情况：

1. 如果$pos.size() \geq 18$，答案就是$(pos[0],pos.back())$。
2. 否则都少于$18$个候选了，直接双重循环枚举$l$和$r$，大数计算收益的增量（用python可以避免写高精度），找到增量最大时对应的$l$和$r$输出即可。

复杂度分析

时间复杂度

遍历一遍$a$数组得到所有满足$a[i] \gt 1$的索引$pos$，时间复杂度为$O(n)$。接下来双重循环枚举（最大常数操作为$18^2$次）+大数连乘的时间复杂度是很低的（数位最多不会超过$200$）。因此，算法的瓶颈还是在于遍历$a$数组，整体时间复杂度为$O(n)$。

空间复杂度

除了输入的数组$a$，空间瓶颈在于$pos$和$a$的前缀和数组$s$（主要是为了快速计算区间和，从而得到收益的增量），它们都是线性的空间消耗。因此，整个算法的额外空间复杂度为$O(n)$。

python 代码

from itertools import accumulate

t = int(input())
for _ in range(t):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    s = list(accumulate(a))
    tot = s[-1]
    window_sum = lambda l, r: s[r] - s[l - 1]
    pos = []
    for i in range(1, n + 1):
        if a[i] > 1:
            pos.append(i)
    if len(pos) >= 18:
        print(pos[0], pos[-1])
    else:
        sz = len(pos)
        left, right = 1, 1
        mx = tot
        for l in range(sz):
            prod = 1
            for r in range(l, sz):
                sumation = window_sum(pos[l], pos[r])
                prod *= a[pos[r]]
                if tot + prod - sumation > mx:
                    mx = tot + prod - sumation
                    left, right = pos[l], pos[r]
        print(left, right)