SP1557 GSS2 - Can you answer these queries II

• 119通过
• 322提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 排序 概率论,统计 线段树
• 难度 NOI/NOI+/CTSC
• 时空限制 1000ms / 1536MB
• 提示：收藏到任务计划后，可在首页查看。

题意翻译

给出n 个数，q 次询问，求最大子段和，相同的数只算一次。

题目描述

Being a completist and a simplist, kid Yang Zhe cannot solve but get Wrong Answer from most of the OI problems. And he refuse to write two program of same kind at all. So he always failes in contests.

When having a contest, Yang Zhe looks at the score of every problems first. For the problems of the same score, Yang Zhe will do only one of them. If he's lucky enough, he can get all the scores wanted.

Amber is going to hold a contest in SPOJ. She has made a list of N candidate problems, which fit Yang Zhe very well. So Yang Zhe can solve any problem he want. Amber lined up the problems, began to select. She will select a subsequence of the list as the final problems. Being A girl of great compassion, she'd like to select such a subsequence (can be empty) that Yang Zhe will get the maximal score over all the possible subsequences.

Amber found the subsequence easily after a few minutes. To make things harder, Amber decided that, Yang Zhe can take this contest only if Yang Zhe can answer her Q questions. The question is: if the final problems are limited to be a subsequence of list[X..Y] (1 <= X <= Y <= N), what's the maximal possible score Yang Zhe can get?

As we know, Yang Zhe is a bit idiot (so why did he solve the problem with a negative score?), he got Wrong Answer again... Tell him the correct answer!

输入输出格式

输入格式：

• Line 1: integer N (1 <= N <= 100000);
• Line 2: N integers denoting the score of each problem, each of them is a integer in range [-100000, 100000];
• Line 3: integer Q (1 <= Q <= 100000);
• Line 3+i (1 <= i <= Q): two integers X and Y denoting the _i_th question.

输出格式：

• Line i: a single integer, the answer to the _i_th question.

输入输出样例

输入样例#1： 复制
9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9
输出样例#1： 复制
4
5
3
提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。