Gestion des Cycles de Trafic et Arbre de Segment

Pour déterminer le temps minimal requis pour atteindre l'école depuis chaque intersection, le traitement doit s'effectuer en ordre inverse, du nœud final vers la source. L'état des feux de signalisation étant périodique, le temps d'arrivée à un point donné peut être réduit modulo $T$, où $T$ représente la somme des durées de phase verte et rouge. Cette propriété permet de mapper chaque position temporelle sur un cercle de taille fixe. L'interrogation du prochain feu vert disponible se ramène à une recherche de minimum dans un intervalle circulaire. Un arbre de segment implicite ou dynamique permet de maintenir les indices des intersections et d'extraire efficacement le prochain nœud atteignable en $O(\log T)$.

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

constexpr int MAX_N = 50005;
constexpr int MAX_TREE = MAX_N * 80;

ll node_count, total_intersections, green_time, red_time, cycle, query_cnt;
ll edge_dist[MAX_N], prefix_sum[MAX_N], dp[MAX_N];

struct SegTree {
    ll root = 1, ptr = 0;
    ll mn[MAX_TREE], lch[MAX_TREE], rch[MAX_TREE];

    void pull(ll idx) {
        mn[idx] = node_count + 1;
        if (lch[idx]) mn[idx] = min(mn[idx], mn[lch[idx]]);
        if (rch[idx]) mn[idx] = min(mn[idx], mn[rch[idx]]);
    }

    void modify(ll &idx, int L, int R, int pos, int val) {
        if (!idx) idx = ++ptr;
        if (L == R) { mn[idx] = val; return; }
        int mid = (L + R) >> 1;
        pos <= mid ? modify(lch[idx], L, mid, pos, val)
                   : modify(rch[idx], mid + 1, R, pos, val);
        pull(idx);
    }

    int range_min(int idx, int L, int R, int qL, int qR) {
        if (qL > qR || !idx) return node_count + 1;
        if (qL <= L && R <= qR) return mn[idx];
        int mid = (L + R) >> 1, res = node_count + 1;
        if (qL <= mid) res = min(res, range_min(lch[idx], L, mid, qL, qR));
        if (qR > mid) res = min(res, range_min(rch[idx], mid + 1, R, qL, qR));
        return res;
    }
} seg;

int find_next_green(int t_mod) {
    int start = (t_mod + green_time) % cycle;
    int end = (t_mod + green_time + red_time - 1) % cycle;
    if (start <= end) return seg.range_min(1, 0, cycle - 1, start, end);
    return min(seg.range_min(1, 0, cycle - 1, start, cycle - 1),
               seg.range_min(1, 0, cycle - 1, 0, end));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> node_count >> green_time >> red_time >> query_cnt;
    cycle = green_time + red_time;
    for (int i = 1; i <= node_count + 1; ++i) {
        cin >> edge_dist[i];
        prefix_sum[i] = prefix_sum[i - 1] + edge_dist[i];
    }
    for (int i = node_count; i >= 1; --i) {
        int target = find_next_green(prefix_sum[i] % cycle);
        dp[i] = dp[target] + (prefix_sum[target] - prefix_sum[i]);
        if (target != node_count + 1) {
            dp[i] += cycle - (prefix_sum[target] - prefix_sum[i]) % cycle;
        }
        seg.modify(seg.root, 0, cycle - 1, prefix_sum[i] % cycle, i);
    }
    while (query_cnt--) {
        ll t; cin >> t;
        int target = find_next_green((cycle - t % cycle) % cycle);
        ll ans = dp[target] + prefix_sum[target] + t;
        if (target != node_count + 1) {
            ans += cycle - (prefix_sum[target] + t) % cycle;
        }
        cout << ans << "\n";
    }
    return 0;
}

Programmation Dynamique sur Arbre avec Accélération par Bitset

Lorsque les contraintes de validité dépendent de l'alignement de sous-chaînes sur une structure arborescente, la programmation dynamique classique atteint rapidement des limites de complexité. En concaténant les séquences avec un caractère séparateur unique, on peut représenter les états valides via des masques binaires. Les transitions se traduisent par des décalages à gauche ou à droite du bitset, tandis que les fusions d'états utilisent des opérations logiques AND. Cette approche réduit la complexité d'un facteur égal à la taille du mot processeur, transformant une approche quadratique en une solution viable pour des entrées de grande taille.

#include <iostream>
#include <vector>
#include <bitset>
#include <string>
using namespace std;

constexpr int MAX_V = 30005;

struct Edge { int to; int weight; };
vector<Edge> adj[MAX_V];
bitset<MAX_V * 2> up[MAX_V], down[MAX_V], valid_pos, char_mask[27];
vector<string> inputs;
string merged_str;
int parent[MAX_V], dfs_order[MAX_V], timer, n, m;
bool visited[MAX_V];

void dfs_build(int u) {
    visited[u] = true;
    dfs_order[++timer] = u;
    for (auto &e : adj[u]) {
        if (e.to != parent[u]) {
            parent[e.to] = u;
            dfs_build(e.to);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; char w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w - 'a'});
        adj[v].push_back({u, w - 'a'});
    }
    cin >> m;
    inputs.resize(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> inputs[i];
        merged_str += char('z' + 1) + inputs[i];
    }
    merged_str += char('z' + 1);
    int len = merged_str.size();
    for (int i = len - 1; i >= 0; --i) {
        char_mask[merged_str[i] - 'a'].set(i);
    }
    valid_pos = char_mask[26];
    dfs_build(1);

    for (int i = n; i >= 1; --i) {
        int u = dfs_order[i];
        up[u] = down[u] = valid_pos;
        for (auto &e : adj[u]) {
            int v = e.to;
            if (v == parent[u]) continue;
            int c = e.weight;
            up[v] = (up[v] << 1) & char_mask[c];
            down[v] = (down[v] >> 1) & char_mask[c];
            valid_pos |= (up[u] << 1) & down[v];
            valid_pos |= down[u] & (up[v] << 1);
            up[u] |= up[v];
            down[u] |= down[v];
        }
    }
    int pos = 1;
    for (int i = 1; i <= m; ++i) {
        bool found = false;
        for (int j = 0; j <= (int)inputs[i].size(); ++j) {
            if (valid_pos.test(pos + j)) { found = true; break; }
        }
        cout << (found ? "YES" : "NO") << "\n";
        pos += inputs[i].size() + 1;
    }
    return 0;
}

Partition de Séquence et Calcul de MEX par Arbre de Segment

La relation de récurrence impliquant la fonction MEX sur les sous-intervalles peut être réorganisée pour calculer les contributions en ordre décroissant. Au lieu de sommer les valeurs depuis le début de la séquence, on propage les effets vers l'arrière. Cette inversion permet de fixer l'extrémité gauche des intervalles et d'utiliser un arbre de segment équipé de trois types de balises paresseuses : addition, multiplication et affectation directe. La structure maintient simultanément les valeurs MEX locales et les sommes partielles de la fonction DP. Une alternative viable repose sur la technique de division et conquête CDQ, qui partitionne les dépendances temporelles pour résoudre les contributions hors diagonale.

Tri Topologique sur Graphe de Non-Coprimalité

Lorsque deux éléments adjacents peuvent être échangés s'ils sont premiers entre eux, la contrainte inverse s'applique : si deux nombres partagent un facteur commun, leur ordre relatif est figé. En construisant un graphe non orienté reliant les paires non premières entre elles, on identifie les composantes de dépendance. Le problème se transforme alors en orientation des arêtes pour former un graphe orienté acyclique (DAG). Une exploration en profondeur (DFS) appliquée de manière gloutonne, traitant les nœuds par ordre croissant de valeur, permet d'établir une orientation cohérente. La séquence finale s'obtient par extraction prioritaire en ordre décroissant, simulant un parcours topologique inversé.

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
using namespace std;
using ll = long long;

const int MAX_N = 2005;

vector<int> undirected[MAX_N], directed[MAX_N];
priority_queue<pair<int, int>> pq;
int arr[MAX_N];
bool processed[MAX_N];

void orient_edges(int u) {
    processed[u] = true;
    for (int v : undirected[u]) {
        if (!processed[v]) {
            directed[u].push_back(v);
            orient_edges(v);
        }
    }
}

int gcd_calc(int a, int b) {
    while (b) { int t = a % b; a = b; b = t; }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (gcd_calc(arr[i], arr[j]) != 1) {
                undirected[i].push_back(j);
                undirected[j].push_back(i);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!processed[i]) {
            orient_edges(i);
            pq.push({arr[i], i});
        }
    }
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        cout << arr[u] << " ";
        for (int v : directed[u]) {
            pq.push({arr[v], v});
        }
    }
    cout << "\n";
    return 0;
}

Invariants de Sous-arbres et Propagation Conditionnelle

Dans une structure arborescente partitionnée en composantes connexes bicolores, chaque groupe peut être représenté par son nœud racine de profondeur minimale. Tous les membres d'une même composante résident nécessairement dans le sous-arbre de ce représentant. Une propriété fondamentale émerge : le nombre de changements de couleur le long du chemin reliant tout nœud d'une composante à la racine globale reste constant. Pour maintenir ces invariants lors de modifications dynamiques, un arbre de segment parcourant la topologie peut conserver les comptes de couleurs par chemin. Lors de la descente des marqueurs paresseux, la propagation est restreinte aux fils dont les compteurs de couleurs alternées correspondent, garantissant ainsi la cohérence structurelle sans recalcul complet. Cette méthode s'apparente à une décomposition lourde-légère implicite, où les intervalles de l'arbre de segment acquièrent une sémantique topologique précise.