Как решить это эффективным способом с оптимальной сложностью времени?

Question

Учитывая набор из N чисел в массиве.Дано Q запросов.Каждый запрос содержит 1 число х.

Для каждого запроса необходимо добавить x к каждому элементу массива, а затем сообщить сумму абсолютных значений в массиве.

Примечание. Изменения в массиве являются постоянными.См. Пример для более подробной информации.

Формат ввода

Первая строка содержит N, количество элементов в массиве.Следующая строка содержит N разделенных пробелом целых чисел массива.Следующая строка содержит Q (количество запросов).Следующая строка содержит целые числа, разделенные пробелом Q (число x).

Формат вывода

Для каждого запроса выведите сумму в новой строке.

Ограничения
1 ≤ N ≤ 500000
1 ≤ Q ≤ 500000
-2000 ≤ число в каждом запросе ≤ 2000
-2000 ≤ значение элемента массива ≤ 2000

Sample Input

3
-1 2 -3
3
1 -2 3

Sample Output

5
7
6

Пояснение

После запроса 1: [0, 3, -2] => сумма = 0 + 3 + 2 = 5

После запроса 2: [-2, 1, -4] => сумма = 2 + 1 + 4 = 7

после запроса 3: [1, 4, -1] => сумма = 1 + 4 + 1 = 6

#include<stdio.h>
#include<stdlib.h>

int main()
{
  int n,*a,q,*aq;
  long int sum=0;
  scanf("%d",&n);
  a=(int*)malloc(sizeof(int)*n);
  for(int i=0;i<n;i++)
    scanf("%d",&a[i]);

  scanf("%d",&q);
  aq=(int*)malloc(sizeof(int)*q);
  for(int i=0;i<n;i++)
    scanf("%d",&aq[i]);

  for(int i=0;i<q;i++)
  {
    for(int j=0;j<n;j++)
    {
        sum+=abs(aq[i]+a[j]);
        a[j]=aq[i]+a[j];
    }

    printf("%ld\n",sum);
    sum=0;

  } 

}  

В некоторых тестовых случаях истекло время ожидания.

Answer 1

Вот схема алгоритма:

Пример ввода

3
-1 2 -3

Сортировка данных и вычисление сумм префиксов:

-3, -1, 2
-3, -4, -2 (prefix sums)

(Использование гистограммы в качестве ИваДауст предположил, что исключит начальную сортировку и любой двоичный поиск, чтобы найти три раздела ниже, что значительно оптимизирует сложность.)

Поддержание текущей дельты:

delta = 0

Для каждого запроса

1 -2 3

Запрос 1:

* update delta:
  delta = 0 + 1 = 1

* identify three sections:
  [negative unaffected] [switches sign] [positive unaffected]
       -3,   -1,                                 2

* Add for each section abs(num_elements * delta + prefix_sum):
   abs(2 * 1 + (-4 - 0))        +        abs(1 * 1 + (-2 -(-4)))
   = abs(2 - 4) + abs(1 + 2)
   = 5

Запрос -2:

* update delta:
  delta = 1 - 2 = -1

* identify three sections:
  [negative unaffected] [switches sign] [positive unaffected]
       -3,   -1,                                 2

* Add for each section abs(num_elements * delta + prefix_sum):
   abs(2 * (-1) + (-4 - 0))     +     abs(1 * (-1) + (-2 -(-4)))
   = abs(-2 - 4) + abs(-1 + 2)
   = 7

Запрос 3:

* update delta:
  delta = -1 + 3 = 2

* identify three sections:
  [negative unaffected] [switches sign] [positive unaffected]
       -3,                   -1,                   2

* Add for each section abs(num_elements * delta + prefix_sum):
 abs(1 * 2 + (-3 - 0)) + abs(1 * 2 + (-4 - (-3))) + abs(1 * 2 + (-2 -(-4)))
   = abs(2 - 3) + abs(2 - 1) + abs(2 + 2)
   = 6

Пример вывода

5
7
6

Answer 2

Ваше решение выполняет операции NQ, что огромно.

Сначала обратите внимание, что диапазон данных умеренный, так что вы можете представить N чисел, используя гистограмму из 4001 записей.Эта гистограмма вычисляется в N операциях (плюс инициализация бинов).

Затем запрашиваемая сумма получается как сумма абсолютных разностей для каждого бина, взвешенная по значениям бина.Это снижает рабочую нагрузку с NQ до BQ (B - это число бинов).

---

Если я прав, мы можем добиться гораздо большего, разложив сумму в подсумму для отрицательных значений и еще одну впозитивы.И эти суммы получены путем вычисления префиксных сумм.Это должно привести к решению в Q-операциях после предварительной обработки гистограммы в B-операциях.