2906. Can you answer these queries - 1

 

You are given an integer sequence a1, a2, ..., an (|ai| ≤ 15007, 1 ≤ n ≤ 50000). A query is defined as follows:

Query(x, y) = MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}

Given m queries, your program must output the results of these queries.

 

Input. The first line contains the integer n. In the second line n integers of the sequence are given. The third line contains the integer m. Then m lines follow, where line i contains two numbers xi and yi.

 

Output. Print the results of the m queries, one query per line.

 

Sample input

3

-1 2 3

1

1 2

 

Sample output

2

 

 

SOLUTION

data structures – segment tree

 

Algorithm analysis

Для решения задачи следует реализовать нетривиальное обобщение дерева отрезков. В каждой его вершине будем хранить четыре величины: сумму summa на этом отрезке, максимальную сумму prefix среди всех префиксов этого отрезка, максимальную сумму suffix среди всех суффиксов, а также максимальную сумму max подотрезка на нём. То есть для каждого отрезка ответ будет предпосчитан не только для него, но и для отрезков, упирающихся в его левую и правую границы.

Пусть отрезок [a..b] соответствует вершине дерева. Пусть левый его сын содержит информацию по отрезку [a..m], а правый – по [m+1..b]. Тогда значения величин в корне пересчитываются через значения величин в сыновьях следующим образом:

prefix[a..b] = max(prefix[a..m], summa[a..m] + prefix[m+1..b])

 suffix[a..b] = max(suffix[m+1..b], suffix[a..m] + summa[m+1..b])

max[a..b] = max(max[a..m], max[m+1..b], suffix[a..m] + prefix[m+1..b])

summa[a..b] = summa[a..m] + summa[m+1..b]

Например, исходя из приведенных равенств, максимальная сумма на отрезке может равняться одному из следующих значений:

·        максимуму на отрезке левого сына (лучший подотрезок в текущей вершине целиком помещается в отрезок левого сына);

·        максимуму на отрезке правого сына (лучший подотрезок в текущей вершине целиком помещается в отрезок правого сына);

·        сумме максимального суффикса в левом сыне и максимального префикса в правом сыне (лучший подотрезок лежит своим началом в левом сыне, а концом в правом)

 

Example. Пусть некоторая вершина дерева соответствует отрезку [0..5]:

 Тогда дополнительные величины, хранящиеся в ней, имеют следующие значения:

 

Пусть указанная вершина имеет левого [0..2] и правого [3..5] сына, дополнительные значения в которых имеют значения:

 

                                                             

 

                             

                            

                            

                         

 

При объединении отрезков [0..2] и [3..5] дополнительные значения пересчитываются следующим образом:

prefix[0..5] = max(prefix[0..2], summa[0..2] + prefix[3..5]) = max (2, 0 + 3) = 3

suffix[0..5] = max(suffix[3..5], suffix[0..2] + summa[3..5]) = max (1, 2 – 3) = 1

max[0..5] = max(max[0..2], max[3..5], suffix[0..2] + prefix[3..5]) = max (4, 3, 2 2 + 3) = 5

summa[0..5] = summa[0..2] + summa[3..5] = 0 – 3 = -3

 

Algorithm realization

Дерево отрезков храним в виде массива t структур node длины MAX, где MAX – максимальное количество элементов, которое может храниться в отрезке.

 

#define MAX 50100

struct node

{

  int summa, prefix, suffix, max;

} t[4*MAX];

 

На вход процедуре build построения дерева отрезков передается массив a, номер текущей вершины дерева v и границы отрезка LeftPos и RightPos, соответствующие вершине v.

 

void build (int *a, int v, int LeftPos, int RightPos)

{

  if (LeftPos == RightPos)

  {

    t[v].max = t[v].prefix = t[v].suffix = t[v].summa = a[LeftPos];

  }

  else

  {

    int Middle = (LeftPos + RightPos) / 2;

    build (a, v*2, LeftPos, Middle);

    build (a, v*2+1, Middle+1, RightPos);

 

    t[v].summa = t[v*2].summa + t[v*2+1].summa;

    t[v].prefix = max(t[2*v].prefix,t[2*v].summa + t[2*v+1].prefix);

    t[v].suffix = max(t[2*v+1].suffix,t[2*v].suffix + t[2*v+1].summa);

 

    t[v].max = max(max(t[2*v].max,t[2*v+1].max),

                                  t[2*v].suffix + t[2*v+1].prefix);

  }

}

 

Вершине v соответствует отрезок [LeftPos; RightPos]. Функция GetMax вычисляет значения четырех параметров (префикс, суффикс, сумма, максимальная сумма) на отрезке [Left; Right] и возвращает структуру node, которая их содержит.

 

struct node GetMax(int v, int LeftPos, int RightPos, int Left, int Right)

{

  if ((Left == LeftPos) && (Right == RightPos)) return t[v];

  int Middle = (LeftPos + RightPos) / 2;

 

  if (Right <= Middle ) return GetMax(2*v,LeftPos, Middle,Left,Right);

  if (Left > Middle) return GetMax(2*v+1,Middle+1,RightPos,Left,Right);

 

  struct node LeftNode  = GetMax(2*v,LeftPos,Middle,Left,Middle);

  struct node RightNode = GetMax(2*v+1,Middle+1,RightPos,Middle+1,Right);

 

  struct node res;

  res.prefix = max(LeftNode.prefix,LeftNode.summa + RightNode.prefix);

  res.suffix = max(RightNode.suffix,RightNode.summa + LeftNode.suffix);

  res.summa = LeftNode.summa + RightNode.summa;

  res.max = max(max(LeftNode.max,RightNode.max),

                LeftNode.suffix + RightNode.prefix);

  return res;

}

 

Основная часть программы. Читаем входные данные. Строим дерево отрезков.

 

scanf("%d",&n);

for(i = 0; i < n; i++) scanf("%d",&mas[i]);

build(mas,1,0,n-1);

 

Последовательно обрабатываем m запросов.

 

scanf("%d",&m);

for(i = 0; i < m; i++)

{

  scanf("%d %d",&L,&R);

  res = GetMax(1,0,n-1,L-1,R-1);

  printf("%d\n",res.max);

}