Este problema envolve determinar, para cada segmento de alvo, em qual passo ele é atingido pela primeira vez por uma sequência de tiros. A abordagem ideal emprega divisão binária sobre o tempo, combinada com uma árvore de Fenwick (BIT) para contagem eficiente de tiros dentro de intervalos.

A ideia central é inverter a perspectiva: ao invés de simular tiros sequencialmente até acertar cada alvo, aplicamso uma busca binária global no eixo do tempo (de 0 a m+1), agrupando consultas por sua resposta provável. Durante cada etapa da recursão, isnerimos os tiros cujos índices caem na metade esquerda do intervalo atual e verificamos quantos deles cobrem cada alvo. Se a cobertura for suficiente, o alvo pertence à metade esquerda; caso contrário, ajustamos seu requisito restante e o direcionamos à metade direita.

O código abaixo implementa essa estratégia com gerenciamento cuidadoso dos limites e restauração do estado da BIT entre chamadas recursivas:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

constexpr int MAX = 200005;
long long n, m;
long long L[MAX], R[MAX], need[MAX], pos[MAX];
int type[MAX], result[MAX], count_per_step[MAX];

struct Fenwick {
    long long tree[MAX];
    static int lowbit(int x) { return x & -x; }
    
    void update(int idx, long long delta) {
        for (; idx <= n; idx += lowbit(idx))
            tree[idx] += delta;
    }
    
    long long prefix_sum(int idx) {
        long long s = 0;
        for (; idx > 0; idx -= lowbit(idx))
            s += tree[idx];
        return s;
    }
    
    long long range_sum(int l, int r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
} bit;

void solve(int left, int right, vector<int>& queries) {
    if (queries.empty()) return;
    if (left == right) {
        for (int q : queries) result[q] = left;
        return;
    }
    
    int mid = (left + right) / 2;
    vector<int> left_group, right_group;
    
    // Processar todas as consultas
    for (int q : queries) {
        if (type[q] == 1) { // tiro
            if (q <= mid) {
                left_group.push_back(q);
                bit.update(pos[q], 1);
            } else {
                right_group.push_back(q);
            }
        } else { // alvo
            long long covered = bit.range_sum(L[q], R[q]);
            if (covered >= need[q]) {
                left_group.push_back(q);
            } else {
                right_group.push_back(q);
                need[q] -= covered;
            }
        }
    }
    
    // Desfazer atualizações feitas nesta camada
    for (int q : left_group) {
        if (type[q] == 1) bit.update(pos[q], -1);
    }
    
    solve(left, mid, left_group);
    solve(mid + 1, right, right_group);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> L[i + m] >> R[i + m] >> need[i + m];
        type[i + m] = 0;
    }
    for (int i = 1; i <= m; ++i) {
        cin >> pos[i];
        type[i] = 1;
    }
    
    vector<int> all_queries;
    for (int i = 1; i <= n + m; ++i) all_queries.push_back(i);
    
    solve(0, m + 1, all_queries);
    
    for (int i = 1; i <= n + m; ++i) {
        if (type[i] == 0) count_per_step[result[i]]++;
    }
    
    for (int i = 1; i <= m; ++i) {
        cout << count_per_step[i] << '\n';
    }
}

Problema: Reversão Ótima de String (CF1430E)

Dado uma string inicial e sua versão invertida, queremos o número mínimo de trocas adjacentes para transformar uma na outra. Essa quantidade equivale ao número de inversões necessárias ao mapear posições dos caracteres na string original para suas respectivas ocorrências na versão final — garantindo que caracteres idênticos sejam emparelhados de forma a minimizar o total de inversões.

O método consiste em:

1. Enumerar as posições da string invertida como 1, 2, ..., n.
2. Para cada caractere na string original, associar sua ocorrência mais antiga ainda não usada na sequência invertida (garantindo ordem lexicográfica mínima nas posições mapaedas).
3. Construir um vetor A onde A[i] é a posição mapeada do i-ésimo caractere original.
4. Contar o número de inversões em A usando uma árvore de Fenwick.

O código a seguir executa esse fluxo com estruturas de dados otimizadas:

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

constexpr int MAX = 200005;
long long n;
string s;
vector<int> positions[26];
int mapping[MAX], ptr[26];
long long bit[MAX];

int lowbit(int x) { return x & -x; }

void add(int idx, long long val) {
    for (; idx <= n; idx += lowbit(idx))
        bit[idx] += val;
}

long long sum(int idx) {
    long long res = 0;
    for (; idx; idx -= lowbit(idx))
        res += bit[idx];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> s;
    s = " " + s;
    
    // Pré-processar posições na string invertida (índices 1..n)
    for (int i = n; i >= 1; --i) {
        int c = s[i] - 'a';
        positions[c].push_back(n - i + 1);
    }
    
    // Construir mapeamento para cada caractere na string original
    for (int i = 1; i <= n; ++i) {
        int c = s[i] - 'a';
        mapping[i] = positions[c][ptr[c]++];
    }
    
    long long ans = 0;
    for (int i = n; i >= 1; --i) {
        ans += sum(mapping[i] - 1);
        add(mapping[i], 1);
    }
    
    cout << ans << '\n';
}