PRACAALI - Praça de alimentação

Olá meus amigos nerds! Hoje vamos resolver o problema PRACAALI - Praça de alimentação pedido pelo nosso amigo Jonas. Mais especificamente, o problema pede para estimar a quantidade máxima de pessoas que podem ter estado dentro de uma cantina, dados os horários de entrada e saída de cada pessoa.

Solução

Esse é um problema difícil, levei um bom tempo para resolver. Quando nos deparamos com um problema assim, a primeira coisa a fazer é tentar resolver uma versão mais fácil do problema. E é assim que vamos resolver esse problema hoje.

Caso não houvessem ? o problema poderia ser modelado como um problema de soma máxima em vetores. Pense que cada pessoa que entra adiciona +1 a soma de pessoas dentro da cantina e cada pessoa que sai -1 a tal soma. Assim, se ordenássemos os eventos de entrada e saída pela hora que eles aconteceram e aplicarmos o algoritmo de soma máxima encontraríamos o número máximo de pessoas dentro da cantina.

Como queremos o número máximo possível de pessoas que poderiam estar na cantina, podemos dispor das ? da forma que quisermos. Então nosso problema se torna em tentar descobrir a atribuição correta de entrada/saída para cada ?.

Vamos começar descobrindo o número de interrogações que temos que transformar em entradas. Sejam num_e o número de eventos de entrada dados na instância do problema, num_s o número de eventos de saída e num_x o número de eventos incertos (?). É garantido pelo enunciado que a entrada do problema é coerente. Ou seja, metade de todos os eventos, mesmo os ?, são de entrada e metade de saída. Além disso, todo evento de saída é correspondente a um evento anterior de entrada.

Vamos estimar o número máximo de eventos ? que podem ser de entrada. Temos dois casos a considerar.

Se num_e > num_s: sabemos que, dos num_x eventos ?, (num_e - num_s) são de saída, para compensar a falta de eventos de saída na entrada. Do restante, metade será de entrada e metade de saída.

Por outro lado, se num_s > num_e, sabemos que (num_s - num_e) eventos ? deverão ser de entrada correspondente aos eventos de saída sobrando.

De forma mais algorítmica, o número máximo de eventos ? que necessariamente tem que ser eventos de entrada (max_entradas) seria:

num_x = total_eventos - (num_s + num_e)
if num_e > num_s
    max_entradas = (num_x - (num_e - num_s)) / 2
else
    max_entradas = num_s - num_e + (num_x - (num_s - num_e)) / 2

 

A grande sacada para resolver esse problema é ver que podemos atribuir os primeiros max_entradas eventos ? como sendo eventos de entrada. A prova de que este algoritmo guloso funciona será por contradição. Vamos supor que exista outra solução e mostrar que nossa solução não será pior que essa outra solução. Para isso, vamos partir da nossa solução e trocar eventos de posição e ver o que acontece

Vamos chamar de período o espaço entre dois eventos correspondentes a uma mesma pessoa, relativo à sua entrada. Ou seja, o período de uma pessoa é o tempo entre seus eventos de entrada e saída. Note que o período depende do horário de entrada.

Suponha uma solução ótima diferente da gerada pelo nosso algoritmo. Consideremos nesta outra solução as duas primeiras pessoas a entrar no local que tenham período diferente da nossa solução. Nosso algoritmo, obviamente, classificaria os 4 eventos, em ordem, como EESS (onde E é entrada e S é saída). Uma solução válida diferente da nossa só pode ser ESES; caso contrário, ela seria incoerente (dado que as pessoas que entraram antes têm eventos coerentes associados a elas). Assim, temos três casos possíveis: ou o momento em que o maior número de pessoas estava no restaurante foi entre os dois primeiros eventos, ou entre o segundo e o terceiro, ou entre os dois últimos (E*E*S*S os momentos são os *). Transformando esta suposta solução ótima na nossa solução (ou seja, trocando o tipo dos dois eventos do meio), obtemos uma solução melhor que essa solução ótima (o número de pessoas no restaurante entre os dois primeiros e entre os dois últimos eventos permanece o mesmo, enquanto o número de pessoas entre os eventos do meio foi aumentado em 1). A partir de sucessivas transformações deste tipo, podemos transformar qualquer solução ótima, sem piorá-la, na solução dada pelo nosso algoritmo. Portanto, esta deve, necessariamente, ser ótima.

Então a solução final para o problema é supor que os primeiros num_entradas eventos ? são de entrada e os outros de saída e aplicar o algorítimo da soma máxima de vetores no array resultante.

Implementação

 

Problema real - Extraindo padrões de textos

Olá meus amigos nerds! Hoje vamos ver que o conhecimento que adquirimos ao brincar em maratonas de programação pode nos ser útil no mundo real. Vou compartilhar com vocês um problema desafiador que tive que resolver essa semana no trabalho.

Essa semana estava trabalhando em um modelo para prever se um candidato seria uma boa indicação para uma dada vaga. Feliz ou infelizmente,  o dataset que eu tinha a minha disposição é bem grande, mas a maior parte da informação contida nele está em forma de texto.

Parte da arte de se criar bons modelos de machine learning está em escolher  e usar as informações certas ao construir o modelo. Features textuais costumam conter bastante informação, entretanto extrair essa informação costuma ser problemático, já que as máquinas gostam de lidar com números.

Em particular, no modelo que eu estava criando, eu gostaria de usar as skills (descrições curtas de habilidades do candidato) presentes nos currículos. E, para minha felicidade, eu tinha a minha disposição uma tabela contendo tal informação.

Infelizmente eu não tinha essa mesma informação para as vagas, então decidi extraí-la da descrição das mesmas. Aí começa o problema.

Dada a descrição textual de uma vaga e uma tabela contendo skills (ex: mineração de dados, vendas, etc) eu gostaria de saber quais são as skills exigidas pela vaga.

O problema

Ué mas não é só dar um .find() das skills no texto e pronto? Onde está o problema desafiador? Aqui no blog já resolvemos alguns problemas de casamento de padrões mais difíceis que esse!

Bem meus amigos, o problema está na escala! Minha tabela de skills continha algo em torno de 1 milhão de registros. Além disso, eu também tinha alguns milhões de vagas o que torna a solução de força bruta inaplicável.

Problemas envolvendo escala costumam ser interessantes e esse não é diferente. Vamos ver como, mesmo algo que é simples quando lidamos com pequenos volume de dados, pode se tornar desafiador quando o tamanho dos dados realmente importa.

Para você ter uma ideia, a biblioteca de regex do python levou um ou dois minutos para compilar toda a tabela em padrões da forma p1|p2|...|pn. Além disso, o automato gerado por ela levava em torno de 1s para extrair os padrões de apenas uma vaga. 1s é o  mesmo que infinito, se considerarmos que o SLA (tempo de resposta acordado) para a maioria das APIs que eu trabalho gira em torno de 200ms. Só para vocês terem uma ideia, usando-se uma máquina moderna levaríamos cerca de 10 dias só para extrair as skills de 1M vagas.

Ou seja, nosso problema é grande o suficiente para que a biblioteca padrão (consideravelmente otimizada) de uma linguagem moderna não seja suficiente.

Solução

Se todas as nossas skills fossem compostas apenas de uma palavra a solução de complexidade ótima (O(# palavras na descrição das vagas)) seria indexar nossas skills em uma tabela hash. Assim, para cada palavra na descrição da vaga, poderíamos verificar se ela esta presente no hash ou não.

O nosso problema é que as skills não são formadas apenas por uma palavra. Para contorná-lo basta criar uma árvore com as palavras das skills, onde cada nó da árvore representa uma palavra e existe uma aresta ligando dois nós se uma skill possui as duas palavras em sequência. Em outras palavras, a ideia para resolver esse problema é uma árvore de prefixos. Cada nó da árvore pode ter vários filhos, que podem ser mantidos em um hash para otimizar a busca.

Para buscar pelas skills então basta tokenizar o texto da vaga e para cada token ir andando com ele na árvore de prefixos de skills, verificando se aquele token gera ou não um match.

Implementação

 

Acho que essa é a primeira vez que uso uma de minhas linguagens preferidas para resolver um problema por aqui. O código Python abaixo implementa a ideia da árvore de prefixos.

1751. A lei vai a Cavalo!

Olá meus amigos nerds. Hoje vamos ajudar a polícia canadense a decidir o número máximo de policiais que podem ter um cavalo para montar. Já que é isso que o problema 1751. A lei vai a Cavalo! nos pede para fazer. Mais especificamente, dadas as afinidades entre cavalos e cavaleiros; e o número de cavaleiros que podem montar cada cavalo, determinar o número máximo de policiais que podem ter um cavalo para montar em uma atribuição entre cavalos e cavaleiro.

Solução

Esse problema envolve uma atribuição (match) entre cavalos e cavaleiros, uma boa forma de modelar a solução de problemas assim é usando grafos. Considere o grafo bipartido onde os vértices representam os cavalos e cavaleiros. Sendo que existe uma aresta entre dois vértices se o cavalo é compatível com o cavaleiro. Além disso, a cada vértice que representa um cavalo vou atribuir uma capacidade c igual ao número de cavaleiros que podem montar esse cavalo. Do mesmo modo, para cada vértice que representa um cavaleiro vou atribuir uma capacidade (igual a 1, já que cada cavaleiro pode montar apenas 1 cavalo).

O número máximo de cavaleiros que poderiam ter um cavalo para montar pode ser calculado como o fluxo máximo que pode passar por esse grafo, considerando-se os cavaleiros como sources e os cavalos como sinks. A ideia por traz disso está no fato de que: a escolha de uma aresta para a passagem do fluxo corresponde a um match entre cavalo e cavaleiro, sendo assim com o fluxo máximo representa o número máximo de arestas que eu consigo usar (cada aresta tem capacidade 1) para atribuir um cavaleiro a um cavalo.

Para usarmos o algoritmo clássico (Ford–Fulkerson) de fluxo máximo, nosso grafo tem que ter apenas um source e um sink. Para transformar um grafo com múltiplos sources em um grafo com apenas um, basta incluir um vértice extra no grafo e liga-lo a cada source, sendo que cada aresta adicionada tem um peso igual a capacidade do vértice (source). Analogamente, podemos usar essa mesma técnica para reduzir o número de sinks para um.

Implementação

1761. Back to the future

Olá meus amigos nerds. Como a zueira não tem limites, eu não poderia deixar a data de ontem passar em branco. E para isso, nada melhor do que resolver um problema que tem 'de volta para o futuro' no nome e trata de viagens e fluxos. Hoje vamos ajudar nossos amigos a voltar da Alemanha gastando o mínimo possível em passagens aéreas. Já que é isso que o problema 1761. Back to the future nos pede para fazer. (Puts, tinha que ter postado esse problema ontem kkk). Mais especificamente, dadas as rotas aéreas e o número de lugares livres por avião, determinar qual é o mínimo possível que um grupo de d amigos precisa gastar para conseguir viajar entre duas cidades a e b dadas.

Solução

Com um nome desses, esse problema não poderia ser fácil. Como em muitos problemas que envolvem rotas, uma abordagem usando grafos é uma boa ideia. As cidades seriam os vértices de forma que cada vôo seria uma aresta. Cada aresta teria um custo (valor da passagem) e uma capacidade (número de acentos livres). Se você conhece um pouco sobre fluxo máximo em grafos, você deve estar vendo onde quero chegar com essa modelagem.

O problema do fluxo máximo consiste em, encontrar qual seria o maior fluxo, que se poderia transferir de um nó de origem para um nó de destino, respeitando a capacidade de transferir fluxo de cada aresta. Uma analogia seria um sistema hidráulico com canos interligando vários pontos...

Uma variação desse problema é o fluxo máximo a custo mínimo, ou seja, onde cada aresta possui um custo associado, para transportar o fluxo. Como vocês podem observar, nosso problema é praticamente esse.

Fluxo máximo a custo mínimo pode ser resolvido usando-se o algoritmo de Edmonds-Karp. Note que, no problema de fluxo, cada aresta tem duas grandezas associadas a ela, um custo e uma capacidade. A ideia desse algoritmo é ir encontrando caminhos da origem para o destino e transferindo o máximo de fluxo que esse caminho suporta. Mais algoritmicamente: (1) encontre um caminho mínimo (em relação ao custo) da origem ao destino. (2) Verifique qual é a aresta desse caminho que admite a menor capacidade. (3) Transfira, por esse caminho, um fluxo igual a essa capacidade. (4) De cada aresta do caminho subtraia a capacidade transportada. (5) Continue com esse procedimento até que não haja mais caminhos da origem para o destino com todas as arestas com capacidades maiores que 0. Observe que o caminho mínimo muda a cada iteração, pois reduzir a capacidade de uma aresta a 0, corresponde a 'tirar' essa aresta do grafo.

Oras, mas esse problema do fluxo máximo é o mesmo do problema que queríamos resolver, de modo que, o custo do fluxo máximo no grafo dos vôos é a resposta! Errado! Observe que no problema do fluxo máximo assume-se que a origem tem capacidade de produzir um fluxo tão grande quanto o grafo possa aguentar. No nosso caso, o número de passageiros é limitado. Mas se você pensar um pouquinho vai ver que é só parar o algoritmo quando tivermos transportado todos nossos amigos de volta para o Brasil.

Implementação

O problema afirma que nossos amigos tem pouco dinheiro. Mas não deixe se enganar, o custo máximo da viajem de todos pode chegar a 10^15 reais (Imagina eu com esse dinheiro todo, dava até para começar a construir minha própria máquina do tempo :D). Felismente 10^15 cabe em um long long.

O código não está la muito bonito (tempos de maratona, lembra?), me desculpem pelas macros não muito elegantes. Mas também, vocês tem que me dar um desconto, fluxo máximo usa até um dijkstra como uma pequena parte dele.

18550. Troco

Olá meus amigos nerds. Hoje completa exatamente um ano que eu resolvi um problema relacionado a moedas. E para comemorar, nada melhor do que resolver outro problema do tipo. Vamos tentar verificar se é possível pagar uma conta de modo exato apenas com as moedas que estão em nosso bolso. Já que é isso que o problema 18550. Troco nos pede para fazer. Mais especificamente, dadas m moedas, determinar se é possível somar exatamente v centavos usando um subconjunto dessas moedas.

Solução

Como todo problema de programação dinâmica esse não é fácil. Uma solução que enumere todos os conjutos possíveis de moedas e verifique se eles somam v não viável.

O segredo, para resolver esse problema, esta em pensar o que acontece quando eu pego uma moeda. Suponha que eu conheça todos os valores que eu consigo somar com as moedas restantes, se a cada um desses valores, eu somar a moeda atual eu fico com um novo conjunto de valores que eu consigo somar. A união desse conjunto e do anterior forma todas as somas que eu consigo fazer até o momento.

Isso sugere uma solução usando programação dinâmica. Com 0 moedas eu só consigo somar 0. Adicionando a primeira moeda eu só consigo somar 0 e o valor da moeda. Com a segunda eu já consigo somar 0, o valor da primeira, o valor da segunda e a soma das duas... Ou seja, se eu armazenar para cada valor possível de soma (menor ou igual a v é claro) se é possível somar aquele valor, para adicionar uma moeda é só eu percorrer esse vetor de estados e ir atualizando as posições dele com as novas somas possíveis.

A ideia acima funciona pois: se já é possível somar x com um conjunto de moedas, se eu adicionar mais uma moeda ao problema, continua sendo possível eu somar x (basta eu não usar a nova moeda). Se eu consigo somar a, b e c e eu adiciono outra moeda (d) ao problema eu vou poder somar além de a, b e c, (a+d), (b+d), (c+d). Algoritmicamente falando:

somas_possiveis = {0}
para cada moeda x
    para cada soma em somas_possiveis
        novas_somas += (x+soma)
    somas_possiveis |= novas_somas

Ou considerando que somas_possiveis sera representado por um vetor
somas_possiveis[0] = True
para cada moeda x
    para i=len(somas_possiveis), i >= x, i--
        Se somas_possiveis[i-x]
            somas_possiveis[i] = True

Note que se eu posso somar i-x centavos, se eu adicionar a moeda atual eu posso somar i centavos. O loop é feito de forma decrescente para garantir que eu não use x duas vezes para uma mesma soma, já que i-x ainda não foi calculado para a moeda atual.

Note que a solução apresentada depende do valor de v, ou seja, é uma solução pseudo polinomial. Mais precisamente a complexidade dessa solução é O(v*m), como v e m são relativamente pequenos essa solução é suficiente para conseguirmos superar o time limit.

Implementação

:P O operador -- serve para alguma coisa! Observe que se invertermos a lógica do loop da linha 22 para uma lógica aditiva o programa deixa de produzir a resposta certa, pois nesse caso quebramos nosso invariante de que somas_possiveis[v-moeda] não utiliza a moeda atual para ser somado.

12939. Păo a metro

Olá meus amigos nerds. Hoje vamos brincar de cortar pães para fazermos sanduíches que serão usados durante uma maratona de programação. Isso mesmo! Já que é isso que o problema 12939. Pão a metro nos pede para fazer. Mais especificamente, dados os tamanhos de pão disponíveis (em centímetros) e a quantidade de pessoas a serem servidas, queremos saber o tamanho inteiro máximo (em centímetros) da fatia que pode ser cortada de maneira a atender todas as pessoas.

Solução

A solução simples para esse problema seria tentar todos os tamanhos possíveis para os pães e escolher o maior. Entretanto, isso, é claro, não é eficiente o suficiente.

Suponha que conheçamos o tamanho de pão máximo. Para tamanhos superiores de pão não conseguimos servir as n pessoas (caso contrário por contradição esse tamanho não seria máximo). Assim, ao invés de procurar por força bruta o tamanho ótimo, podemos aplicar busca binária ao problema, uma vez que temos uma propriedade que é verificada para valores inferiores a um número (o tamanho máximo), mas não o é para valores inferiores.

Agora só nos falta definir os limites nos quais queremos aplicar busca binária. Obviamente, o tamanho mínimo de pão é 1. Já o máximo é o maior tamanho entre as k fatias de pão (lembre-se de que não podemos juntar duas fatias).

Implementação

Observe que o código testa duas condições de contorno. Uma delas é o pão de tamanho 1 (limite inferior do intervalo) e outra o pão de tamanho k (todos os pedaços são do mesmo tamanho).

17384. Desfile dos Patos

Olá meus amigos nerds, depois de um bom hiato, devido a eu ter me mudado e ficado algum tempo sem internet :(, estamos de volta para resolver mais problemas.

Mas para compensar hoje vamos resolver um tipo de problema que eu gosto muito: um problema que a solução fácil, não é suficientemente boa, nos forçando a ir além e fazer melhor.

Hoje vamos verificar qual a cor que mais aparece durante um desfile de patos. Já que é isso que o problema 17384. Desfile dos Patos nos pede. Mais especificamente, dada uma fila de patos, em que cada pato tem uma plumagem de cor diferente, determinar qual é a cor majoritária dentre as cores da plumagem dos patos, isto é, a cor que aparece em mais da metade das plumagens.

Solução

Apesar da aparente simplicidade esse problema é bem difícil. Ele possuí um limite de tempo muito apertado, e isso faz com que algo que geralmente não é muito importante, quando tratamos de complexidade de algoritmos, se tornar relevante, as constantes.

Vocês já devem ter percebido que um simples mapa resolve o problema, isto é armazene contadores para cada cor e no final verifique qual cor majoritária. Se implementarmos o mapa como um hash, esse algoritmo é linear. Além disso, ele tem complexidade ótima, já que não é possível resolver esse problema sem analisar cada elemento da lista.

Entretanto o algoritmo acima não é eficiente o suficiente para resolvermos esse problema. Quem diria, um hash não é eficiente o suficiente para resolve-lo! Depois de muito pensar (e até achar que quem inseriu o problema cometeu algum equivoco no time limit), observamos que o problema tem uma característica especial, a cor mais frequente é majoritária, isso é ela tem mais aparições na lista que a soma de todas as outras cores. Isso nos permite abrir mão do hash e usar um único contador para verificar qual é a cor majoritária.

A ideia é a seguinte, se do número de aparições da cor majoritária subtrairmos o número de aparições de cada uma das outras cores, esse resultado é necessariamente maior que 0. Assim, podemos usar um algoritmo guloso para contar a diferença entre o número de aparições da cor majoritária para as outras cores. Podemos iniciar nossa contagem com qualquer cor, já que ao final necessariamente a cor majoritária tem elementos o suficiente para "cancelar" com cada um dos elementos das outras cores. O algoritmo abaixo vai verificando qual a cor majoritária até a 0-ésima posição do vetor, 1-ésima posição, ..., n-ésima, etc

corMajoritaria = 0
cnt = 0
for cor in corPatos
    if cnt == 0
       corMajoritaria = cor
    if cor == corMajoritaria
        cnt++
    else
        cnt--

O algorítmo acima é mais eficiente que um hash, pois não tem que pagar o custo de iterar sobre todos os elementos do hash ao final para verificar qual é o que tem o maior contador.

Implementação

11611. Homem, elefante e rato

Olá meus amigos nerds, hoje o bicho vai pegar. Como prometido, essa semana, humildemente, trago a vocês um problema bem interessante. 

Hoje vamos brincar de Homem, Elefante e Rato nome que os criativos Nlogôlianos deram para nosso famoso pedra, papel, tesoura, já que é isso que o problema 11611. Homem, elefante e rato nos pede. Mais especificamente, o problema pede que computemos a frequência de cada símbolo (homem, elefante, rato) após cada rodada do jogo. Parece fácil, não é, mas há uma particularidade: Os habitantes da Nlogônia, que são estrategistas natos de Homem (pedra), Elefante (papel) e Rato (tesoura), utilizam a seguinte técnica no campeonato nacional, realizado todos os anos: começam sempre jogando Homem até o momento em que este símbolo causa empates com a maioria dos oponentes. Eles então trocam sua estratégia para o símbolo que ganha daquele que usavam anteriormente. Assim, os jogadores vão mudar de Homem para Elefante, depois para Rato, depois de volta a Homem. Nossa tarefa é contabilizar quantos jogadores irão utilizar cada símbolo após cada rodada.

Solução

Após ter lido o problema, você deve estar pensando: seu nerd burro esse problema é extremamente fácil! Basta eu ter um array com a opção atual de cada jogador e simular o que acontece a cada rodada e pronto.

Seja opcaoJogador um array em que cada elemento representa a opção (pedra, papel, tesoura) atual do jogador

Seja operacoes as operações que temos que simular a cada rodada

for operacao in operacoes

  Sejam inf e sup os limites, inferior e superior

   if operacao == mostra

     imprime  a frequencia de homem, elefante rato em opcaoJogador[inf : sup]

   else

     for i de inf a sup

       atualiza opcaoJogador[i]

Você está certo! Eu sou burro! O código acima realmente resolve o problema. Mas ele não leva em conta um detalhe muito importante: escala! Analisar o tamanho da entrada que seu algoritmo é capaz de lidar é de extrema importância. Uma rápida olhada, em nosso pseudo código, nos mostra que ele tem complexidade O(#operacoes * len(sup-inf)). Agora vamos supor, que nosso código vai ser rodado em uma máquina que consegue executar 10^9 operações por segundo, como len(#operações) = 10^5 e len(sup-inf)=10^6 nosso computador imaginário levaria mais ou menos uns 100s para rodar nosso código, ou seja, não passariamos no limite de tempo 1s (TLE).

Uma pequena divagação, se pararmos para pensar muitos dos problemas interessantes que as grandes empresas de TI, como Google e Microsoft, enfrentam não são complicados, o que torna esses problemas desafiadores muitas vezes é a escala monstruosa do tamanho dos dados que eles tem que lidar.

Voltemos ao nosso problema! A escolha correta da estrutura de dados a ser usada pode transformar um problema impossível em um problema trivial. E é isso que eu vou fazer agora. Existe uma estrutura de dados chamada segment tree que é capaz de executar as operações de consulta em um intervalo e atualização de um intervalo em O(log n). Se substituirmos o array opcaoJogador, no pseudo código acima, por uma segtree nosso problema com TLE está resolvido. Isso mesmo, a alteração de uma estrutura de dados nos levaria a uma otimização de 100x no tempo de execução de nosso problema!!

Esse seria o momento em que eu explicaria o que é uma segtree e como implementá-la. Mas essa é uma estrutura por demais interessante, que certamente merece umas duas ou três horas do seu tempo para estudá-la. Então vamos fazer o seguinte, vou deixar para você como desafio estudar um pouco sobre uma segtree e tentar resolver esse problema. No fim da semana vou postar uma explicação detalhada de como se implementar uma segtree. Mas só para não te deixar muito no ar:

Uma segtree é uma árvore binária, cada uma de suas folhas representa um intervalo que tem alguma propriedade que pode ser compartilhada com outros intervalos. Cada nó interno representa a união de alguns intervalos folhas e é capaz de sumarizar os intervalos folhas. Uma segtree é capaz de realizar duas operações importantes para o nosso problema:

• Buscar o estado de um intervalo. Por exemplo, no nosso problema, eu poderia perguntar a segtree qual é a frequência de Elefantes no intervalo do primeiro ao último participante. Essa pergunta seria respondida em O(log n).
• Atualizar o estado de um intervalo inteiro. Por exemplo, no nosso problema, eu poderia pedir a segtree que alterasse a figura colocada de Elefante para Rato, de todos os participantes no intervalo do primeiro participante ao participante n/2. Essa operação, também, seria realizada em O(log n).

Implementação

É claro que eu não deixaria você sem a implementação do problema de hoje. Observe como o código da segtree é delicado, qualquer erro é bastante difícil de ser debugado.

Veja também a pequena otimização com o uso da macro __attribute__((always_inline)); para forçar algumas funções a ser inline. Além disso, observe a alocação estática de memória, também com o objetivo de ganhar tempo.

Pensei em implementar a segtree de modo genérico (template) mas isso geraria mais um nível de complexidade, então para tornar o código mais simples não fiz isso.