Solução escrita por Márcio Vitor
Conhecimentos Prévios:
Subtarefa 2 ($N,Q \le 1000$) (7 pontos):
Para cada intervalo itere de $c_i$ a $t_i$ contando quantas vezes cada valor de $p$ aparece no intervalo e então conforme passamos por cada elemento vamos manter duas variavéis $cnt$, $val$ que será a contagem de quantas vezes o valor mais frequente aparece e qual é esse valor respectivamente.
Complexidade: $\mathcal{O}(N \cdot Q)$
Subtarefa 3 (No intervalo de $c=1$ a $t=N$, nenhuma quantidade se repete mais de duas vezes) (9 pontos):
perceba que o vetor completo tem apenas um pico ou seja ele apenas sobe e depois apenas desce
Como o intervalo completo começa subindo e termina descendo, pelas propriedades $2$ e $3$. ele sempre conterá o pico do array e portanto a resposta sempre será “$P[c]$ $2$” exceto quando c = pico do array e assim t = c+1, que nesse caso a resposta é “$P[c] – 1$ $1$”.
Complexidade: $\mathcal{O}(Q)$
Subtarefa 4 ($P_i \le 30$) (18 pontos):
Existem no máximo 31 valores possíveis que podem ser respostas (de $0 a 30$) então podemos manter 31 somas de prefixo que calculam quantas vezes o valor $x$ aparece no prefixo.
Então para cada intervalo iteramos $x$ de 0 a 30 contamos quantas vezes $x$ aparece e atualize a resposta conforme cada iteração
Complexidade: $\mathcal{O}(30 \cdot (N + Q))$
Subtarefa 5 ($N \le 10^5 e Q \le 10^5$) (30 pontos):
A principal observação para esse problema é que dois intervalos completos não podem se intercectar parcialmente, ou seja não existem dois intervalos completos $L_1,R_1$ e $L_2,R_2$, com $L_1 \lt L_2 \le R_1$ e $R_2 \gt R_1$.
Prova:
Seja $L_1,R_1$ e $L_2,R_2$ dois intervalos completos que se interctam parcialmente, em que $L_1 \lt L_2$, note que $L_2 \lt R_1-1$, pois $p[R_1-2] \gt p[R_1-1] \gt P[R_1]$.
Dessa forma, $P[L_2] \ge P[L_1]$ e como $P[R_1] \lt P[L_1] \implies R_1 \le R_2$, contradizendo que os intervalos se interceptam parcialmente.
Assim os intervalos completos formam uma estrutura de árvore em que intervalos menores se juntam para virarem intervalos maiores, isso nos da a intuição de usar small-to-large para combinar “sub-árvores”.
Inicie com $N$ folhas sendo os intervalos e guardamos para cada um deles os limites $L,R$, seu tamanho e dois $set<pair<int,int>>$ guardando ${val, cnt}$ e o outro ${-cnt,val}$(chame-os de $set1$ e $set2$ por exemplo. Assim para um intervalo a resposta do nosso problema vai ser o primeiro elemento do $set2$ similar a ideia da subtarefa 2.
Ordenes os intervalos em ordem crescente de tamanho e itere por cada um e então caso esse intervalo já esteja presente nos que calculamos pegue a resposta dele, caso contrário junte o primeiro com o segundo sub intervalos contidos em $C_i,T_i$ (para mais detalhes olhe o código abaixo).
Complexidade: $\mathcal{O}(Q \cdot log_2(Q) + N \cdot log_2^2{N})$
Subtarefa 6 (Sem restrições adicionais) (100 pontos):
Para otimizar vamos ter que melhorar a forma que juntamos dois intervalos.
ao invés de guardar dois $set$’s vamos manter um $pair<int,int> = {-cnt, val}$ ao invés do $set1$ e então toda vez que adicionamos um elemento no intervalo atualizamos a resposta caso precisamos.
para manter a contagem de cada elemento vamos manter um $deque<int>$ em que a i-ésima posição guarda quantos vezes o elemento $mn + i$ aparece no intervalo onde $mn$ é o minimo no mesmo.
Dessa forma podemos juntar intervalos em $O(1)$ em média, note que a deque do std por debaixo dos panos usa um $map$ então para não estorar os limites de memória eu codei uma na mão usando $vector$.
Complexidade: $\mathcal{O}(Q \cdot log_2(Q) + N \cdot log_2{N})$