#P2482. [Spoj1557] Can you answer these queries II

[Spoj1557] Can you answer these queries II

题目描述

给定 nn 个元素的序列。给出 mm 个询问:求 li~ril_i ~ r_i 的最大子段和(可选空子段)。
这个最大子段和有点特殊:一个数字在一段中出现了两次只算一次。
比如:1,2,3,2,21,2,3,2,2,22 出现了 33 次,但只算一次,于是这个序列的和是 1+2+3=61+2+3=6。

输入格式

  第一行一个数 nn。
第二行 nn 个数,为给定的序列,这些数的绝对值小于等于 1×1051 \times 10^5。
第三行一个数 mm。
接下来 mm 行,每行两个数,li,ril_i,r_i。

输出格式

MM 行,每行一个数,为每个询问的答案。

9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9
4
5
3

数据规模与约定

30%30\%的数据满足:1≤n,m≤1001 \le n,m \le 100。
100%100\%的数据满足:1≤n,m≤1×1051 \le n,m \le 1 \times 10^5。

题目来源

spoj gss2