P3203 [HNOI2010] – Bouncing Sheep

Para cada posição, registramos quantos passos são necessários para sair do bloco atual e qual é a posição de destino após a saída. O cálculo é feito de trás para frente dentro de cada bloco.

#include <bits/stdc++.h>
#define MAXN 200100

using namespace std;

int n, m, tam;
int bloco[MAXN], salto[MAXN];
int prox[MAXN], passos[MAXN];
struct Intervalo { int l, r; } inter[MAXN];

int ler() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { s = (s << 1) + (s << 3) + ch - '0'; ch = getchar(); }
    return s * w;
}

void init() {
    tam = sqrt(n);
    for (int i = 0; i < n; i++) bloco[i] = i / tam;
    int ultimoBloco = bloco[n - 1];
    for (int i = 0; i <= ultimoBloco; i++) {
        inter[i].l = i * tam;
        inter[i].r = (i + 1) * tam - 1;
    }
    inter[ultimoBloco].r = n - 1;
}

void recalcula(int l, int r) {
    for (int i = r; i >= l; i--) {
        int destino = i + salto[i];
        if (destino > inter[bloco[i]].r) {
            prox[i] = destino;
            passos[i] = 1;
        } else {
            prox[i] = prox[destino];
            passos[i] = passos[destino] + 1;
        }
    }
}

int main() {
    n = ler();
    for (int i = 0; i < n; i++) salto[i] = ler();
    init();
    recalcula(0, n - 1);
    m = ler();
    for (int i = 0; i < m; i++) {
        int op = ler(), x = ler();
        if (op == 1) {
            int p = x, ans = 0;
            while (p < n) {
                ans += passos[p];
                p = prox[p];
            }
            printf("%d\n", ans);
        } else {
            int y = ler();
            salto[x] = y;
            int b = bloco[x];
            recalcula(inter[b].l, inter[b].r);
        }
    }
    return 0;
}

P4168 [Violet] – Dandelion

Armazenamos a posição de cada cor e pré‑calculamos, para cada par de blocos, o valor que mais se repete (moda) dentro desse intervalo. Consultas: blocos intermediários usam a tabela; bordas são varridas individualmente. É necessário discretizar as cores.

#include <bits/stdc++.h>
#define MAXN 100010

using namespace std;

int n, ids, L, R, total, consultas, ansAnterior, blocoAtual;
int arr[MAXN], nums[MAXN], bucket[MAXN];
int cnt[MAXN], modaBloco[3010][3010], sorted[MAXN];
vector<int> posicoes[MAXN];
map<int, int> compress;

int ler() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { s = (s << 1) + (s << 3) + ch - '0'; ch = getchar(); }
    return s * w;
}

int conta(int l, int r, int cor) {
    return upper_bound(posicoes[cor].begin(), posicoes[cor].end(), r)
         - lower_bound(posicoes[cor].begin(), posicoes[cor].end(), l);
}

void precalc(int blocoIni) {
    memset(cnt, 0, sizeof(cnt));
    int melhor = 0, corMelhor = 0;
    int inicio = (blocoIni - 1) * total + 1;
    for (int i = inicio; i <= n; i++) {
        cnt[arr[i]]++;
        if (cnt[arr[i]] > melhor || (cnt[arr[i]] == melhor && arr[i] < corMelhor)) {
            melhor = cnt[arr[i]];
            corMelhor = arr[i];
        }
        modaBloco[blocoIni][bucket[i]] = corMelhor;
    }
}

int consulta(int l, int r) {
    int melhorCnt = 0, corMelhor = 0;
    int blocoL = bucket[l], blocoR = bucket[r];

    if (blocoL + 1 < blocoR) {
        int corMeio = modaBloco[blocoL + 1][blocoR - 1];
        melhorCnt = conta(l, r, corMeio);
        corMelhor = corMeio;
    }

    int limE = min(r, blocoL * total);
    for (int i = l; i <= limE; i++) {
        int c = conta(l, r, arr[i]);
        if (c > melhorCnt || (c == melhorCnt && arr[i] < corMelhor)) {
            melhorCnt = c;
            corMelhor = arr[i];
        }
    }
    if (blocoL != blocoR) {
        int inicioDir = (blocoR - 1) * total + 1;
        for (int i = inicioDir; i <= r; i++) {
            int c = conta(l, r, arr[i]);
            if (c > melhorCnt || (c == melhorCnt && arr[i] < corMelhor)) {
                melhorCnt = c;
                corMelhor = arr[i];
            }
        }
    }
    return nums[corMelhor];
}

int main() {
    n = ler(); consultas = ler();
    for (int i = 1; i <= n; i++) {
        arr[i] = ler();
        sorted[i] = arr[i];
    }
    sort(sorted + 1, sorted + n + 1);
    for (int i = 1; i <= n; i++) {
        if (!compress[sorted[i]]) {
            ids++;
            compress[sorted[i]] = ids;
            nums[ids] = sorted[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        arr[i] = compress[arr[i]];
        posicoes[arr[i]].push_back(i);
    }
    for (int i = 1; i <= ids; i++) posicoes[i].push_back(n + 1);

    total = sqrt(n);
    for (int i = 1; i <= n; i++) bucket[i] = (i - 1) / total + 1;
    int numBlocos = bucket[n];
    for (int i = 1; i <= numBlocos; i++) precalc(i);

    for (int i = 0; i < consultas; i++) {
        L = ler(); R = ler();
        L = (L + ansAnterior - 1) % n + 1;
        R = (R + ansAnterior - 1) % n + 1;
        if (L > R) swap(L, R);
        ansAnterior = consulta(L, R);
        printf("%d\n", ansAnterior);
    }
    return 0;
}