Per risolvere questo problema ho prima provato con un bubblesort che contava le inversioni (che andava in TLE), poi ho implementato un Fenwick tree…che sta ampiamente nei limiti, ma dà WA nell’ultimo subtask! Eppure non riesco a capire quale sia il problema. Questa è la mia implementazione.
#include
#include
#include
#define MAXN 200000
class fenwickTree
{
private:
std::vector ft;
public:
fenwickTree(int N)
{
ft.assign(N + 1, 0);
}
int rsq(int i)
{
int ans = 0;
while(i != 0)
{
ans += ft[i];
i -= (i & (-i));
}
return ans;
}
void adjust(int k, int v)
{
while(k < (int)ft.size())
{
ft[k] += v;
k += (k & (-k));
}
}
};
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int N;
int ans=0;
int sidi[MAXN];
std::cin >> N;
for(int i = 0; i < N; i++)
std::cin >> sidi[i];
fenwickTree ft(*std::max_element(sidi, sidi+N));
for(int i = N - 1; i >= 0; i--)
{
ans += ft.rsq(sidi[i]);
ft.adjust(sidi[i], 1);
}
std::cout << ans;
return 0;
}
EDIT: avevo sbagliato codice xD questo è quello che ho uploadato in realtà
