문제2756--재재새와 재재새 부분집합

2756: 재재새와 재재새 부분집합

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 13  통과: 4
[제출] [채점기록] [묻고답하기]

문제 설명

재재새는 최근 집합에 빠져있다.

 

특히, 집합에서는 부분집합에 빠져 있으며,

 

부분집합 중에서도, 연속된 원소들을 갖는 부분집합에 빠져있다.

 

이제부터, 이런 부분집합을 재재새 부분집합이라고 명명하겠다.

 

일단, 예를 들어보자.

 

S = {1, 2, 3, 4, -5, 2, 4, 6, 7}

 

집합 S의 재재새 부분집합의 예시는 다음과 같다.

 

{1}, {1,2}, {1,2,3}, {2,3,4,-5}, $ \dots $

 

 

재재새는 특정 구간이 주어졌을때, 그 구간 내의 재재새 부분집합 중에서 합의 최댓값을 구하고 싶어한다.

 

위의 집합 S의 구간 [2, 6]의 재재새 부분집합 중, 최댓값은 {2,3,4}의 합인 9이다.

 

N, M이 순서대로 입력되며,

N개의 집합 원소가 순서대로 입력된다.

M개의 쿼리의 구간이 주어진다.

 

쿼리내의 재재새 부분집합 중, 최댓값을 구해주면 된다.

입력 설명

$1 \leq N \leq 100000$ $1 \leq M \leq 100000$

$ -1000000 \leq e_i \leq 1000000 ( 1 \leq i \leq N ) $

$ 1 \leq a_i, b_i \leq N $

출력 설명

쿼리의 재재새 부분집합의 합 중 최댓값을 한 줄에 하나씩 출력한다.

입력 예시 Copy

5 3
1 2 3 -1 3
1 5
3 4
4 5

출력 예시 Copy

8
3
3

출처/분류