Infinite Inversions (Codeforces 540E)
Tags: Implement, trees

There is an infinite sequence consisting of all positive integers in the increasing order: p = {1, 2, 3, ...}. We performed n swap operations with this sequence. A swap(a, b) is an operation of swapping the elements of the sequence on positions a and b. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (i, j), that i < j and pi > pj.

Input: The first line contains a single integer n (1 ≤ n ≤ 105) — the number of swap operations applied to the sequence.Each of the next n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 109, ai ≠ bi) — the arguments of the swap operation.

Output: Print a single integer — the number of inversions in the resulting sequence.

Note: In the first sample the sequence is being modified as follows: . It has 4 inversions formed by index pairs (1, 4), (2, 3), (2, 4) and (3, 4).

Sample Inputs:
2
4 2
1 4

3
1 6
3 4
2 5

Sample Outputs:
4

15

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_sum(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
s = [0]
for (a, b) in ab:
    s.append(a)
    s.append(b)
s = list(set(sorted(s)))
s.sort()
d = dict()
l = len(s)
for i in range(l):
    d[s[i]] = i
x = [i for i in range(l)]
for (a, b) in ab:
    (u, v) = (d[a], d[b])
    (x[u], x[v]) = (x[v], x[u])
tree = [0] * (l + 5)
ans = 0
for i in x[::-1][:-1]:
    ans += get_sum(i)
    add(i, 1)
for i in range(1, l):
    j = x[i]
    ans += abs(s[i] - s[j])
    ans -= abs(i - j)
print(ans)

Solution (Python):
import sys
from collections import defaultdict

class BIT:

    def __init__(self, n):
        self.n = n
        self.tree = [0] * n

    def _get_sum(self, r):
        """"""
        result = 0
        while r > 0:
            result += self.tree[r - 1]
            r &= r - 1
        return result

    def get_sum(self, l, r):
        """"""
        return self._get_sum(r) - self._get_sum(l)

    def add(self, i, value=1):
        while i < self.n:
            self.tree[i] += value
            i |= i + 1
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
n = int(input())
swaps = []
for _ in range(n):
    (i, j) = map(int, input().split())
    swaps.append(i)
    swaps.append(j)
pos = defaultdict(list)
for (i, val) in enumerate(swaps):
    pos[val].append(i)
c = 0
prev = -1
compr = [0] * (2 * n)
decompr = {}
for val in sorted(swaps):
    if prev == val:
        continue
    for j in pos[val]:
        compr[j] = c
    decompr[c] = val
    c += 1
    prev = val
arr = list(range(c))
for t in range(n):
    (i, j) = (compr[t << 1], compr[t << 1 | 1])
    (arr[i], arr[j]) = (arr[j], arr[i])
bit = BIT(c)
total_inv = 0
for (i, val) in enumerate(arr):
    total_inv += bit.get_sum(val + 1, c)
    if i != val:
        total_inv += abs(decompr[val] - decompr[i]) - abs(val - i)
    bit.add(val)
print(total_inv)

Solution (Python):
""""""
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

    def wrapped_func(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
                continue
            stack.pop()
            if not stack:
                break
            to = stack[-1].send(to)
        return to
    return wrapped_func

def inp():
    return sys.stdin.readline().rstrip('\r\n')

def out(var):
    sys.stdout.write(str(var))

def lis():
    return list(map(int, inp().split()))

def stringlis():
    return list(map(str, inp().split()))

def sep():
    return map(int, inp().split())

def strsep():
    return map(str, inp().split())

def testcase(t):
    for pp in range(t):
        solve(pp)

def google(p):
    print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
    return a * b // gcd(a, b)

def power(x, y, p):
    y %= p - 1
    res = 1
    x = x % p
    if x == 0:
        return 0
    while y > 0:
        if y & 1 == 1:
            res = res * x % p
        y = y >> 1
        x = x * x % p
    return res

def ncr(n, r):
    return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i = i + 6
    return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

class FenwickTree:

    def __init__(self, x):
        """"""
        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):
        """"""
        while idx < len(self.bit):
            self.bit[idx] += x
            idx |= idx + 1

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

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

    def printpref(self):
        out = []
        for i in range(len(self.bit) + 1):
            out.append(self.query(i))
        print(out)

def solve(case):
    n = int(inp())
    op = []
    have = {}
    for i in range(n):
        (a, b) = sep()
        have[a] = 1
        have[b] = 1
        op.append((a, b))
    a = []
    for i in have:
        a.append(i)
    a = sorted(a)
    orpos = {}
    for i in have:
        orpos[i] = i
    pos = {}
    for i in range(len(a)):
        pos[a[i]] = i
    curr = 1
    mapper = {}
    for i in range(len(a)):
        mapper[a[i]] = curr
        curr += 1
    for (i, j) in op:
        (orpos[i], orpos[j]) = (orpos[j], orpos[i])
        (a[pos[i]], a[pos[j]]) = (a[pos[j]], a[pos[i]])
        (pos[i], pos[j]) = (pos[j], pos[i])
    for i in range(len(a)):
        a[i] = mapper[a[i]]
    mapp = {}
    for i in mapper:
        mapp[mapper[i]] = i
    ans = 0
    bit = FenwickTree([0] * (len(a) + 1))
    for i in range(len(a)):
        bit.update(a[i], 1)
        ans += i - bit.query(a[i])
        ans += abs(mapp[i + 1] - mapp[a[i]]) - abs(i + 1 - a[i])
    print(ans)
''
testcase(1)