Description technique

On considère une ligne de n positions numérotées de 1 à n. Deux opérations sont disponibles :

• Ajouter une nouvelle entité sur l'intervalle fermé [l, r]. Chaque ajout correspond à un type distintc.
• Interroger le nombre de types distincts présents dans l'intervalle [l, r].

Le nombre total d'opérations, noté m, est de l'ordre de 10<sup>5</sup>, ce qui impose une solution en O(m log n).

Transformation du problème

Une entité créée sur [a, b] intersecte une requête [L, R] si et seulemant si :

a ≤ R  et  b ≥ L

Il suffit donc de compter les entités ayant commencé au plus à R, puis de retirer celles déjà terminées avant L. Chaque ajout d'intervalle est ainsi décomposé en deux événements ponctuels : un début en a et une fin en b.

Maintien des cumuls

Deux arbres de Fenwick (Binary Indexed Tree) maintiennent les cumuls :

• start : nombre de débuts d'intervalles jusqu'à l'indice i.
• finish : nombre de fins d'intervalles jusqu'à l'indice i.

La réponse à une requête [L, R] s'obtient alors par :

start.prefix(R) - finish.prefix(L - 1)

Le premier terme compte toutes les entités ayant débuté au plus à R. Le second retire celles terminées strictement avant L.

Complexité

Chaque mise à jour et chaque requête s'effectuent en O(log n). La complexité totale est O(m log n) et l'occupation mémoire est en O(n).

Implémentation

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    vector<int> bit;
    int n;
    Fenwick(int n = 0) { init(n); }
    void init(int n) {
        this->n = n;
        bit.assign(n + 1, 0);
    }
    void update(int idx, int delta) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
    }
    int query(int idx) const {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    if (!(cin >> n >> m)) return 0;
    
    Fenwick start(n), finish(n);
    
    for (int i = 0; i < m; ++i) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            start.update(l, 1);
            finish.update(r, 1);
        } else {
            int active = start.query(r);
            int alreadyFinished = finish.query(l - 1);
            cout << active - alreadyFinished << '\n';
        }
    }
    return 0;
}