Maximum Crossings (Easy Version) (Codeforces 1676H1)
Tags: Others, brute force

The only difference between the two versions is that in this version $$$n \leq 1000$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.A terminal is a row of $$$n$$$ equal segments numbered $$$1$$$ to $$$n$$$ in order. There are two terminals, one above the other. You are given an array $$$a$$$ of length $$$n$$$. For all $$$i = 1, 2, \dots, n$$$, there should be a straight wire from some point on segment $$$i$$$ of the top terminal to some point on segment $$$a_i$$$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $$$n=7$$$ and $$$a=[4,1,4,6,7,7,5]$$$.  A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.What is the maximum number of crossings there can be if you place the wires optimally?

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the length of the array.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.The sum of $$$n$$$ across all test cases does not exceed $$$1000$$$.

Output: For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.

Note: The first test case is shown in the second picture in the statement.In the second test case, the only wiring possible has the two wires cross, so the answer is $$$1$$$.In the third test case, the only wiring possible has one wire, so the answer is $$$0$$$.

Sample Inputs:
4
7
4 1 4 6 7 7 5
2
2 1
1
1
3
2 2 2

Sample Outputs:
6
1
0
3

Solution (Python):
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound

class FenwickTree:

    def __init__(self, x):
        bit = self.bit = list(x)
        size = self.size = len(bit)
        for i in range(size):
            j = i | i + 1
            if j < size:
                bit[j] += bit[i]

    def update(self, idx, x):
        while idx < self.size:
            self.bit[idx] += x
            idx |= idx + 1

    def __call__(self, end):
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x

    def find_kth(self, k):
        idx = -1
        for d in reversed(range(self.size.bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < self.size and self.bit[right_idx] <= k:
                idx = right_idx
                k -= self.bit[idx]
        return (idx + 1, k)

class SortedList:
    block_size = 700

    def __init__(self, iterable=()):
        self.macro = []
        self.micros = [[]]
        self.micro_size = [0]
        self.fenwick = FenwickTree([0])
        self.size = 0
        for item in iterable:
            self.insert(item)

    def insert(self, x):
        i = lower_bound(self.macro, x)
        j = upper_bound(self.micros[i], x)
        self.micros[i].insert(j, x)
        self.size += 1
        self.micro_size[i] += 1
        self.fenwick.update(i, 1)
        if len(self.micros[i]) >= self.block_size:
            self.micros[i:i + 1] = (self.micros[i][:self.block_size >> 1], self.micros[i][self.block_size >> 1:])
            self.micro_size[i:i + 1] = (self.block_size >> 1, self.block_size >> 1)
            self.fenwick = FenwickTree(self.micro_size)
            self.macro.insert(i, self.micros[i + 1][0])

    def pop(self, k=-1):
        (i, j) = self._find_kth(k)
        self.size -= 1
        self.micro_size[i] -= 1
        self.fenwick.update(i, -1)
        return self.micros[i].pop(j)

    def __getitem__(self, k):
        (i, j) = self._find_kth(k)
        return self.micros[i][j]

    def count(self, x):
        return self.upper_bound(x) - self.lower_bound(x)

    def __contains__(self, x):
        return self.count(x) > 0

    def lower_bound(self, x):
        i = lower_bound(self.macro, x)
        return self.fenwick(i) + lower_bound(self.micros[i], x)

    def upper_bound(self, x):
        i = upper_bound(self.macro, x)
        return self.fenwick(i) + upper_bound(self.micros[i], x)

    def _find_kth(self, k):
        return self.fenwick.find_kth(k + self.size if k < 0 else k)

    def __len__(self):
        return self.size

    def __iter__(self):
        return (x for micro in self.micros for x in micro)

    def __repr__(self):
        return str(list(self))
for i in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0
    S = SortedList([A[0]])
    for j in range(1, n):
        ans += len(S) - S.lower_bound(A[j])
        S.insert(A[j])
    print(ans)

Solution (Python):
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    res = [0]

    def merge(nums):
        if len(nums) == 1:
            return nums
        m = len(nums) // 2
        left = merge(nums[:m])
        right = merge(nums[m:])
        i = len(left) - 1
        j = len(right) - 1
        while i >= 0 and j >= 0:
            if left[i] >= right[j]:
                res[-1] += j + 1
                i -= 1
            else:
                j -= 1
        add = []
        i = 0
        j = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                add.append(left[i])
                i += 1
            else:
                add.append(right[j])
                j += 1
        if i < len(left):
            add += left[i:]
        if j < len(right):
            add += right[j:]
        return add
    merge(a)
    return res[-1]
t = int(input())
for _ in range(t):
    print(solve())

Solution (Python):
import sys
input = lambda : sys.stdin.readline().strip()
ans = 0

def mergeSort(arr):
    global ans
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]
        mergeSort(L)
        mergeSort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
                ans += len(L) - i
            k += 1
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    ans = 0
    mergeSort(l)
    print(ans)