INVQUER - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Fenwick trees/segment trees

PROBLEM:

You’re given a permutation A.
Answer Q queries on it:

  • Given L and R, create a new array B where B_i = \text{clamp}(A_i, L, R).
  • Report the number of inversions in B.

EXPLANATION:

Consider two indices i and j, i \lt j.
Let’s analyze how their relative values change with respect to L and R.

  • If A_i \lt A_j, then no matter what the values of L and R are, we’ll have B_i \leq B_j.
    So, this pair of indices can never form an inversion.
  • If A_i \gt A_j, there are a few cases:
    • If L \lt A_i, then B_i \geq B_j, with equality only when L = R.
    • On the other hand, if L \geq A_i then we’ll have B_i = B_j = L.
    • If R \gt A_j, again B_i \geq B_j, with equality only when L = R.
    • If R \leq A_j, we’ll have B_i = B_j = R.

So, a pair of indices that don’t form an inversion in A, still won’t form an inversion in B.
A pair of indices that do form an inversion in A can either remain an inversion in B, or become a non-inversion.

In particular, given L and R, observe that the only inversions that become non-inversions are those with either both elements \leq L, or both elements \geq R.
Every other inversion will remain (except if L = R).

This in fact gives us a fairly simple solution.
Let \text{Inv} denote the number of inversions in A, \text{pre}_L denote the number of inversions in A when considering only elements \leq L, and \text{suf}_R denote the number of inversions when considering only elements \geq R.
The answer to query (L, R) is then just \text{Inv} - \text{pre}_L - \text{suf}_R.
As noted above, L = R is an edge case that doesn’t satisfy this: but for L = R the answer is trivially 0 since all elements will be equal.

Now, we need to compute the value of \text{Inv}, as well as every \text{pre}_L and \text{suf}_R.
Note that \text{Inv} = \text{pre}_N so that’s automatically handled by the latter anyway.

Let’s look at how the \text{pre}_L values can be computed. The \text{suf}_R values can be computed similarly.
First, we can initialize \text{pre}_L to \text{pre}_{L-1}, which takes care of all pairs with values \leq L-1.
We’re now left with only inversions involving L and an element smaller than L, which in turn is just the number of elements smaller than L which appear after it.

There are a couple of different ways of computing this.
For instance, one way is to maintain a “mark” array M, where M_i = 1 if A_i \leq L and M_i = 0 otherwise.
If we had such an array M, the value we’re looking for would just be M_{p+1} + M_{p+2} + \ldots + M_N, where p is the position of L, i.e. A_p = L.
Processing L in increasing order makes maintaining M trivial, since moving from L to L+1 just causes one element in M to change value from 0 to 1.
To do this quickly we need a data structure that supports point updates and range sum queries, which a fenwick tree or segment tree can handle.

Alternately, in C++ you can use order statistics trees which are luckily built in; other languages unfortunately don’t have this luxury.

TIME COMPLEXITY:

\mathcal{O}(N \log N + Q) per testcase.

CODE:

Editorialist's code (PyPy3) 
# https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/FenwickTree.py
class FenwickTree:
    def __init__(self, x):
        """transform list into BIT"""
        self.bit = x
        for i in range(len(x)):
            j = i | (i + 1)
            if j < len(x):
                x[j] += x[i]

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

    def query(self, end):
        """calc sum(bit[:end])"""
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x
        
for _ in range(int(input())):
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    pos = [0]*(n+1)
    for i in range(n): pos[a[i]] = i
    
    pref, suf = [0]*(n+1), [0]*(n+2)
    fen = FenwickTree([0]*n)
    for i in range(1, n+1):
        u = pos[i]
        pref[i] = pref[i-1] + i-1-fen.query(u)
        fen.update(u, 1)
    fen = FenwickTree([0]*n)
    for i in reversed(range(1, n+1)):
        u = pos[i]
        suf[i] = suf[i+1] + fen.query(u)
        fen.update(u, 1)
    
    while q > 0:
        l, r = map(int, input().split())
        if l == r: print(0)
        else: print(pref[n] - pref[l] - suf[r])
        q -= 1
1 Like