Cod sursă (job #785890)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int DIM = 5e3;
const int MOD = 1e9 + 7;

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

struct Aib {
  int aib[1 + DIM], size;

  void init( int n ) {
    size = n;
    for ( int i = 1; i <= n; ++i ) {
      aib[i] = 0;
    }
  }
  void upd( int pos, int add ) {
    while ( pos <= size ) { 
      aib[pos] += add;
      pos += pos & -pos;
    }
  }
  int sum( int pos ) {
    int res = 0;
    while ( pos > 0 ) {
      res += aib[pos];
      pos -= pos & -pos;
    }
    return res;
  }
};

inline void addmod( int &a, int b ) {
  a += b;
  if ( a >= MOD ) a -= MOD;
}

int cnt[1 + DIM][1 + DIM / 2];

void get_cnt( int n ) {
  for ( int i = 0; i <= n / 2; ++i ) {
    cnt[n][i] = 1;
  }
  for ( int i = n - 1; i >= 1; --i ) {
    for ( int p = 0; p <= i / 2; ++p ) {
      int uniq = i - 2 * p, rem = n - i + p;
      addmod(cnt[i][p], (ll)cnt[i + 1][p + 1] * uniq % MOD);
      addmod(cnt[i][p], (ll)cnt[i + 1][p] * rem % MOD);
    }
  }
}

int uses[1 + DIM];

void solve_queries( int n, int q ) {
  Aib two; // aib pentru valorile cu 2 "folosiri" ramase
  Aib one; // aib pentru valorile cu 1 "folosire" ramasa
  while ( q-- ) {
    two.init(n);
    one.init(n);
    for ( int i = 1; i <= n; ++i ) {
      two.upd(i, +1);
      uses[i] = 2;
    }
    int val, rank = 0, pairs = 0;
    for ( int i = 1; i <= n; ++i ) {
      fin >> val; 

      addmod(rank, (ll)two.sum(val - 1) * cnt[i][pairs] % MOD);
      addmod(rank, (ll)one.sum(val - 1) * cnt[i][pairs + 1] % MOD);

      --uses[val];
      if ( uses[val] == 1 ) {
 	two.upd(val, -1);
	one.upd(val, +1);
      } else {
	one.upd(val, -1);
	++pairs;
      }
    }
    fout << rank << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int n, q;

  fin >> n >> q;

  get_cnt(n);
  solve_queries(n, q);

  fin.close();
  fout.close();
  return 0;
}