愚直にシミュレーションすると になりTLEしていまいます。Fenwick Treeを用いて転倒数を高速に求めても になり厳しいです。
転倒数は左りに整数 があり、右に整数 があるようなペア で影響されます。
例として ではペア がそれぞれ 1, 2, 2, 1個あります。
そのようなペアは の100通りしかありません。これらのペアの中で を満足するペアの個数が転倒数となります。上の数列では の個数 2 が転倒数となります。
また、クエリごとに変化した数列のペアも100種類しかないです。また、ペアは から に変化します。
よってクエリごとに数列の要素の種類数を とすると の計算量で転倒数を計算できます。
最初にペアの個数を計算するのに かかるため、この問題が で解けました。
実装例(c++)
c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
int n, q; cin >> n >> q;
vector<int> p(n);
for(int i = 0; i < n; i++) cin >> p[i];
vector<vector<int>> v(10, vector<int>(10, 0));
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
v[p[i]][p[j]]++;
}
}
while(q--)
{
vector<int> t(10);
for(int i = 0; i < 10; i++) cin >> t[i];
int ans = 0;
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < 10; j++)
{
if(t[i] > t[j]) ans += v[i][j];
}
}
cout << ans << '\n';
}
}