Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/k-RYEjhwNTo_XdaCidXQUGMU/site/?key=statement
Zrobiłem mniej więcej takim pomysłem, jak jest opisane w książeczce z XXII OI: https://oi.edu.pl/l/22oi_ksiazeczka/
Robie sumy prefiksowe. Pierwsze wystąpienie dodaje do sum prefiksowych wartość koszty[i], drugie odejmuje koszty[j], a późniejsze nic nie robią, chyba że w aktualizacjach one staną się wcześniejsze. W książeczce OI napisali, że można to zrobić drzewem przedziałowym i tyle.
Ja napisałem drzewo przedzial-przedział (dodaj na przedziale, odczytaj maxa na przedziale), ale dostaję tylko 33pkt(przekroczono limit czasu), wydaje mi się, to trochę dziwne, ale nie wiem co zrobić innaczej. Kod:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
int n = 0, m = 0, base = (1 << 20), rozmiar_drzewa = base * 2;
ll suma = 0, wyn = 0;
vector<int> liczby;
vector<vector<int>> wystapienia;
vector<int> koszty;
vector<int> wystapienia_wsk;
vector<ll> tree;
vector<ll> tree2;
inline ll querry_max(int l_kontrolowane, int p_kontrolowane, int l_zap, int p_zap, int v)
{
if (l_kontrolowane > p_zap or p_kontrolowane < l_zap)
return 0;
else if (l_kontrolowane >= l_zap and p_kontrolowane <= p_zap)
return tree[v];
else if (l_kontrolowane != p_kontrolowane)
{
if (tree2[v] != 0)
{
tree2[v*2+1] += tree2[v];
tree2[v*2] += tree2[v];
tree[v*2+1] += tree2[v];
tree[v*2] += tree2[v];
tree2[v] = 0;
}
return max(querry_max(l_kontrolowane,l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1 - 2) / 2,l_zap,p_zap,v*2), querry_max(l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1) / 2,p_kontrolowane,l_zap,p_zap,v*2+1));
}
}
inline void update (int l_kontrolowane, int p_kontrolowane, int l_zap, int p_zap, int v, int val)
{
//cout << "V: " << v << endl;
if (l_kontrolowane > p_zap or p_kontrolowane < l_zap)
return;
else if (l_kontrolowane >= l_zap and p_kontrolowane <= p_zap)
{
tree[v] += val;
tree2[v] += val;
}
else if (l_kontrolowane != p_kontrolowane)
{
if (tree2[v] != 0)
{
tree2[v*2+1] += tree2[v];
tree2[v*2] += tree2[v];
tree[v*2+1] += tree2[v];
tree[v*2] += tree2[v];
tree2[v] = 0;
}
update(l_kontrolowane,l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1 - 2) / 2,l_zap,p_zap,v*2,val);
update(l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1) / 2,p_kontrolowane,l_zap,p_zap,v*2+1,val);
tree[v] = max(tree[v*2], tree[v*2+1]);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
tree.assign(rozmiar_drzewa,0);
tree2.assign(rozmiar_drzewa,0);
liczby.assign(n,-1);
for (int i = 0; i < n; ++i)
cin >> liczby[i];
wystapienia.assign(1e6+1,{});
wystapienia_wsk.assign(1e6+1,0);
for (int i = 0; i < n; ++i)
wystapienia[liczby[i]].push_back(i);
koszty.assign(m+1,-1);
for (int i = 1; i <= m; ++i)
cin >> koszty[i];
for (int i = 0; i < n; ++i)
{
if (wystapienia_wsk[liczby[i]] == 0)
suma += koszty[liczby[i]];
else if (wystapienia_wsk[liczby[i]] == 1)
suma -= koszty[liczby[i]];
wystapienia_wsk[liczby[i]]++;
update(1,base,i+1,i+1,1,suma);
}
fill(wystapienia_wsk.begin(), wystapienia_wsk.end(), 0);
ll ile_dod = 0;
for (int i = 0; i < n; ++i)
{
wyn = max(wyn, querry_max(1,base,i+1,n,1) + ile_dod);
int val = liczby[i];
if (wystapienia_wsk[val] + 1 == wystapienia[val].size())
ile_dod += -koszty[val];
else if (wystapienia_wsk[val] + 2 == wystapienia[val].size())
{
ile_dod += -koszty[val];
update(1,base, wystapienia[val][wystapienia_wsk[val]+1]+1,n,1,2 * koszty[val]);
}
else
{
ile_dod += -koszty[val];
update(1,base,wystapienia[val][wystapienia_wsk[val]+1]+1,n,1,2 * koszty[val]);
update(1,base,wystapienia[val][wystapienia_wsk[val]+2]+1,n,1,-koszty[val]);
}
wystapienia_wsk[val]++;
}
cout << wyn << '\n';
return 0;
}
Co ciekawe samo napełnienie drzewa początkowe zajmuje mniej więcej połowę czasu.
Z góry dziękuję za pomoc i poświęcony czas!