Pashmak and Parmida's problem (Codeforces 459D)
Tags: Others, divide and conquer

Parmida is a clever girl and she wants to participate in Olympiads this year. Of course she wants her partner to be clever too (although he's not)! Parmida has prepared the following test problem for Pashmak.There is a sequence a that consists of n integers a1, a2, ..., an. Let's denote f(l, r, x) the number of indices k such that: l ≤ k ≤ r and ak = x. His task is to calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that f(1, i, ai) > f(j, n, aj).Help Pashmak with the test.

Input: The first line of the input contains an integer n (1 ≤ n ≤ 106). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output: Print a single integer — the answer to the problem.


Sample Inputs:
7
1 2 1 1 2 2 1

3
1 1 1

5
1 2 3 4 5

Sample Outputs:
8

1

0

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
b = list(map(int, input().split()))
d = dict()
pre = []
j = 0
while j <= n - 1:
    if b[j] in d.keys():
        d[b[j]] += 1
    else:
        d[b[j]] = 1
    pre.append(d[b[j]])
    j += 1
suff = []
d = dict()
j = n - 1
while j >= 0:
    if b[j] in d.keys():
        d[b[j]] += 1
    else:
        d[b[j]] = 1
    suff.append(d[b[j]])
    j += -1
suff.reverse()

def update(bit, index, val):
    l = len(bit)
    while index < l:
        bit[index] += val
        index += index & -1 * index

def getsum(bit, index):
    ans = 0
    while index > 0:
        ans += bit[index]
        index -= index & -1 * index
    return ans
l = len(pre)
bit = [0] * (max(suff) + 1)
res = 0
j = l - 1
while j >= 0:
    res += getsum(bit, pre[j] - 1)
    update(bit, suff[j], 1)
    j += -1
print(res)

Solution (Python):
import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque

def bootstrap(f, stack=[]):

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

class Graphs:

    def __init__(self):
        self.graph = graphDict(set)

    def add_edge(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs_utility(self, nodes, visited_nodes):
        visited_nodes.add(nodes)
        for neighbour in self.graph[nodes]:
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes)

    def dfs(self, node):
        Visited = set()
        self.dfs_utility(i, Visited)

    def bfs(self, node, f_node):
        count = float('inf')
        visited = set()
        level = 0
        if node not in visited:
            queue.append([node, level])
            visited.add(node)
        flag = 0
        while queue:
            parent = queue.popleft()
            if parent[0] == f_node:
                flag = 1
                count = min(count, parent[1])
            level = parent[1] + 1
            for item in self.graph[parent[0]]:
                if item not in visited:
                    queue.append([item, level])
                    visited.add(item)
        return count if flag else -1

class Tree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder(node, lis):
    if node:
        inorder(node.left, lis)
        lis.append(node.data)
        inorder(node.right, lis)
    return lis

def leaf_node_sum(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return root.data
    return leaf_node_sum(root.left) + leaf_node_sum(root.right)

def hight(root):
    if root is None:
        return -1
    if root.left is None and root.right is None:
        return 0
    return max(hight(root.left), hight(root.right)) + 1

class DisjointSets:

    def __init__(self, size: int) -> None:
        self.parents = [-1 for _ in range(size)]
        self.sizes = [1 for _ in range(size)]
        self._count = size

    @bootstrap
    def find(self, x: int) -> int:
        if self.parents[x] == -1:
            yield x
        self.parents[x] = (yield self.find(self.parents[x]))
        yield self.parents[x]

    def union(self, x: int, y: int) -> bool:
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return False
        self._count -= 1
        if self.sizes[x_root] < self.sizes[y_root]:
            (x_root, y_root) = (y_root, x_root)
        self.parents[y_root] = x_root
        self.sizes[x_root] += self.sizes[y_root]
        self.large = max(self.large, self.sizes[x_root])
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def count(self):
        return self._count

def rounding(n):
    return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
    return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0), []))

def p_sum(array):
    return list(itertools.accumulate(array))

def diophantine(a: int, b: int, c: int):
    (d, x, y) = extended_gcd(a, b)
    r = c // d
    return (r * x, r * y)

@bootstrap
def extended_gcd(a: int, b: int):
    if b == 0:
        (d, x, y) = (a, 1, 0)
    else:
        (d, p, q) = (yield extended_gcd(b, a % b))
        x = q
        y = p - q * (a // b)
    yield (d, x, y)
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, **kwargs):
        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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def inp():
    return sys.stdin.readline().strip()

def map_inp(v_type):
    return map(v_type, inp().split())

def list_inp(v_type):
    return list(map_inp(v_type))
fen_tree = [0 for it in range(10 ** 6 + 1)]

def update(index):
    while index < len(fen_tree):
        fen_tree[index] += 1
        index += index & -index

def query(index):
    s = 0
    while index > 0:
        s += fen_tree[index]
        index -= index & -index
    return s
n = int(inp())
arr = list_inp(int)
dic = collections.Counter()
left = []
right = []
ans = 0
for i in range(n):
    dic[arr[i]] += 1
    left.append(dic[arr[i]])
dic.clear()
for i in range(n)[::-1]:
    dic[arr[i]] += 1
    right.append(dic[arr[i]])
    if i < n - 1:
        ans += query(left[i] - 1)
    update(right[n - (i + 1)])
print(ans)

Solution (Python):
import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque

def bootstrap(f, stack=[]):

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

class Graphs:

    def __init__(self):
        self.graph = graphDict(set)

    def add_edge(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs_utility(self, nodes, visited_nodes):
        visited_nodes.add(nodes)
        for neighbour in self.graph[nodes]:
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes)

    def dfs(self, node):
        Visited = set()
        self.dfs_utility(i, Visited)

    def bfs(self, node, f_node):
        count = float('inf')
        visited = set()
        level = 0
        if node not in visited:
            queue.append([node, level])
            visited.add(node)
        flag = 0
        while queue:
            parent = queue.popleft()
            if parent[0] == f_node:
                flag = 1
                count = min(count, parent[1])
            level = parent[1] + 1
            for item in self.graph[parent[0]]:
                if item not in visited:
                    queue.append([item, level])
                    visited.add(item)
        return count if flag else -1

class Tree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder(node, lis):
    if node:
        inorder(node.left, lis)
        lis.append(node.data)
        inorder(node.right, lis)
    return lis

def leaf_node_sum(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return root.data
    return leaf_node_sum(root.left) + leaf_node_sum(root.right)

def hight(root):
    if root is None:
        return -1
    if root.left is None and root.right is None:
        return 0
    return max(hight(root.left), hight(root.right)) + 1

class DisjointSets:

    def __init__(self, size: int) -> None:
        self.parents = [-1 for _ in range(size)]
        self.sizes = [1 for _ in range(size)]
        self._count = size

    @bootstrap
    def find(self, x: int) -> int:
        if self.parents[x] == -1:
            yield x
        self.parents[x] = (yield self.find(self.parents[x]))
        yield self.parents[x]

    def union(self, x: int, y: int) -> bool:
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return False
        self._count -= 1
        if self.sizes[x_root] < self.sizes[y_root]:
            (x_root, y_root) = (y_root, x_root)
        self.parents[y_root] = x_root
        self.sizes[x_root] += self.sizes[y_root]
        self.large = max(self.large, self.sizes[x_root])
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def count(self):
        return self._count

def rounding(n):
    return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
    return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0), []))

def p_sum(array):
    return list(itertools.accumulate(array))

def diophantine(a: int, b: int, c: int):
    (d, x, y) = extended_gcd(a, b)
    r = c // d
    return (r * x, r * y)

@bootstrap
def extended_gcd(a: int, b: int):
    if b == 0:
        (d, x, y) = (a, 1, 0)
    else:
        (d, p, q) = (yield extended_gcd(b, a % b))
        x = q
        y = p - q * (a // b)
    yield (d, x, y)
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, **kwargs):
        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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def inp():
    return sys.stdin.readline().strip()

def map_inp(v_type):
    return map(v_type, inp().split())

def list_inp(v_type):
    return list(map_inp(v_type))
fen_tree = [0 for it in range(10 ** 6 + 1)]

def update(index):
    while index < len(fen_tree):
        fen_tree[index] += 1
        index += index & -index

def query(index):
    s = 0
    while index > 0:
        s += fen_tree[index]
        index -= index & -index
    return s
n = int(inp())
arr = list_inp(int)
dic = collections.Counter()
left = []
right = []
ans = 0
for i in range(n):
    dic[arr[i]] += 1
    left.append(dic[arr[i]])
dic.clear()
for i in range(n)[::-1]:
    dic[arr[i]] += 1
    right.append(dic[arr[i]])
    if i < n - 1:
        ans += query(left[i] - 1)
    update(right[n - (i + 1)])
print(ans)