Cod sursă (job #785978)

#include <fstream>
#define mod 1000000007
using namespace std;
ifstream fin ("dejavu.in");
ofstream fout ("dejavu.out");
int n,q,fr2,dp[5001][5001],v[5001],fr[5001],aib1[5001],aib2[5001];
void update (int aib[],int pos,int val)
{
    while (pos<=n)
    {
        aib[pos]+=val;
        pos+=(pos&(-pos));
    }
}
int query (int aib[],int pos)
{
    int sol=0;
    while (pos>0)
    {
        sol+=aib[pos];
        pos-=(pos&(-pos));
    }
    return sol;
}
void read_init ()
{
    for (int i=1; i<=n; i++)
        fin>>v[i];
    for (int i=1; i<=n; i++)
        aib1[i]=aib2[i]=0;
    for (int i=1; i<=n; i++)
    {
        update (aib2,i,1);
        fr[i]=2; ///frecventa fiecarui numar este 2 la inceput
    }
}
void make_dp ()
{
    ///dp[n][per]=cate posibilitati exista de a completa prefix cu n numere cu per perechi
    ///se pune un numar deja din prefix => unic*dp[i+1][per+1]
    ///se pune un numar care nu este in prefix => nefol*dp[i+1][per]
    for (int per=0; per<=n/2; per++)
        dp[n][per]=1;
    for (int i=n-1; i>0; i--)
    {
        for (int per=0; per<=i/2; per++)
        {
            int unic=i-2*per; ///cate numere mai pot fi folosite o data
            int nefol=n-per-unic; ///cate numere pot fi folosite de doua ori
            dp[i][per]=(1ll*unic*dp[i+1][per+1]%mod+1ll*nefol*dp[i+1][per]%mod)%mod;
        }
    }
}
int get_sol (int i)
{
    int nr2=query (aib2,v[i]-1); ///cate numere au frecventa=2
    int nr1=query (aib1,v[i]-1); ///cate numere au frecventa=1
    return (1ll*nr2*dp[i][fr2]%mod+1ll*nr1*dp[i][fr2+1]%mod)%mod;
}
void update_pos (int i)
{
    if (fr[v[i]]==2)
    {
        fr[v[i]]=1;
        update (aib2,v[i],-1);
        update (aib1,v[i],1);
    }
    else if (fr[v[i]]==1)
    {
        fr[v[i]]=0;
        fr2++;
        update (aib1,v[i],-1);
    }
}
void solve_queries ()
{
    while (q--)
    {
        int sol=0;
        read_init ();
        fr2=0; ///cate numere au fost folosite de 2 ori in prefix
        for (int i=1; i<=n; i++)
        {
            sol=(sol+get_sol (i))%mod;
            update_pos (i);
        }
        fout<<sol<<"\n";
    }
}
int main()
{
    fin>>n>>q;
    make_dp ();
    solve_queries ();
    return 0;
}