Messenger Simulator (Codeforces 1288E)
Tags: Others, data structures

Polycarp is a frequent user of the very popular messenger. He's chatting with his friends all the time. He has $$$n$$$ friends, numbered from $$$1$$$ to $$$n$$$.Recall that a permutation of size $$$n$$$ is an array of size $$$n$$$ such that each integer from $$$1$$$ to $$$n$$$ occurs exactly once in this array.So his recent chat list can be represented with a permutation $$$p$$$ of size $$$n$$$. $$$p_1$$$ is the most recent friend Polycarp talked to, $$$p_2$$$ is the second most recent and so on.Initially, Polycarp's recent chat list $$$p$$$ looks like $$$1, 2, \dots, n$$$ (in other words, it is an identity permutation).After that he receives $$$m$$$ messages, the $$$j$$$-th message comes from the friend $$$a_j$$$. And that causes friend $$$a_j$$$ to move to the first position in a permutation, shifting everyone between the first position and the current position of $$$a_j$$$ by $$$1$$$. Note that if the friend $$$a_j$$$ is in the first position already then nothing happens.For example, let the recent chat list be $$$p = [4, 1, 5, 3, 2]$$$:   if he gets messaged by friend $$$3$$$, then $$$p$$$ becomes $$$[3, 4, 1, 5, 2]$$$;  if he gets messaged by friend $$$4$$$, then $$$p$$$ doesn't change $$$[4, 1, 5, 3, 2]$$$;  if he gets messaged by friend $$$2$$$, then $$$p$$$ becomes $$$[2, 4, 1, 5, 3]$$$. For each friend consider all position he has been at in the beginning and after receiving each message. Polycarp wants to know what were the minimum and the maximum positions.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — the number of Polycarp's friends and the number of received messages, respectively.The second line contains $$$m$$$ integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$) — the descriptions of the received messages.

Output: Print $$$n$$$ pairs of integers. For each friend output the minimum and the maximum positions he has been in the beginning and after receiving each message.

Note: In the first example, Polycarp's recent chat list looks like this:   $$$[1, 2, 3, 4, 5]$$$  $$$[3, 1, 2, 4, 5]$$$  $$$[5, 3, 1, 2, 4]$$$  $$$[1, 5, 3, 2, 4]$$$  $$$[4, 1, 5, 3, 2]$$$ So, for example, the positions of the friend $$$2$$$ are $$$2, 3, 4, 4, 5$$$, respectively. Out of these $$$2$$$ is the minimum one and $$$5$$$ is the maximum one. Thus, the answer for the friend $$$2$$$ is a pair $$$(2, 5)$$$.In the second example, Polycarp's recent chat list looks like this:   $$$[1, 2, 3, 4]$$$  $$$[1, 2, 3, 4]$$$  $$$[2, 1, 3, 4]$$$  $$$[4, 2, 1, 3]$$$ 

Sample Inputs:
5 4
3 5 1 4

4 3
1 2 4

Sample Outputs:
1 3
2 5
1 4
1 5
1 5

1 3
1 2
3 4
1 4

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')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
    return map(int, sys.stdin.readline().rstrip().split())

def RLL():
    return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
    return int(input())

def comb(n, m):
    return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
    return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

class BIT:

    def __init__(self, n):
        self.btree = [0] * (n + 1)
        self.n = n

    def lowbit(self, num):
        return num & -num

    def update(self, ind, val):
        while ind < self.n + 1:
            self.btree[ind] += val
            ind += self.lowbit(ind)

    def sum(self, ind):
        res = 0
        while ind:
            res += self.btree[ind]
            ind -= self.lowbit(ind)
        return res

def main():
    (n, m) = RL()
    arr = RLL()
    bt = BIT(n + m)
    mi = [i for i in range(n + 1)]
    ma = [i for i in range(n + 1)]
    for i in range(1, n + 1):
        bt.update(m + i, 1)
    rec = [i + m for i in range(n + 1)]
    pos = m
    for q in arr:
        mi[q] = 1
        ma[q] = max(ma[q], bt.sum(rec[q]))
        bt.update(pos, 1)
        bt.update(rec[q], -1)
        rec[q] = pos
        pos -= 1
    for i in range(1, n + 1):
        ma[i] = max(ma[i], bt.sum(rec[i]))
    for i in range(1, n + 1):
        print(mi[i], ma[i])
if __name__ == '__main__':
    main()

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
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 zerolist(n):
    return [0] * n

def nextline():
    out('\n')

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

def printlist(a):
    for p in range(0, len(a)):
        out(str(a[p]) + ' ')

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

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

def power(x, y, p):
    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 = 998244353

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, m) = sep()
    a = lis()
    for i in range(m):
        a[i] -= 1
    temp = [1 for i in range(n)]
    for i in range(m):
        temp.append(0)
    f = FenwickTree(temp)
    mn = [i for i in range(0, n)]
    for i in range(m):
        mn[a[i]] = 0
    mx = [i for i in range(n)]
    pos = [n - i - 1 for i in range(n)]
    for i in range(m):
        mx[a[i]] = max(mx[a[i]], n - f.query(pos[a[i]] + 1))
        f.update(pos[a[i]], -1)
        pos[a[i]] = i + n
        f.update(pos[a[i]], 1)
    for i in range(n):
        mx[i] = max(mx[i], n - f.query(pos[i] + 1))
    for i in range(n):
        print(mn[i] + 1, mx[i] + 1)
testcase(1)

Solution (Python):
import sys

class BIT:

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

    def add(self, i, value=1):
        (N, tree) = (self.N, self.tree)
        while i < N:
            tree[i] += value
            i |= i + 1

    def sum(self, r):
        """"""
        (N, tree) = (self.N, self.tree)
        result = 0
        while r > 0:
            result += tree[r - 1]
            r &= r - 1
        return result
input = sys.stdin.readline
(n, m) = map(int, input().split())
queries = [int(x) - 1 for x in input().split()]
bit = BIT(n + m)
pos = list(reversed(range(n)))
for i in range(n):
    bit.add(i)
mins = list(range(n))
maxs = list(range(n))
for (i, q) in enumerate(queries):
    p = pos[q]
    bit.add(p, value=-1)
    mins[q] = 0
    maxs[q] = max(maxs[q], n - 1 - bit.sum(p))
    p = n + i
    bit.add(p)
    pos[q] = p
for (i, p) in enumerate(pos):
    maxs[i] = max(maxs[i], n - 1 - bit.sum(p))
for i in range(n):
    sys.stdout.write(f'{mins[i] + 1} {maxs[i] + 1}\n')