Solução escrita por Márcio Vitor
Conhecimentos Prévios:
Subtarefa 2 ($N, M, Q \le 500$) (11 pontos):
Para cada consulta itere pelo seu sub-retângulo mantendo um vetor: $mark[i]$ que vai marcar se já passamos por um terreno de um certo dono $i$, inicialmente com zeros, caso encontremos alguém que não foi marcado ainda aumentamos a resposta para query e marque ele no vetor.
Complexidade: $\mathcal{O}(N \cdot M \cdot Q)$
Subtarefa 3 (A região pertence inteiramente a uma única linha da matriz) (16 pontos):
Vamos primeiro pensar em como resolver o problema para o caso em que a matriz é um vetor ou seja $N=1$, um pensamento que soa natural para esse problema é escolher um único quadrado “lider” para cada região da matriz. E em uma consulta $L,R$ contar a quantidade de lideres presentes usando soma de prefixo.
Se uma região de um dono está completamente dentro do intervalo da consulta, será contada normalmente. Mas regiões que estão parcialmente dentro da consulta podem ser que seus lideres. estejam fora e não sejam contabilizados.
Porém existem no máximo duas regiões que podem “escapar” da consulta, a região do quadrado $L$ e a região do quadrado $R$, então podemos olhar para cada uma das duas se seu lider não foi contado e nesse caso adicionar a resposta.
Assim podemos resolver esse caso $1D$ para cada uma das linhas da nossa consulta $l1, l1 +1, …, l2$, pois as regiões estão contidas em apenas uma linha
Complexidade: $\mathcal{O}(N \cdot M + Q \cdot N)$
Subtarefa 4 (o identi cador de cada região é um inteiro entre 1 e 50) (20 pontos):
Como temos no máximo 50 regiões diferentes para cada consulta podemos contar para cada região se ela tem interseção com o sub-retângulo.
Para isso vamos precalcular uma matriz de soma de prefixo para cada região i que conta quantos quadrados são do dono $i$
Assim para cada query $q$ itere pela região $i$ de $1$ a $50$ e calcule a quantidade de quadrados que dentro de ($l1_q$, $c1_q$) a ($l2_q$, $c2_q$) se for maior que 0 então vamos ter negociar com o dono dessa região pois algum terreno dele está na consulta.
Complexidade: $\mathcal{O}(N \cdot M \cdot X + Q \cdot X)$ onde X é a quantidade de regiões
Subtarefa 5 (Todas as opções estudadas pela empresa começam no canto
superior esquerdo do Condado (l1 = 1 e c1 = 1).) (22 pontos):
Essa subtarefa é bem parecida com a solução completa mas você não precisa conhecer o truque da soma de prefixo 2d, para calcular qualquer sub-retângulo, pois todos eles estão contidos no canto superior esquerdo.
Subtarefa 6 (Sem restrições adicionais) (100 pontos):
usando uma ideia similar da Subtarefa 3, vamos escolher um “líder” para cada região da matriz. E então usar uma soma de prefixo 2d pra contar quantos lideres estão no sub-retângulo de cada consulta.
Os únicos caras que podem estar de fora da contagem estão na borda do sub-retângulo, ou seja, basta iterar por essa borda e adicionar 1 na resposta para cada região que o líder está fora do sub-retângulo.
Complexidade: $\mathcal{O}(Q(N+M))$