Comentário Seletiva IOI 2019 - Dia 4 - Problema "Bolsa de Brinquedos"

Comentário por Henrique Vianna

Conhecimento prévio necessário:

 

Esse problema pode ser reduzido ao seguinte - dado um vetor v de tamanho N em que 1 \leq v[i] \leq M para todo 1 \leq i \leq N, sendo que cada tipo de elemento tem um custo c[i] especifico, deve-se responder a Q consultas da forma: dado um intervalo [l_i,r_i], entre os elementos cuja frequência é no mínimo K nesse intervalo, qual o valor mínimo de K*C[i], sendo i o tipo do elemento em questão?

 

Subtask 1: \leq N \leq 10^3 e 1 \leq Q \leq 10^3, valendo 10 pontos.

Para a resolução dessa parcial, basta passarmos pelo intervalo inteiro para cada uma das consultas, calculando a resposta com o auxílio de um vetor de frequência, por exemplo.

 

Subtask 2: K=1, valendo 20 pontos.

Como K=1, qualquer elemento que ocorra alguma vez no intervalo pode ser considerado para a resposta. Sendo assim, basta utilizarmos uma Segment Tree, que guarda o custo minimo considerando um dado intervalo. Com isso, conseguimos responder cada consulta em \mathcal{O}(logN).

 

Subtask 3: 1 \leq N \leq 10^5 e 1 \leq Q \leq 10^5, valendo 50 pontos

Para a resolução dessa parcial, podemos fazer a técnica de decomposição em blocos de tamanho \sqrt N: o Algoritmo de Mo. Como qualquer problema de Mo, só nos preocupamos em como adicionar e remover um índice ao intervalo atual. Para fazer isso, faremos uso de algumas estruturas auxiliares:

  • f[x] guarda a frequência de x no intervalo atual.
  • Manteremos, além disso, um multiset que guarda os custos dos tipos de brinquedos que podem ser considerados para a resposta.

Sendo assim, podemos sintetizar as operações de adição e remoção como o seguinte:

  • Adição: deve-se somar 1 a f[t[i]]. Caso f[t[i]] passe a ser K, podemos adicionar seu custo ao multiset.
  • Remoção: deve-se subtrair 1 a f[t[i]]. Caso f[t[i]] passe a ser K-1, deve-se remover o custo do multiset.

Vale notar que, por conta do TL generoso de 8 segundos, é possível que essa solução passe para 100 pontos com um Mo bem otimizado (veja o código.


#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int MAX = 1e6 + 15;
const int INF = 0x3f3f3f3f;
int n, m, k, q, c[MAX], t[MAX], T;
int ans[MAX], block[MAX], f[MAX];
struct Query
{
int l, r, id;
Query(int a = 0, int b = 0, int c = 0) : l(a), r(b), id(c) { }
bool operator < (Query other)
{
if(block[l] != block[other.l]) return block[l] < block[other.l];
return (block[l] % 2 == 0 ? r < other.r : r > other.r);
}
};
int32_t main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
for(int i = 1; i <= m; i++) cin >> c[i];
for(int i = 1; i <= n; i++) cin >> t[i];
T = sqrt(n) + 1;
for(int i = 1; i <= n; i++) block[i] = i / T;
cin >> q;
vector<Query> queries;
for(int i = 1; i <= q; i++)
{
int l, r; cin >> l >> r;
queries.emplace_back(l, r, i);
}
sort(queries.begin(), queries.end());
multiset<int> work;
auto add = [&](int x){ if(++f[x] == k) work.insert(c[x]); };
auto remove = [&](int x){ if(--f[x] == k - 1) work.erase(work.find(c[x])); };
auto getAns = [&](void){ if(work.empty()) return (int)-1; return k * (*work.begin()); };
int l = 0, r = -1;
for(auto [curL, curR, id] : queries)
{
while(l > curL) add(t[--l]);
while(r < curR) add(t[++r]);
while(l < curL) remove(t[l++]);
while(r > curR) remove(t[r--]);
ans[id] = getAns();
}
for(int i = 1; i <= q; i++)
cout << ans[i] << '\n';
}

view raw

bolsa_de_brinquedos_Mo.cpp

hosted with ❤ by GitHub

 

Subtask 4: Sem restrições adicionais.

Para a solução final, utilizaremos a técnica de line sweep, respondendo as queries de forma offline. Guardaremos um vector<int> para cada um dos tipos de brinquedos, adicionando as posições em que ele ocorreu. Passaremos pelos índices de 1 a N, mantendo uma Segment Tree que guarda em toda posição j o custo de t[j]. Ativamos uma posição apenas quando ela se torna a K-ésima ultima ocorrência de seu tipo. Para responder uma consulta, basta fazermos uma query de minimo na nossa Segment Tree. Para melhor compreensão, confira o código abaixo:


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
array<int, 4*MAXN> seg;
void update(int pos, int ini, int fim, int id, int val)
{
if (id < ini || id > fim) return;
if (ini == fim)
{
seg[pos] = val;
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
update(e, ini, m, id, val);
update(d, m+1, fim, id, val);
seg[pos] = min(seg[e], seg[d]);
}
int query(int pos, int ini, int fim, int p, int q)
{
if (q < ini || p > fim) return INF;
if (p <= ini && fim <= q) return seg[pos];
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
return min(query(e, ini, m, p, q), query(d, m+1, fim, p, q));
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K;
cin >> N >> M >> K;
vector<int> custo(M+1);
for (int i = 1; i <= M; i++) cin >> custo[i];
vector<int> v(N+1);
for (int i = 1; i <= N; i++) cin >> v[i];
int Q;
cin >> Q;
vector<vector<pair<int, int>>> queries(N+1); vector<int> resp(Q);
for (int i = 0; i < Q; i++)
{
int L, R;
cin >> L >> R;
queries[R].emplace_back(L, i);
}
seg.fill(INF);
vector<vector<int>> brinq(M+1);
for (int i = 1; i <= N; i++)
{
brinq[v[i]].push_back(i);
if (brinq[v[i]].size() >= K) update(1, 1, N, brinq[v[i]][brinq[v[i]].size() - K], custo[v[i]]);
for (auto [L, id] : queries[i]) resp[id] = query(1, 1, N, L, i);
}
for (auto x : resp) cout << (x == INF ? -1 : x * K) << '\n';
}

view raw

bolsa_de_brinquedos.cpp

hosted with ❤ by GitHub