1. Estabilidade de Operações Comerciais ====================

Este problema envolve o cálculo da estabilidade das operações comerciais de uma empresa usando a estrutura Splay Tree. O objetivo é determinar o valor mínimo de flutuação diária comparado com os dias anteriores.

#include <cstdio>
#include <algorithm>

using namespace std;

struct No {
    No *esq, *dir;
    int val, tam;
    No(int v) : esq(nullptr), dir(nullptr), val(v), tam(1) {}
};

inline int tamanho(No* n) { return n ? n->tam : 0; }

void atualizaTam(No* n) {
    if (n) n->tam = 1 + tamanho(n->esq) + tamanho(n->dir);
}

void rotacionaDireita(No*& raiz, No* x) {
    No* y = x->esq;
    x->esq = y->dir;
    y->dir = x;
    atualizaTam(x);
    atualizaTam(y);
    if (raiz == x) raiz = y;
}

void rotacionaEsquerda(No*& raiz, No* x) {
    No* y = x->dir;
    x->dir = y->esq;
    y->esq = x;
    atualizaTam(x);
    atualizaTam(y);
    if (raiz == x) raiz = y;
}

void insere(No*& raiz, int val) {
    if (!raiz) {
        raiz = new No(val);
        return;
    }
    No** filho = &raiz;
    while (*filho) {
        if (val < (*filho)->val) {
            filho = &(*filho)->esq;
        } else {
            filho = &(*filho)->dir;
        }
    }
    *filho = new No(val);
    atualizaTam(raiz);
}

int consultaPredecessor(No* raiz, int val) {
    int res = -1e9;
    while (raiz) {
        if (val > raiz->val) {
            res = max(res, raiz->val);
            raiz = raiz->dir;
        } else {
            raiz = raiz->esq;
        }
    }
    return res;
}

int consultaSucessor(No* raiz, int val) {
    int res = 1e9;
    while (raiz) {
        if (val < raiz->val) {
            res = min(res, raiz->val);
            raiz = raiz->esq;
        } else {
            raiz = raiz->dir;
        }
    }
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    No* raiz = nullptr;
    long long soma = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        if (i == 1) soma += x;
        else {
            int pred = consultaPredecessor(raiz, x);
            int succ = consultaSucessor(raiz, x);
            soma += min(x - pred, succ - x);
        }
        insere(raiz, x);
    }
    printf("%lld\n", soma);
    return 0;
}

2. Distribuição de Cartas ===============

O desafio aqui é simular a distrbiuição de cartas seguindo regras específicas utilizando segmant tree para otimização.

#include <cstdio>
#include <vector>

using namespace std;

const int MAXN = 7e5 + 5;

struct SegmentTree {
    vector<int> nodes;
    int tam;

    void build(int l, int r, int idx) {
        if (l == r) {
            nodes[idx] = 1;
        } else {
            int mid = (l + r) / 2;
            build(l, mid, 2 * idx);
            build(mid + 1, r, 2 * idx + 1);
            nodes[idx] = r - l + 1;
        }
    }

    int kth(int l, int r, int idx, int pos) {
        if (l == r) return l;
        int mid = (l + r) / 2;
        if (nodes[2 * idx] >= pos) return kth(l, mid, 2 * idx, pos);
        else return kth(mid + 1, r, 2 * idx + 1, pos - nodes[2 * idx]);
    }

    void remove(int l, int r, int idx, int pos) {
        if (l == r) {
            nodes[idx] = 0;
        } else {
            int mid = (l + r) / 2;
            if (pos <= mid) remove(l, mid, 2 * idx, pos);
            else remove(mid + 1, r, 2 * idx + 1, pos);
            nodes[idx]--;
        }
    }
} segtree;

int main() {
    int n;
    scanf("%d", &n);
    segtree.nodes.assign(4 * n, 0);
    segtree.build(1, n, 1);
    int currentPos = 0;
    for (int i = 1; i <= n; ++i) {
        int r;
        scanf("%d", &r);
        currentPos = (currentPos + r) % i + 1;
        int carta = segtree.kth(1, n, 1, currentPos);
        printf("%d\n", carta);
        segtree.remove(1, n, 1, carta);
    }
    return 0;
}

3. Divisão de Sequência em Blocos ==========

Ipmlementação do algoritmo de divisão de sequência em blocos com operações de intervalo.

#include <cstdio>
#include <set>

using namespace std;

struct Bloco {
    int inicio, fim, valor;
    bool operator<(const Bloco& outro) const {
        return inicio < outro.inicio;
    }
};

set<Bloco> blocos;
int n;

set<Bloco>::iterator divide(set<Bloco>::iterator it, int pos) {
    if (it != blocos.end() && it->inicio == pos) return it;
    Bloco blocoAtual = *it;
    blocos.erase(it);
    blocos.insert(Bloco{blocoAtual.inicio, pos - 1, blocoAtual.valor});
    return blocos.insert(Bloco{pos, blocoAtual.fim, blocoAtual.valor}).first;
}

void atribui(int l, int r, int v) {
    auto itR = divide(blocos.upper_bound({r + 1}), r + 1);
    auto itL = divide(blocos.lower_bound({l}), l);
    blocos.erase(itL, itR);
    blocos.insert(Bloco{l, r, v});
}

int consulta(int l, int r, int v) {
    auto itR = blocos.upper_bound({r + 1});
    auto itL = blocos.lower_bound({l});
    int res = 0;
    for (; itL != itR; ++itL) {
        if (itL->valor == v) res += itL->fim - itL->inicio + 1;
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        blocos.insert(Bloco{i, i, x});
    }
    for (int i = 1; i <= n; ++i) {
        int l, r, v;
        scanf("%d %d %d", &l, &r, &v);
        printf("%d\n", consulta(l, r, v));
        atribui(l, r, v);
    }
    return 0;
}