Propozycje optymalizacji kodu, aby przekazać TLE na SPOJ

Question

Próbuję rozwiązać problem, który jest mniej więcej tak:

Ja podanych liczb n (n = 1 < < = 10^5) .I Muszę napisać sumę wszystkich liczb po lewej, które są mniejsze od aktualnej liczby i powtórzyć proces dla wszystkich liczb n. Następnie muszę znaleźć sumę wszystkich poprzednio uzyskanych sum. (Każda liczba N, 0 < = N < = 10^6).

Na przykład

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

Trywialny rozwiązanie tego problemu będzie uruchomić dwie pętle i dla każdego z podanym numerem znaleźć sumę wszystkich liczb mniejszych od tej liczby i wreszcie dać sumę tych suma jako wynik. Złożoność czasu wynosi O (n^2).

Myślę, że lepsze rozwiązanie O (nlogn) dla tego problemu przy użyciu binarnie indeksowanego drzewa (drzewa Fenwick). Dla każdego numeru dodam każdą z liczb w tablicy globalnej a i wykonam dwie oczywiste operacje BIT.Myślę, że złożoność czasowa tego algorytmu to O (nlogn), która jeśli jest prawdziwa jest oczywiście lepsza niż poprzednia O (n^2).

Zaimplementowałem kod w 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; 
} 

Mam dwa pytania:

pierwsze, robię to prawidłowe?/Czy moja logika jest poprawna?

Po drugie, jeśli mam rację co do złożoności czasu, która ma być O (nlogn), to dlaczego działa wolno? Czy możesz mi pomóc z dalszymi optymalizacjami?

Został zaakceptowany przez 1,41 sekundy. W tym samym czasie zaktualizowałem mój ostatecznie zaakceptowany kod. Sugestię optymalizacji?

Na podstawie uwag Próbowałem własną funkcję do szybszego I/O, ale nadal to nie będzie moje way.This jest moja funkcja do szybkiego I/O:

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; 
} 

tym odnośnikiem do problemu :

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

Jeśli jest ktoś, kto jest niepełnosprawny go rozwiązać, proszę dać mi znać. Dzięki.

Answer 1

Myślę, że podejście jest dobry. Bawiłem się z tym trochę i nie wymyśliłem niczego ogólnie lepszego niż to, co masz.

Istnieje jednak kilka błędów w kodzie. Jest kilka miejsc cierpiących na przepełnienie liczby całkowitej. należy zmienić na:

long long a[max]; 

i

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

Im bardziej oczywiste jest to, że bug jesteś zsumowanie cyfr, które są mniej niż lub równa aktualny numer. Aby rozwiązać ten problem, można dodać drugą globalną tablicę do śledzenia zliczenie każdej wartości:

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

Nie może być bardziej skuteczny sposób, aby naprawić ten błąd, ale ogólnie to wciąż wydaje się szybkiego rozwiązania.

Answer 2

Oto inne podejście: problem jest podobny do zliczania inwersji, z tym że trzeba zsumować elementy odpowiedzialne za generowanie inwersji. Możemy to rozwiązać za pomocą sortowania scalonego. Zmodyfikować funkcję scalania tak:

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 

Intuicyjnie powiedziałbym rekurencyjny mergesort jest wolniejszy niż rozwiązanie bit, ale kto wie? Spróbuj.

Edit: To dostaje 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; 
}