A. [P12074] L'exercice arithmétique (3)
Lien du problème : P12074
On détermine la validité d'une suite de signes pour les \(a_i\) en parcourant de droite à gauche. On regarde les indices avec le même \(j\) comme des chaînes. L'insertion d'un élément ne dépend que de la parité de la longueur de la chaîne actuelle. Il suffit donc de compter le nombre de chaînes de longueur impaire.
On définit \(f_{i,j}\) comme le nombre de chaînes de longueur impaire dans \([i,n]\). En reformulant l'état comme le nombre de symboles \(+1\) dans le suffixe, on peut prouver que le tableau dp est convexe. La transition est maintenue avec un std::multiset, et les bornes supérieure et inférieure des états sont calculées dynamiquement.
Complexité temporelle : \(\mathcal O(n\log n)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 3e5 + 5;
const ll INF = 1e18;
ll valeurs[MAXN];
void resoudre() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) cin >> valeurs[i];
reverse(valeurs + 1, valeurs + m + 1);
ll total = 0;
multiset<ll> ensemble;
for (int i = 1, limite, precedent = 0; i <= m; ++i, precedent = limite) {
limite = min(i, (n + i) / 2);
ensemble.insert(2 * valeurs[i]);
if (limite == precedent) ensemble.erase(ensemble.begin());
if (i % 2 == 1) {
total += *ensemble.rbegin();
ensemble.erase(--ensemble.end());
}
}
for (auto val : ensemble) total += max(0ll, val);
cout << total - accumulate(valeurs + 1, valeurs + m + 1, 0ll) << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests;
cin >> tests;
while (tests--) resoudre();
return 0;
}
B. [P13786] LCS des permutations (8)
Lien du problème : P13786
En supposant \(p = [1,\dots,n]\), alors \(a = \mathrm{LIS}(q)\) et \(b = \mathrm{LIS}(r)\). D'après les contraintes partielles \(a=1, c=n\), on conjecture que les conditions légales sont \(abc \ge n\), \(a+b \le c+n\) et leurs rotations.
La condition \(a+b \le c+n\) est évidente car les LIS de longueur \(a\) et \(b\) ont au moins une LCS de longueur \(a+b-n\). Lorsque \(abc < n\), on a \(\mathrm{LDS}(q) \ge \frac{n}{a} \ge bc+1\). En considérant l'ordre des éléments de \(\mathrm{LDS}(q)\) dans \(r\), on obtient des contradictions sur les produits de LIS et LDS.
La construction pour \(n=abc\) utilise des séquences ascendantes avec des domaines décroissants et des séquences descendantes avec des domaines croissants. En appliquant cela, on obtient \(q\) avec \(bc\) séquences ascendantes de longueur \(a\), et \(r\) avec \(b\) séquences descendantes de longueur \(ac\), donnant une LCS de longueur \(a\).
Complexité temporelle : \(\mathcal O(n\log n)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 5;
void resoudre() {
ll n, a, b, c, type, m;
cin >> n >> a >> b >> c >> type;
m = n;
if (a * b * c < n || a + b > c + n || a + c > b + n || b + c > a + n) {
cout << "No\n";
return;
}
cout << "Yes\n";
if (!type) return;
int compteur = 0;
for (; n && (a - 1) * (b - 1) * (c - 1) >= n - 1; ++compteur, --a, --b, --c, --n);
basic_string<int> B, C;
if (!n);
else if (a + b + c - 2 > n) {
for (int i = n - 1; ~i; --i) B += i, C += i;
swap(B[0], B[1]);
swap(C[1], C[2]);
} else {
map<ll, int> X;
vector<array<ll, 2>> Y, Z;
auto inserer = [&](ll x) {
X[x] = 0;
Y.push_back({-(x / a), x});
Z.push_back({x / a / c, -x});
};
inserer(0);
for (int i = 1; i < a; ++i) inserer(i);
for (int i = 1; i < b; ++i) inserer(a * c * i);
for (int i = 1; i < c; ++i) inserer(a * i);
for (int i = 0; i < n && (int)X.size() < n; ++i)
if (!X.count(i)) inserer(i);
sort(Y.begin(), Y.end());
sort(Z.begin(), Z.end());
int t = 0;
for (auto &o : X) o.second = t++;
for (auto o : Y) B += X[o[1]];
for (auto o : Z) C += X[-o[1]];
}
for (int i = n; i < m; ++i) B += i, C += i;
for (int i = 0; i < m; ++i) cout << i + 1 << " \n"[i == m - 1];
for (int i = 0; i < m; ++i) cout << B[i] + 1 << " \n"[i == m - 1];
for (int i = 0; i < m; ++i) cout << C[i] + 1 << " \n"[i == m - 1];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests;
cin >> tests;
while (tests--) resoudre();
return 0;
}
C. [P14470] L'écureuil (3)
Lien du problème : P14470
La transition consiste à énumérer une couleur \(c\), puis à xor les valeurs SG de chaque segment continu obtenu après suppression de cette couleur. On observe que les intervalles \([l,r]\) après une transition satisfont que \(a_{r+1}\) ou \(a_{l-1}\) n'apparaît pas dans \(a[l,r]\). En énumérant \(l\), les intervalles où \(a_{r+1} \notin a[l,r]\) sont au plus \(V\) en nombre.
On prétraite les valeurs SG de tous ces intervalles. Pour accélérer le calcul de la somme xor après suppression d'une couleur, on traite les intervalles où \(a_{l-1} = a_{r+1}\) comme des intervalles consécutifs.
Complexité temporelle : \(\mathcal O((nV+q)V)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, q, a[MAXN], prochain[MAXN];
array<int, 32> L[MAXN], R[MAXN], f[MAXN], g[MAXN], somme[MAXN];
bool visite[MAXN];
int dp(int l, int r) {
if (l == r) return 1;
if (r - l == 1) return a[l] == a[r];
unsigned long long masque = -1;
for (int v = 0; v < 32; ++v) {
if (R[l][v] < r) {
int x = R[l][v], y = L[r][v], z = somme[x][v] ^ somme[y][v];
if (v != a[l] || x > l + 1) z ^= f[l + (v == a[l])][v];
if (v != a[r] || y < r - 1) z ^= g[r - (v == a[r])][v];
masque &= ~(1ll << z);
}
}
if (R[l][a[l]] > r) masque &= ~(1ll << g[r][a[l]]);
if (R[l][a[r]] == r) masque &= ~(1ll << f[l + (a[l] == a[r])][a[r]]);
return __builtin_ctzll(masque);
}
vector<array<int, 2>> requetes[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
--a[i];
L[i + 1] = L[i];
L[i + 1][a[i]] = i;
}
R[n].fill(n + 1);
for (int i = n; i >= 1; --i) {
R[i - 1] = R[i];
prochain[i] = R[i][a[i]];
R[i - 1][a[i]] = i;
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 32; ++j) {
if (j != a[i]) requetes[L[i][j] + 1].push_back({i, j});
}
}
for (int i = n; i >= 1; --i) {
for (int j = 0; j < 32; ++j) requetes[i].push_back({R[i][j] - 1, 32 + j});
sort(requetes[i].begin(), requetes[i].end());
for (auto &req : requetes[i]) {
if (req[1] < 32) g[req[0]][req[1]] = dp(i, req[0]);
else f[i][req[1] - 32] = dp(i, req[0]);
}
somme[i] = somme[i + 1];
if (R[i][a[i]] > i + 1) somme[i][a[i]] ^= f[i + 1][a[i]];
}
for (int l, r; q--;) {
cin >> l >> r;
cout << (dp(l, r) ? "Toni\n" : "Jakov\n");
}
return 0;
}
D. [P12204] Élection du comité (7)
Lien du problème : P12204
En inversant les arêtes, on exige que chaque point blanc ait au moins un prédécesseur noir. On colore chaque SCC alternativement en noir et blanc, mais sans arête de noir à noir entre SCC. On traite par ordre topologique : à chaque étape, on colore tous les SCC sans degré entrant en alternant, et on supprime ces points.
Pour optimiser, on observe que la suppression ne fait que diviser les SCC initiaux, et le graphe reste biparti. On colore les points sans degré entrant en noir, puis on supprime récursivement les successeurs. On utilise une approche similaire à un tri topologique pour la suppression, puis on choisit une coloration bipartite.
Complexité temporelle : \(\mathcal O(n+m)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
basic_string<int> G[MAXN], V[MAXN], E[MAXN];
int n, m, dfn[MAXN], basse[MAXN], compteurDfn, pile[MAXN], hautPile, bloc[MAXN], compteurSCC, degre[MAXN], entrant[MAXN];
bool dansPile[MAXN], visite[MAXN], couleur[MAXN];
void tarjan(int u) {
dfn[u] = basse[u] = ++compteurDfn;
pile[++hautPile] = u;
dansPile[u] = true;
for (int v : G[u]) {
if (!dfn[v]) {
tarjan(v);
basse[u] = min(basse[u], basse[v]);
} else if (dansPile[v]) {
basse[u] = min(basse[u], dfn[v]);
}
}
if (basse[u] == dfn[u]) {
++compteurSCC;
while (dansPile[u]) {
bloc[pile[hautPile]] = compteurSCC;
dansPile[pile[hautPile--]] = false;
}
}
}
void coloreSCC(int u, int x) {
visite[u] = true;
for (int v : G[u]) {
if (bloc[v] == x && !visite[v]) {
couleur[v] = couleur[u] ^ 1;
coloreSCC(v, x);
}
}
}
void traite(int x) {
queue<int> file;
for (int u : V[x]) {
if (!visite[u] && !entrant[u]) file.push(u);
}
while (!file.empty()) {
int u = file.front();
file.pop();
couleur[u] = 1;
visite[u] = 1;
for (int v : G[u]) {
if (bloc[v] == x && !visite[v]) {
visite[v] = 1;
for (int e : G[v]) {
if (bloc[e] == x && !visite[e] && !--entrant[e]) file.push(e);
}
}
}
}
for (int u : V[x]) {
if (!visite[u]) coloreSCC(u, x);
}
for (int u : V[x]) {
if (couleur[u]) {
for (int v : G[u]) {
if (!visite[v]) {
visite[v] = 1;
for (int e : G[v]) {
if (bloc[e] == bloc[v]) --entrant[e];
}
}
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
G[v] += u;
}
for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; ++i) {
V[bloc[i]] += i;
dfn[i] = basse[i] = 0;
for (int j : G[i]) {
if (bloc[i] != bloc[j]) {
E[bloc[i]] += bloc[j];
++degre[bloc[j]];
} else ++entrant[j];
}
}
compteurDfn = 0;
queue<int> file;
for (int i = 1; i <= compteurSCC; ++i) if (!degre[i]) file.push(i);
while (!file.empty()) {
int u = file.front();
file.pop();
traite(u);
for (int v : E[u]) if (!--degre[v]) file.push(v);
}
cout << count(couleur + 1, couleur + n + 1, 1) << "\n";
for (int i = 1; i <= n; ++i) if (couleur[i]) cout << i << " ";
cout << "\n";
return 0;
}
E. [P11924] Le voleur avide (4.5)
Lien du problème : P11924
On effectue un DP de droite à gauche, maintenant dynamiquement les montants \(f_i\) que chaque personne reçoit dans le suffixe courant. En ajoutant une nouvelle personne \(x\), on satisfait les demandes de la moitié des personnes par ordre croissant de \(f_i + a_i\), et les autres obtiennent \(f \gets 0\). Si \(m\) ne suffit pas, alors \(f_x \gets -\infty\).
On remarque que la plage de valeurs de \(f\) est \(\mathcal O(V)\), car après la dernière opération avec \(f_i \neq \infty\), au moins la moitié des \(f_i \le 0\). On maintient directement le nombre d'éléments pour chaque paire \((a_i, f_i)\) et on calcule les points satisfaits avec \(a_i + f_i \le w\).
Complexité temporelle : \(\mathcal O(nV^2 + nV \log n)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 5, MAXS = 4e7 + 5;
int n, m, gauche[MAXS], droite[MAXS], compteur[MAXS], totalNoeuds;
void insertion(int x, int &p, int l = 1, int r = n) {
if (!p) p = ++totalNoeuds;
++compteur[p];
if (l == r) return;
int milieu = (l + r) >> 1;
if (x <= milieu) insertion(x, gauche[p], l, milieu);
else insertion(x, droite[p], milieu + 1, r);
}
void fusion(int q, int &p, int l = 1, int r = n) {
if (!p || !q) { p |= q; return; }
compteur[p] += compteur[q];
if (l == r) return;
int milieu = (l + r) >> 1;
fusion(gauche[q], gauche[p], l, milieu);
fusion(droite[q], droite[p], milieu + 1, r);
}
void separation(int u, int x, int &p, int &q, int l = 1, int r = n) {
if (!u) { p = q = 0; return; }
if (l == r) { p = u; q = 0; return; }
int milieu = (l + r) >> 1;
if (x <= milieu) {
p = ++totalNoeuds;
q = u;
separation(gauche[u], x, gauche[p], gauche[q], l, milieu);
} else {
p = u;
q = ++totalNoeuds;
separation(droite[u], x, droite[p], droite[q], milieu + 1, r);
}
compteur[q] = compteur[gauche[q]] + compteur[droite[q]];
compteur[p] = compteur[gauche[p]] + compteur[droite[p]];
}
int q = 64, a[MAXN], f[MAXN], racine[75][75], bornes[75], tmpBornes[75], nouveau[75][75];
void dfs(int x, int p, int l = 1, int r = n) {
if (!compteur[p]) return;
if (l == r) { f[l] = x; return; }
int milieu = (l + r) >> 1;
dfs(x, gauche[p], l, milieu);
dfs(x, droite[p], milieu + 1, r);
}
int requete(int k) {
int l = 1, r = n;
memcpy(tmpBornes, bornes, sizeof(bornes));
while (l < r) {
int milieu = (l + r) >> 1, w = 0;
for (int i = 1; i <= q; ++i) w += compteur[gauche[tmpBornes[i]]];
for (int i = 1; i <= q; ++i) tmpBornes[i] = (w < k ? droite[tmpBornes[i]] : gauche[tmpBornes[i]]);
if (w < k) { k -= w; l = milieu + 1; }
else r = milieu;
}
return l;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
reverse(a + 1, a + n + 1);
int special = 0;
for (int k = 1; k <= n; ++k) {
memset(nouveau, 0, sizeof(nouveau));
int t = (k - 1) / 2;
f[k] = m;
for (int v = 0; ; ++v) {
int c = 0;
for (int i = 1; i <= q; ++i) {
bornes[i] = (!v ? racine[q + 1][i] : (i <= v ? racine[v - i][i] : 0));
c += compteur[bornes[i]];
}
f[k] -= v * min(c, t);
if (f[k] < 0) break;
if (c >= t) {
int h = requete(t);
for (int i = 1, l, r; i <= q; ++i) {
separation(bornes[i], h, l, r);
fusion(l, nouveau[v][i]);
fusion(r, nouveau[0][i]);
}
for (int y = 1; y <= q; ++y) fusion(racine[q + 1][y], nouveau[0][y]);
for (int x = 0; x <= q; ++x) {
for (int y = 1; y <= q; ++y) {
if (x + y > v) fusion(racine[x][y], nouveau[0][y]);
if (x + y < v) fusion(racine[x][y], nouveau[x + y][y]);
}
}
break;
}
t -= c;
}
if (f[k] < 0) {
f[k] = -1;
insertion(k, racine[q + 1][a[k]]);
continue;
}
if (special) {
insertion(special, nouveau[0][a[special]]);
special = 0;
}
if (f[k] <= q) insertion(k, nouveau[f[k]][a[k]]);
else special = k;
memcpy(racine, nouveau, sizeof(nouveau));
}
for (int x = 0; x <= q + 1; ++x) {
for (int y = 1; y <= q; ++y) {
dfs(x > q ? -1 : x, racine[x][y]);
}
}
for (int i = n; i; --i) cout << f[i] << " \n"[i == 1];
return 0;
}
F. [P14471] L'étincelle (8)
Lien du problème : P14471
Pour \(t=0\), c'est un problème classique de sac à dos sur l'ordre dfn, réalisable en \(\mathcal O(nk)\). Pour gérer les informations de sous-arbre, on note que la restriction est que pour chaque opération \(u\), on ne peut pas sélectionner plus de \(c_u - w_u\) fois, où \(w_u\) est le nombre de points dans le sous-arbre sélectionnés par l'opération 1.
On traite les informations de sous-arbre comme des intervalles sur l'ordre dfn. On maintient les préfixes des sélections des opérations 1 et 2, et on optimise les transitions avec une file monotone. Si \(u\) n'est pas sélectionné par l'opération 2, on transfère directement de \(l_u\) à \(r_u\).
Complexité temporelle : \(\mathcal O(nkt \log t)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e4 + 5;
const ll inf = 1e18;
int n, k, t, gain[MAXN], parent[MAXN], a[MAXN * 2], m, debut[MAXN], fin[MAXN];
ll poids[MAXN], distance[MAXN];
vector<int> graphe[MAXN];
basic_string<ll> valeurs[MAXN];
void dfs(int u) {
distance[u] = poids[u] + distance[parent[u]];
valeurs[u] = {distance[u]};
a[++m] = u;
debut[u] = m;
for (int v : graphe[u]) {
dfs(v);
int ancienTaille = valeurs[u].size();
valeurs[u] += valeurs[v];
inplace_merge(valeurs[u].begin(), valeurs[u].begin() + ancienTaille, valeurs[u].end(), greater<>());
if ((int)valeurs[u].size() > t) valeurs[u].resize(t);
}
a[++m] = u;
fin[u] = m;
}
vector<vector<ll>> f[MAXN * 2];
ll g[MAXN], h[MAXN];
void diviserPourRegner(int l, int r, int L, int R, const basic_string<ll> &C) {
if (l > r) return;
int milieu = (l + r) >> 1;
int M = 0;
for (int i = L; i <= R && i <= milieu; ++i) {
ll z = g[milieu - i] + C[i];
if (z > h[milieu]) { h[milieu] = z; M = i; }
}
diviserPourRegner(l, milieu - 1, L, M, C);
diviserPourRegner(milieu + 1, r, M, R, C);
}
void transition(int L, int R) {
static int file[MAXN];
for (int i = 0, gauche = 1, droite = 0; i <= k; ++i) {
for (; gauche <= droite && file[gauche] < i - R; ++gauche);
h[i] = L ? -inf : g[i];
if (gauche <= droite) h[i] = max(h[i], g[file[gauche]]);
for (; gauche <= droite && g[file[droite]] <= g[i]; --droite);
file[++droite] = i;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k >> t;
for (int i = 1; i <= n; ++i) cin >> gain[i] >> poids[i];
for (int i = 2; i <= n; ++i) {
cin >> parent[i];
graphe[parent[i]].push_back(i);
}
dfs(1);
for (int i = 1; i <= n; ++i) {
valeurs[i].insert(valeurs[i].begin(), 0);
for (int j = 1; j < (int)valeurs[i].size(); ++j) valeurs[i][j] += valeurs[i][j - 1];
}
for (int i = 0; i <= 2 * n; ++i) f[i] = vector<vector<ll>>(t + 1, vector<ll>(k + 1, -inf));
f[0][0][0] = 0;
for (int o = 1; o <= 2 * n; ++o) {
int u = a[o];
if (o == debut[u]) {
for (int j = 0; j <= k; ++j) {
for (int i = 0; i <= t; ++i) g[i] = f[o - 1][i][j];
h[i] = -inf;
diviserPourRegner(0, t, 0, valeurs[u].size() - 1, valeurs[u]);
for (int i = 0; i <= t; ++i) f[fin[u]][i][j] = max(f[fin[u]][i][j], h[i]);
}
for (int i = 0; i <= t; ++i) {
for (int j = 0; j <= k; ++j) g[j] = f[o - 1][i][j] - poids[u] * j;
transition(0, i);
for (int j = 0; j <= k; ++j) {
f[o][i][j] = max(f[o][i][j], h[j] + poids[u] * j);
if (i < t) f[o][i + 1][j] = max(f[o][i + 1][j], h[j] + poids[u] * j + distance[u]);
}
}
} else {
for (int i = 0; i <= t; ++i) {
for (int j = 0; j <= k; ++j) g[j] = f[o - 1][i][j] - poids[u] * j;
transition(1, gain[u] - i);
for (int j = 0; j <= k; ++j) f[o][i][j] = max(f[o][i][j], h[j] + poids[u] * j);
}
}
}
cout << *max_element(f[2 * n][t].begin(), f[2 * n][t].end()) << "\n";
return 0;
}
G. [P11611] La réduction (3.5)
Lien du problème : P11611
Les restrictions sont des segments de la forme \(s[l,r] \neq t\). On utilise l'inclusion-exclusion. D'abord, on élimine les restrictions qui se contiennent mutuellement et peuvent coexister, ce qui peut être décrit par un automate AC. On trie ensuite les restrictions par \(r\) et on effectue un DP en ne considérant que les relations entre intervalles adjacents.
Pour les intervalles qui se chevauchent, on énumère les suffixes et préfixes correspondants et on utilise le hachage de chaînes pour une transition rapide. Pour les intervalles disjoints, on utilise un arbre de Fenwick pour une maintainance simple.
Complexité temporelle : \(\mathcal O(|S| \log |S|)\).
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int MAXN = 1e6 + 5, MOD = 1e9 + 7, i2 = (MOD + 1) / 2, P = 1e6 + 3;
ll puissance[MAXN], puissanceInverse[MAXN], f[MAXN];
int n, m, transition[MAXN][2], echec[MAXN], total;
struct Info { int l, r, p; vector<int> w; } a[MAXN];
int inserer(vector<int> &s) {
int p = 0;
for (int c : s) p = transition[p][c] = transition[p][c] ? transition[p][c] : ++total;
return p;
}
vector<int> grapheEchec[MAXN];
int dfn[MAXN], finDfn[MAXN], compteurDfn;
void construire() {
queue<int> file;
for (int c : {0, 1}) if (transition[0][c]) file.push(transition[0][c]);
while (!file.empty()) {
int u = file.front();
file.pop();
grapheEchec[echec[u]].push_back(u);
for (int c : {0, 1}) {
if (transition[u][c]) {
echec[transition[u][c]] = transition[echec[u]][c];
file.push(transition[u][c]);
} else {
transition[u][c] = transition[echec[u]][c];
}
}
}
}
void dfs(int u) {
dfn[u] = ++compteurDfn;
for (int v : grapheEchec[u]) dfs(v);
finDfn[u] = compteurDfn;
}
struct ArbreFenwick {
ll arbre[MAXN], somme;
void ajouter(int x, int v) { for (; x <= n + 1; x += x & -x) arbre[x] = (arbre[x] + v) % MOD; }
ll requete(int x) { somme = 0; for (; x; x &= x - 1) somme = (somme + arbre[x]) % MOD; return somme; }
} T;
struct ArbreFenwick2 {
int arbre[MAXN], somme, pile[MAXN], hautPile;
void ajouter(int x, int v) { pile[++hautPile] = x; for (; x <= compteurDfn; x += x & -x) arbre[x] += v; }
int requete(int x) { somme = 0; for (; x; x &= x - 1) somme += arbre[x]; return somme; }
void initialiser() { while (hautPile) for (int x = pile[hautPile--]; x <= compteurDfn; x += x & -x) arbre[x] = 0; }
} Q;
vector<array<int, 2>> ajout[MAXN];
mt19937_64 generateurAleatoire(time(0));
ull hashValeur[MAXN][2], cle[MAXN];
int compteur, prochainCle[MAXN], tete[P], g[MAXN];
void ajouterHash(ull s, int z) {
for (int x = tete[s % P]; x; x = prochainCle[x]) {
if (cle[x] == s) { g[x] = (g[x] + z) % MOD; return; }
}
cle[++compteur] = s;
g[compteur] = z;
prochainCle[compteur] = tete[s % P];
tete[s % P] = compteur;
}
int requeteHash(ull s) {
for (int x = tete[s % P]; x; x = prochainCle[x]) if (cle[x] == s) return g[x];
return 0;
}
signed main() {
cin >> n;
getchar();
string S;
for (int i = puissance[0] = puissanceInverse[0] = 1; i <= n + 1; ++i) {
puissance[i] = puissance[i - 1] * 2 % MOD;
puissanceInverse[i] = puissanceInverse[i - 1] * i2 % MOD;
hashValeur[i][0] = generateurAleatoire();
hashValeur[i][1] = generateurAleatoire();
}
for (char c = getchar(); c != '\n'; c = getchar()) if (c != ' ') S += c;
for (int l = 0, r; l < (int)S.size(); l = r + 2) {
for (r = l; S[r] != ')'; ++r);
int L = n, R = 0;
vector<int> s;
for (int x = l + 1, y, z; x < r; x = y + 1) {
for (y = x + 1 + (S[x] == '~'), z = 0; isdigit(S[y]); ++y) z = z * 10 + S[y] - '0';
s.push_back(S[x] == '~' ? -z : z);
L = min(L, z);
R = max(R, z);
}
++m;
a[m].l = L;
a[m].r = R;
a[m].w = vector<int>(R - L + 1, 1);
for (int x : s) if (x > 0) a[m].w[x - L] = 0;
a[m].p = inserer(a[m].w);
}
construire();
dfs(0);
for (int i = 1; i <= m; ++i) {
ajout[a[i].r].push_back({dfn[a[i].p], 1});
ajout[a[i].r].push_back({finDfn[a[i].p] + 1, -1});
}
for (int i = 1; i <= n; ++i) {
ajout[i].push_back({0, 0});
sort(ajout[i].begin(), ajout[i].end());
for (int j = 1; j < (int)ajout[i].size(); ++j) ajout[i][j][1] += ajout[i][j - 1][1];
}
sort(a + 1, a + m + 1, [&](auto &x, auto &y) { return x.r != y.r ? x.r < y.r : x.l > y.l; });
T.ajouter(1, puissanceInverse[1]);
for (int i = 1; i <= m; ++i) {
if (i > 1 && a[i].r > a[i - 1].r) Q.initialiser();
if (Q.requete(dfn[a[i].p])) continue;
bool interdit = false;
for (int j = a[i].l, p = 0; j < a[i].r; ++j) {
p = transition[p][a[i].w[j - a[i].l]];
auto it = lower_bound(ajout[j].begin(), ajout[j].end(), array<int, 2>{dfn[p] + 1, -m});
if (it != ajout[j].begin() && (*--it)[1]) { interdit = true; break; }
}
if (interdit) continue;
Q.ajouter(dfn[a[i].p], 1);
Q.ajouter(finDfn[a[i].p] + 1, -1);
f[i] = puissance[a[i].l] * T.requete(a[i].l) % MOD;
ull h = 0;
for (int j = a[i].l; j < a[i].r; ++j) {
h += hashValeur[j][a[i].w[j - a[i].l]];
f[i] = (f[i] + requeteHash(h)) % MOD;
}
h = 0;
f[i] = MOD - f[i];
T.ajouter(a[i].r + 1, f[i] * puissanceInverse[a[i].r + 1] % MOD);
for (int j = a[i].r; j > a[i].l; --j) {
h += hashValeur[j][a[i].w[j - a[i].l]];
ajouterHash(h, f[i]);
}
}
cout << puissance[n + 1] * T.requete(n + 1) % MOD << "\n";
return 0;
}
H. [P11834] Les années (7.5)
Lien du problème : P11834
Pour \(w=1\), la condition est que le DAG après condensation ait un seul SCC de degré entrant zéro. On utilise l'inclusion-exclusion classique en ajoutant une couche de points de degré entrant zéro \(T\) avec coefficient \((-1)^{|T|-1} w_T\).
On applique l'inclusion-exclusion sur l'ensemble réel des points de degré entrant zéro \(S\). On calcule le nombre de configurations où \(S\) forme un SCC, le nombre de configurations où \(S\) est partitionné en un nombre impair ou pair de SCC, et le nombre de configurations où \(S\) est un DAG.
Pour la réponse, on énumère le SCC racine et on calcule le nombre de DAGs où l'ensemble des points sans degré entrant est exactement ce SCC, réalisable en \(\mathcal O(3^n)\). En ajoutant la restriction \(w\), on connecte les blocs connectés entre eux.
Complexité temporelle : \(\mathcal O(n^2 2^n + 3^n)\).
#include <bits/stdc++.h>
#define clr(a) memset(a, 0, sizeof(a))
using namespace std;
const int MOD = 1e9 + 7, i2 = (MOD + 1) / 2;
int n, m, compteur[1 << 15], dp[1 << 15], f[1 << 15], g[1 << 15][2], h[1 << 15], puissance[255], puissanceInverse[255];
int arete(int s, int t) { return compteur[s | t] - compteur[s - (s & t)] - compteur[t] + 2 * compteur[s & t]; }
vector<array<int, 2>> graphe[255];
int dsu[15], bloc[15], sousEnsemble[1 << 15], entrant[1 << 15], produit[1 << 15], somme[1 << 15];
int trouver(int x) { return dsu[x] != x ? dsu[x] = trouver(dsu[x]) : x; }
void resoudre() {
cin >> n >> m;
clr(h);
for (int i = 1; i <= m; ++i) graphe[i].clear();
for (int i = 1, u, v, w; i <= m; ++i) {
cin >> u >> v >> w;
graphe[w].push_back({u - 1, v - 1});
}
for (int i = 0; i < n; ++i) { dsu[i] = i; h[1 << i] = 1; }
for (int w = 1; w <= m; ++w) {
clr(sousEnsemble);
clr(compteur);
for (int i = 0; i < n; ++i) {
bloc[i] = trouver(i);
sousEnsemble[1 << bloc[i]] |= 1 << i;
}
for (int s = 0; s < (1 << n); ++s) sousEnsemble[s] = sousEnsemble[s & -s] | sousEnsemble[s & (s - 1)];
for (auto &e : graphe[w]) {
for (int s = 0; s < (1 << n); ++s) {
if ((s >> e[0] & 1) && (s >> e[1] & 1)) ++compteur[s];
}
if (trouver(e[0]) != trouver(e[1])) dsu[trouver(e[0])] = trouver(e[1]);
}
for (int rt = 0; rt < n; ++rt) {
if (dsu[rt] == rt) {
int U = 0;
for (int i = 0; i < n; ++i) {
if (bloc[i] == i && trouver(i) == rt) U |= sousEnsemble[1 << i];
}
if (U == sousEnsemble[1 << rt]) {
for (int s = 1; s < (1 << n); ++s) {
if ((s & U) == s) h[s] = 1ll * h[s] * puissance[arete(U, U)] % MOD;
}
continue;
}
clr(dp);
clr(f);
clr(g);
clr(entrant);
clr(produit);
clr(somme);
for (int s = 0; s < (1 << n); ++s) {
if ((s & U) == s) {
for (int i = 0; i < n; ++i) if (s >> i & 1) entrant[s] |= 1 << bloc[i];
}
}
dp[0] = f[0] = g[0][0] = 1;
for (int s = 1; s < (1 << n); ++s) {
if ((s & U) == s) {
int S = entrant[s];
for (int T = S, t; T; T = (T - 1) & S) {
if (T & (S & -S)) {
t = s & sousEnsemble[entrant[T]];
g[s][0] = (g[s][0] + 1ll * f[t] * g[s ^ t][1]) % MOD;
g[s][1] = (g[s][1] + 1ll * f[t] * g[s ^ t][0]) % MOD;
}
}
f[s] = puissance[arete(sousEnsemble[S], s)];
for (int T = S, t; T; T = (T - 1) & S) {
t = s & sousEnsemble[T];
f[s] = (f[s] + 1ll * (g[t][0] + MOD - g[t][1]) * puissance[arete(sousEnsemble[S], s ^ t)]) % MOD;
}
g[s][1] = (g[s][1] + f[s]) % MOD;
for (int T = S, t; T; T = (T - 1) & S) {
t = s & sousEnsemble[T];
dp[s] = (dp[s] + 1ll * (g[t][1] + MOD - g[t][0]) * puissance[arete(sousEnsemble[T], s ^ t)] % MOD * dp[s ^ t]) % MOD;
}
}
}
for (int s = 0, S; s < (1 << n); ++s) {
if ((s & U) == s) {
S = entrant[s];
produit[s] = 1;
for (int i = 0; i < n; ++i) if (S >> i & 1) produit[s] = 1ll * produit[s] * h[s & sousEnsemble[1 << i]] % MOD;
somme[S] = (somme[S] + 1ll * produit[s] * dp[s] % MOD * puissance[arete(U ^ sousEnsemble[S], s) + arete(U, sousEnsemble[S] ^ s)]) % MOD;
}
}
for (int s = 1; s < (1 << n); ++s) {
if ((s & U) == s) {
h[s] = 0;
for (int t = U ^ sousEnsemble[entrant[s]]; ; t = (t - 1) & (U ^ sousEnsemble[entrant[s]])) {
h[s] = (h[s] + 1ll * produit[s | t] * (g[t][0] + MOD - g[t][1]) % MOD * somme[entrant[U] ^ entrant[s | t]] % MOD * puissance[arete(U, sousEnsemble[entrant[s | t]] ^ s ^ t)]) % MOD;
if (!t) break;
}
h[s] = 1ll * h[s] * f[s] % MOD;
}
}
}
}
}
int reponse = 0;
for (int s = 1; s < (1 << n); ++s) reponse = (reponse + h[s]) % MOD;
cout << 1ll * reponse * puissanceInverse[2 * m] % MOD << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for (int i = puissance[0] = puissanceInverse[0] = 1; i < 255; ++i) {
puissance[i] = puissance[i - 1] * 2 % MOD;
puissanceInverse[i] = 1ll * puissanceInverse[i - 1] * i2 % MOD;
}
int type, tests;
cin >> type >> tests;
while (tests--) resoudre();
return 0;
}
I. [P11880] Sélection d'intervalles (4)
Lien du problème : P11880
On binaire sur la réponse \(k\), puis on énumère le nombre d'opérations de type deux \(t\). On considère cela comme donner à plusieurs intervalles une réduction de \(-2\) sur la sélection complète de l'opération une, pour que la valeur maximale soit \(\le k - t\).
On peut utiliser un tas pour une approche gloutonne : à chaque étape, on extrait le segment avec le plus grand point droit. La complexité est \(\mathcal O(n^2 \log^2 n)\). En observant les propriétés des opérations de type deux, on note que \(t\) ne dépasse pas \(w - k + 1\), où \(w\) est la couverture initiale maximale.
Complexité temporelle : \(\mathcal O(n \log^2 n)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 5;
vector<array<int, 2>> segments[MAXN];
int n, m, maximum, couverture[MAXN], dp[MAXN], operation[MAXN];
bool resoudre(int borne, int t) {
memset(dp, 0, sizeof(dp));
memset(operation, 0, sizeof(operation));
borne -= t;
priority_queue<array<int, 2>> tas;
for (int i = 0, z = 0; i <= m; ++i) {
for (auto &seg : segments[i]) tas.push(seg);
z += dp[i];
while (couverture[i] - z > borne) {
if (tas.empty() || !t || tas.top()[0] < i) return false;
z += 2;
dp[tas.top()[0] + 1] -= 2;
operation[tas.top()[1]] = 1;
tas.pop();
--t;
}
}
return true;
}
bool verifier(int k) { return resoudre(k, maximum - k) || resoudre(k, maximum - k + 1); }
signed main() {
cin >> n;
m = 2 * n;
for (int i = 1, l, r; i <= n; ++i) {
cin >> l >> r;
++couverture[l];
--couverture[r + 1];
segments[l].push_back({r, i});
}
for (int i = 1; i <= m; ++i) maximum = max(maximum, couverture[i] += couverture[i - 1]);
int z = maximum;
for (int k = 1 << __lg(z); k; k >>= 1) {
if (z >= k && verifier(z - k)) z -= k;
}
cout << z << "\n";
verifier(z);
for (int i = 1; i <= n; ++i) cout << 1 - operation[i];
cout << "\n";
return 0;
}
J. [P14355] Le sceau (7.5)
Lien du problème : P14355
On énumère le premier moment \(L\) qui produit une contribution et le moment \(R\) pour le calcul de la contribution. On discute tous les segments. Si \(l \in [L,R]\), on doit sélectionner \([l, \min(r,R)]\). Si \(r \le R\), on peut contribuer à la réponse.
Il suffit de vérifier que chaque position dans \([L,R]\) a une couverture \(\le k\). On balaie \(L\) en ordre décroissant et on maintient \(R\) avec un pointeur. Pour les segments avec \(l < L\), on utilise une approche gloutonne qui obéit au modèle de matroïde. On ajuste avec un arbre de segments.
Complexité temporelle : \(\mathcal O(n \log n)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef array<int, 2> pii;
const int MAXN = 6e5 + 5, inf = 1e9 + 1, N = 1 << 20;
int n, k, gauche[MAXN], droite[MAXN], poids[MAXN], a[MAXN];
struct ArbreSegments1 {
int maximum[N << 1], addition[N << 1];
void appliquer(int p, int z) { maximum[p] += z; addition[p] += z; }
void propager(int p) { if (addition[p]) { appliquer(p << 1, addition[p]); appliquer(p << 1 | 1, addition[p]); addition[p] = 0; } }
void mettreAJour(int p) { maximum[p] = max(maximum[p << 1], maximum[p << 1 | 1]); }
void ajouter(int ul, int ur, int z, int l = 1, int r = 2 * n, int p = 1) {
if (ul <= l && r <= ur) { appliquer(p, z); return; }
int milieu = (l + r) >> 1;
propager(p);
if (ul <= milieu) ajouter(ul, ur, z, l, milieu, p << 1);
if (milieu < ur) ajouter(ul, ur, z, milieu + 1, r, p << 1 | 1);
mettreAJour(p);
}
int suivant(int x, int z, int l = 1, int r = 2 * n, int p = 1) {
if (maximum[p] < z) return 2 * n + 1;
if (l == r) return l;
int milieu = (l + r) >> 1, t = 2 * n + 1;
propager(p);
if (x <= milieu) t = suivant(x, z, l, milieu, p << 1);
return t <= 2 * n ? t : suivant(x, z, milieu + 1, r, p << 1 | 1);
}
int precedent(int x, int z, int l = 1, int r = 2 * n, int p = 1) {
if (maximum[p] < z) return 0;
if (l == r) return l;
int milieu = (l + r) >> 1, t = 0;
propager(p);
if (x > milieu) t = precedent(x, z, milieu + 1, r, p << 1 | 1);
return t ? t : precedent(x, z, l, milieu, p << 1);
}
} T;
struct ArbreSegments2 {
pii arbre[N << 1];
ArbreSegments2() { fill(arbre, arbre + (N << 1), pii{inf, 0}); }
void mettreAJour(int x, int z) {
for (arbre[x + N] = {z, x}, x += N; x > 1; x >>= 1) arbre[x >> 1] = min(arbre[x], arbre[x ^ 1]);
}
pii requete(int l, int r) {
pii resultat = {inf, 0};
for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (~l & 1) resultat = min(resultat, arbre[l ^ 1]);
if (r & 1) resultat = min(resultat, arbre[r ^ 1]);
}
return resultat;
}
} S;
struct ArbreSegments3 {
pii arbre[N << 1];
void mettreAJour(int x, int z) {
for (arbre[x + N] = {z, x}, x += N; x > 1; x >>= 1) arbre[x >> 1] = max(arbre[x], arbre[x ^ 1]);
}
pii requete(int l, int r) {
pii resultat = {0, 0};
for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (~l & 1) resultat = min(resultat, arbre[l ^ 1]);
if (r & 1) resultat = min(resultat, arbre[r ^ 1]);
}
return resultat;
}
} Q;
bool visite[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> gauche[i] >> droite[i] >> poids[i];
for (int i = 1; i <= n; ++i) a[gauche[i]] = a[droite[i]] = i;
ll reponse = 0, somme = 0;
for (int l = 2 * n, r = 2 * n; l >= 1; --l) {
if (l == droite[a[l]]) {
int h = T.suivant(l, k);
if (h > l) {
somme += poids[a[l]];
visite[a[l]] = 1;
T.ajouter(gauche[a[l]], l, 1);
S.mettreAJour(l, poids[a[l]]);
} else {
auto o = S.requete(l, r);
if (o[1] && o[0] < poids[a[l]]) {
visite[a[o[1]]] = 0;
S.mettreAJour(o[1], inf);
T.ajouter(gauche[a[o[1]]], o[1], -1);
Q.mettreAJour(o[1], o[0]);
somme += poids[a[l]] - o[0];
visite[a[l]] = 1;
T.ajouter(gauche[a[l]], l, 1);
S.mettreAJour(l, poids[a[l]]);
} else Q.mettreAJour(l, poids[a[l]]);
}
} else if (!visite[a[l]]) {
Q.mettreAJour(droite[a[l]], 0);
T.ajouter(l, droite[a[l]], 1);
visite[a[l]] = 1;
if (droite[a[l]] <= r) {
Q.mettreAJour(droite[a[l]], 0);
somme += poids[a[l]];
}
for (int h = T.precedent(r, k + 1); h >= l; h = T.precedent(r, k + 1)) {
auto o = S.requete(h, r);
if (o[1]) {
somme -= o[0];
visite[a[o[1]]] = 0;
S.mettreAJour(o[1], inf);
T.ajouter(gauche[a[o[1]]], o[1], -1);
Q.mettreAJour(o[1], o[0]);
o = Q.requete(l, min(r, T.suivant(l, k) - 1));
if (o[0]) {
somme += o[0];
visite[a[o[1]]] = 1;
Q.mettreAJour(o[1], 0);
S.mettreAJour(o[1], o[0]);
T.ajouter(gauche[a[o[1]]], o[1], 1);
}
} else {
for (; r >= h; --r) {
if (r == droite[a[r]]) {
if (gauche[a[r]] >= l) somme -= poids[a[r]];
else if (!visite[a[r]]) Q.mettreAJour(r, 0);
else {
somme -= poids[a[r]];
visite[a[r]] = 0;
S.mettreAJour(r, inf);
T.ajouter(gauche[a[r]], r, -1);
o = Q.requete(l, min(h, T.suivant(l, k)) - 1);
if (o[0]) {
somme += o[0];
visite[a[o[1]]] = 1;
Q.mettreAJour(o[1], 0);
S.mettreAJour(o[1], o[0]);
T.ajouter(gauche[a[o[1]]], o[1], 1);
}
}
} else {
visite[a[r]] = 0;
T.ajouter(r, droite[a[r]], -1);
}
}
}
}
} else S.mettreAJour(droite[a[l]], inf);
reponse = max(reponse, somme);
}
cout << reponse << "\n";
return 0;
}
K. [P12558] Héros et Monstres (4)
Lien du problème : P12558
On énumère \(k\) en ordre, et la stratégie consiste à matcher séquentiellement \(b_1 \sim b_k\) et \(b_{k+1} \sim b_n\). On définit \(f_{i,j}\) comme le nombre d'éléments de \(S\) sélectionnés parmi les \(i\) premiers éléments. Les contraintes des \(b_1 \sim b_k\) limitent la borne supérieure de \(j\) dans le préfixe, tandis que les \(b_{k+1} \sim b_n\) limitent la borne inférieure de \(i - j + k\).
Ces deux types d'éléments ont des plages de contraintes disjointes, donc on prétraite le nombre de configurations où le préfixe satisfait les contraintes de \(b[1,k]\) et le suffixe satisfait celles de \(b[k,n]\), puis on combine.
Complexité temporelle : \(\mathcal O(n^2)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005, MOD = 998244353;
int n, m, a[MAXN], b[MAXN], position[MAXN], borneMin[MAXN], borneMax[MAXN], f[MAXN][MAXN], g[MAXN][MAXN], s[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int i = 0; i <= n + 1; ++i) borneMin[i] = i, borneMax[i] = n + 1 - i;
for (int i = 1; i <= n; ++i) {
position[i] = upper_bound(a + 1, a + n + 1, b[i]) - a - 1;
borneMin[position[i]] = min(borneMin[position[i]], i - 1);
borneMax[position[i] + 1] = min(borneMax[position[i] + 1], n - i);
}
f[0][0] = g[n + 1][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= borneMin[i]; ++j) f[i][j] = (f[i - 1][j] + (j ? f[i - 1][j - 1] : 0)) % MOD;
}
for (int i = n; i; --i) {
for (int j = 0; j <= borneMax[i]; ++j) g[i][j] = (g[i + 1][j] + (j ? g[i + 1][j - 1] : 0)) % MOD;
}
s[0] = s[n] = 1;
for (int i = 1; i <= n; ++i) { s[0] &= a[i] < b[i]; s[n] &= a[i] > b[i]; }
for (int k = 1; k < n; ++k) {
for (int i = 0; i <= k; ++i) {
int j = (n - k) - (position[k] - i);
if (j >= 0) s[k] = (s[k] + 1ll * f[position[k]][i] * g[position[k] + 1][j]) % MOD;
}
}
for (int i = 1; i <= n; ++i) s[i] = (s[i - 1] + s[i]) % MOD;
cin >> m;
for (int L, R; m--;) {
cin >> L >> R;
cout << (s[R] + (L ? MOD - s[L - 1] : 0)) % MOD << "\n";
}
return 0;
}
L. [P12636] Réduction de tableau (7)
Lien du problème : P12636
Soit \(k \gets k + t\). On énumère le nombre d'opérations \(c\), qui doit satisfaire \(\sum \max(\lceil \frac{a_i + tc}{k} \rceil, 0) \ge c\). On énumère la borne \([1,m]\) où \(a_i + tc \ge 0\), et on décompose le côté gauche en \(\sum \lceil \frac{a_i}{k} \rceil\), \(m \lfloor \frac{tc}{k} \rfloor\), et une partie dépendant des restes.
Pour chaque \(m\), les plages de \(c\) valides sont disjointes et croissantes. On itère depuis la valeur minimale possible de \(c\) jusqu'à ce que \(c\) soit valide ou dépasse la borne supérieure. On prétend que seulement \(\mathcal O(1)\) valeurs de \(m\) passent le test.
Complexité temporelle : \(\mathcal O(n \log n \log V)\).
#include <bits/stdc++.h>
#define ll __int128
using namespace std;
namespace IO {
int ow, olim = (1 << 21) - 100;
char buf[1 << 21], *p1 = buf, *p2 = buf, obuf[1 << 21];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
ll lire() {
ll x = 0, f = 1;
char c = gc();
while (!isdigit(c)) { f = (c == '-' ? -f : f); c = gc(); }
while (isdigit(c)) { x = x * 10 + (c ^ 48); c = gc(); }
return f * x;
}
void vider() { fwrite(obuf, ow, 1, stdout); ow = 0; }
void ecrire(ll x) {
if (!x) obuf[ow++] = '0';
else {
int t = ow;
for (; x; x /= 10) obuf[ow++] = (x % 10) ^ 48;
reverse(obuf + t, obuf + ow);
}
if (ow >= olim) vider();
}
void ecrireChar(char c) { obuf[ow++] = c; if (ow >= olim) vider(); }
void ecrireStr(const string &s) { for (auto &c : s) obuf[ow++] = c; if (ow >= olim) vider(); }
#undef gc
}
const int MAXN = 1e6 + 5, B = 150;
const ll inf = 1e18, INF = 1e36;
int n, id[MAXN];
ll k, t, a[MAXN], a0[MAXN], b[MAXN];
ll diviser(ll x, ll y) { return x > 0 ? x / y : (x - y + 1) / y; }
struct ArbreFenwick {
int arbre[MAXN], somme;
void ajouter(int x) { for (; x <= n; x += x & -x) ++arbre[x]; }
int requete(int x) { somme = 0; for (; x; x &= x - 1) somme += arbre[x]; return somme; }
} T;
signed main() {
n = IO::lire();
k = IO::lire();
t = IO::lire();
k += t;
for (int i = 1; i <= n; ++i) { a[i] = IO::lire(); a0[i] = a[i]; }
sort(a + 1, a + n + 1, greater<>());
if (a[1] <= 0) {
IO::ecrireStr("0\n");
for (int i = 1; i <= n; ++i) { IO::ecrireChar('0'); IO::ecrireChar(" \n"[i == n]); }
IO::vider();
return 0;
}
if (k == t) { puts("-1"); return 0; }
if (t == 0) {
ll z = 0;
for (int i = 1; i <= n; ++i) if (a[i] > 0) z += (a[i] + k - 1) / k;
IO::ecrire(z);
IO::ecrireChar('\n');
for (int i = 1; i <= n; ++i) {
IO::ecrire(max((ll)0, (a0[i] + k - 1) / k));
IO::ecrireChar(" \n"[i == n]);
}
IO::vider();
return 0;
}
for (int i = 1; i <= n; ++i) b[i] = k - (a[i] % k + k - 1) % k;
sort(b + 1, b + n + 1);
auto position = [&](ll x) { return upper_bound(b + 1, b + n + 1, x) - b - 1; };
ll z = inf, S = 0;
for (int m = 1; m <= n; ++m) {
S += diviser(a[m] + k - 1, k);
T.ajouter(position(k - (a[m] % k + k - 1) % k));
if (a[m + 1] > 0 || k <= m * t) continue;
auto verifier = [&](ll c) {
if (a[m] + c * t <= 0) return false;
return c * t / k * m + S + T.requete(position(c * t % k)) <= c;
};
if (m < n) {
ll c0 = max((ll)0, (-a[m]) / t + 1);
for (ll c1, _ = 0; a[m + 1] + c0 * t <= 0 && _ <= B; c0 = c1, ++_) {
c1 = c0 * t / k * m + S + T.requete(position(c0 * t % k));
if (c0 >= c1) break;
}
if (a[m + 1] + c0 * t > 0) continue;
}
for (int o = 0; o < m; ++o) {
if (z > o) {
ll w = (z - o - 1) / m;
if (m < n) {
if (-a[m + 1] - o * t < 0) continue;
w = min(w, (-a[m + 1] - o * t) / m / t);
}
if (!verifier(w * m + o)) continue;
for (ll d = (ll)1 << 63; d; d >>= 1) {
if (w >= d && verifier((w - d) * m + o)) w -= d;
}
z = min(z, w * m + o);
}
}
if (z < inf) break;
}
if (z == inf) { puts("-1"); return 0; }
IO::ecrire(z);
IO::ecrireChar('\n');
for (int i = 1; i <= n; ++i) {
IO::ecrire(max((ll)0, (a0[i] + z * t + k - 1) / k));
IO::ecrireChar(" \n"[i == n]);
}
IO::vider();
return 0;
}
M. [P12445] Bon graphique (5)
Lien du problème : P12445
Pour \(k=n\), chaque point a un degré sortant et entrant. On utilise l'inclusion-exclusion en imposant que certains points n'aient pas de degré sortant, et on maintient le nombre de tels points dans le préfixe.
Le problème général part d'un graphe avec \(n=k\), et on insère des points accessibles depuis \(1\) mais pas atteignables par \(n\), ainsi que des points inaccessibles depuis \(1\). On effectue un DP séparé pour le nombre de configurations avec \(j\) tels points parmi les \(i\) premiers, puis on combine pour chaque \(k\).
Complexité temporelle : \(\mathcal O(n^2)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2005;
int n, MOD, f[MAXN][MAXN], g[MAXN], h[MAXN][MAXN], puissance[MAXN], w[MAXN][MAXN], z[MAXN];
int exponentiationRapide(int a, int b) {
int resultat = 1;
for (; b; a = 1ll * a * a % MOD, b >>= 1) if (b & 1) resultat = 1ll * resultat * a % MOD;
return resultat;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> MOD;
for (int i = puissance[0] = 1; i <= n; ++i) puissance[i] = puissance[i - 1] * 2 % MOD;
f[1][0] = g[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (f[i][j]) {
f[i + 1][j + 1] = (f[i + 1][j + 1] + 1ll * f[i][j] * (puissance[j + 1] - 1)) % MOD;
f[i + 1][j] = (f[i + 1][j] + 1ll * (MOD - f[i][j]) * (puissance[j] - 1)) % MOD;
g[i] = (g[i] + f[i][j]) % MOD;
}
}
}
h[1][0] = w[1][0] = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
h[i + 1][j] = (h[i + 1][j] + h[i][j]) % MOD;
h[i + 1][j + 1] = (h[i + 1][j + 1] + 1ll * h[i][j] * (puissance[i] - 1)) % MOD;
w[i + 1][j] = (w[i + 1][j] + 1ll * w[i][j] * puissance[j]) % MOD;
w[i + 1][j + 1] = (w[i + 1][j + 1] + 1ll * w[i][j] * puissance[j]) % MOD;
}
}
z[0] = exponentiationRapide(2, n * (n - 1) / 2);
for (int i = 2; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
z[i] = (z[i] + 1ll * h[j - 1][j - i] * w[n - 1][n - j] % MOD * puissance[n - j]) % MOD;
}
z[i] = 1ll * z[i] * g[i] % MOD;
z[0] = (z[0] + MOD - z[i]) % MOD;
}
for (int i = 0; i <= n; ++i) cout << z[i] << " \n"[i == n];
return 0;
}
N. [P13533] Trouver la fausse pièce (7.5)
Lien du problème : P13533
On modélise les opérations comme la somme des indices des pièces fausses dans un intervalle. Une approche naïve consiste à diviser la plage de valeurs en blocs, et si un intervalle contient au plus une pièce fausse, on la détermine directement. Sinon, on divise en deux moitiés et on récure.
Pour éviter que deux pièces fausses proches induisent \(\mathcal O(k \log n)\) requêtes, on choisit à chaque fois un milieu approprié pour que les deux côtés contiennent des pièces fausses. On binaire sur \(c\), et on vérifie si le milieu correspondant est légal.
En utilisant récursivement toutes les informations pour optimiser les bornes de \(c\), et en priorisant la récursion du côté avec la plus petite plage de valeurs, le nombre de requêtes est proche de la limite théorique.
Complexité temporelle : \(\mathcal O(k \log n)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> resultat;
ll requete(int x, ll z) {
cout << "? " << x << endl;
ll o;
cin >> o;
return 1ll * x * (x + 1) / 2 - o - z;
}
int n, k;
void ajouter(int x) { resultat.push_back(x); }
int borneInferieure(ll w, int L) {
int x = 0;
for (; w >= L; ++x, w -= L, ++L);
return x;
}
int borneSuperieure(ll w, int R) {
int x = 0;
for (; R && w >= R; ++x, w -= R, --R);
return x;
}
int diviserPourRegner(int l, int r, int cl, int cr, ll o, ll w) {
if (!w) return 0;
if (l <= w && w <= 2 * l) { ajouter(w); return 1; }
cl = max({1, cl, borneSuperieure(w, r)});
cr = min(cr, borneInferieure(w, l));
if (cr <= 1) { ajouter(w); return 1; }
int cm = (cl + cr + 1) >> 1;
int milieu = w / cm;
ll v = milieu < l ? 0 : milieu >= r ? w : requete(milieu, o);
if (!v) return diviserPourRegner(milieu + 1, r, cl, cm - 1, o, w);
if (v == w) return diviserPourRegner(l, milieu, cm + 1, cr, o, w);
int xl = max(borneSuperieure(v, milieu), cl - borneInferieure(w - v, milieu + 1));
int xr = min(borneInferieure(v, l), cr - borneSuperieure(w - v, r));
int yl = max(borneSuperieure(w - v, r), cl - borneInferieure(v, l));
int yr = min(borneInferieure(w - v, milieu + 1), cr - borneSuperieure(v, milieu));
int compteur = 0;
if (xr - xl <= yr - yl) {
compteur += diviserPourRegner(l, milieu, xl, xr, o, v);
compteur += diviserPourRegner(milieu + 1, r, cl - compteur, cr - compteur, o + v, w - v);
} else {
compteur += diviserPourRegner(milieu + 1, r, yl, yr, o + v, w - v);
compteur += diviserPourRegner(l, milieu, cl - compteur, cr - compteur, o, v);
}
return compteur;
}
void resoudre() {
cin >> n >> k;
resultat.clear();
diviserPourRegner(1, n, k, k, 0, requete(n, 0));
sort(resultat.begin(), resultat.end());
cout << "! ";
for (int x : resultat) cout << x << " ";
cout << endl;
int o;
cin >> o;
}
signed main() {
int tests;
cin >> tests;
while (tests--) resoudre();
return 0;
}
O. [P11629] Jeu de Nim (5)
Lien du problème : P11629
On effectue une approche gloutonne. Si \(a_1 = 0\), la stratégie est d'ajuster, pour chaque bit \(k\) où le XOR est 1, un nombre sans \(2^k\) mais avec le plus grand des bits inférieurs, pour ajuster ce nombre à \(2^k\). On peut conjecturer que toutes les solutions optimales suivent cette forme.
On effectue une recherche exhaustive. Si l'élément courant ne conduit pas à une solution optimale, on revient en arrière. Pour chaque \(k\), on trie tous les nombres par leur valeur inférieure.
Sans \(a_1 = 0\), lorsqu'on rencontre un bit où tous \(a_i\) sont 1, on ne peut pas continuer. On génère alors manuellement un élément avec \(a_i = 0\) en choisissant une position \(k\) au-dessus du bit le plus élevé du XOR, et en ajustant deux nombres pour que ce bit soit 1.
Complexité temporelle : \(\mathcal O(n \log V \log n + m \log^2 V)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
int n, m;
ll a[MAXN], w;
vector<map<int, ll>> solutions;
vector<array<ll, 2>> blocs[64];
bool rechercheExhaustive(int k, ll S, const map<int, ll> &g, ll z) {
if (z > w || (int)solutions.size() >= m) return 0;
if (k < 0) {
if (z < w) { w = z; solutions.clear(); }
solutions.push_back(g);
return 1;
}
if (!(S >> k & 1)) return rechercheExhaustive(k - 1, S, g, z);
map<int, ll> h;
bool ok = 0;
ll U = 1ll << k;
for (auto &i : blocs[k]) {
if (!g.count(i[1])) {
h = g;
h[i[1]] += U - i[0];
if (rechercheExhaustive(k - 1, S ^ U ^ i[0], h, z + U - i[0])) ok = 1;
else return ok;
}
}
for (auto &i : g) {
h = g;
h[i.first] += U;
if (rechercheExhaustive(k - 1, S ^ U, h, z + U)) ok = 1;
else return ok;
}
return ok;
}
void resoudre() {
cin >> n >> m;
solutions.clear();
w = 9e18;
ll S = 0;
for (int i = 1; i <= n; ++i) { cin >> a[i]; S ^= a[i]; }
for (int k = 0; k < 61; ++k) {
ll U = (1ll << k) - 1;
blocs[k].clear();
for (int i = 1; i <= n; ++i) {
if (!(a[i] >> k & 1)) blocs[k].push_back({a[i] & U, i});
}
sort(blocs[k].begin(), blocs[k].end(), greater<>());
}
rechercheExhaustive(59, S, {}, 0);
for (int k = 0; k < 61; ++k) {
if (!(S >> k)) {
ll U = 1ll << k;
++m;
for (auto &i : blocs[k]) {
bool ok = 0;
for (auto &j : blocs[k]) {
if (i > j) {
if (!rechercheExhaustive(k - 1, S ^ i[0] ^ j[0], {{i[1], U - i[0]}, {j[1], U - j[0]}}, U - i[0] + U - j[0])) break;
else ok = 1;
}
}
if (!ok) break;
}
if ((int)solutions.size() > (--m)) solutions.pop_back();
}
}
cout << w << "\n" << solutions.size() << "\n";
for (auto &o : solutions) {
cout << o.size() << "\n";
for (auto &i : o) cout << i.first << " ";
cout << "\n";
for (auto &i : o) cout << i.second << " ";
cout << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int type, tests;
cin >> type >> tests;
while (tests--) resoudre();
return 0;
}
P. [P13346] Attaque laser (7.5)
Lien du problème : P13346
L'information transmise ne peut concerner que le premier point supprimé. Pour une graphe en étoile, on peut conserver le point qui n'est pas supprimé initialement pour obtenir la racine. Pour une chaîne, on supprime alternativement le point le plus bas à gauche et à droite.
On extrait le point médian du diamètre comme racine, puis à chaque niveau, on supprime les points de bas en haut. Comme chaque niveau a plus d'un point, on peut éviter de supprimer consécutivement des points ayant une relation parenet-enfant.
Pour les arêtes, on ne peut pas transmettre directement l'information, mais comme elles sont disjointes, on peut réordonner ces arêtes pour transmettre l'état de suppression. On trie les arêtes par ordre lexicographique, puis on inverse les segments consécutifs avec le même état.
Complexité temporelle : \(\mathcal O(n \log n)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n;
namespace solveur {
vector<int> graphe[MAXN];
int parent[MAXN], distance[MAXN], hauteur[MAXN], dernier = 0;
void dfs(int u, int fz) {
parent[u] = fz;
distance[u] = distance[fz] + 1;
for (int v : graphe[u]) if (v != fz) dfs(v, u);
}
bool visite[MAXN];
int poids(int x) { return (n + 1) * min(x, parent[x]) + max(x, parent[x]); }
vector<int> D[MAXN], S[MAXN];
void supprimer(int u) {
visite[u] = true;
cout << u - 1 << " ";
dernier = parent[u];
for (int x : S[parent[u]]) if (!visite[x]) supprimer(x);
}
void resoudre() {
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
++u; ++v;
graphe[u].push_back(v);
graphe[v].push_back(u);
}
int o;
dfs(1, 0);
o = max_element(distance + 1, distance + n + 1) - distance;
dfs(o, 0);
o = max_element(distance + 1, distance + n + 1) - distance;
int k = distance[o];
for (int i = 0, u = o; i < k; ++i, u = parent[u]) hauteur[i] = u;
if (k % 2 == 1) dfs(hauteur[k / 2], 0);
else {
int l = hauteur[k / 2], r = hauteur[k / 2 - 1];
graphe[l].erase(find(graphe[l].begin(), graphe[l].end(), r));
graphe[r].erase(find(graphe[r].begin(), graphe[r].end(), l));
dfs(l, 0);
dfs(r, 0);
}
for (int i = 1; i <= n; ++i) {
if (parent[i]) {
D[distance[i]].push_back(i);
S[parent[i]].push_back(i);
if (graphe[i].size() > 1) visite[parent[i]] = true;
}
}
vector<int> f;
for (int i = 1; i <= n; ++i) {
if (parent[i] && !visite[parent[i]]) {
f.push_back(i);
visite[parent[i]] = true;
}
}
memset(visite, 0, sizeof(visite));
sort(f.begin(), f.end(), [&](int i, int j) { return poids(i) < poids(j); });
for (auto l = f.begin(), r = l; l != f.end(); l = r) {
for (r = l; r != f.end() && (*r < parent[*r]) == (*l < parent[*l]); ++r);
reverse(l, r);
}
cout << (f[0] > parent[f[0]]) << endl;
for (int x : f) supprimer(x);
for (int i = n; i > 1; --i) {
vector<int> q;
for (int u : D[i]) if (!visite[u]) q.push_back(u);
if (q.empty()) continue;
sort(q.begin(), q.end(), [&](int x, int y) { return S[x].size() > S[y].size(); });
if (q[0] == dernier) swap(q[0], q[1]);
for (int x : q) if (!visite[x]) supprimer(x);
}
if (k % 2 == 0) cout << (hauteur[k / 2] == dernier ? hauteur[k / 2 - 1] : hauteur[k / 2]) - 1 << " ";
cout << endl;
}
}
int f[MAXN];
signed main() {
int tests;
cin >> tests >> n;
if (tests == 1) return solveur::resoudre(), 0;
string o;
cin >> o;
int x = o[0] - '0';
array<int, 2> dernier = {0, 0}, e;
for (int i = 1; i < n; ++i) {
cin >> e[0] >> e[1];
if (i == 1) {
dernier = e;
if (x) swap(e[0], e[1]);
} else if (f[e[0]] == i - 1 || f[e[1]] == i - 1) {
if (f[e[0]] == i - 1) swap(e[0], e[1]);
} else if (f[e[0]] || f[e[1]]) {
if (f[e[1]]) swap(e[0], e[1]);
} else {
x ^= dernier < e;
dernier = e;
if (x) swap(e[0], e[1]);
}
cout << e[0] << endl;
f[e[0]] = f[e[1]] = i;
}
return 0;
}
Q. [P13531] Problème de chaîne (7)
Lien du problème : P13531
On décompose la contribution en utilisant la réponse pour \([1,r]\) moins celle pour \([1,l-1]\), et on soustrait également le nombre de \(t[a,b]\) avec \(a < l \le b \le r\). On trouve le plus grand \(b\) dans ces couples, et on calcule la réponse pour \([1,b]\) moins celle pour \([1,l-1]\), moins celle pour \([l,b]\).
Les chaînes \(t[a,b]\) sont des motifs, et \(t[l,b]\) sont des suffixes de motifs. Il y a \(\mathcal O(|S|)\) telles chaînes, traitables avec un automate AC.
Complexité temporelle : \(\mathcal O(|S| \Sigma + m \log |T|)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n;
namespace solveur {
vector<int> graphe[MAXN];
int parent[MAXN], distance[MAXN], hauteur[MAXN], dernier = 0;
void dfs(int u, int fz) {
parent[u] = fz;
distance[u] = distance[fz] + 1;
for (int v : graphe[u]) if (v != fz) dfs(v, u);
}
bool visite[MAXN];
int poids(int x) { return (n + 1) * min(x, parent[x]) + max(x, parent[x]); }
vector<int> D[MAXN], S[MAXN];
void supprimer(int u) {
visite[u] = true;
cout << u - 1 << " ";
dernier = parent[u];
for (int x : S[parent[u]]) if (!visite[x]) supprimer(x);
}
void resoudre() {
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
++u; ++v;
graphe[u].push_back(v);
graphe[v].push_back(u);
}
int o;
dfs(1, 0);
o = max_element(distance + 1, distance + n + 1) - distance;
dfs(o, 0);
o = max_element(distance + 1, distance + n + 1) - distance;
int k = distance[o];
for (int i = 0, u = o; i < k; ++i, u = parent[u]) hauteur[i] = u;
if (k % 2 == 1) dfs(hauteur[k / 2], 0);
else {
int l = hauteur[k / 2], r = hauteur[k / 2 - 1];
graphe[l].erase(find(graphe[l].begin(), graphe[l].end(), r));
graphe[r].erase(find(graphe[r].begin(), graphe[r].end(), l));
dfs(l, 0);
dfs(r, 0);
}
for (int i = 1; i <= n; ++i) {
if (parent[i]) {
D[distance[i]].push_back(i);
S[parent[i]].push_back(i);
if (graphe[i].size() > 1) visite[parent[i]] = true;
}
}
vector<int> f;
for (int i = 1; i <= n; ++i) {
if (parent[i] && !visite[parent[i]]) {
f.push_back(i);
visite[parent[i]] = true;
}
}
memset(visite, 0, sizeof(visite));
sort(f.begin(), f.end(), [&](int i, int j) { return poids(i) < poids(j); });
for (auto l = f.begin(), r = l; l != f.end(); l = r) {
for (r = l; r != f.end() && (*r < parent[*r]) == (*l < parent[*l]); ++r);
reverse(l, r);
}
cout << (f[0] > parent[f[0]]) << endl;
for (int x : f) supprimer(x);
for (int i = n; i > 1; --i) {
vector<int> q;
for (int u : D[i]) if (!visite[u]) q.push_back(u);
if (q.empty()) continue;
sort(q.begin(), q.end(), [&](int x, int y) { return S[x].size() > S[y].size(); });
if (q[0] == dernier) swap(q[0], q[1]);
for (int x : q) if (!visite[x]) supprimer(x);
}
if (k % 2 == 0) cout << (hauteur[k / 2] == dernier ? hauteur[k / 2 - 1] : hauteur[k / 2]) - 1 << " ";
cout << endl;
}
}
int f[MAXN];
signed main() {
int tests;
cin >> tests >> n;
if (tests == 1) return solveur::resoudre(), 0;
string o;
cin >> o;
int x = o[0] - '0';
array<int, 2> dernier = {0, 0}, e;
for (int i = 1; i < n; ++i) {
cin >> e[0] >> e[1];
if (i == 1) {
dernier = e;
if (x) swap(e[0], e[1]);
} else if (f[e[0]] == i - 1 || f[e[1]] == i - 1) {
if (f[e[0]] == i - 1) swap(e[0], e[1]);
} else if (f[e[0]] || f[e[1]]) {
if (f[e[1]]) swap(e[0], e[1]);
} else {
x ^= dernier < e;
dernier = e;
if (x) swap(e[0], e[1]);
}
cout << e[0] << endl;
f[e[0]] = f[e[1]] = i;
}
return 0;
}
R. [P11436] Arbre couvrant (4.5)
Lien du problème : P11436
La réponse ne dépasse pas le produit des degrés entrants de chaque point, et la somme des degrés est 100. On détermine goulument les degrés \(d_2 \sim d_n\) pour que le produit soit \(\ge k\) et la somme minimale. On relie ensuite \(2 \to 3 \to \cdots \to n\) en chaîne.
Pour ajuster la réponse, on soustrait \(\prod_{j \le i} d_j\) en connectant \(n\) à \(i+1\). Les degrés restants sont connectés depuis 1. On effectue un ajustement similaire à une représentation ternaire.
Complexité temporelle : \(\mathcal O(n)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll f[105], d[105], m;
void resoudre() {
cin >> m;
f[1] = 1;
d[2] = 1;
int n = 2;
while (f[n - 1] * d[n] < m) {
if (d[n] < 3 || n == 34) ++d[n];
else { f[n] = f[n - 1] * d[n]; d[++n] = 1; }
}
f[n] = f[n - 1] * d[n];
vector<array<int, 2>> aretes;
for (int i = 2; i < n; ++i) {
--d[i + 1];
aretes.push_back({i, i + 1});
}
ll x = f[n];
for (int i = n - 1; i >= 1; --i) {
while (x - f[i] >= m) {
x -= f[i];
aretes.push_back({n, i + 1});
--d[i + 1];
}
}
for (int i = 2; i <= n; ++i) {
while (d[i]--) aretes.push_back({1, i});
}
cout << n << " " << aretes.size() << "\n";
for (auto &e : aretes) cout << e[0] << " " << e[1] << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests;
cin >> tests;
while (tests--) resoudre();
return 0;
}
S. [P13508] Burenka et Pether (4)
Lien du problème : P13508
Chaque point \(i\) peut atteindre les points dans \([i, r_i]\) avec \(a_j > a_i\). On caractérise la stratégie : sauter vers le point avec la plus grande valeur de \(a\) parmi les points légaux.
On partitionne la plage de valeurs de \(a\) en blocs. Si \(a_v \in [l,r]\), on traite par ordre décroissant de \(a_v\), et on maintient dynamiquement le moment où chaque point saute dans \([l, a_v]\). Pour les points qui ne peuvent pas sauter dans \([l, a_v]\), on les contracte avec leurs successeurs.
Complexité temporelle : \(\mathcal O((n+q) \sqrt{n})\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
int n, D, _, q, B, a[MAXN], b[MAXN], c[MAXN], z[MAXN];
vector<array<int, 2>> requetes[MAXN];
void initialiser() {
static int L[MAXN], R[MAXN];
for (int i = 1; i <= n; ++i) L[i] = i - 1, R[i] = i + 1;
set<int> S;
S.insert(n + 1);
for (int i = n; i >= 1; --i) {
int x = b[i];
c[x] = min(n, *S.lower_bound(x) + D);
R[L[x]] = R[x];
L[R[x]] = L[x];
if (R[x] - L[x] > D) S.insert(L[x]);
}
}
int id[MAXN], st[MAXN], f[MAXN], mx[MAXN], parent[MAXN], d[MAXN], e[MAXN];
void trouver(int x) {
if (parent[x] == x) return;
trouver(parent[x]);
d[x] += d[parent[x]];
parent[x] = parent[parent[x]];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> D >> _;
B = min(n, 2 * (int)sqrt(n));
for (int i = 1; i <= n; ++i) cin >> a[i], b[a[i]] = i;
cin >> q;
for (int i = 1, u, v; i <= q; ++i) {
cin >> z[i] >> u >> v;
if (a[u] < a[v]) requetes[a[v]].push_back({u, i});
else z[i] = 0;
}
initialiser();
for (int i = 1; i <= n; ++i) f[i] = a[i];
for (int L = 1, R; L <= n; L = R + 1) {
R = min(n, L + B - 1);
int k = 0;
for (int i = 1; i <= n; ++i) {
if (L <= a[i] && a[i] <= R) st[++k] = a[i];
id[i] = k;
}
for (int i = R; i; --i) {
int x = b[i];
if (id[c[x]] > id[x - 1]) { parent[x] = x; d[x] = 0; }
else { parent[x] = parent[b[f[x]]]; d[x] = d[b[f[x]]] + 1; }
}
for (int v = R; v >= L; --v) {
e[k + 1] = k + 1;
for (int i = k, p = k + 1; i >= 1; --i) e[i] = p = (st[i] <= v ? i : p);
for (auto &o : requetes[v]) {
int u = o[0], s = 0;
while (a[u] < v) {
trouver(u);
s += d[u];
u = parent[u];
int x = f[u];
for (int i = e[id[u - 1] + 1]; i <= id[c[u]]; i = e[i + 1]) {
if (st[i] <= v) x = max(x, st[i]);
}
if (x == a[u]) { z[o[1]] = 0; break; }
if (x < L) { parent[u] = b[x]; d[u] = 1; }
++s;
u = b[x];
}
if (z[o[1]]) z[o[1]] = z[o[1]] == 1 ? 1 : s;
}
}
for (int i = n; i >= 1; --i) {
if (L <= a[i] && a[i] <= R) {
for (int j = id[i]; j <= k; ++j) mx[j] = max(mx[j], a[i]);
}
if (id[c[i]] > id[i - 1]) f[i] = max(f[i], mx[id[c[i]]]);
}
}
for (int i = 1; i <= q; ++i) cout << z[i] << "\n";
return 0;
}
T. [P11613] Couverture (7.5)
Lien du problème : P11613
On transforme en ensemble indépendant maximal. Pour compter modulo \(p\), on extrait les deux premiers points. Si leurs voisinages diffèrent, on les échange pour obtenir un graphe isomorphe. Ainsi, ces deux points ont le même voisinage.
On discute s'il y a une arête entre eux. S'il y en a une, on ne peut en sélectionner au plus un, ce qui équivaut à supprimer un point. Sinon, on doit les sélectionner ou non ensemble, générant un point de taille 2. On fusionne ainsi deux points de même taille.
On note \(m = \sum 2^{a_i}\). On calcule \(f(n,m)\), le nombre de configurations pour obtenir \(m\) groupes. On utilise des propriétés de parité et des transitions simples.
Complexité temporelle : \(\mathcal O(n^2)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1 << 14 | 5;
bitset<MAXN> f, g, h, z;
vector<array<int, 2>> requetes[MAXN];
int n, q;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> q;
for (int i = 1, x, y; i <= q; ++i) {
cin >> x >> y;
n = max(n, x);
requetes[x].push_back({x - y, i});
}
f[0] = 1;
for (int i = 1; i <= n; ++i) {
h.reset();
g.reset();
for (int x = 1; x <= i; ++x) {
h[x] = f[x - 1] ^ f[x + (x & -x) - 1];
if (h[x]) { g.flip(x); g.flip(x & (x - 1)); }
}
f = h;
for (auto &o : requetes[i]) z[o[1]] = g[o[0]];
}
for (int i = 1; i <= q; ++i) cout << z[i] << "\n";
return 0;
}
U. [P13526] Célébration (3.5)
Lien du problème : P13526
On définit \(f_{u,d}\) comme la réponse pour le sous-arbre de \(u\) avec profondeur maximale \(d\). La transition est \(f'_{v,d} \gets \max(f_{v,d}, f_{v,d-1} + w)\), puis \(f_{u, \max(x,y)} \gets f_{u,x} + f_{v,y}\) si \(x + y \le x\).
On conjecture que la réponse est convexe, ce qui permet de maintenir les transitions avec un std::multiset. Pour la seconde transition, on se contente d'une complexité en \(\min(|f_u|, |f_v|)\).
Complexité temporelle : \(\mathcal O(n \log n)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 3e5 + 5;
multiset<ll, greater<>> f[MAXN];
ll g[MAXN], poids[MAXN], z[MAXN];
int n, k, parent[MAXN];
vector<int> graphe[MAXN];
ll a[MAXN], b[MAXN], c[MAXN];
void fusionner(int u, int v) {
if (f[v].size() > f[u].size()) swap(g[u], g[v]), swap(f[u], f[v]);
int s = f[u].size(), t = f[v].size();
if (2 * t + 2 >= s) {
memset(c, 0, (s + 1) << 3);
s = t = 0;
a[0] = b[0] = 0;
for (ll x : f[u]) ++s, a[s] = a[s - 1] + x;
for (ll x : f[v]) ++t, b[t] = b[t - 1] + x;
for (int i = 0; i <= s; ++i) c[i] = max(c[i], a[i] + b[min({t, i, k - i})]);
for (int i = 0; i <= t; ++i) c[i] = max(c[i], b[i] + a[min({s, i, k - i})]);
for (int i = 1; i <= s; ++i) c[i] = max(c[i], c[i - 1]);
g[u] = c[s];
for (int i = s; i; --i) c[i] -= c[i - 1];
f[u] = multiset<ll, greater<>>(c + 1, c + s + 1);
return;
}
memset(c, 0, (t + 2) << 3);
t = 0;
a[0] = b[0] = 0;
for (ll x : f[v]) ++t, b[t] = b[t - 1] + x;
auto it = f[u].begin();
for (int i = 1; i <= t + 1; ++i, ++it) a[i] = a[i - 1] + *it;
f[u].erase(f[u].begin(), it);
c[t + 1] = a[t + 1] + b[t];
for (int i = 0; i <= t; ++i) c[i] = max(a[i] + b[min({t, i, k - i})], b[i] + a[min({t, i, k - i})]);
for (int i = 0; i <= t; ++i) {
c[i + 1] = max(c[i + 1], c[i]);
f[u].insert(c[i + 1] - c[i]);
}
it = f[u].end();
a[0] = g[u];
for (int i = 1; i <= t + 1; ++i) a[i] = a[i - 1] - *--it;
f[u].erase(it, f[u].end());
memset(c, 0, (t + 2) << 3);
for (int i = 0; i <= t + 1; ++i) c[i] = a[i] + b[min({t, s - i, k - (s - i)})];
for (int i = t; ~i; --i) c[i] = max(c[i], c[i + 1]);
for (int i = 0; i <= t; ++i) f[u].insert(c[i] - c[i + 1]);
g[u] = c[0];
}
void dfs(int u) {
for (int v : graphe[u]) {
dfs(v);
f[v].insert(poids[v]);
g[v] += poids[v];
if ((int)f[v].size() > k) {
g[v] -= *f[v].rbegin();
f[v].erase(--f[v].end());
}
fusionner(u, v);
}
z[u] = g[u];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 2; i <= n; ++i) {
cin >> parent[i] >> poids[i];
graphe[parent[i]].push_back(i);
}
dfs(1);
for (int i = 1; i <= n; ++i) cout << z[i] << "\n";
return 0;
}
V. [P13919] Salle sombre (4)
Lien du problème : P13919
On atteint la racine, puis on augmente la profondeur de 2 en deux opérations. Si les quatre petits-fils existent, on interroge le plus à gauche. Sinon, on discute les cas. Le nombre d'interrogations est \(\frac{n}{2} + 1\).
Pour optimiser l'interrogation à la racine, on utilise les deux premières interrogations pour déterminer la profondeur et le sous-arbre au quatrième niveau. On effectue un DFS pour obtenir le graphe des quatre premiers niveaux et les plus courts chemins. On énumère \(x,y\) pour lesquels les différences de distance vers les feuilles sont toutes distinctes.
Complexité temporelle : \(\mathcal O(n)\).
#include <bits/stdc++.h>
using namespace std;
const int B = 1000;
const string OP[5] = {"up", "right", "downright", "downleft", "left"};
string deplacer(int x) { cout << OP[x] << endl; string o; cin >> o; return o; }
int interroger() { cout << "app" << endl; int o; cin >> o; return o; }
string s, l, r;
int d, gauche[32], droite[32], f[32][32], infini = 1e9;
bool g[32];
void ajouter(int u, int v, int w) { f[u][v] = f[v][u] = min(f[u][v], w); }
void dfs(int u) {
g[u] = 1;
if (u >= 16) return;
if (s[3] == '1') { s = deplacer(3); dfs(u << 1); s = deplacer(0); }
if (s[2] == '1') { s = deplacer(2); dfs(u << 1 | 1); s = deplacer(0); }
}
void resoudre() {
for (int x; d;) {
if (s[2] == '0') { s = deplacer(3); --d; continue; }
if (s[3] == '0') { s = deplacer(2); --d; continue; }
if (d == 1) {
s = deplacer(3);
x = interroger();
if (x != d - 1) s = deplacer(1);
break;
}
r = deplacer(2);
l = deplacer(4);
int c = l[2] - '0' + l[3] - '0' + r[2] - '0' + r[3] - '0';
if (c == 4) {
s = deplacer(3);
x = interroger();
for (int t = d - 2; t < x; ++t) s = deplacer(1);
d -= 2;
} else if (c == 3) {
if (l[3] == '0') {
s = deplacer(2);
x = interroger();
for (int t = d - 2; t < x; ++t) s = deplacer(1);
} else if (r[2] == '0') {
s = deplacer(3);
x = interroger();
for (int t = d - 2; t < x; ++t) s = deplacer(1);
} else if (l[2] == '0') {
deplacer(1);
s = deplacer(2);
x = interroger();
if (x == d - 1) s = deplacer(4);
else if (x == d + 1) { deplacer(0); deplacer(4); s = deplacer(3); }
} else {
s = deplacer(3);
x = interroger();
if (x == d - 1) s = deplacer(1);
else if (x == d + 1) { deplacer(0); deplacer(1); s = deplacer(2); }
}
d -= 2;
} else {
if (r[2] == '0' && r[3] == '0') { s = l; --d; continue; }
if (l[2] == '0' && l[3] == '0') { s = deplacer(1); --d; continue; }
s = l;
x = interroger();
if (x != d - 1) s = deplacer(1);
--d;
}
}
cout << "here" << endl;
}
signed main() {
for (cin >> s; s[0] == '1'; s = deplacer(0));
dfs(1);
int ct = count(g + 16, g + 32, 1);
for (int i = 1; i < 32; ++i) for (int j = 1; j < 32; ++j) f[i][j] = i == j ? 0 : infini;
for (int i = 2; i < 32; ++i) if (g[i]) {
ajouter(i >> 1, i, B + 1);
if ((i & (i - 1)) && g[i - 1]) ajouter(i - 1, i, 1);
}
for (int k = 1; k < 32; ++k) for (int i = 1; i < 32; ++i) for (int j = 1; j < 32; ++j) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
for (int x = 1; x < 32; ++x) {
if (g[x]) {
for (int y = x + 1; y < 32; ++y) {
if (g[y]) {
map<int, int> o;
for (int i = 16; i < 32; ++i) if (g[i]) o[f[x][i] % B - f[y][i] % B] = i;
if ((int)o.size() != ct) continue;
for (int t = __lg(x) - 1; ~t; --t) s = deplacer(3 - (x >> t & 1));
int X = interroger();
for (int t = __lg(x) - 1; ~t; --t) s = deplacer(0);
if (X <= 990) {
d = interroger();
resoudre();
return 0;
}
for (int t = __lg(y) - 1; ~t; --t) s = deplacer(3 - (y >> t & 1));
int Y = interroger();
for (int t = __lg(y) - 1; ~t; --t) s = deplacer(0);
d = X - f[x][o[X - Y]] % B;
for (int t = 3; ~t; --t) s = deplacer(3 - (o[X - Y] >> t & 1));
resoudre();
return 0;
}
}
}
}
d = interroger();
resoudre();
return 0;
}
W. [P13548] Air Reform (2.5)
Lien du problème : P13548
On effectue l'algorithme de Kruskal sur l'arbre de reconstruction Kruskal. Par ordre croissant des valeurs, lors de la fusion des sous-arbres gauche et droit d'un point, on connecte toutes les arêtes existantes entre les deux sous-arbres.
On maintient dynamiquement les ensembles de points et les composantes connexes des sous-arbres. On énumère goulument les points du sous-arbre léger, et pour chaque composante connexe du sous-arbre lourd, on compte les points sans arête avec le point courant.
Complexité temporelle : \(\mathcal O(m \log n)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
int n, m, dsu[MAXN * 2], taille[MAXN], dsuOriginal[MAXN], compteur[MAXN];
bool dansFile[MAXN];
basic_string<int> graphe[MAXN], f[MAXN], g[MAXN];
int trouverOriginal(int x) { return dsuOriginal[x] != x ? dsuOriginal[x] = trouverOriginal(dsuOriginal[x]) : x; }
int trouver(int x) { return dsu[x] != x ? dsu[x] = trouver(dsu[x]) : x; }
int enfant[MAXN * 2][2], poids[MAXN * 2], dfn[MAXN * 2], compteurDfn, st[MAXN * 2][20];
int comparer(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
void dfs(int u, int fz) {
dfn[u] = ++compteurDfn;
st[compteurDfn][0] = fz;
if (u > n) for (int v : enfant[u]) dfs(v, u);
}
int lca(int x, int y) {
if (x == y) return x;
int l = min(dfn[x], dfn[y]) + 1, r = max(dfn[x], dfn[y]), k = __lg(r - l + 1);
return comparer(st[l][k], st[r - (1 << k) + 1][k]);
}
void resoudre() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
dsu[i] = dsuOriginal[i] = i;
taille[i] = 1;
dansFile[i] = 0;
f[i] = g[i] = {i};
graphe[i].clear();
}
vector<array<int, 4>> E, Z;
for (int i = 1, u, v, z; i <= m; ++i) {
cin >> u >> v >> z;
graphe[u].push_back(v);
graphe[v].push_back(u);
E.push_back({z, u, v, i});
}
sort(E.begin(), E.end());
for (auto &e : E) {
int L = trouverOriginal(e[1]), R = trouverOriginal(e[2]);
if (L == R) continue;
if (g[L].size() < g[R].size()) swap(L, R);
dsuOriginal[R] = L;
for (int u : g[R]) {
int h = trouver(u);
basic_string<int> Q, N;
for (int x : f[L]) {
if (x != h) { Q += x; compteur[x] = taille[x]; dansFile[x] = 1; }
}
for (int x : graphe[u]) {
if (dansFile[trouver(x)]) --compteur[trouver(x)];
}
for (int x : Q) {
if (!compteur[x]) N += x;
else { Z.push_back({e[0], h, x}); taille[h] += taille[x]; dsu[x] = h; }
compteur[x] = 0;
dansFile[x] = 0;
}
N += h;
f[L].swap(N);
}
g[L] += g[R];
}
int h = n;
iota(dsu + 1, dsu + 2 * n, 1);
for (auto &e : Z) {
int u = trouver(e[1]), v = trouver(e[2]);
poids[++h] = e[0];
enfant[h][0] = u;
enfant[h][1] = v;
dsu[u] = dsu[v] = h;
}
compteurDfn = 0;
dfs(h, 0);
for (int k = 1; k < 20; ++k) {
for (int i = 1; i + (1 << k) - 1 <= compteurDfn; ++i) {
st[i][k] = comparer(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}
}
sort(E.begin(), E.end(), [](auto x, auto y) { return x[3] < y[3]; });
for (int i = 0; i < m; ++i) cout << poids[lca(E[i][1], E[i][2])] << " \n"[i == m - 1];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests, type;
cin >> tests >> type;
while (tests--) resoudre();
return 0;
}
X. [P14021] Saut de Baud 2 (4.5)
Lien du problème : P14021
Si \(S\) et \(\mathrm{rev}(S)\) se croisent, la chaîne est un palindrome, et le plus long préfixe propre est optimal. Donc, une fois un palindrome obtenu, le nombre d'opérations est directement calculable. Avant cela, chaque opération réduit la longueur de moitié, soit \(\mathcal O(\log n)\) opérations.
On part du palindrome final \(S\) et on remonte. Pour chaque position \(l\), on détermine le plus long palindrome commençant par \(l\), puis on étend goulument. On utilise des structures de données de suffixes pour optimiser la recherche.
Complexité temporelle : \(\mathcal O(n \log^2 n)\).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
struct ArbreSuffixes {
char s[MAXN];
int n, m, sa[MAXN], rk[MAXN], compteur[MAXN], t[MAXN], f[MAXN][20];
void initialiser() {
m = 27;
memset(compteur, 0, (m + 1) << 2);
s[n + 1] = 0;
for (int i = 1; i <= n; ++i) {
rk[i] = s[i] - 'a' + 1;
++compteur[rk[i]];
}
for (int i = 1; i <= m; ++i) compteur[i] += compteur[i - 1];
for (int i = n; i; --i) sa[compteur[rk[i]]--] = i;
for (int k = 1; ; k <<= 1) {
for (int i = 1; i <= k; ++i) t[i] = i + n - k;
for (int i = 1, h = k; i <= n; ++i) if (sa[i] > k) t[++h] = sa[i] - k;
memset(compteur, 0, (m + 1) << 2);
for (int i = 1; i <= n; ++i) ++compteur[rk[i]];
for (int i = 1; i <= m; ++i) compteur[i] += compteur[i - 1];
for (int i = n; i; --i) sa[compteur[rk[t[i]]]--] = t[i];
memcpy(t, rk, (n + 1) << 2);
m = 0;
t[n + 1] = 0;
for (int i = 1; i <= n; ++i) {
rk[sa[i]] = m += (i == 1 || t[sa[i]] != t[sa[i - 1]] || t[min(n + 1, sa[i] + k)] != t[min(n + 1, sa[i - 1] + k)]);
}
if (m == n) break;
}
for (int i = 1, k = 0; i <= n; ++i) {
for (k = max(k - 1, 0); s[i + k] == s[sa[rk[i] - 1] + k]; ++k);
f[rk[i]][0] = k;
}
for (int k = 1; k < 20; ++k) {
for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
f[i][k] = min(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
}
}
}
int lcs(int x, int y) {
if (x == y) return n - x + 1;
int l = min(rk[x], rk[y]) + 1, r = max(rk[x], rk[y]), k = __lg(r - l + 1);
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
} S;
struct ArbreSegments {
int taille[MAXN * 20], gauche[MAXN * 20], droite[MAXN * 20], totalNoeuds;
void initialiser() {
for (int i = 1; i <= totalNoeuds; ++i) taille[i] = gauche[i] = droite[i] = 0;
totalNoeuds = 0;
}
void inserer(int x, int l, int r, int q, int &p) {
taille[p = ++totalNoeuds] = taille[q] + 1;
if (l == r) return;
int milieu = (l + r) >> 1;
if (x <= milieu) inserer(x, l, milieu, gauche[q], gauche[p]), droite[p] = droite[q];
else inserer(x, milieu + 1, r, droite[q], droite[p]), gauche[p] = gauche[q];
}
int requete(int x, int l, int r, int q, int p) {
if (taille[p] == taille[q]) return S.n + 1;
if (l == r) return l;
int milieu = (l + r) >> 1, t = S.n + 1;
if (x <= milieu) t = requete(x, l, milieu, gauche[q], gauche[p]);
return t > S.n ? requete(x, milieu + 1, r, droite[q], droite[p]) : t;
}
} T;
int n, R[MAXN], hauteur[MAXN], dsu[MAXN];
int trouver(int x) { return x != dsu[x] ? dsu[x] = trouver(dsu[x]) : x; }
void mettreAJour(int l, int r, int w, int z) {
for (int x = trouver(l); x <= r; dsu[x] = x + 1, x = trouver(x)) R[x] = w - x, hauteur[x] = z;
}
int pr[MAXN], nx[MAXN], racine[MAXN];
string s;
int requete(int l, int r) {
int x = S.rk[2 * n + 2 - r], y = x;
for (int i = 19, k = 1 << i; ~i; k >>= 1, --i) {
if (x > k && S.f[x - k + 1][i] >= r - l + 1) x -= k;
if (y + k <= S.n && S.f[y + 1][i] >= r - l + 1) y += k;
}
int o = T.requete(r + 1, 1, S.n, racine[y], racine[x - 1]);
return o > n ? -1 : o + r - l;
}
void resoudre() {
cin >> s;
n = s.size();
s = " " + s + "{" + s;
T.initialiser();
reverse(s.begin() + n + 2, s.end());
S.n = 2 * n + 1;
for (int i = 1; i <= S.n; ++i) S.s[i] = s[i];
S.initialiser();
pr[1] = nx[n] = 1;
for (int i = 1; i <= S.n; ++i) T.inserer(S.sa[i], 1, S.n, racine[i - 1], racine[i]);
for (int i = 2; i <= n; ++i) pr[i] = s[i] == s[i - 1] ? pr[i - 1] + 1 : 1;
for (int i = n - 1; i; --i) nx[i] = s[i] == s[i + 1] ? nx[i + 1] + 1 : 1;
for (int i = 1; i <= n + 1; ++i) dsu[i] = i;
for (int i = n; i >= 1; --i) {
int d = S.lcs(i, 2 * n + 2 - i);
mettreAJour(i - d + 1, i, 2 * i, 2 * min(pr[i], nx[i]) - 1);
if (i > 1 && s[i] == s[i - 1]) {
d = S.lcs(i, 2 * n + 3 - i);
mettreAJour(i - d, i - 1, 2 * i - 1, 2 * min(pr[i - 1], nx[i]));
}
}
int z = 0;
vector<array<int, 2>> e;
for (int i = 1; i <= n; ++i) e.push_back({(R[i] - i + 1 - hauteur[i]) / 2 + hauteur[i] - 1, i});
sort(e.begin(), e.end(), greater<>());
for (auto &o : e) {
int w = o[0], i = o[1];
if (w + __lg((n - R[i]) / (R[i] - i + 1) + 1) <= z) continue;
for (int r = R[i]; ~r; r = requete(i, r), ++w);
z = max(z, w - 1);
}
cout << z << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests;
cin >> tests;
while (tests--) resoudre();
return 0;
}
Y. [P12403] Bête à trompe (4)
Lien du problème : P12403
Dans un arbre, si la distance entre \(s\) et \(t\) est >2, ils peuvent se rapprocher, donc on énumère seulement les paires à distance \(\le 2\). Pour les arbres à cycle, si ni \(s\) ni \(t\) n'est sur le cycle, on ne considère que les distances \(\le 2\).
Sinon, on énumère le cycle. Il y a un point sur le cycle, disons \(s\). On discute s'il y a un point noir sur le cycle. S'il y en a, les points roses et noirs sont des intervalles séparés par au plus un point bleu. On énumère l'intervalle rose et on vérifie l'intervalle noir correspondant.
Sans point noir, les points bleus et noirs sont des intervalles, et les points roses sont dans un sous-arbre des extrémités de l'intervalle bleu. On effectue un DP de changement de racine pour calculer les profondeurs maximales dans et hors du sous-arbre pour chaque point.
Complexité temporelle : \(\mathcal O(n + m)\).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 4e5 + 5;
vector<int> graphe[MAXN], aretes[MAXN];
int n, m, vc, A, B, dfn[MAXN], basse[MAXN], compteurDfn, pile[MAXN], hautPile;
bool dansPile[MAXN];
void tarjan(int u) {
dfn[u] = basse[u] = ++compteurDfn;
pile[++hautPile] = u;
dansPile[u] = true;
for (int v : aretes[u]) {
if (!dfn[v]) {
tarjan(v);
basse[u] = min(basse[u], basse[v]);
if (basse[v] >= dfn[u]) {
graphe[u].push_back(++vc);
while (dansPile[v]) {
graphe[vc].push_back(pile[hautPile]);
dansPile[pile[hautPile--]] = false;
}
}
} else basse[u] = min(basse[u], dfn[v]);
}
}
int taille[MAXN], parent[MAXN], c[MAXN], f[MAXN];
void dfs1(int u, int fz) {
taille[u] = u <= n;
parent[u] = fz;
for (int v : graphe[u]) {
dfs1(v, u);
taille[u] += taille[v];
}
if (u <= n) {
for (int v : graphe[u]) f[u] = max(f[u], f[v]);
} else {
c[u] = graphe[u].size() + 1;
for (int i = 0; i < c[u] - 1; ++i) {
f[u] = max(f[u], f[graphe[u][i]] + min(i + 1, c[u] - 1 - i));
}
}
}
int g[MAXN], file[MAXN], w[MAXN];
void dfs2(int u) {
if (u <= n) {
int premier = g[u], second = 0;
for (int v : graphe[u]) {
second = max(second, min(premier, f[v]));
premier = max(premier, f[v]);
}
for (int v : graphe[u]) g[v] = (f[v] == premier ? second : premier);
} else {
w[c[u] - 1] = g[u];
for (int i = 0; i < c[u] - 1; ++i) w[i] = w[i + c[u]] = f[graphe[u][i]];
int debut = 1, fin = 0, d = c[u] / 2;
for (int o = 2; o--;) {
for (int i = 0; i < 2 * c[u] - 1; ++i) {
while (debut <= fin && file[debut] < i - d) ++debut;
if (i >= c[u]) g[graphe[u][i - c[u]]] = max(g[graphe[u][i - c[u]]], i - file[debut] + w[file[debut]]);
while (debut <= fin && w[file[fin]] - file[fin] <= w[i] - i) --fin;
file[++fin] = i;
}
reverse(w, w + 2 * c[u] - 1);
reverse(graphe[u].begin(), graphe[u].end());
}
}
for (int v : graphe[u]) dfs2(v);
}
vector<int> H[MAXN];
int d[MAXN], b[MAXN], pa[MAXN], pb[MAXN], xa[MAXN], xb[MAXN];
ll s[MAXN];
bool vis[MAXN];
int dans(int x, int e) {
queue<array<int, 2>> file;
file.push({x, 0});
while (true) {
auto u = file.front();
file.pop();
if (u[1] == e) return u[0];
for (int v : aretes[u[0]]) {
if (!vis[v]) {
vis[v] = true;
file.push({v, u[1] + 1});
}
}
}
}
void resoudre() {
cin >> n >> m >> A >> B;
vc = n;
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
aretes[u].push_back(v);
aretes[v].push_back(u);
}
tarjan(1);
dfs1(1, 0);
for (int u = 1; u <= n; ++u) {
if (!parent[u] || graphe[parent[u]].size() > 1) continue;
if (taille[u] == A && n - taille[u] == B) {
cout << u << " " << parent[parent[u]] << "\n";
return;
}
if (taille[u] == B && n - taille[u] == A) {
cout << parent[parent[u]] << " " << u << "\n";
return;
}
}
for (int u = 1; u <= n; ++u) {
if (parent[u] && graphe[parent[u]].size() == 1) H[n - taille[u]].push_back(parent[parent[u]]);
for (int v : graphe[u]) {
if (graphe[v].size() == 1) H[taille[v]].push_back(graphe[v][0]);
}
if (A == B && H[A].size() > 1) {
cout << H[A][0] << " " << H[A][1] << "\n";
return;
}
if (A != B && !H[A].empty() && !H[B].empty()) {
cout << H[A][0] << " " << H[B][0] << "\n";
return;
}
H[n - taille[u]].clear();
for (int v : graphe[u]) H[taille[v]].clear();
}
dfs2(1);
for (int u = n + 1; u <= vc; ++u) {
if (graphe[u].size() > 1) {
for (int i = 0; i < c[u] - 1; ++i) {
s[i + 1] = s[i + c[u] + 1] = taille[graphe[u][i]];
d[i + 1] = d[i + c[u] + 1] = f[graphe[u][i]];
b[i + 1] = b[i + c[u] + 1] = graphe[u][i];
}
s[c[u]] = s[2 * c[u]] = n - taille[u];
d[c[u]] = d[2 * c[u]] = g[u];
b[0] = b[c[u]] = b[2 * c[u]] = parent[u];
for (int i = 1; i <= 2 * c[u]; ++i) s[i] += s[i - 1], pa[i] = pb[i] = xa[i] = xb[i] = 0;
for (int i = 1, j = 1, k = 1; i <= c[u]; ++i) {
while (s[j] - s[i - 1] < A) ++j;
while (s[k] - s[i - 1] < B) ++k;
if (s[j] - s[i - 1] == A) pa[i] = j;
if (s[k] - s[i - 1] == B) pb[i] = k;
}
for (int i = 2 * c[u], j = i, k = i; i > c[u]; --i) {
while (s[i] - s[j - 1] < A) --j;
while (s[i] - s[k - 1] < B) --k;
if (s[i] - s[j - 1] == A) pa[i] = j;
if (s[i] - s[k - 1] == B) pb[i] = k;
}
for (int i = 2 * c[u], debut = 1, fin = 0; i; --i) {
while (debut <= fin && d[file[fin]] <= d[i]) --fin;
file[++fin] = i;
if (i <= c[u] && pa[i]) {
while (debut <= fin && file[debut] > pa[i]) ++debut;
xa[i] = file[debut];
}
}
for (int i = 2 * c[u], debut = 1, fin = 0; i; --i) {
while (debut <= fin && d[file[fin]] <= d[i]) --fin;
file[++fin] = i;
if (i <= c[u] && pb[i]) {
while (debut <= fin && file[debut] > pb[i]) ++debut;
xb[i] = file[debut];
}
}
for (int i = 1; i <= c[u]; ++i) {
if (pa[i]) {
auto verifier = [&](int lx, int rx, int ly, int ry) {
if (ly > ry) return 0;
if (ly > c[u]) ly -= c[u], ry -= c[u];
if (s[ry] - s[ly - 1] != B) return 0;
int dx = rx - lx + 1, dy = ry - ly + 1;
if (dx % 2 != dy % 2) return 0;
int k = (dx - dy) / 2;
if (k > 0) {
if (d[xb[ly]] < k) return 0;
for (int x = 1; x <= c[u]; ++x) vis[b[x]] = 1;
cout << b[lx + ry - xb[ly] + k] << " " << dans(b[xb[ly]], k) << "\n";
return 1;
} else {
if (d[xa[lx]] < -k) return 0;
for (int x = 1; x <= c[u]; ++x) vis[b[x]] = 1;
cout << dans(b[xa[lx]], -k) << " " << b[ly + rx - xa[lx] - k] << "\n";
return 1;
}
};
for (int l : {pa[i] + 1, pa[i] + 2}) {
for (int r : {i + c[u] - 2, i + c[u] - 1}) {
if (verifier(i, pa[i], l, r)) return;
}
}
}
}
auto verifier = [&](int x, int up, int l, int r, int o) {
if (!l || !r) return 0;
if (r - l + 1 >= c[u] || r - l + 1 < (c[u] + 1) / 2) return 0;
int t = r - l + 1 - (c[u] + 1) / 2;
if (t > up) return 0;
for (int i = 1; i <= c[u]; ++i) vis[b[i]] = 1;
vis[x] = 1;
int y = dans(x, t), z = (o & 2 ? b[r - t] : b[l + t]);
if (o & 1) swap(y, z);
cout << y << " " << z << "\n";
return 1;
};
for (int i = 1; i <= c[u]; ++i) {
for (int x : graphe[b[i]]) {
if (graphe[x].size() == 1) {
int j = (i < c[u] ? i + 1 : 1), k = (i > 1 ? i + c[u] - 1 : 2 * c[u]);
if (taille[x] == A && verifier(graphe[x][0], f[x] - 1, j, pb[j], 0)) return;
if (taille[x] == B && verifier(graphe[x][0], f[x] - 1, j, pa[j], 1)) return;
if (taille[x] == A && verifier(graphe[x][0], f[x] - 1, pb[k], k, 2)) return;
if (taille[x] == B && verifier(graphe[x][0], f[x] - 1, pa[k], k, 3)) return;
}
}
}
if (parent[parent[u]] && graphe[parent[parent[u]]].size() == 1) {
int x = parent[parent[u]];
if (n - taille[x] == A && verifier(parent[x], g[x], 1, pb[1], 0)) return;
if (n - taille[x] == B && verifier(parent[x], g[x], 1, pa[1], 1)) return;
if (n - taille[x] == A && verifier(parent[x], g[x], pb[2 * c[u] - 1], 2 * c[u] - 1, 2)) return;
if (n - taille[x] == B && verifier(parent[x], g[x], pa[2 * c[u] - 1], 2 * c[u] - 1, 3)) return;
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests;
cin >> tests;
while (tests--) {
resoudre();
compteurDfn = hautPile = 0;
for (int i = 0; i <= 2 * n; ++i) {
graphe[i].clear();
aretes[i].clear();
H[i].clear();
dfn[i] = basse[i] = pile[i] = dansPile[i] = 0;
taille[i] = parent[i] = c[i] = f[i] = g[i] = file[i] = w[i] = 0;
d[i] = b[i] = s[i] = pa[i] = pb[i] = xa[i] = xb[i] = vis[i] = 0;
}
}
return 0;
}
Z. [P14164] Composition (3)
Lien du problème : P14164
Après discussion, le problème revient à maintenir l'équivalence des arêtes initiales. On supporte la division d'intervalles et la maintenance dynamique des classes d'équivalence. Pour chaque arête \(e\), on maintient si elle est couverte dans chaque requête, sous forme de chaîne \(s_e\). On s'intéresse aux classes de sous-chaînes propres de \(s_e[1,i]\).
On utilise un arbre de présidents pour maintenir \(s_e\), et on trie par ordre lexicographique avec un hachage binaire. On énumère \(i\) en ordre décroissant, et on utilise une structure union-find pour maintenir les classes d'équivalence.
Complexité temporelle : \(\mathcal O(n \log^2 n)\).
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int MAXN = 2.5e5 + 5;
mt19937_64 generateurAleatoire(time(0));
int n, m, c1[MAXN], c2[MAXN], racine[MAXN], id[MAXN];
ull hv[MAXN];
struct ArbreSegments {
ull hs[MAXN * 40];
int gauche[MAXN * 40], droite[MAXN * 40], totalNoeuds;
void initialiser() {
for (int i = 1; i <= totalNoeuds; ++i) hs[i] = gauche[i] = droite[i] = 0;
totalNoeuds = 0;
}
void inserer(int x, int l, int r, int q, int &p) {
hs[p = ++totalNoeuds] = hs[q] ^ hv[x];
if (l == r) return;
int milieu = (l + r) >> 1;
if (x <= milieu) inserer(x, l, milieu, gauche[q], gauche[p]), droite[p] = droite[q];
else inserer(x, milieu + 1, r, droite[q], droite[p]), gauche[p] = gauche[q];
}
bool comparer(int p, int q) {
if (hs[p] == hs[q]) return 0;
int l = 1, r = m;
while (l < r) {
int milieu = (l + r) >> 1;
if (hs[gauche[p]] == hs[gauche[q]]) p = droite[p], q = droite[q], l = milieu + 1;
else p = gauche[p], q = gauche[q], r = milieu;
}
return hs[p] < hs[q];
}
int lcp(int p, int q) {
if (hs[p] == hs[q]) return m;
int l = 1, r = m;
while (l < r) {
int milieu = (l + r) >> 1;
if (hs[gauche[p]] == hs[gauche[q]]) p = droite[p], q = droite[q], l = milieu + 1;
else p = gauche[p], q = gauche[q], r = milieu;
}
return l - 1;
}
} T;
vector<int> X[MAXN];
vector<array<int, 2>> E[MAXN];
int dsu[MAXN], taille[MAXN];
int trouver(int x) { return dsu[x] != x ? dsu[x] = trouver(dsu[x]) : x; }
ll reponse[MAXN], somme;
void resoudre() {
cin >> n >> m;
T.initialiser();
somme = 0;
for (int i = 1; i <= n; ++i) X[i].clear();
for (int i = 1; i <= m; ++i) E[i].clear();
set<int> S1, S2;
S1.insert(n);
S2.insert(n);
for (int i = 1; i < n; ++i) S1.insert(i);
for (int i = 1, l, r; i <= m; ++i) {
cin >> l >> r;
if (l > r) swap(l, r);
hv[i] = generateurAleatoire();
X[l].push_back(i);
X[r].push_back(i);
for (auto it = S2.lower_bound(l); *it < r; it = S2.erase(it));
for (auto it = S1.lower_bound(l); *it < r; it = S1.erase(it)) S2.insert(*it);
c1[i] = S1.size() - 1;
c2[i] = S2.size() - 1;
}
for (int i = 1; i < n; ++i) {
racine[i] = racine[i - 1];
id[i] = i;
for (int x : X[i]) T.inserer(x, 1, m, racine[i], racine[i]);
}
stable_sort(id + 1, id + n, [&](int x, int y) { return T.comparer(racine[x], racine[y]); });
for (int i = 2; i < n; ++i) E[T.lcp(racine[id[i - 1]], racine[id[i]])].push_back({id[i - 1], id[i]});
for (int i = 1; i < n; ++i) { taille[i] = 1; dsu[i] = i; }
for (int i = m; i >= 1; --i) {
for (auto &e : E[i]) {
int x = trouver(e[0]), y = trouver(e[1]);
somme += 1ll * taille[x] * taille[y];
dsu[y] = x;
taille[x] += taille[y];
}
reponse[i] = somme + 1ll * c1[i] * (n - 1 + i - c1[i]) + c2[i];
}
for (int i = 1; i <= m; ++i) cout << reponse[i] << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests;
cin >> tests;
while (tests--) resoudre();
return 0;
}
AA. [P13955] Distance d'extension (7)
Lien du problème : P13955
On modélise avec un réseau de flot. On transforme le plus court chemin en une coupe minimale dans le graphe dual. L'opération consiste à augmenter la capacité de certaines arêtes pour augmenter le flot maximum de \(k\).
On construit des arêtes \((u,v,w,0)\) et \((u,v,\infty,1)\), puis on cherche un flot maximum de capacité \(dis + k\) à coût minimal. On peut d'abord augmenter les arêtes \((u,v,w,0)\), puis ajouter les arêtes \((u,v,\infty,1)\) et chercher un flot maximum de capacité \(k\) à coût minimal.
Complexité temporelle : \(\mathcal O(n^3 m^3 + n^2 m^2 k)\).
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct Arete { int v, e, f, w; } G[10005];
int S, T, ec = 1, tete[505], dis[505], pre[505];
bool dansFile[505];
void ajouterArete(int u, int v, int f, int w) { G[++ec] = {v, tete[u], f, w}; tete[u] = ec; }
void lien(int u, int v, int f, int w = 0) { ajouterArete(u, v, f, w); ajouterArete(v, u, 0, -w); }
bool SPFA() {
memset(dis, 0x3f, sizeof(dis));
memset(pre, 0, sizeof(pre));
memset(dansFile, false, sizeof(dansFile));
queue<int> file;
file.push(S);
dansFile[S] = true;
dis[S] = 0;
while (!file.empty()) {
int u = file.front();
file.pop();
dansFile[u] = false;
for (int i = tete[u], v; i; i = G[i].e) {
if (G[i].f && dis[v = G[i].v] > dis[u] + G[i].w) {
dis[v] = dis[u] + G[i].w;
pre[v] = i;
if (!dansFile[v]) { file.push(v); dansFile[v] = true; }
}
}
}
return pre[T];
}
array<int, 2> SSP() {
int f = 0, c = 0;
while (SPFA()) {
int g = inf;
for (int u = T; u != S; u = G[pre[u] ^ 1].v) g = min(g, G[pre[u]].f);
f += g;
c += g * dis[T];
for (int u = T; u != S; u = G[pre[u] ^ 1].v) { G[pre[u]].f -= g; G[pre[u] ^ 1].f += g; }
}
return {f, c};
}
int courant[505], profondeur[505];
bool BFS() {
memcpy(courant, tete, sizeof(courant));
memset(profondeur, -1, sizeof(profondeur));
queue<int> file;
file.push(S);
profondeur[S] = 0;
while (!file.empty()) {
int u = file.front();
file.pop();
for (int i = tete[u]; i; i = G[i].e) {
if (G[i].f && profondeur[G[i].v] == -1) {
profondeur[G[i].v] = profondeur[u] + 1;
file.push(G[i].v);
}
}
}
return profondeur[T] != -1;
}
int dfs(int u, int f) {
if (u == T) return f;
int r = f;
for (int i = courant[u]; i; i = G[i].e) {
int v = G[courant[u] = i].v;
if (G[i].f && profondeur[v] == profondeur[u] + 1) {
int g = dfs(v, min(r, G[i].f));
if (!g) profondeur[v] = -1;
G[i].f -= g;
G[i ^ 1].f += g;
r -= g;
}
if (!r) return f;
}
return f - r;
}
int n, m, k, a[505][505], b[505][505], z1[505][505], z2[505][505];
int identifiant(int x, int y) { return x < 1 ? S : (x < n ? (x - 1) * (m - 1) + y : T); }
void resoudre() {
memset(tete, 0, sizeof(tete));
ec = 1;
cin >> n >> m >> k;
S = (n - 1) * (m - 1) + 1;
T = S + 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
cin >> z1[i][j];
lien(identifiant(i - 1, j), identifiant(i, j), z1[i][j]);
lien(identifiant(i, j), identifiant(i - 1, j), z1[i][j]);
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> z2[i][j];
if (1 < j && j < m) {
lien(identifiant(i, j - 1), identifiant(i, j), z2[i][j]);
lien(identifiant(i, j), identifiant(i, j - 1), z2[i][j]);
}
}
}
int flotInitial = 0;
while (BFS()) flotInitial += dfs(S, inf);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
lien(identifiant(i - 1, j), identifiant(i, j), k, 1);
lien(identifiant(i, j), identifiant(i - 1, j), k, 1);
a[i][j] = ec;
}
}
for (int i = 1; i < n; ++i) {
for (int j = 2; j < m; ++j) {
lien(identifiant(i, j - 1), identifiant(i, j), k, 1);
lien(identifiant(i, j), identifiant(i, j - 1), k, 1);
b[i][j] = ec;
}
}
++T;
lien(T - 1, T, k, 0);
cout << SSP()[1] << "\n";
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
cout << z1[i][j] + G[a[i][j]].f + G[a[i][j] - 2].f << " \n"[j == m - 1];
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
cout << z2[i][j] + (1 < j && j < m ? G[b[i][j]].f + G[b[i][j] - 2].f : 0) << " \n"[j == m];
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests;
cin >> tests;
while (tests--) resoudre();
return 0;
}
AB. [P13960] Structure de suffixe (3.5)
Lien du problème : P13960
On discute si \(f(i,j) \ge j\). Si \(f(i,j) \le j\), la valeur est le nœud atteint par \(t[1,j]\) dans l'automate AC de \(s\). Sinon, on cherche \(s_x = s_y + t[1,j]\), et on note \(p_y\) le plus grand \(j\) tel que \(t[1,j]\) existe. \(y\) est le premier ancêtre de \(i\) dans l'arbre des échecs avec \(p_y \ge j\).
On calcule \(p\) par hachage binaire, puis on énumère \(j\). On maintient dynamiquement le nombre de \(i\) appariés pour chaque \(y\), avec une structure union-find.
Complexité temporelle : \(\mathcal O(n \log n)\).
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int MAXN = 2e5 + 5, P = 1e6 + 3;
struct ArbreSegments {
int arbre[MAXN * 20], gauche[MAXN * 20], droite[MAXN * 20], totalNoeuds;
void inserer(int x, int c, int l, int r, int q, int &p) {
arbre[p = ++totalNoeuds] = c;
if (l == r) return;
int milieu = (l + r) >> 1;
if (x <= milieu) inserer(x, c, l, milieu, gauche[q], gauche[p]), droite[p] = droite[q];
else inserer(x, c, milieu + 1, r, droite[q], droite[p]), gauche[p] = gauche[q];
}
int requete(int x, int l, int r, int p) {
if (l == r) return arbre[p];
int milieu = (l + r) >> 1;
return x <= milieu ? requete(x, l, milieu, gauche[p]) : requete(x, milieu + 1, r, droite[p]);
}
void initialiser() {
for (int i = 1; i <= totalNoeuds; ++i) arbre[i] = gauche[i] = droite[i] = 0;
totalNoeuds = 0;
}
} T;
int n, m, parent[MAXN], a[MAXN], b[MAXN], d[MAXN], prochain[MAXN], tete[P];
ull B, puissance[MAXN], hc[MAXN], ha[MAXN], hb[MAXN];
vector<int> graphe[MAXN], X[MAXN];
bool requete(ull z) {
for (int u = tete[z % P]; u; u = prochain[u]) if (ha[u] == z) return 1;
return 0;
}
int longueur[MAXN], racine[MAXN], haut[MAXN], dsu[MAXN], taille[MAXN];
int trouver(int x) { return dsu[x] != x ? dsu[x] = trouver(dsu[x]) : x; }
void resoudre() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> parent[i];
for (int i = 1; i <= n; ++i) {
cin >> a[i];
ha[i] = ha[parent[i]] * B + hc[a[i]];
longueur[i] = longueur[parent[i]] + 1;
graphe[parent[i]].push_back(i);
prochain[i] = i;
swap(prochain[i], tete[ha[i] % P]);
}
for (int i = 1; i <= m; ++i) cin >> b[i], hb[i] = hb[i - 1] * B + hc[b[i]];
for (int i = 1; i <= n; ++i) {
for (int k = 1 << 19; k; k >>= 1) {
if (d[i] + k <= m && requete(ha[i] * puissance[d[i] + k] + hb[d[i] + k])) d[i] += k;
}
}
queue<int> file;
for (int x : graphe[0]) {
T.inserer(a[x], x, 1, n, racine[0], racine[0]);
file.push(x);
}
while (!file.empty()) {
int u = file.front();
file.pop();
racine[u] = racine[haut[u]];
X[d[u]].push_back(u);
for (int x : graphe[u]) {
haut[x] = T.requete(a[x], 1, n, racine[u]);
T.inserer(a[x], x, 1, n, racine[u], racine[u]);
file.push(x);
}
}
ll somme = 0;
for (int i = 0; i <= n; ++i) { dsu[i] = i; taille[i] = i > 0; somme += longueur[i]; }
for (int i = 1, o = 0; i <= m; ++i) {
o = T.requete(b[i], 1, n, racine[o]);
for (int x : X[i - 1]) {
int y = trouver(haut[x]);
somme -= 1ll * taille[x] * (longueur[x] - longueur[y]);
dsu[x] = y;
taille[y] += taille[x];
}
cout << somme + 1ll * (n - taille[0]) * i + 1ll * taille[0] * longueur[o] << " \n"[i == m];
}
T.initialiser();
for (int i = 0; i <= m; ++i) X[i].clear();
for (int i = 0; i <= n; ++i) {
graphe[i].clear();
longueur[i] = d[i] = prochain[i] = racine[i] = haut[i] = 0;
tete[ha[i] % P] = 0;
}
}
mt19937_64 generateurAleatoire(time(0));
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
B = generateurAleatoire() | 1;
for (int i = puissance[0] = 1; i < MAXN; ++i) puissance[i] = puissance[i - 1] * B, hc[i] = generateurAleatoire();
int tests;
cin >> tests;
while (tests--) resoudre();
return 0;
}