Biblioteca Alfabetizada

Este problema foi inspirado pelo jogo Ex Libris (https://boardgamegeek.com/boardgame/201825/ex-libris).

O grau de desorganização descrito pelo problema também pode ser chamado de número de inversões. Como a ordenação dos livros é feita de forma lexicográfica, é questão de criar um vetor de pares associando o título de cada livro com o seu índice, ordenar este vetor, e extrair os índices, obtendo então uma permutação em que se podem contar as inversões. Pode-se dizer que fazendo esse processo estamos "comprimindo" os títulos de livros originais em números comparáveis.

Existem algumas maneiras diferentes de resolver o problema de contar inversões, incluindo o uso de árvores de Fenwick, árvore de segmentos ou MergeSort. Cuidado apenas para não tentar "reiniciar" as árvores por completo (até o limite de $$$10^5$$$ livros) em cada nova biblioteca, já que esse processamento vai passar do tempo limite ($$$10^{10}$$$ operações), restrinja-se a zerar apenas o intervalo que será utilizado. Todas elas rodam em tempo $$$\mathcal{O}(n \lg n)$$$, que não é mais do que já foi usado para ordenar cada biblioteca.

Em seguida, obtido a contagem de inversões de cada biblioteca, vem a parte talvez mais desafiadora que é entender como que os $$$K$$$ bibliotecários são distribuídos. O enunciado quer que você os distribua de tal maneira:

Fazendo essas contas usando long long, obtemos um valor para cada biblioteca que soma $$$K$$$. Lembre-se que se todas as bibliotecas estiverem organizadas, é só imprimir $$$n$$$ zeros, se você tentar dividir por $$$0$$$, vai receber um erro em tempo de execução.