Cet article explore la résolution de trois problèmes de programmation compétitive, chacun nécessitant des algorithmes et des structures de données avancées. Nous aborderons la manipulation de bases linéaires pour les sommes XOR, la programmation dynamique sur des arbres et l'utilisation de balayages et de structures de données pour des problèmes de géométrie computationnelle impliquant des rectangles.

Problème 1 : Sommes XOR et Multiples de LCM

Le premier problème concerne le comptage de sous-ensembles d'un ensemble de nombres entiers tels que la somme XOR des éléments du sous-ensemble soit un multiple de leur plus petit commun multiple (PPCM). Une observation clé est que si la somme XOR \(X\) d'un sous-ensemble est un multiple du PPCM \(L\) de ses éléments, alors soit \(X = 0\), soit les nombres ont une structure très spécifique (par exemple, si \(X \ne 0\), alors \(X \ge L\), ce qui est rarement possible puisque \(X\) a généralement moins de bits que \(L\)). Le problème se simplifie souvent à compter les sous-ensembles dont la somme XOR est nulle, ou des cas particuliers liés aux relations de divisibilité.

La solution utilise une base linéaire pour gérer les sommes XOR. Une base linéaire permet de déterminer si un nombre peut être formé par un sous-ensemble via XOR, ou de trouver la dimension de l'espace vectoriel XOR des nombres. Le nombre de sous-ensembles dont la somme XOR est 0 à partir d'un ensemble de \(N\) nombres, où \(k\) nombres n'ont pas pu être insérés dans la base linéaire (car ils sont linéairement dépendants), est \(2^k - 1\) (en excluant l'ensemble vide).

Le code met en œuvre cette idée avec une approche combinatoire et basée sur la théorie des nombres. Il calcule d'abord le nombre de sous-ensembles dont la somme XOR est 0 parmi tous les nombres donnés. Ensuite, il ajoute des contributions pour des cas spécifiques où la relation de multiplicité avec le PPCM est satisfaite, souvent liée aux diviseurs des nombres. La structure bases[k] semble stocker une base linéaire de diviseurs de k pertinents, tandis que bases[0] est pour tous les nombres.

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

#define int long long
using namespace std;

const int MOD = 998244353; // Module pour les opérations modulaires

// Fonction pour lire un entier rapidement
inline char getChar() {
    static char buf[1000005], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000005, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readInt() {
    int value = 0;
    char c = getChar();
    while (c < '0' || c > '9') c = getChar();
    while ('0' <= c && c <= '9') value = value * 10 + c - 48, c = getChar();
    return value;
}

int numElements;
int inputValues[1000005]; // Valeurs d'entrée
int counts[1000005]; // Fréquence de chaque nombre d'entrée

// Structure pour une base linéaire XOR
struct XORLinearBasis {
    int basisVectors[20]; // Vecteurs de base, max 20 bits pour des nombres < 2^20
    int freeElementsCount; // Compte des éléments qui n'ont pas pu être insérés (dépendants)

    XORLinearBasis() : freeElementsCount(0) {
        for (int i = 0; i < 20; ++i) basisVectors[i] = 0;
    }

    // Insérer un nombre dans la base
    void insert(int x) {
        for (int i = 19; ~i; --i) { // Itérer des bits les plus significatifs aux moins significatifs
            if (!(x & (1 << i))) continue; // Si le i-ème bit est 0, continuer
            if (basisVectors[i]) {
                x ^= basisVectors[i]; // XOR avec le vecteur de base existant
            } else {
                basisVectors[i] = x; // Insérer comme nouveau vecteur de base
                return;
            }
        }
        ++freeElementsCount; // Le nombre est linéairement dépendant
    }
};

XORLinearBasis basisPerFactor[1000005]; // Bases linéaires pour les facteurs/multiples

// Exponentiation modulaire (x^y mod P)
int power(int base, int exp) {
    int res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

// Factorielles et inverses modulaires pour les combinaisons
int factorials[1000005], invFactorials[1000005], inverses[1000005];

void precomputeCombinations(int n_max) {
    factorials[0] = 1;
    invFactorials[0] = 1;
    inverses[1] = 1;
    for (int i = 1; i <= n_max; ++i) {
        factorials[i] = (factorials[i - 1] * i) % MOD;
        if (i > 1) inverses[i] = (MOD - (MOD / i) * inverses[MOD % i] % MOD) % MOD;
        invFactorials[i] = (invFactorials[i - 1] * inverses[i]) % MOD;
    }
}

// Calcul des combinaisons C(n, m)
int combinations(int n, int m) {
    if (m < 0 || m > n) return 0;
    return (((factorials[n] * invFactorials[m]) % MOD) * invFactorials[n - m]) % MOD;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("xor.in", "r", stdin); // Décommenter pour les fichiers d'entrée/sortie
    // freopen("xor.out", "w", stdout);

    cin >> numElements;
    int maxVal = 0;
    for (int i = 1; i <= numElements; ++i) {
        cin >> inputValues[i];
        counts[inputValues[i]]++;
        basisPerFactor[0].insert(inputValues[i]); // Base linéaire pour tous les nombres
        maxVal = max(maxVal, inputValues[i]);
    }

    precomputeCombinations(numElements);

    // Initialiser la réponse avec les sous-ensembles dont la somme XOR est 0 (pour tous les nombres)
    int totalAnswer = power(2, basisPerFactor[0].freeElementsCount);

    // Construire les bases linéaires pour les diviseurs
    // basisPerFactor[k] contiendra une base des diviseurs de k qui sont présents dans l'entrée
    for (int i = 1; i <= maxVal; ++i) {
        if (counts[i] == 0) continue; // Si le nombre i n'est pas dans l'entrée, passez
        for (int j = 1; i * j <= maxVal; ++j) {
            if (counts[i * j] > 0) { // Si i*j est un nombre d'entrée
                // Insérer i (un diviseur) dans la base de i*j
                // Ceci est une interprétation spécifique du problème et de son lien avec les facteurs/multiples
                for (int k_idx = 0; k_idx < counts[i]; ++k_idx) { // Insérer i 'counts[i]' fois
                     basisPerFactor[i * j].insert(i);
                }
            }
        }
    }

    // Ajouter des contributions pour les cas où un nombre i est un multiple, et d'autres conditions spécifiques
    // C'est la partie qui gère "un nombre est un multiple de tous les autres, et les autres XOR à 0"
    for (int i = 1; i <= maxVal; ++i) {
        if (counts[i] > 0) { // Si le nombre i est présent dans l'entrée
            for (int j = 1; j <= counts[i]; j += 2) { // Choisir un nombre impair de 'i'
                // Contribution = C(counts[i], j) * 2^(éléments libres dans la base de 'i')
                totalAnswer = (totalAnswer + (combinations(counts[i], j) * power(2, basisPerFactor[i].freeElementsCount)) % MOD) % MOD;
            }
        }
    }
    
    // Soustraire 1 pour enlever l'ensemble vide si il a été inclus
    totalAnswer = (totalAnswer + MOD - 1) % MOD;

    cout << totalAnswer << "\n";

    return 0;
}

Problème 2 : DP sur Arbres pour Blocs Connectés

Le deuxième problème est une programmation dynamique (DP) sur un arbre pour trouver le nombre maximum de blocs connectés, avec des contraintes sur la parité et la valeur de la somme des éléments dans le bloc. À partir des feuilles, la DP monte vers la racine. Pour chaque nœud, nous devons décider s'il fait partie du bloc connecté le plus élevé, ou s'il commence un nouveau bloc.

L'état de la DP pour un nœud \(x\) est un pair<int, int>: (nombre_max_de_blocs, somme_du_bloc_le_plus_haut). Nous maintenons deux de ces paires pour chaque nœud : une pour une somme de bloc paire et une pour une somme de bloc impaire.

dpState[x][0] : (max blocs dans le sous-arbre de \(x\), somme du bloc supérieur, dont la somme est paire) dpState[x][1] : (max blocs dans le sous-arbre de \(x\), somme du bloc supérieur, dont la somme est impaire)

La transition combine les résultats des enfants. Pour chaque enfant \(v\), nous avons deux choix: soit connecter le bloc supérieur de \(v\) à \(x\), soit "couper" le bloc supérieur de \(v\) (ce qui ajoute max(f[v][0].first, f[v][1].first) blocs) et commencer un nouveau bloc à \(x\). Si la somme du bloc supérieur d'un nœud atteint ou dépasse \(k\) et a la parité souhaitée, un nouveau bloc est formé (le compteur de blocs augmente de 1, la somme du bloc supérieur est réinitialisée à 0).

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

#define int long long
using namespace std;

const int INF = 2e18; // Utiliser une grande valeur pour l'infini (pour des sommes)
const int NEG_INF = -INF; // Utiliser une grande valeur négative pour l'infini

int numNodes, targetValueK;
vector<int> adjList[1000005]; // Liste d'adjacence pour l'arbre
int nodeValues[1000005]; // Valeurs associées à chaque nœud

// dpState[node][parity] stocke {max_blocks, top_block_sum}
pair<int, int> dpState[1000005][2];

// Surcharge de l'opérateur + pour combiner les paires (sommes et blocs)
pair<int, int> operator+(pair<int, int> p1, pair<int, int> p2) {
    return {p1.first + p2.first, p1.second + p2.second};
}

// Fonction de parcours en profondeur (DFS) pour la DP sur arbre
void treeDFS(int currentNode, int parentNode) {
    // Premièrement, récurrence sur les enfants
    for (int neighbor : adjList[currentNode]) {
        if (neighbor != parentNode) {
            treeDFS(neighbor, currentNode);
        }
    }

    // Initialiser les états temporaires pour le nœud courant
    // tmpState[parity] stocke {max_blocks, top_block_sum} en considérant uniquement le nœud courant
    pair<int, int> tmpState[2];
    tmpState[0] = {NEG_INF, NEG_INF};
    tmpState[1] = {NEG_INF, NEG_INF};
    
    // Le nœud courant forme son propre bloc initial
    tmpState[nodeValues[currentNode] & 1] = {0, nodeValues[currentNode]};

    int blocksFromDisconnectedChildren = 0; // Somme des blocs maximaux des sous-arbres des enfants qui ne sont pas connectés à currentNode

    // Fusionner les résultats des enfants
    for (int neighbor : adjList[currentNode]) {
        if (neighbor == parentNode) continue;

        // blocksFromDisconnectedChildren accumule les blocs maximaux des enfants
        // si leur bloc supérieur n'est pas connecté à currentNode
        blocksFromDisconnectedChildren += max(dpState[neighbor][0].first, dpState[neighbor][1].first);

        // Cloner les états temporaires pour les nouvelles combinaisons
        pair<int, int> currentTmp0 = tmpState[0];
        pair<int, int> currentTmp1 = tmpState[1];

        // Mettre à jour tmpState[0] (somme paire)
        // Option 1: fusionner avec un enfant pair
        tmpState[0] = max(tmpState[0], currentTmp0 + dpState[neighbor][0]);
        // Option 2: fusionner avec un enfant impair
        tmpState[0] = max(tmpState[0], currentTmp1 + dpState[neighbor][1]);

        // Mettre à jour tmpState[1] (somme impaire)
        // Option 1: fusionner avec un enfant pair
        tmpState[1] = max(tmpState[1], currentTmp0 + dpState[neighbor][1]);
        // Option 2: fusionner avec un enfant impair
        tmpState[1] = max(tmpState[1], currentTmp1 + dpState[neighbor][0]);
    }

    // Option de ne pas connecter le nœud courant aux blocs supérieurs de ses enfants
    // Dans ce cas, les enfants contribuent seulement par leur nombre maximal de blocs
    // et la somme du bloc supérieur de currentNode est 0
    tmpState[0] = max(tmpState[0], {blocksFromDisconnectedChildren, 0LL});

    // Appliquer les règles de "coupe" pour former de nouveaux blocs si possible
    for (int parity = 0; parity < 2; ++parity) {
        dpState[currentNode][parity] = max(dpState[currentNode][parity], tmpState[parity]);

        // Si la somme du bloc supérieur atteint targetValueK et a la parité requise
        if ((parity == (targetValueK & 1)) && tmpState[parity].second >= targetValueK) {
            // Un nouveau bloc est formé: +1 au compte de blocs, somme du bloc supérieur réinitialisée à 0
            dpState[currentNode][0] = max(dpState[currentNode][0], {tmpState[parity].first + 1, 0LL});
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("linkcut.in", "r", stdin); // Décommenter pour les fichiers d'entrée/sortie
    // freopen("linkcut.out", "w", stdout);

    int testCases;
    cin >> testCases;
    while (testCases--) {
        cin >> numNodes >> targetValueK;

        // Réinitialiser les listes d'adjacence et les valeurs des nœuds
        for (int i = 1; i <= numNodes; ++i) {
            adjList[i].clear();
            cin >> nodeValues[i];
        }

        // Lire les arêtes et construire la liste d'adjacence
        for (int i = 1; i < numNodes; ++i) {
            int u, v;
            cin >> u >> v;
            adjList[u].push_back(v);
            adjList[v].push_back(u);
        }

        treeDFS(1, 0); // Lancer la DFS à partir du nœud 1 (arbitrairement choisi comme racine)

        // La réponse est le maximum des blocs formés, qu'ils soient de parité 0 ou 1
        cout << max(dpState[1][0].first, dpState[1][1].first) << "\n";
    }
    return 0;
}

Problème 3 : Comptage de Triples de Rectangles Non-chevauchants

Le troisième problème consiste à compter les triples de rectangles \((R_i, R_j, R_k)\) où les trois rectangles sont deux à deux non-chevauchants. La solution utilise le principe d'inclusion-exclusion, une compression de coordonnées, un balayage, un arbre de Fenwick (BIT) et un arbre de segments.

Le nombre total de triples est \(N(N-1)(N-2)/6\). Nous soustrayons ensuite les triples où au moins une paire chevauche. La stratégie est d'utiliser la formule : \(N_{non_chevauchant} = N_{total} - N_{au_moins_1_chevauchement}\)

Cependant, il est souvent plus facile de calculer les cas spécifiques de chevauchement: \(N_{total} - N_{exactement_1_chevauchement} - N_{exactement_2_chevauchements} - N_{exactement_3_chevauchements}\) Le problème simplifie cela à \(N_{total} - ans1 - ans2\), où ans1 représente les triples avec un certain type de chevauchement (souvent liés à un seul rectangle chevauchant un autre, et non pas le troisième), et ans2 représente les triples où tous les trois rectangles se chevauchent mutuellement. Le fait que N_2 (exactemetn 2 chevauchements) ne soit pas explicitement soustrait ou soit inclus dans ans1 est une subtilité de l'énoncé ou de l'analyse du problème.

1. Compression de Coordonnées: Les coordonnées des rectangles sont compressées pour réduire l'espace et les rendre contiguës.
2. Calcul de nonOverlapCount[i]: Pour chaque rectangle \(R_i\), on calcule nonOverlapCount[i], le nombre de rectangles \(R_j\) qui ne le chevauchent pas. Cela se fait en comptant les rectangles entièrement à gauche, à droite, en dessous ou au-dessus de \(R_i\), en utilisant des balayages et un arbre de Fenwick. Des corrections sont appliquées pour les rectangles dans les "coins" (par exemple, à la fois à gauche et en dessous).
3. Calcul de ans1: Le terme ans1 est calculé comme \(\frac{1}{2} \sum_{i=1}^N \text{nonOverlapCount}[i] \times (N - 1 - \text{nonOverlapCount}[i])\). Ce terme compte des triples \((R_j, R_i, R_k)\) où \(R_j\) ne chevauche pas \(R_i\), et \(R_k\) chevauche \(R_i\). Selon le contexte précis du problème, ceci peut correspondre au nombre de triples avec exactement un chevauchement, ou une somme pondérée.
4. Calcul de ans2 (Triples de chevauchement total): Un balayage est effectué sur les coordonnées x. Pour chaque position x, les rectangles dont la plage x inclut cette position sont considérés. Un arbre de segments est utilisé pour maintenir des informations sur les intervalles y des rectangles "actifs". L'arbre de segments compte les paires d'intervalles y qui se chevauchent ou non. À chaque étape du balayage, lorsque \(R_i\) commence, on compte les paires \((R_j, R_k)\) parmi les rectangles actifs (ceux qui chevauchent \(R_i\) horizontalement et verticalement) qui se chevauchent mutuellement (verticalement). Cela permet de compter les triples \((R_i, R_j, R_k)\) où les trois se chevauchent.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>

#define int long long
#define LOWBIT(x) ((x) & (-(x))) // Macro pour Fenwick Tree

using namespace std;

int numRectangles;

struct Rectangle {
    int x1, x2, y1, y2;
    int nonOverlapCount; // Nombre de rectangles ne chevauchant pas ce rectangle
} rectangles[2000005];

// Structure pour Fenwick Tree (BIT)
struct FenwickTree {
    int treeData[4000005]; // Tableau pour le Fenwick Tree

    void update(int index, int value) {
        for (; index <= 4000000; index += LOWBIT(index)) {
            treeData[index] += value;
        }
    }

    int querySum(int index) {
        int sum = 0;
        for (; index > 0; index -= LOWBIT(index)) {
            sum += treeData[index];
        }
        return sum;
    }

    void clear() {
        memset(treeData, 0, sizeof(treeData)); // Réinitialiser le tableau
    }
} bit, bit2; // Deux instances de Fenwick Tree

// Mappages pour la compression des coordonnées
map<int, int> coordMap[2];
int uniqueCoords[2][2000005]; // Stocke les coordonnées uniques pour la compression

// Vecteurs pour stocker les indices de rectangles par coordonnées (pour le balayage)
vector<int> rectsByStartX[4000005], rectsByEndX[4000005];
vector<int> rectsByStartY[4000005], rectsByEndY[4000005];

// Nœud de l'arbre de segments
struct SegmentTreeNode {
    int leftCount;  // Nombre d'intervalles commençant dans cette plage
    int rightCount; // Nombre d'intervalles finissant dans cette plage
    int nonOverlapPairs; // Nombre de paires d'intervalles qui ne se chevauchent pas
} segmentTreeNodes[4000005];

// Opérateur pour fusionner les nœuds de l'arbre de segments
SegmentTreeNode operator+(SegmentTreeNode nodeA, SegmentTreeNode nodeB) {
    SegmentTreeNode result;
    result.leftCount = nodeA.leftCount + nodeB.leftCount;
    result.rightCount = nodeA.rightCount + nodeB.rightCount;
    // La valeur nonOverlapPairs représente la somme (count_right_left * count_left_right)
    // C'est le nombre de paires où un intervalle finit avant qu'un autre ne commence
    result.nonOverlapPairs = nodeA.nonOverlapPairs + nodeB.nonOverlapPairs + nodeA.rightCount * nodeB.leftCount;
    return result;
}

// Structure pour l'arbre de segments
struct SegmentTree {
    // Ajouter un "démarrage d'intervalle" (coordonnée gauche)
    void updateLeftCoord(int nodeIdx, int start, int end, int targetCoord, int value) {
        if (start == end) {
            segmentTreeNodes[nodeIdx].leftCount += value;
            return;
        }
        int mid = (start + end) >> 1;
        if (targetCoord <= mid) {
            updateLeftCoord(nodeIdx << 1, start, mid, targetCoord, value);
        } else {
            updateLeftCoord(nodeIdx << 1 | 1, mid + 1, end, targetCoord, value);
        }
        segmentTreeNodes[nodeIdx] = segmentTreeNodes[nodeIdx << 1] + segmentTreeNodes[nodeIdx << 1 | 1];
    }

    // Ajouter une "fin d'intervalle" (coordonnée droite)
    void updateRightCoord(int nodeIdx, int start, int end, int targetCoord, int value) {
        if (start == end) {
            segmentTreeNodes[nodeIdx].rightCount += value;
            return;
        }
        int mid = (start + end) >> 1;
        if (targetCoord <= mid) {
            updateRightCoord(nodeIdx << 1, start, mid, targetCoord, value);
        } else {
            updateRightCoord(nodeIdx << 1 | 1, mid + 1, end, targetCoord, value);
        }
        segmentTreeNodes[nodeIdx] = segmentTreeNodes[nodeIdx << 1] + segmentTreeNodes[nodeIdx << 1 | 1];
    }

    // Interroger la somme de paires non-chevauchantes dans une plage d'intervalles
    SegmentTreeNode queryIntervals(int nodeIdx, int start, int end, int queryL, int queryR) {
        if (queryL <= start && end <= queryR) {
            return segmentTreeNodes[nodeIdx];
        }
        int mid = (start + end) >> 1;
        if (queryR <= mid) {
            return queryIntervals(nodeIdx << 1, start, mid, queryL, queryR);
        }
        if (queryL > mid) {
            return queryIntervals(nodeIdx << 1 | 1, mid + 1, end, queryL, queryR);
        }
        return queryIntervals(nodeIdx << 1, start, mid, queryL, mid) + queryIntervals(nodeIdx << 1 | 1, mid + 1, end, mid + 1, queryR);
    }
} segTree;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("rect.in", "r", stdin); // Décommenter pour les fichiers d'entrée/sortie
    // freopen("rect.out", "w", stdout);

    cin >> numRectangles;

    // Lecture des rectangles et collecte des coordonnées uniques
    for (int i = 1; i <= numRectangles; ++i) {
        cin >> rectangles[i].x1 >> rectangles[i].x2 >> rectangles[i].y1 >> rectangles[i].y2;
        uniqueCoords[0][++uniqueCoords[0][0]] = rectangles[i].x1;
        uniqueCoords[0][++uniqueCoords[0][0]] = rectangles[i].x2;
        uniqueCoords[1][++uniqueCoords[1][0]] = rectangles[i].y1;
        uniqueCoords[1][++uniqueCoords[1][0]] = rectangles[i].y2;
    }

    // Compression des coordonnées X et Y
    sort(uniqueCoords[0] + 1, uniqueCoords[0] + uniqueCoords[0][0] + 1);
    sort(uniqueCoords[1] + 1, uniqueCoords[1] + uniqueCoords[1][0] + 1);

    for (int i = 1; i <= numRectangles * 2; ++i) {
        coordMap[0][uniqueCoords[0][i]] = (coordMap[0][uniqueCoords[0][i - 1]] + (uniqueCoords[0][i] != uniqueCoords[0][i - 1]));
        coordMap[1][uniqueCoords[1][i]] = (coordMap[1][uniqueCoords[1][i - 1]] + (uniqueCoords[1][i] != uniqueCoords[1][i - 1]));
    }

    int compressedMaxX = coordMap[0][uniqueCoords[0][numRectangles * 2]];
    int compressedMaxY = coordMap[1][uniqueCoords[1][numRectangles * 2]];

    // Mettre à jour les coordonnées compressées et organiser les rectangles pour le balayage
    for (int i = 1; i <= numRectangles; ++i) {
        rectangles[i].x1 = coordMap[0][rectangles[i].x1];
        rectangles[i].x2 = coordMap[0][rectangles[i].x2];
        rectangles[i].y1 = coordMap[1][rectangles[i].y1];
        rectangles[i].y2 = coordMap[1][rectangles[i].y2];

        rectsByStartX[rectangles[i].x1].emplace_back(i);
        rectsByEndX[rectangles[i].x2].emplace_back(i);
        rectsByStartY[rectangles[i].y1].emplace_back(i);
        rectsByEndY[rectangles[i].y2].emplace_back(i);
    }

    // Calcul de nonOverlapCount pour chaque rectangle
    // 1. Rectangles entièrement à gauche
    int currentCount = 0;
    for (int i = 1; i <= compressedMaxX; ++i) {
        for (int rectIdx : rectsByStartX[i]) rectangles[rectIdx].nonOverlapCount += currentCount;
        currentCount += rectsByEndX[i].size();
    }

    // 2. Rectangles entièrement à droite
    currentCount = 0;
    for (int i = compressedMaxX; i >= 1; --i) {
        for (int rectIdx : rectsByEndX[i]) rectangles[rectIdx].nonOverlapCount += currentCount;
        currentCount += rectsByStartX[i].size();
    }

    // 3. Rectangles entièrement en dessous
    currentCount = 0;
    for (int i = 1; i <= compressedMaxY; ++i) {
        for (int rectIdx : rectsByStartY[i]) rectangles[rectIdx].nonOverlapCount += currentCount;
        currentCount += rectsByEndY[i].size();
    }

    // 4. Rectangles entièrement au-dessus
    currentCount = 0;
    for (int i = compressedMaxY; i >= 1; --i) {
        for (int rectIdx : rectsByEndY[i]) rectangles[rectIdx].nonOverlapCount += currentCount;
        currentCount += rectsByStartY[i].size();
    }

    // Corrections pour les rectangles dans les "coins" (ex: à gauche ET en dessous)
    // Ces corrections sont nécessaires car les sommes précédentes comptent ces rectangles plusieurs fois.
    bit.clear();
    for (int i = 1; i <= compressedMaxX; ++i) {
        for (int rectIdx : rectsByStartX[i]) rectangles[rectIdx].nonOverlapCount -= (bit.querySum(compressedMaxY) - bit.querySum(rectangles[rectIdx].y2));
        for (int rectIdx : rectsByEndX[i]) bit.update(rectangles[rectIdx].y1, 1);
    }
    bit.clear();
    for (int i = compressedMaxX; i >= 1; --i) {
        for (int rectIdx : rectsByEndX[i]) rectangles[rectIdx].nonOverlapCount -= bit.querySum(rectangles[rectIdx].y1 - 1);
        for (int rectIdx : rectsByStartX[i]) bit.update(rectangles[rectIdx].y2, 1);
    }
    bit.clear();
    for (int i = 1; i <= compressedMaxX; ++i) {
        for (int rectIdx : rectsByStartX[i]) rectangles[rectIdx].nonOverlapCount -= bit.querySum(rectangles[rectIdx].y1 - 1);
        for (int rectIdx : rectsByEndX[i]) bit.update(rectangles[rectIdx].y2, 1);
    }
    bit.clear();
    for (int i = compressedMaxX; i >= 1; --i) {
        for (int rectIdx : rectsByEndX[i]) rectangles[rectIdx].nonOverlapCount -= (bit.querySum(compressedMaxY) - bit.querySum(rectangles[rectIdx].y2));
        for (int rectIdx : rectsByStartX[i]) bit.update(rectangles[rectIdx].y1, 1);
    }
    bit.clear();

    // Calcul de ans1 : Triples avec exactement un chevauchement (ou une somme de chevauchements spécifiques)
    int ans1 = 0;
    for (int i = 1; i <= numRectangles; ++i) {
        ans1 += rectangles[i].nonOverlapCount * (numRectangles - 1 - rectangles[i].nonOverlapCount);
    }
    ans1 /= 2;

    // Calcul de ans2 : Triples où les trois rectangles se chevauchent mutuellement
    int ans2 = 0;
    int currentActiveRects = 0; // Compteur de rectangles actifs (intersectant la ligne de balayage X)

    for (int i = 1; i <= compressedMaxX; ++i) {
        // Traiter les rectangles qui commencent à x = i
        for (int rectIdx : rectsByStartX[i]) {
            // tmp compte les rectangles actifs qui chevauchent verticalement le rectangle courant
            int tmpCountVerticalOverlap = currentActiveRects - bit.querySum(rectangles[rectIdx].y1 - 1) - (bit2.querySum(compressedMaxY) - bit2.querySum(rectangles[rectIdx].y2));
            
            // On ajoute à ans2 : (toutes les paires parmi tmpCountVerticalOverlap) - (paires non-chevauchantes verticalement)
            // Cela donne les paires qui chevauchent verticalement
            ans2 += tmpCountVerticalOverlap * (tmpCountVerticalOverlap - 1) / 2 - segTree.queryIntervals(1, 1, compressedMaxY, rectangles[rectIdx].y1, rectangles[rectIdx].y2).nonOverlapPairs;

            // Mettre à jour les structures de données pour le rectangle ajouté
            bit.update(rectangles[rectIdx].y2, 1); // Pour compter les fins d'intervalles y
            bit2.update(rectangles[rectIdx].y1, 1); // Pour compter les débuts d'intervalles y
            segTree.updateLeftCoord(1, 1, compressedMaxY, rectangles[rectIdx].y1, 1);
            segTree.updateRightCoord(1, 1, compressedMaxY, rectangles[rectIdx].y2, 1);
            currentActiveRects++;
        }

        // Traiter les rectangles qui finissent à x = i
        for (int rectIdx : rectsByEndX[i]) {
            // Mettre à jour les structures de données pour le rectangle supprimé
            currentActiveRects--;
            bit.update(rectangles[rectIdx].y2, -1);
            bit2.update(rectangles[rectIdx].y1, -1);
            segTree.updateLeftCoord(1, 1, compressedMaxY, rectangles[rectIdx].y1, -1);
            segTree.updateRightCoord(1, 1, compressedMaxY, rectangles[rectIdx].y2, -1);
        }
    }

    // Calcul de la réponse finale
    // N_total - N_1 - N_3 (où N_1 est ans1, N_3 est ans2)
    // Cela suppose que N_2 (exactement 2 chevauchements) est 0 ou déjà inclus dans ans1.
    int totalTriples = numRectangles * (numRectangles - 1) * (numRectangles - 2) / 6;
    cout << totalTriples - ans1 - ans2 << "\n";

    return 0;
}