Maximum Crossings (Hard Version) (Codeforces 1676H2)
Tags: Others, divide and conquer

The only difference between the two versions is that in this version $$$n \leq 2 \cdot 10^5$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.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 2 \cdot 10^5$$$) — 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 $$$2 \cdot 10^5$$$.

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):
def update(aib, pos, n):
    while pos <= n:
        aib[pos] = aib[pos] + 1
        pos += pos & -pos

def query(aib, pos):
    ans = 0
    while pos > 0:
        ans += aib[pos]
        pos -= pos & -pos
    return ans
t = int(input())
for tt in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    aib = [0] * (n + 1)
    for i in range(n):
        ans += i - query(aib, a[i] - 1)
        update(aib, a[i], n)
    print(ans)

Solution (Python):
def q(i):
    r = 0
    j = i
    while i > 0:
        r += g[i]
        i -= i & -i
    while j <= n:
        g[j] += 1
        j += j & -j
    return r
for f in range(int(input())):
    n = int(input())
    (s, g) = (0, [0] * (n + 1))
    for x in reversed(input().split()):
        s += q(int(x))
    print(s)

Solution (Python):
def q(i):
    r = 0
    j = i
    while i > 0:
        r += g[i]
        i -= i & -i
    while j <= n:
        g[j] += 1
        j += j & -j
    return r
for f in range(int(input())):
    n = int(input())
    (s, g) = (0, [0] * (n + 1))
    for x in reversed(input().split()):
        s += q(int(x))
    print(s)