11/4

• Conjuntos: Para lidar com $2^k$ conjuntos, onde cada conjunto tem todos os seus subconjuntos marcados, uma abordagem em $O(k2^k)$ é viável.
• Coloração: Para dois sequências, $a$ monotonicamente crescente e $b$ monotonicamente decrescente, encontrar o mínimo de $\max(a_i, b_i)$ pode ser resolvido eficientemente com busca binária.
• Placa de Circuito: Ao usar priority\_queue com funções de comparação customizadas, evite variáveis globais. Toda a lógica de comparação deve ser encapsulada dentro da estrutura (functor).
• Problema da Declaração Mais Concisa da História II: Ao realizar múltiplas consultas lower\_bound em $n$ vetores, pré-processar prefixos somados para os primeiros vetores pode otimizar o desempenho.

11/5

• Divisão de Bens: Para uma sequência $a$ de $n$ números onde $|a_i| \leq W$, é possível atribuir sinais de mais ou menos a cada elemento para que o valor absoluto da soma seja no máximo $W$.
• Problema da Declaração Mais Concisa da História III: Para equações de programação dinâmica (DP) que envolvem apenas valores booleanos, bitset pode ser usado para otimização.

11/6

• Problema da Declaração Mais Concisa da História IV: Ao usar Dijkstra para encontrar a árvore de caminho mais curto e posteriormente determinar se uma aresta é uma aresta da árvore, é crucial salvar o ID da aresta em vez de usar verificações como fa\[u\] != v && fa\[v\] != u. Isso é necessário para lidar corretamente com arestas múltiplas. De forma geral, se um problema não especifica explicitamente a ausência de arestas múltiplas, a identificação de arestas deve ser feita por ID, não apenas pelos seus pontos finais.
• Pomba Branca: Fluxo de custo mínimo pode ser acelerado com Dinic, embora a implementação possa ser extensa. Ao resolver problemas de fluxo em rede, é recomendável mesclar arestas múltiplas para economizar tempo.
• Diferença em Árvores:
  1. Para contar quantos elementos $f(x)$ satisfazem $f(x)=i$, primeiro conte quantos satisfazem $i|f(x)$ e depois aplique a diferença de Dirichlet (essencialmente uma inclusão-exclusão).
  2. Se um algoritmo tem complexidade de tempo como $O(n \cdot \sum i)$, considere a divisão por limiar. Aplique um algoritmo para $i \leq B$ e outro para $i > B$.
• Fixo de Pomba: Se um problema requer uma função dos $m$ maiores ou o $m$-ésimo maior elemento em um intervalo, considere usar uma lista encadeada. Encontre o $m$-ésimo maior elemento e expanda $m$ posições para a esquerda e para a direita.
• Pato de Ano Novo: A decomposição de cadeia em árvores pode ser uma forma eficaz de implementar DP em árvores. A abordagem envolve recursão em cadeias pesadas e subárvores leves (aquelas que crescem de uma cadeia pesada).
• Dados Rodoviários: Ao considerar busca binária e um domínio de valor muito grande, pode-se alternativamente escolher um valor aleatório e usar a contagem de elementos maiores para guiar a recursão binária.
• Invisível: Para determinar se existe um número que aparece um número ímpar de vezes em um intervalo, atribua um valor aleatório grande a cada número. Calcule o XOR-soma do intervalo. Se o resultado não for zero, um número aparece um número ímpar de vezes; caso contrário, presume-se que não.
• Numb: Para provar a existência de um conjunto, tente encontrar outro conjunto que tenha uma correspondência um-para-um com o conjunto original, garantindo que não haja contagem dupla nem omissões.

11/7

• Artista:
  1. Para fusões em árvore de conjuntos, use fusão heurística. Lembre-se de swap(mp\[x\], mp\[y\]) em vez de swap(x, y). A operação swap em map é linear.
  2. Para contar estática ou dinamicamente quantos elementos distintos existem em um intervalo, use um map. Quando mp.size() == length, todos os elementos são distintos. Lembre-se de mp.erase(x) quando (--mp\[x\]) == 0.
  3. Alternativamente, para contar elementos distintos em um intervalo, registre lst\[i\] como a posição anterior onde o mesmo número em s\[i\] apareceu. Um intervalo \[l, r\] contém apenas elementos distintos se max(lst\[i\] for l <= i <= r) < l. lst\[i\] pode ser mantido dinamicamente com uma árvore de segmentos (embora isso possa levar a Time Limit Exceeded devido a constantes grandes).
• Árvore Preto e Branco:
  1. Quando $k$ é pequeno, pré-calcular $2^k$ pode economizar o fator $\log \mod$.
  2. Propriedade: Para qualquer diâmetro $x-y$ de uma árvore e qualquer ponto $u$, se $d = \max(\text{dist}(u, x), \text{dist}(u, y))$, então para qualquer outro ponto $v$ na árvore, $\text{dist}(u, v) \leq d$. A prova envolve considerar a distância de $u$ ao diâmetro.
• Esquema de Remoção de Arestas:

  1. Inversão Binomial: $q_T = \sum_{T \subseteq S} p_S \iff p_S = \sum_{S \subseteq T} (-1)^{|T|} q_T$. A prova é direta, por expansão.

  2. Enumerar todos os subconjuntos não vazios em ordem crescente: ```

     for(int s00 = s & (s - 1); s00; s00 = (s00 - 1) & s) { int s0 = s ^ s00; // ... }

11/13

• Conteúdo da Palestra:
  • ARC101E Ribbons on Tree: Inclusão-exclusão em árvores, com DP baseada em arestas.
  • WF16 A Balanced Diet: Para uma sequência com limites inferiores e superiores em cada elemento, considere prmieiro satisfazer os limites inferiores; os limites superiores podem ser automaticamente satisfeitos.
  • Problema de Origem Desconhecida: A área de união de retângulos em expansão pode ser uma função quadrática do tempo. A interpolação pode ser usada para encontrar os coeficientes.
  • HDU6978 New Equipments II: Para problemas de fluxo de custo em grafos bipartidos onde apenas algumas arestas podem não existir, considere remover os nós já visitados.
• Lagarta:
  1. Para calcular a soma de nós em uma árvore, excluindo subárvores e ancestrais, use duas DFS. A primeira percorre as arestas de saída em ordem direta, e a segunda em ordem reversa. Mantenha uma variável global; atribua-a a um nó ao chegar e atualize-a ao sair.
  2. Base de XOR Linear: Use um array a\[64\], onde a\[i\] armazena o número com o bit mais significativo em $i$. Inserções e mesclagens são muito simples.

11/14

• Números:
  1. Problemas relacionados à teoria dos números às vezes podem confiar em complexidades de tempo "místicas"; algoritmos aparentemente falhos podem passar em 95% dos casos.
  2. A divisão de números é útil. Use o algoritmo A para $g \leq 100$, B para $g \geq 10^7$, e C para o restante. Ajuste o tamanho do bloco; usar A para $g \leq 10^4$ e B para $g > 10^4$ levou a 95% de sucesso.
• Viagem:

  1. Um algoritmo $O(n^2)$ pode passar com $n^2$ na ordem de um milhão. Vale a pena implementar, mesmo que apenas para 60% da pontuação.

  2. Método de limpeza $O(1)$ para árvores de Fenwick: ```

     class FTree { int n, w, c[N * 2]; int his[N], hcnt;

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

     public: void init(int _n) { n = _n; hcnt = 1; }

      void poke(int p, int x) {
          while (p <= n) {
              if (his[p] != hcnt) {
                  his[p] = hcnt;
                  c[p] = 0;
              }
              c[p] += x;
              p += lowbit(p);
          }
      }
     
      int peek(int p) const {
          int res = 0;
          while (p) {
              if (his[p] == hcnt) res += c[p];
              p -= lowbit(p);
          }
          return res;
      }
     
      void clear() {
          hcnt++;
      }
     

     };

  3. Evite usar #define int long long cegamente. Escreva-o inicialmente e, após concluir o programa, revise quais partes podem usar int. Isso resultará em uma melhoria significativa de velocidade, especialmente em hardware mais antigo.

  4. Evite vector se possível, especialmente vetores unidimensionais, pois isso também pode melhorar a velocidade.

• Strings: Ao definir estados de DP, distinga claramente o que cada estado representa, especialmente se $f[k]$ com $k=n$ representar todos os casos onde $k \geq n$. Nesses casos, use transições progressivas para evitar a omissão de casos.
• Torneio: Não pense demais no problema.

11/21

• Você ainda não guiou a luz?: Ao retirar números de várias sequências, garantindo que a soma seja sempre $\geq 0$, faça um passe progressivo (garantindo que cada soma parcial seja $\geq 0$ e calculando os valores iniciais necessários) e depois um passe reverso (calcule a soma total, negue os números na sequência e processe de trás para frente). Isso funciona porque, após o passe progressivo, a soma restante é $< 0$; ao negá-la, torna-se $> 0$, permitindo o processamento reverso. Condições de impossibilidade: 1) A soma total é $< 0$; 2) Em algum momento, não é possível retirar mais números, seja no passe progressivo ou reverso.
• Jogo de Adivinhação: Para adivinhar um número em $[1, n]$ com busca binária, o número de tentativas necessárias é $\lfloor \log_2(n+1) \rfloor$, não $\lfloor \log_2(n) \rfloor$.

11/22

• Jogo de Adivinhação: Uma técnica poderosa é inverter o domínio de valores e uma dimensão do DP. Se o número de estados de $f(i, j, k)$ for muito grande, mas o intervalo de valores de $f(i, j, k)$ for pequeno, defina $g(i, j, x)$ como o menor $k$ tal que $f(i, j, k) \leq x$. Isso é chamado de inversão de domínio de valores. As transições após a inversão de domínio de valores podem lidar com a monotonicidade da transição original simultaneamente. Durante o processamento, adicione muitos comentários para indicar se cada termo está aumentando ou diminuindo. É melhor escrever um pequeno trecho de código para verificar.

11/26

• Grafos Não Direcionados Simples: Para problemas como "dada $l_1, r_1, l_2, r_2$, conecte uma aresta de $x$ para $y$ onde $l_1 \leq x \leq r_1$ e $l_2 \leq y \leq r_2$", a abordagem comum é transformar isso em um problema de adição de 1 em retângulos e resolvê-lo com uma linha de varredura. Em problemas com muitas arestas dadas de forma implícita, a transformação para o grafo complementar pode ser muito eficaz.

• Vira-tempo Dourado: Para manter dinamicamente segmentos, encontrando e excluindo todos os segmentos que se intersectam com um dado segmento: ```

  set< pair >::iterator it = st.lower_bound(make_pair(y1, -MAX));

  if (it != st.begin()) { it--; if ((*it).second < y1) it++; }

  while (it != st.end() && (*it).first <= y2) { y1 = min(y1, (*it).first); y2 = max(y2, (*it).second); st.erase(it++); }

  st.insert(make_pair(y1, y2));

11/28

• Combinações: Ao enumerar combinações, é melhor fixar um ponto e depois enumerar os outros. A abordagem ${n \choose 3}$ pode levar a contagens repetidas difíceis de gerenciar.
• Conectividade: Técnica importante: Interpolação de Lagrange. Particularmente útil para problemas de mochila, especialmente mochila em árvores. Se uma forma de convolução como $f_{u,i}=\sum_{v_1,v_2,\dots,v_s \in son(u)} \sum_{j_1+j_2+\dots+j_s=i} {f_{v_1,j_1}f_{v_2,j_2}\dots f_{v_s,j_s}}$ aparecer, defina $F(u,x) = \sum_{i=1}^{n} f_{u,i} x^i$. Então, $F(u,x)=\prod_{v \in son(u)} F(v,x)$. O grau de $F(u,x)$ é no máximo $n$. Registrar os valores de $F(u,x)$ em $x=0, 1, \dots, n$ permite transições em $O(n^2)$ em vez de $O(n^3)$. Ao "decodificar", se você precisar dos coeficientes de um polinômio, pré-calcule os coeficientes $d_k$ de $\prod_{j \neq i}{\frac{x-j}{i-j}}$. Então, para um $u$, $[x^k]F(u,x) = \sum_{x=0}^{n}{d_k y_k}$. Se os coeficientes não forem necessários, aplique diretamente a fórmula de interpolação de Lagrange. Como calcular $\prod_{j \neq i}{\frac{x-j}{i-j}}$? 1. Pré-calcule $\frac{1}{i!}$ para os denominadores. 2. Calcule o polinômio $s(x)=x(x-1)\dots(x-n)$ em $O(n^2)$. 3. Para $i=0, 1, \dots, n$, calcule $\frac{s(x)}{x-i}$ em $O(n)$ usando divisão longa.
• Sequência de Operações: Use o princípio de normalização.

11/30

• Número de Árvores: Técnica importante: Decomposição por Cadeia Longa. A decomposição por cadeia longa associa a cada nó um filho longo (o filho que leva ao nó mais profundo). A vantagem é que, para DPs onde a informação de um filho pode ser herdada em $O(1)$, herde a informação do filho longo em $O(1)$ e processe os outros filhos normalmente. A complexidade de tempo é $O(\sum_{u} \sum_{v \in son\_u} \text{len}_v) = O(n)$, onde $\text{len}_v$ é o comprimento da cadeia longa a partir de $v$. Que tipo de DP pode herdar em $O(1)$? Aqueles onde a informação mantida depende apenas da profundidade, como $f[u][j]$ (número de nós a uma distância $j$ de $u$) ou $g[u][j]$ (soma dos pesos dos nós a uma distância $j$ de $u$). Como herdar em $O(1)$? Mantenha um array de tamanho $O(n)$ e um ponteiro. Ao chegar ao cabeçal de uma cadeia longa $u$, aloque um espaço de comprimento $\text{len}_u$ para ele, ou seja, $f_u = \text{pos}$. Então, para o filho longo $son\_u$, defina $f_{son(u)} = f_u \pm 1$ para herdar informações dependentes da profundidade em $O(1)$. A diferença em árvores é útil com decomposição por cadeia longa.
• Concatenação: Técnica importante: Autômato de Sufixos. Um autômato de sufixos é um autômato mágico que aceita todos os subsegmentos de uma string $s$. Ao usar um autômato de sufixos, evite processar nós em ordem decrescente de ID. As transições do autômato de sufixos nem sempre apontam de IDs menores para maiores. Use busca com memorização ou ordem topológica inversa!

12/2

• Experiência de Vida: Para problemas do tipo "uma sequência é boa se e somente se pode ser transformada em algo X; conte o número de sequências boas", defina uma função $f_a(x)$ para a sequência e encontre uma relação de recorrência entre $f_a(x)$ e o método de transformação. Se o domínio e o intervalo de valores de $f$ forem pequenos, divida a recorrência com base nos valores que $f_a(x)$ assume.

12/3

• Strings: Para determinar se os subsegmentos de uma string são isomorfos, calcule $last_i$ como a posição anterior a $i$ com o mesmo caractere que $s_i$. Verifique se as sequências $last$ dos subsegmentos são idênticas. Nota: Ao calcular a sequência $last$ para um subsegmento $[l, r]$, a sequência $last$ só pode ser calculada de trás para frente até $l$. Portanto, é necessário usar uma主席树 (árvore de prefixo persistente) ou um array de blocos persistente. Técnica importante: Array de Blocos Persistente. Basicamente, divida o array em blocos. Ao atualizar, use apenas um bloco para atualização. Registre cada bloco inteiro atualizado. Pré-processamento $O(n\sqrt{n})$, consulta $O(1)$. Para este problema, onde as consultas são usadas para ordenação, isso resulta em $O(n \log^2 n + n\sqrt{n})$, melhor do que usar uma árvore de prefixo persistente $O(n \log^3 n)$.

12/11

• P5024 [NOIP2018 Higher] Guardians of the Kingdom: Técnica importante: DP para Otimização de Matriz -> Árvore de Aumento de Nível. Algumas equações de transição de DP parecem difíceis de lidar com aumento de nível. Transforme-as em formato de matriz e use a associatividade para aumento de nível! Como determinar se uma multiplicação de matriz generalizada satisfaz a associatividade? Consulte: https://www.cnblogs.com/luckyblock/p/14430820.html Em suma, a multiplicação generalizada $\otimes$ deve ter distributividade sobre a adição generalizada $\oplus$, e a multiplicação generalizada $\otimes$ deve ser comutativa e associativa. Ou seja, $(a \oplus b) \otimes c = (a \otimes c) \oplus (b \otimes c)$ é sempre verdadeiro. Um exemplo clássico é $\oplus = \min, \otimes = +$, ou seja, $c(i, j) = \min(a(i, k) + b(k, j))$ (substituir por $\max$ também funciona). Pare de derivar fórmulas cegamente!