Участник:Kachanov vv/YODANESS

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/YODANESS/

max_value = 30007
 
def get(position: int):
    s = 0
    while position > 0:
        s += background[position]
        position -= (position & -position)
    return s
 
def add(pos: int, value: int):
    while pos < max_value:
        background[pos] += value
        pos += (pos & -pos)
 
t = int(input())
for _ in range(t):
    word_count = int(input())
    incorrect = input().split()
    correct = input().split()
    positions = {}
    word_indexes = [0] * (word_count + 1)
    for idx, word in enumerate(incorrect, 1):
        positions[word] = idx
    for idx, word in enumerate(correct, 1):
        word_indexes[idx] = positions[word]
    background = [0] * max_value
    inv = 0
    for i in range(word_count, 0, -1):
        inv += get(word_indexes[i] - 1)
        add(word_indexes[i], 1)
    print(inv)