Problème 0112G : Sous-séquence et carré de la diversité

Énoncé

Soit une séquence d'entiers positifs \(A_1, A_2, \dots, A_n\). On définit \(f(l,r)\) comme la taille de l'ensemble distinct \(\{A_l, A_{l+1}, \dots, A_r\}\). Calculer \(\sum_{l=1}^n \sum_{r=l}^n (f(l,r))^2 \mod 10^9+7\).

Approche

Commençons par le calcul de \(\sum_{l=1}^n\sum_{r=l}^n f(l,r) \mod 10^9+7\). On traite chaque valeur distincte séparément. Pour une valeur \(x\) apparaissant à cretaines positions, on considère les intervalles où elle contribue. Soit la séquence ..x..x. : les contributions de \(x\) sont : pour \(R\in[1,2]\) aucune, pour \(R\in[3,5]\) celle du premier \(x\), pour \(R\in[6,7]\) celle du second. On maintient un arbre de segments : quand on rencontre une occurrence de \(x\) à la position \(p\), on ajoute 1 sur l'intervalle \([pos\_prec+1, p]\) (où \(pos\_prec\) est la position précédente de \(x\)). Pour chaque \(R\) on interroge la somme sur \([1,R]\).

Pour le carré, notons \(S\) la somme des carrés des diversités sur tous les intervalles se terminant à la position courante, et \(sum\) la somme des diversités. Quand on ajoute une nouvelle position \(R\), la nouvelle valeur pour un intervalle démarrant en \(L\) devient \(f(L,R) = f(L,R-1)+1\) si l'élément en \(R\) n'est pas dans \([L,R-1]\) (grâce à l'intervalle mis à jour). Ainsi la mise à jour sur le segment \([L,R]\) est : \((S+x)^2 = S^2 + 2x\cdot sum + x\cdot (r-l+1)\), et \(sum \leftarrow sum + (r-l+1)\). On utilise un arbre de segments pour appliquer ces mises à jour par intervalle et cumuler les réponses.

Problème 0112H : Le pays sans retour

Énoncé

Points numérotés \(1,\dots,n\), chacun avec un poids distinct. Deux opérations :

• Connecter les points \(x\) et \(y\).
• Demander le numéro du \(k\)-ième plus petit poids dans la composante connexe de \(x\).

Approche

Union-Find combiné à un arbre de segments de valeurs persistants (pour les poids). On fusionne les arbres lors des unions.

Problème 0112I : Rotations d'arbres (POI2011)

Énoncé

Arbre binaire dont les feuilles sont une permutation de \(1\) à \(n\). On peut échanger les sous-arbres gauche et droit d'un nœud interne un nombre quelconque de fois. Minimiser le nombre d'inversions dans le parcours préfixe final.

Approche

Pour un nœud \(x\), les échanges dans les sous-arbres n'affectent pas le nombre d'inversions entre les deux sous-arbres de \(x\). La contribution totale est : inversions du sous-arbre gauche + inversions du sous-arbre droit + min(inversions si gauche avant droite, inversions si droite avant gauche). On construit un arbre de segments sur les poids des feuilles. Pour deux sous-arbres \(A\) et \(B\) représentés par des arbres de segments, le nombre d'inversions entre eux est \(\min(cnt_A[gauche] \times cnt_B[droite], cnt_A[droite] \times cnt_B[gauche])\). On fusionne les arbres en remontant.

Problème 0112J : Opérations sur une séquence binaire

Énoncé

Séquence binaire de longueur \(n\). Cinq opérations :

• 0 a b : mettre tous les bits de \([a,b]\) à 0.
• 1 a b : mettre tous les bits de \([a,b]\) à 1.
• 2 a b : inverser tous les bits de \([a,b]\).
• 3 a b : demander le nombre de 1 dans \([a,b]\).
• 4 a b : demander la longueur maximale de 1 consécutifs dans \([a,b]\).

Approche

Arbre de segments stockant pour chaque nœud : longueur du préfixe de 0, suffixe de 0, max de 0, idem pour 1, plus un indicateur de propagation pour les mises à jour d'ensemble et les inversions. La fusion est classique.

Problème 0114E : Somme par saut

Énoncé

Soit une séquence \(a\) de longueur \(n\). \(q\) requêtes : pour chaque \((t,k)\), calculer \(a_t + a_{t+k} + a_{t+2k} + \dots\) tant que l'indice reste \(\le n\).

Approche

On traite les requêtes offline avec une technique de seuil (\(T = 2000\)). Si \(k > T\), on calcule directement par boucle. Sinon, on regroupe les requêtes par \(k\) et on précalcule par DP : pour un \(k\) fixé, on parcourt les indices de \(n\) à \(1\) avec \(f[i] = a[i] + f[i+k]\).

Code (exemple réécrit)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300010;
const int THR = 2000;
typedef long long ll;
int n, q, a[MAXN];
ll ans[MAXN];
vector<int> req[THR+5];
int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    scanf("%d", &q);
    for (int i=1; i<=q; i++) {
        int t, k; scanf("%d %d", &t, &k);
        if (k <= THR) req[k].push_back(i);
        else {
            int cur = t;
            while (cur <= n) {
                ans[i] += a[cur];
                cur += k;
            }
        }
    }
    for (int k=1; k<=THR; k++) {
        if (req[k].empty()) continue;
        vector<ll> dp(n+5, 0);
        for (int i=n; i>=1; i--) dp[i] = a[i] + dp[i+k];
        for (int idx : req[k]) ans[idx] = dp[ idx ];
    }
    for (int i=1; i<=q; i++) printf("%lld\n", ans[i]);
    return 0;
}

Problème 0114F : Découpage de tableau

Énoncé

Découper un tableau de longueur \(n\) en segments dont la somme de chaque segment est \(\ge 0\). Compter le nombre de façons (modulo \(10^9+7\)).

Aprpoche

On calcule les sommes préfixes. On veut compter le nombre de façons de couper à des positions où la somme préfixe est croissante. On utilise un arbre de Fenwick indexé par les valeurs des sommes préfixes (après compression). On initialise \(F[0]=1\), puis pour chaque position \(i\), \(F[i] =\) somme sur les \(F[j]\) avec \(sum[j] \le sum[i]\). On met à jour l'arbre avec \(F[i]\).

Code (exemple réécrit)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int N = 2000010;
int n;
int a[N];
long long pref[N];
int bit[N];
void add(int idx, int val) {
    while (idx <= n+1) {
        bit[idx] = (bit[idx] + val) % MOD;
        idx += idx & -idx;
    }
}
int ask(int idx) {
    int res = 0;
    while (idx > 0) {
        res = (res + bit[idx]) % MOD;
        idx -= idx & -idx;
    }
    return res;
}
int main() {
    scanf("%d", &n);
    vector<long long> vals;
    vals.push_back(0);
    for (int i=1; i<=n; i++) {
        scanf("%d", &a[i]);
        pref[i] = pref[i-1] + a[i];
        vals.push_back(pref[i]);
    }
    // compression
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    auto comp = [&](long long x){ return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1; };
    // DP
    add(comp(0), 1);
    long long ans = 0;
    for (int i=1; i<=n; i++) {
        int idx = comp(pref[i]);
        int cur = ask(idx);
        if (i == n) ans = cur;
        else add(idx, cur);
    }
    printf("%lld\n", ans % MOD);
    return 0;
}

Problème 0114G : Opérations sur séquence (places libres)

Énoncé

Initialement tous les éléments sont 0. Opérations :

• A p : trouver le premier intervalle de \(p\) zéros consécutifs, les mettre à 1 ; si impossible, échec.
• L a b : remettre à 0 l'intervalle \([a,b]\).

Compter le nombre d'échecs de type A.

Approche

Arbre de segments classique stockant la longueur du préfixe de 0, suffixe de 0, maximum de 0 consécutifs, et un indicateur de paresse pour les mises à jour de plage. On utilise une fonction de recherche pour trouver le premier emplacement contenant au moins \(p\) zéros.

Code (exemple réécrit)

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int n, m, fails=0;
struct SegTree {
    int l[N*4], r[N*4];
    int pre[N*4], suf[N*4], mx[N*4];
    int lazy[N*4]; // -1: none, 0: set to 0, 1: set to 1
    void push(int rt) {
        if (lazy[rt]==-1 || l[rt]==r[rt]) return;
        int left = rt*2, right = rt*2+1;
        lazy[left] = lazy[rt];
        lazy[right] = lazy[rt];
        int lenL = r[left] - l[left] + 1;
        int lenR = r[right] - l[right] + 1;
        pre[left] = suf[left] = mx[left] = (lazy[rt]==0) ? lenL : 0;
        pre[right] = suf[right] = mx[right] = (lazy[rt]==0) ? lenR : 0;
        lazy[rt] = -1;
    }
    void merge(int rt) {
        int L = rt*2, R = rt*2+1;
        pre[rt] = pre[L];
        if (pre[L] == (r[L]-l[L]+1)) pre[rt] += pre[R];
        suf[rt] = suf[R];
        if (suf[R] == (r[R]-l[R]+1)) suf[rt] += suf[L];
        mx[rt] = max({mx[L], mx[R], suf[L] + pre[R]});
    }
    void build(int rt, int L, int R) {
        l[rt]=L; r[rt]=R; lazy[rt]=-1;
        if (L==R) {
            pre[rt]=suf[rt]=mx[rt]=1;
            return;
        }
        int mid = (L+R)/2;
        build(rt*2, L, mid);
        build(rt*2+1, mid+1, R);
        merge(rt);
    }
    void update(int rt, int L, int R, int val) {
        if (L>r[rt] || R<l :="" avant="" devrait="" g="" if="" int="" l="" lazy="" left="rt*2," len="" merge="" pre="" push="" query="" r="" return="" right="rt*2+1;" rt="" update="" val="">= len) return query(left, len);
        else if (suf[left] + pre[right] >= len) return r[left] - suf[left] + 1; // début de l'intervalle
        else return query(right, len);
    }
} seg;
int main() {
    scanf("%d %d", &n, &m);
    seg.build(1,1,n);
    for (int i=0; i<m a="" b="" char="" continue="" else="" fails="" i="" if="" int="" op="" pos="seg.query(1," printf="" return="" scanf="" seg.update="" x=""></m></l>

Problème 0114H : Boutons (énoncé non textuel)

Approche

Problème standard d'arbre de segments pour des opérations de mise à jour et d'interrogation de plage.