Partitionnement de Séquence et Optimisation de Pente CDQ

Énoncé du Problème

Étant donné une séquence \(t\) de longueur \(N\), l'objectif est de la diviser en \(K\) sous-segments contigus. Si le \(i\)-ème sous-segment s'étend de l'indice \(l_i\) à \(r_i\), le coût total est défini par \(\sum_{i = 1} ^ K (t_{l_i} - t_{r_i}) ^ 2\). Le but est de minimiser ce coût.

Approche Algorithmique

Une approche de programmation dynamique standard définit \(f[i][j]\) comme le coût minimal pour partitionner les \(j\) premiers éléments en \(i\) segments. La transition s'écrit :

Pour résoudre ce problème, l'algorithme de CDQ (Divide and Conquer) est parfaitement adapté. À chaque étape de la récursion, les points de la moitié gauche sont triés par coordonnée \(x\), et ceux de la moitié droite par la pente requise. L'enveloppe convexe est construite dynamiquement pour la moitié gauche afin de répondre aux requêtes de la moitié droite. Une attention particulière doit être portée aux multiplications croisées pour éviter les erreurs de précision lors des comparaisons de pentes.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using int64 = long long;

const int64 INF = 1e18;

struct Point {
    int64 x, y;
    int id;
};

int n, k_segments;
vector<int64> seq;
vector<vector<int64>> dp;
vector<Point> left_points, right_points, temp_points;

inline int64 square(int64 val) { return val * val; }

bool cross_product(const Point& a, const Point& b, const Point& c) {
    return (b.y - a.y) * (c.x - b.x) >= (c.y - b.y) * (b.x - a.x);
}

void cdq_solve(int left, int right, int current_k) {
    if (left == right) {
        dp[current_k][left] = min(dp[current_k][left], dp[current_k - 1][left - 1]);
        return;
    }
    
    int mid = left + (right - left) / 2;
    cdq_solve(left, mid, current_k);
    
    left_points.clear();
    right_points.clear();
    
    for (int i = left - 1; i <= mid; ++i) {
        if (dp[current_k - 1][i] != INF) {
            left_points.push_back({2 * seq[i + 1], dp[current_k - 1][i] + square(seq[i + 1]), i});
        }
    }
    for (int i = mid + 1; i <= right; ++i) {
        right_points.push_back({seq[i], 0, i});
    }
    
    sort(left_points.begin(), left_points.end(), [](const Point& a, const Point& b) {
        return a.x < b.x;
    });
    sort(right_points.begin(), right_points.end(), [](const Point& a, const Point& b) {
        return a.x < b.x;
    });
    
    vector<Point> hull;
    int hull_ptr = 0;
    
    for (const auto& req : right_points) {
        while (left_points.size() > 0 && hull_ptr < left_points.size()) {
            hull.push_back(left_points[hull_ptr++]);
            while (hull.size() >= 3 && cross_product(hull[hull.size() - 3], hull[hull.size() - 2], hull.back())) {
                hull.erase(hull.end() - 2);
            }
        }
        
        int opt = 0;
        while (opt + 1 < hull.size()) {
            int64 dy = hull[opt + 1].y - hull[opt].y;
            int64 dx = hull[opt + 1].x - hull[opt].x;
            if (dy <= req.x * dx) opt++;
            else break;
        }
        
        if (!hull.empty()) {
            int64 cost = dp[current_k - 1][hull[opt].id] + square(seq[hull[opt].id + 1] - req.x);
            dp[current_k][req.id] = min(dp[current_k][req.id], cost);
        }
    }
    
    cdq_solve(mid + 1, right, current_k);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> n >> k_segments)) return 0;
    
    seq.resize(n + 1);
    for (int i = 1; i <= n; ++i) cin >> seq[i];
    
    dp.assign(k_segments + 1, vector<int64>(n + 1, INF));
    for (int i = 1; i <= n; ++i) dp[1][i] = square(seq[i] - seq[1]);
    
    for (int k = 2; k <= k_segments; ++k) {
        cdq_solve(1, n, k);
    }
    
    cout << dp[k_segments][n] << "\n";
    return 0;
}

Couplage Parfait et Déterminant avec Racines de l'Unité

Énoncé du Problème

On considère un graphe biparti composé de \(2N\) sommets. Les arêtes possèdent un poids ou n'existent pas (représenté par \(-1\)). La question est de déterminer s'il existe un couplage parfait dont la somme des poids est un multiple de \(K\), avec \(1 \le N, K \le 100\).

Approche Algorithmique

La vérification de l'existence d'un couplage parfait dans un graphe biparti peut être effectuée via la matrice de Tutte. On construit une matrice \(M\) où \(M_{i,j} = X_{i,j}\) (une variable aléatoire) si l'arête existe, et \(0\) sinon. Le graphe possède un couplage parfait si et seulement si le déterminant \(\det(M) \neq 0\).

Pour filtrer les couplages dont le poids \(S\) satisfait \(S \equiv 0 \pmod K\), on utilise les propriétés des racines de l'unité. En remplaçant les variables aléatoires par \(X_{i,j} \cdot \omega_K^{i \cdot \text{poids}}\), la somme des déterminants sur toutes les racines annulera les couplages dont le poids n'est pas un multiple de \(K\). L'identité fondamentale est :

#include <iostream>
#include <vector>
#include <random>

using namespace std;
using int64 = long long;

int64 mod_pow(int64 base, int64 exp, int64 mod) {
    int64 res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int64 mod_inverse(int64 n, int64 mod) {
    return mod_pow(n, mod - 2, mod);
}

int64 compute_determinant(vector<vector<int64>> mat, int64 mod) {
    int n = mat.size();
    int64 det = 1;
    int sign = 1;
    
    for (int i = 0; i < n; ++i) {
        int pivot = i;
        while (pivot < n && mat[pivot][i] == 0) pivot++;
        if (pivot == n) return 0;
        
        if (pivot != i) {
            swap(mat[i], mat[pivot]);
            sign = -sign;
        }
        
        det = (det * mat[i][i]) % mod;
        int64 inv = mod_inverse(mat[i][i], mod);
        
        for (int j = i + 1; j < n; ++j) {
            int64 factor = (mat[j][i] * inv) % mod;
            for (int k = i; k < n; ++k) {
                mat[j][k] = (mat[j][k] - factor * mat[i][k]) % mod;
                if (mat[j][k] < 0) mat[j][k] += mod;
            }
        }
    }
    return (sign == -1) ? (mod - det) % mod : det % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, k;
    if (!(cin >> n >> k)) return 0;
    if (k == 1) k = 2;
    
    vector<vector<int>> weights(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> weights[i][j];
        }
    }
    
    // Exemple de configuration pour K=2
    int64 prime_mod = 1073741827; 
    int64 primitive_root = 2; 
    
    mt19937 rng(1337);
    vector<vector<int64>> rand_vars(n, vector<int64>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            rand_vars[i][j] = rng() % (prime_mod - 1) + 1;
        }
    }
    
    int64 total_ans = 0;
    int64 w_k = mod_pow(primitive_root, (prime_mod - 1) / k, prime_mod);
    
    for (int c = 0; c < k; ++c) {
        vector<vector<int64>> current_mat(n, vector<int64>(n, 0));
        int64 root_pow = mod_pow(w_k, c, prime_mod);
        
        vector<int64> powers(k, 1);
        for (int i = 1; i < k; ++i) powers[i] = (powers[i - 1] * root_pow) % prime_mod;
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (weights[i][j] != -1) {
                    int64 w = weights[i][j] % k;
                    current_mat[i][j] = (rand_vars[i][j] * powers[w]) % prime_mod;
                }
            }
        }
        total_ans = (total_ans + compute_determinant(current_mat, prime_mod)) % prime_mod;
    }
    
    cout << (total_ans != 0 ? "Yes" : "No") << "\n";
    return 0;
}

Arbre de Segments pour Opérations Bit à Bit

Énoncé du Problème

On doit maintenir une séquence \(a\) de longueur \(N\) soumise à trois types d'opérations :

• Appliquer un ET bit à bit (AND) avec \(x\) sur l'intervalle \([l, r]\).
• Appliquer un OU bit à bit (OR) avec \(x\) sur l'intervalle \([l, r]\).
• Retourner la valeur maximale sur l'intervalle \([l, r]\).

Les contraintes sont \(N \le 2 \times 10^5\) et \(0 \le x \le 2^{20}\).

Approche Algorithmique

Les opérations bit à bit sur des intervalles peuvent être optimisées en identifiant des classes d'équivalence. Si, pour un bit donné, tous les éléments d'un nœud de l'arbre de segments partagent la même valeur (tous à \(0\) ou tous à \(1\)), une opération AND ou OR affectera l'ensemble du sous-arbre de manière uniforme. Ce cmoportement peut être vérifié en comparant le résultat du AND global et du OR global du segment : si (val_and ^ val_or) == 0 pour un bit spécifique, ce bit est identique pour tous les éléments.

Lorsqu'une opération AND avec \(x\) est appliquée, les bits à \(0\) dans \(x\) forceront les bits correspondants de l'intervalle à \(0\). Si tous les bits correspondants dans le segment sont déjà identiques, on peut appliquer une mise à jour paresseuse (lazy propagation). La même logique s'applique pour l'opération OR.

L'analyse de complexité repose sur la méthode du potentiel. Soit \(\Phi\) le potentiel global défini par la somme des différences bit à bit sur tous les nœuds. Une modification d'intervalle augmente le potentiel d'au plus \(O(k \log N)\) (où \(k\) est le nombre de bits). Chaque descente dans l'arbre qui ne s'arrête pas grâce aux classes d'équivalence réduit strictement le potentiel. Ainsi, la complexité amortie totale sur \(Q\) requêtes est bornée par \(O((N + Q) k \log N)\).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct SegmentNode {
    unsigned int val_and;
    unsigned int val_or;
    unsigned int tag_and;
    unsigned int tag_or;
    unsigned int max_val;
    
    SegmentNode() {
        val_and = ~0u;
        val_or = 0;
        tag_and = ~0u;
        tag_or = 0;
        max_val = 0;
    }
    
    void apply_and(unsigned int mask) {
        val_and &= mask;
        val_or &= mask;
        tag_and &= mask;
        tag_or &= mask;
        max_val &= mask;
    }
    
    void apply_or(unsigned int mask) {
        val_and |= mask;
        val_or |= mask;
        tag_and |= mask;
        tag_or |= mask;
        max_val |= mask;
    }
    
    unsigned int uniform_bits() const {
        return ~(val_and ^ val_or);
    }
};

class BitwiseSegmentTree {
private:
    int n;
    vector<SegmentNode> tree;
    vector<unsigned int> data;
    
    void push_up(int node) {
        int left = 2 * node, right = 2 * node + 1;
        tree[node].val_and = tree[left].val_and & tree[right].val_and;
        tree[node].val_or = tree[left].val_or | tree[right].val_or;
        tree[node].max_val = max(tree[left].max_val, tree[right].max_val);
    }
    
    void push_down(int node) {
        int left = 2 * node, right = 2 * node + 1;
        
        tree[left].apply_and(tree[node].tag_and);
        tree[left].apply_or(tree[node].tag_or);
        
        tree[right].apply_and(tree[node].tag_and);
        tree[right].apply_or(tree[node].tag_or);
        
        tree[node].tag_and = ~0u;
        tree[node].tag_or = 0;
    }
    
    void build(int node, int start, int end) {
        if (start == end) {
            tree[node].val_and = tree[node].val_or = tree[node].max_val = data[start];
            return;
        }
        int mid = start + (end - start) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        push_up(node);
    }
    
    void update_and(int node, int start, int end, int l, int r, unsigned int mask) {
        if (l <= start && end <= r && (tree[node].uniform_bits() & ~mask) == ~mask) {
            tree[node].apply_and(mask);
            return;
        }
        push_down(node);
        int mid = start + (end - start) / 2;
        if (l <= mid) update_and(2 * node, start, mid, l, r, mask);
        if (r > mid) update_and(2 * node + 1, mid + 1, end, l, r, mask);
        push_up(node);
    }
    
    void update_or(int node, int start, int end, int l, int r, unsigned int mask) {
        if (l <= start && end <= r && (tree[node].uniform_bits() & mask) == mask) {
            tree[node].apply_or(mask);
            return;
        }
        push_down(node);
        int mid = start + (end - start) / 2;
        if (l <= mid) update_or(2 * node, start, mid, l, r, mask);
        if (r > mid) update_or(2 * node + 1, mid + 1, end, l, r, mask);
        push_up(node);
    }
    
    unsigned int query_max(int node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return tree[node].max_val;
        push_down(node);
        int mid = start + (end - start) / 2;
        unsigned int res = 0;
        if (l <= mid) res = max(res, query_max(2 * node, start, mid, l, r));
        if (r > mid) res = max(res, query_max(2 * node + 1, mid + 1, end, l, r));
        return res;
    }

public:
    BitwiseSegmentTree(const vector<unsigned int>& input) {
        n = input.size() - 1;
        data = input;
        tree.resize(4 * n + 1);
        build(1, 1, n);
    }
    
    void range_and(int l, int r, unsigned int mask) {
        update_and(1, 1, n, l, r, mask);
    }
    
    void range_or(int l, int r, unsigned int mask) {
        update_or(1, 1, n, l, r, mask);
    }
    
    unsigned int range_max(int l, int r) {
        return query_max(1, 1, n, l, r);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, q;
    if (!(cin >> n >> q)) return 0;
    
    vector<unsigned int> arr(n + 1);
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    
    BitwiseSegmentTree st(arr);
    
    for (int i = 0; i < q; ++i) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            unsigned int x;
            cin >> x;
            st.range_and(l, r, x);
        } else if (type == 2) {
            unsigned int x;
            cin >> x;
            st.range_or(l, r, x);
        } else if (type == 3) {
            cout << st.range_max(l, r) << "\n";
        }
    }
    
    return 0;
}