Problème T1 : Arbre couvrant minimum avec poids conditionnel

Énoncé : Soit un graphe G. On doit trouver un arbre couvrant minimum dont le poids est défini ainsi : si le poids maximal des arêtes w_max ≤ k, alors le poids est k - w_max ; sinon, le poids est la somme des |w_i - k| pour toutes les arêtes avec w_i ≥ k.

Analyse : Les cas spéciaux où toutes les arêtes sont ≤ k ou ≥ k sont simples. En combinant ces observations, on peut résoudre le problème général.

Solution : On utilise l'algorithme de Kruskal sur les arêtes avec poids ≤ k. Si le graphe devient connexe, on calcule k - w_max. Sinon, on ajoute les arêtes avec poids > k et on applique à nouveau Kruskal pour obtenir la somme des |w_i - k|. La complexité est O(m log m + m α(n)).

#include <bits/stdc++.h>
#define INF_VAL 0x3f3f3f3f
#define INF_LONG 0x3f3f3f3f3f3f3f3f
using namespace std;

int n, m;
long long threshold;

struct Edge {
    int u, v;
    long long weight;
    bool operator<(const Edge& other) const { return weight < other.weight; }
};
vector<Edge> low_edges, high_edges;

int parent[200010], size[200010];
void compress_path(int& x) { while (parent[x] != x) x = parent[x] = parent[parent[x]]; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> threshold;
    for (int i = 1; i <= n; i++) parent[i] = i, size[i] = 1;
    for (int i = 1; i <= m; i++) {
        int u, v; long long w;
        cin >> u >> v >> w;
        if (w <= threshold) low_edges.push_back({u, v, w});
        else high_edges.push_back({u, v, w});
    }

    int added = 0;
    long long max_low = -INF_LONG;
    for (auto& e : low_edges) {
        compress_path(e.u);
        compress_path(e.v);
        if (e.u != e.v) {
            if (size[e.u] > size[e.v]) swap(e.u, e.v);
            parent[e.u] = e.v;
            size[e.v] += size[e.u];
            added++;
        }
        max_low = max(max_low, e.weight);
    }

    sort(high_edges.begin(), high_edges.end());
    if (added == n - 1) {
        long long result = 0;
        if (high_edges.empty()) result = threshold - max_low;
        else result = min(threshold - max_low, high_edges[0].weight - threshold);
        cout << result << "\n";
    } else {
        long long result = 0;
        for (auto& e : high_edges) {
            compress_path(e.u);
            compress_path(e.v);
            if (e.u != e.v) {
                if (size[e.u] > size[e.v]) swap(e.u, e.v);
                parent[e.u] = e.v;
                size[e.v] += size[e.u];
                result += e.weight - threshold;
            }
        }
        cout << result << "\n";
    }

    return 0;
}

Problème T3 : Séquence à pic unique avec opérations de mise à jour

Énoncé : On maintient une séquence avec les opérations suivantes : ajouter une valeur à un intervalle ; vérifier si tous les éléments sont égaux ; vérifier si la séquence est strictement croissante ; vérifier si elle est strictement décroissante ; vérifier si elle forme un pic unique (c'est-à-dire croissante puis décroissante).

Sloution : On utilise une décomposition en blocs avec des étiquettes pour les propriétés locales, combinée à un arbre de segment pour les requêtes de maximum. Chaque bloc a des marques pour égalité, croissance ou décroissance. L'ajout de valeurs utilise un marqueur de paresse par bloc. Pour l'opération de pic unique, on localise le maximum dans l'intervalle et on vérifie les propriétés sur les sous-intervalles correspondants. La complexité est O(q log n + q √n).

#include <bits/stdc++.h>
#define INF_VAL 0x3f3f3f3f
#define INF_LONG 0x3f3f3f3f3f3f3f3f
using namespace std;

class SegmentTree {
private:
    struct Node {
        int left, right;
        pair<long long, int> max_val;
        long long lazy;
    } tree[400010];

public:
    void push_down(int idx) {
        if (!tree[idx].lazy) return;
        tree[idx << 1].lazy += tree[idx].lazy;
        tree[idx << 1 | 1].lazy += tree[idx].lazy;
        tree[idx << 1].max_val.first += tree[idx].lazy;
        tree[idx << 1 | 1].max_val.first += tree[idx].lazy;
        tree[idx].lazy = 0;
    }

    void push_up(int idx) {
        tree[idx].max_val = max(tree[idx << 1].max_val, tree[idx << 1 | 1].max_val);
    }

    void build(int l, int r, long long* arr, int idx = 1) {
        tree[idx] = {l, r, {-INF_LONG, 0}, 0};
        if (l == r) {
            tree[idx].max_val = {arr[l], l};
        } else {
            int mid = (l + r) >> 1;
            build(l, mid, arr, idx << 1);
            build(mid + 1, r, arr, idx << 1 | 1);
            push_up(idx);
        }
    }

    void update(int l, int r, long long val, int idx = 1) {
        if (l <= tree[idx].left && tree[idx].right <= r) {
            tree[idx].lazy += val;
            tree[idx].max_val.first += val;
        } else {
            push_down(idx);
            int mid = (tree[idx].left + tree[idx].right) >> 1;
            if (l <= mid) update(l, r, val, idx << 1);
            if (r > mid) update(l, r, val, idx << 1 | 1);
            push_up(idx);
        }
    }

    pair<long long, int> query(int l, int r, int idx = 1) {
        if (l <= tree[idx].left && tree[idx].right <= r) return tree[idx].max_val;
        push_down(idx);
        int mid = (tree[idx].left + tree[idx].right) >> 1;
        pair<long long, int> res = {-INF_LONG, 0};
        if (l <= mid) res = max(res, query(l, r, idx << 1));
        if (r > mid) res = max(res, query(l, r, idx << 1 | 1));
        return res;
    }
};

SegmentTree seg_tree;

int n, q;
long long arr[100010];

int block_size, block_id[100010], block_start[320];
long long block_lazy[320];
int block_type[320]; // 0: mixte, 1: croissant, 2: décroissant, 3: constant

void apply_lazy(int block) {
    if (!block_lazy[block]) return;
    for (int i = block_start[block]; i < block_start[block + 1]; i++) arr[i] += block_lazy[block];
    block_lazy[block] = 0;
}

void update_block(int block) {
    bool inc = true, dec = true, same = true;
    for (int i = block_start[block] + 1; i < block_start[block + 1]; i++) {
        inc &= (arr[i - 1] < arr[i]);
        dec &= (arr[i - 1] > arr[i]);
        same &= (arr[i - 1] == arr[i]);
    }
    if (inc) block_type[block] = 1;
    else if (dec) block_type[block] = 2;
    else if (same) block_type[block] = 3;
    else block_type[block] = 0;
}

void range_add(int l, int r, long long x) {
    int bl = block_id[l], br = block_id[r];
    if (bl == br) {
        for (int i = l; i <= r; i++) arr[i] += x;
        apply_lazy(bl);
        update_block(bl);
    } else {
        for (int i = l; i < block_start[bl + 1]; i++) arr[i] += x;
        for (int i = bl + 1; i < br; i++) block_lazy[i] += x;
        for (int i = block_start[br]; i <= r; i++) arr[i] += x;
        apply_lazy(bl);
        apply_lazy(br);
        update_block(bl);
        update_block(br);
    }
}

bool query_equal(int l, int r) {
    bool res = true;
    int bl = block_id[l], br = block_id[r];
    if (bl == br) {
        apply_lazy(bl);
        for (int i = l + 1; i <= r; i++) res &= (arr[i - 1] == arr[i]);
    } else {
        apply_lazy(bl);
        apply_lazy(br);
        long long val = arr[l];
        for (int i = l; i < block_start[bl + 1]; i++) res &= (arr[i] == val);
        for (int i = bl + 1; i < br; i++) res &= (block_type[i] == 3 && block_lazy[i] + arr[block_start[i]] == val);
        for (int i = block_start[br]; i <= r; i++) res &= (arr[i] == val);
    }
    return res;
}

bool query_increasing(int l, int r) {
    bool res = true;
    int bl = block_id[l], br = block_id[r];
    if (bl == br) {
        apply_lazy(bl);
        for (int i = l + 1; i <= r; i++) res &= (arr[i - 1] < arr[i]);
    } else {
        apply_lazy(bl);
        apply_lazy(br);
        for (int i = l + 1; i < block_start[bl + 1]; i++) res &= (arr[i - 1] < arr[i]);
        for (int i = bl + 1; i < br; i++) res &= (block_type[i] == 1 && block_lazy[i - 1] + arr[block_start[i] - 1] < block_lazy[i] + arr[block_start[i]]);
        res &= (block_lazy[br - 1] + arr[block_start[br] - 1] < arr[block_start[br]]);
        for (int i = block_start[br] + 1; i <= r; i++) res &= (arr[i - 1] < arr[i]);
    }
    return res;
}

bool query_decreasing(int l, int r) {
    bool res = true;
    int bl = block_id[l], br = block_id[r];
    if (bl == br) {
        apply_lazy(bl);
        for (int i = l + 1; i <= r; i++) res &= (arr[i - 1] > arr[i]);
    } else {
        apply_lazy(bl);
        apply_lazy(br);
        for (int i = l + 1; i < block_start[bl + 1]; i++) res &= (arr[i - 1] > arr[i]);
        for (int i = bl + 1; i < br; i++) res &= (block_type[i] == 2 && block_lazy[i - 1] + arr[block_start[i] - 1] > block_lazy[i] + arr[block_start[i]]);
        res &= (block_lazy[br - 1] + arr[block_start[br] - 1] > arr[block_start[br]]);
        for (int i = block_start[br] + 1; i <= r; i++) res &= (arr[i - 1] > arr[i]);
    }
    return res;
}

bool query_peak(int l, int r) {
    auto max_pair = seg_tree.query(l, r);
    int pos = max_pair.second;
    if (pos == l || pos == r) return false;
    return query_increasing(l, pos) && query_decreasing(pos, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    block_size = max((int)sqrt(n), 1);
    for (int i = 1; i <= n; i++) {
        block_id[i] = (i - 1) / block_size + 1;
        if (!block_start[block_id[i]]) block_start[block_id[i]] = i;
    }
    block_start[block_id[n] + 1] = n + 1;

    for (int i = 1; i <= block_id[n]; i++) {
        update_block(i);
    }

    seg_tree.build(1, n, arr);

    cin >> q;
    while (q--) {
        int op, l, r; cin >> op >> l >> r;
        if (op == 1) {
            long long x; cin >> x;
            range_add(l, r, x);
            seg_tree.update(l, r, x);
        } else if (op == 2) {
            cout << query_equal(l, r) << "\n";
        } else if (op == 3) {
            cout << query_increasing(l, r) << "\n";
        } else if (op == 4) {
            cout << query_decreasing(l, r) << "\n";
        } else if (op == 5) {
            cout << query_peak(l, r) << "\n";
        }
    }

    return 0;
}