L'Atelier Monstre

Introduction à l'Arbre Cartésien L'arbre cartésien est une structure de données arborescente binaire dérivée d'une séquence de nombres. Il est particulièrement utile pour résoudre des problèmes tels que les requêtes de minimum/maximum sur un intervalle (RMQ) et les requêtes de type "top-k". Introduit par Jean Vuillemin en 1980 pour ré ...

L'objectif est de compter le nombre d'inversions dans une séquence d'entiers. Une inversion est une paire d'indices (i, j) telle que i < j et arr[i] > arr[j]. Nous allons explorer deux approches principales, toutes deux offrant une complexité temporelle de O(log n) après prétraitement. Approche par Division et Fusion (Merge Sort) Cette mé ...

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}^ ...