Предложения по оптимизации кода для передачи TLE на SPOJ

Question

Я пытаюсь решить проблему, которая выглядит примерно так:

Мне дано n чисел (1 <= n <= 10 ^ 5). Мне нужно написать сумму всех чисел слева, которые меньше текущего числа, и повторить процесс для всех n чисел. Затем Я должен найти сумму всех ранее полученных сумм. (Каждое число N, 0 <= N <= 10 ^ 6). </p>

Например,

1 5 3 6 4
less1 less5 less3 less6 less4
 (0) + (1) + (1)+(1+5+3)+(1+3)
  0  +  1  +  1  +  9  +  4
= 15

Тривиальным решением этой проблемы будет запуск двух циклов, и для каждого из заданного числа найдите сумму всех чисел, меньших, чем это число, и, наконец, дайте сумму этих сумм в качестве выходных данных. Сложность по времени равна O (n ^ 2).

Я думаю, что лучшее решение O (nlogn) для этой проблемы с использованием Binary Indexed Tree (Fenwick Tree). Для каждого числа я добавлю каждое из чисел в глобальном массиве a и выполню две очевидные операции BIT. Я думаю, что временная сложность этого алгоритма равна O (nlogn), которая, если true, очевидно, лучше, чем предыдущая O (n ^ 2).

Я реализовал код на C ++.

#include<iostream>
#include<cstdio>

using namespace std;

#define max 1000001

long int a[max];

void add(long int v,int idx){
while(idx<max){
    a[idx] += v;
    idx += (idx & -idx);
}
}

long int sum(int idx){
long int s=0;
while(idx>0){
    s += a[idx];
    idx -= (idx & -idx);
}
return s;
 }

 int main()
 {
int t;
scanf("%d",&t);
for(int w=0;w<t;w++){
    int n;
    scanf("%d",&n);

    for(int i=0;i<max;i++)
        a[i]=0;

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

    long long res=0;

    for(int i=0;i<n;i++){
        if(arr[i]!=0){
           add(arr[i],arr[i]);
           res += (sum(arr[i]-1));
                     }  
    }

    printf("%lld\n",res);
}

return 0;
}

У меня два вопроса:

Во-первых, я делаю это правильно? / Правильна ли моя логика?

Во-вторых, если я прав насчет временной сложности, чтобы быть O (nlogn), то почему он работает медленно? Можете ли вы помочь мне с дальнейшей оптимизацией?

Получено за 1,41 секунды. В то же время я обновил окончательно принятый код. Есть предложения по оптимизации?

Основываясь на комментариях, я попробовал свою собственную функцию для более быстрого ввода-вывода, но, тем не менее, она не идет своим чередом. Это моя функция для быстрого ввода-вывода:

 inline int read(){
char c=getchar_unlocked();
int n=0;
while(!(c>='0' && c<='9'))
    c=getchar_unlocked();

while(c>='0' && c<='9'){
    n=n*10 + (c-'0');
    c=getchar_unlocked();   
}
return n;
 }

Это ссылка на проблему:

http://www.spoj.pl/problems/DCEPC206/

Если есть кто-то, кто может решить это, пожалуйста, дайте мне знать. Спасибо.

Answer 1

Я думаю, что ваш подход хорош.Я немного поиграл с этим и не придумал ничего лучше, чем у вас.

В вашем коде есть пара ошибок.Есть несколько мест, страдающих от целочисленного переполнения.Вы должны изменить на:

long long a[max];

и

long long sum(int idx){
long long s=0;

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

int b[max];
...
...
    for(int i=0;i<max;i++)
        a[i]=b[i]=0;
    ...
    ...
        res += (sum(idx)-(++b[idx]*val));

Возможно, существует более эффективный способ исправить эту ошибку, но в целом это все еще кажется быстрым решением.

Answer 2

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

merge(left, middle, right, array)
  temp = new array
  k = 0, i = left, j = middle + 1

  while i <= middle and j <= right
    if array[i] < array[j]
      temp[k++] = array[i]
      // array[i] is also smaller than all array[j+1], ..., array[right]
      globalSum += array[i] * (right - j + 1)
    else
      // same as the classical function

Интуитивно я бы сказал, что рекурсивная сортировка слиянием медленнее, чем решение BIT, но кто знает? Попробуйте.

Редактировать: Получается AC:

    #include<stdio.h>
#include <iostream>

using namespace std;

#define max 100001

int n;
long long res = 0;

int temp[max];
int arr[max];
void merge(int left, int m, int right)
{
    int k = 0;
    int i = left, j = m + 1;
    while (i <= m && j <= right)
        if (arr[i] < arr[j])
        {
            temp[k++] = arr[i];
            res += (long long)(right - j + 1) * arr[i++];
        }
        else
            temp[k++] = arr[j++];

    while (j <= right)
        temp[k++] = arr[j++];
    while (i <= m)
        temp[k++] = arr[i++];

    for (int i = 0; i < k; ++i)
        arr[left + i] = temp[i];
}

void sort(int left, int right)
{
    if (left < right)
    {
        int m = left + (right - left) / 2;
        sort(left, m);
        sort(m + 1, right);
        merge(left, m, right);
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    for(int w=0;w<t;w++)
    {
        scanf("%d", &n);
        for(int i=0;i<n;i++)
            scanf("%d", &arr[i]);

        res=0;
        sort(0, n - 1);

        printf("%lld\n",res);
    }

    return 0;
}