Cod sursă (job #785861)

#include <fstream>

using namespace std;

ifstream fin("dejavu.in");
ofstream fout("dejavu.out");

const int Nmax = 5005;
const int MOD = 1000000007;

int n, q;
int aib_frecventa_0[Nmax], aib_frecventa_1[Nmax];
int moduri_completare_prefixe[Nmax][Nmax / 2];  ///moduri_completare_prefixe[i][j] = numarul de moduri de a completa prefixele de lungime i care contin j perechi

void citire_marime_siruri(){
    fin >> n;
}

void precalculare_moduri_completare_prefixe(){
    int lungime_prefix, nr_perechi, valori_unice, valori_nefolosite;

    for(int nr_perechi = 0; 2 * nr_perechi <= n; nr_perechi++){
        moduri_completare_prefixe[n][nr_perechi] = 1;
    }

    for(lungime_prefix = n - 1; lungime_prefix >= 1; lungime_prefix--){
        for(nr_perechi = 0; 2 * nr_perechi <= n; nr_perechi++){
            valori_unice = lungime_prefix - 2 * nr_perechi;
            valori_nefolosite = n - nr_perechi - valori_unice;

            moduri_completare_prefixe[lungime_prefix][nr_perechi] = (1LL * valori_unice * moduri_completare_prefixe[lungime_prefix + 1][nr_perechi + 1] +
                                                                     1LL * valori_nefolosite * moduri_completare_prefixe[lungime_prefix + 1][nr_perechi]) % MOD;
        }
    }
}

void update_aib(int aib[], int poz, int val){
    for(int i = poz; i <= n; i += (i & (-i))){
        aib[i] += val;
    }
}

int query_aib(int aib[], int poz){
    int sol = 0;

    for(int i = poz; i >= 1; i -= (i & (-i))){
        sol += aib[i];
    }

    return sol;
}

bool numarat_in_aib(int aib[], int poz){
    return (query_aib(aib, poz) - query_aib(aib, poz - 1));
}

void resetare_aib(int aib[]){
    for(int i = 1; i <= n; i++){
        aib[i] = 0;
    }
}

void precalculare_aib_frecventa_0(){
    resetare_aib(aib_frecventa_0);

    for(int i = 1; i <= n; i++){
        update_aib(aib_frecventa_0, i, 1);
    }
}

void rezolvare_query(){
    int sol, val, numar_perechi, predecesori_frecventa_0, predecesori_frecventa_1;

    sol = 0;
    numar_perechi = 0;
    resetare_aib(aib_frecventa_1);
    precalculare_aib_frecventa_0();

    for(int i = 1; i <= n; i++){
        fin >> val;

        predecesori_frecventa_0 = query_aib(aib_frecventa_0, val - 1);
        predecesori_frecventa_1 = query_aib(aib_frecventa_1, val - 1);

        sol = (1LL * sol + 1LL * predecesori_frecventa_0 * moduri_completare_prefixe[i][numar_perechi] + 1LL * predecesori_frecventa_1 * moduri_completare_prefixe[i][numar_perechi + 1]) % MOD;

        if(numarat_in_aib(aib_frecventa_0, val)){
            update_aib(aib_frecventa_0, val, -1);
            update_aib(aib_frecventa_1, val, 1);
        }
        else if(numarat_in_aib(aib_frecventa_1, val)){
            update_aib(aib_frecventa_1, val, -1);
            numar_perechi++;
        }
    }

    fout << sol << '\n';
}

void citire_si_rezolvare_queryuri(){
    fin >> q;

    for(int i = 1; i <= q; i++){
        rezolvare_query();
    }
}

int main(){
    citire_marime_siruri();
    precalculare_moduri_completare_prefixe();

    citire_si_rezolvare_queryuri();

    return 0;
}