Sto circa uscendo pazzo da fenwick2.
L’idea di base l’ho capita, la soluzione in O(n^2) sarebbe:
per ogni a[i]
dp[i] = 1
per ogni a[j] con j < i
se a[j] < a[i] dp[i] += dp[j]
A questo punto la soluzione è Σ (dp)
Con un fenwick, la soluzione diventa O(n log n):ordinare l’array tenendo conto di quali sono gli indici originari (poniamo che l’indice originario dell’elemento i sia ind(i)), poi:
update(0, 1)
per ogni a[i] con i da 1 a n - 1
update(ind(i), query(ind(i) - 1) + 1)
E a questo punto il risultato è query(n)
…solo che questa soluzione fa 10/100 e non ne capisco il motivo, anche controllando delle sequenze generate casualmente (grazie random.org) con la soluzione esponenziale vengono uguali alla soluzione con fenwick. Help!
Di seguito il codice:
#include <bits/stdc++.h>
#define lsb(i) i&(-i)
using namespace std;
const int MOD = 1000000007;
size_t n;
int *ft;
bool cmp(pair<int, int> a, pair<int, int> b)
{
if (a.first == b.first) return a.second > b.second;
return a.first < b.first;
}
void update(size_t i, int k)
{
while (i <= n) {
ft[i] += k % MOD;
i += lsb(i);
}
}
size_t query(size_t i)
{
int ans = 0;
while (i > 0) {
ans += ft[i] % MOD;
i -= lsb(i);
}
return ans % MOD;
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
pair<int, int> *a;
int temp;
cin >> n;
a = new pair<int, int>[n];
ft = new int[n + 1];
for (size_t i = 0; i < n; i++) cin >> a[i].first, a[i].second = i + 1, ft[i + 1] = 0;
sort(a, a + n, cmp);
temp = 1;
for (size_t i = 0; i < n; i++) {
if (i != 0 && a[i].first != a[i - 1].first) temp = query(a[i].second - 1) + 1;
update(a[i].second, temp % MOD);
}
cout << query(n) % MOD;
return 0;
}