Problem:

Score : 300 points

Problem Statement

There are N cities on a 2D plane. The coordinate of the i-th city is (x_i, y_i). Here (x_1, x_2, \dots, x_N) and (y_1, y_2, \dots, y_N) are both permuations of (1, 2, \dots, N).

For each k = 1,2,\dots,N, find the answer to the following question:

Rng is in City k.
Rng can perform the following move arbitrarily many times:

move to another city that has a smaller x-coordinate and a smaller y-coordinate, or a larger x-coordinate and a larger y-coordinate, than the city he is currently in.

How many cities (including City k) are reachable from City k?

Constraints

1 \leq N \leq 200,000

(x_1, x_2, \dots, x_N) is a permutation of (1, 2, \dots, N).

(y_1, y_2, \dots, y_N) is a permutation of (1, 2, \dots, N).

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print N lines. In i-th line print the answer to the question when k = i.

Sample Input 1

4
1 4
2 3
3 1
4 2

Sample Output 1

1
1
2
2

Rng can reach City 4 from City 3, or conversely City 3 from City 4.

Sample Input 2

7
6 4
4 3
3 5
7 1
2 7
5 2
1 6

Sample Output 2

3
3
1
1
2
3
2



Sample input:
4
1 4
2 3
3 1
4 2


Sample output:
1
1
2
2

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return self.sum(r-1) - self.sum(l-1)
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

    def bisearch_fore(self, l, r, x):
        """ 区間[l, r]を左から右に向かってx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF

    def bisearch_back(self, l, r, x):
        """ 区間[l, r]を右から左に向かってx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -INF

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
        self.tree = [True] * n
        self.grpcnt = n

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

    def union(self, x, y):
        """ 併合 """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        self.grpcnt -= 1
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N = INT()
XY = []
XtoY = [0] * (N+1)
YtoI = [0] * (N+1)
for i in range(N):
    x, y = MAP()
    XY.append((x, y))
    XtoY[x] = (y, i)
    YtoI[y] = i

bit = BIT(N+1)
uf = UnionFind(N)
for i in range(1, N+1):
    bit.add(i, 1)
for x in range(1, N+1):
    y, i = XtoY[x]
    cury = y
    while 1:
        nxty = bit.bisearch_fore(cury+1, N, 1)
        if nxty == INF:
            break
        else:
            j = YtoI[nxty]
            if uf.is_same(i, j):
                break
            else:
                uf.union(i, j)
                cury = nxty
    bit.add(y, -1)

for i in range(N):
    ans = uf.get_size(i)
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# import bisect
# import heapq
# import math
# import random
# from collections import Counter, defaultdict, deque
# from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
# from fractions import Fraction
# from functools import lru_cache, reduce
# from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
# from operator import add, mul, sub, itemgetter, attrgetter
from collections import defaultdict

import sys
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 63


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        # ep('u', i, v)
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])
        # ep(self.__tree[self.__size:])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]

    def p(self):
        ep(self.__tree[self.__size:])


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
            return x
        else:
            a = x
            ul = []
            while a != self.__table[a]:
                ul.append(a)
                a = self.__table[a]
            for u in ul:
                self.__table[u] = a

        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        # ep(x, y)
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


def ref(N, XY):

    uf = UnionFind()
    for i in range(N):
        xi, yi = XY[i]
        for j in range(i+1, N):
            xj, yj = XY[j]
            if xj < xi and yj < yi or xj > xi and yj > yi:
                uf.union(i, j)

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.size(i)

    return ans


@mt
def slv(N, XY):
    xyi = [(x, y, i) for i, (x, y) in enumerate(XY)]
    xyi.sort()

    y2i = {}
    y2x = {}
    x2y = {}
    # ia = [INF] * (N+1)
    for x, y, i in xyi:
        y2i[y] = i
        y2x[y] = x
        x2y[x] = y
        # ia[y] = y
    ia = list(range(N+1))
    ia[0] = INF
    styr = SegmentTree(ia, min, INF)

    uf = UnionFind()
    for x, y, i in xyi:
        a = y
        mx = 0
        my = 0
        styr.update(y, INF)
        while True:
            v = styr.query(a+1, N+1)
            if v == INF:
                break
            j = y2i[v]
            uf.union(i, j)
            styr.update(v, INF)
            a = v
            mx = max(mx, y2x[v])
            my = max(my, v)

        if mx > x:
            styr.update(x2y[mx], my)
            y2i[my] = i

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.size(i)

    return ans


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(*slv(N, XY), sep='\n')

    # from random import shuffle
    # N = 2 * 10**5
    # X = list(range(1, N+1))
    # Y = list(range(1, N+1))
    # shuffle(X)
    # shuffle(Y)
    # XY = list(zip(X, Y))
    # # XY = [(2, 5), (1, 3), (3, 2), (5, 1), (4, 4)]
    # b = slv(N, XY)

    # for _ in range(1000):
    #     from random import shuffle
    #     # N = 2 * 10**5
    #     N = 5
    #     X = list(range(1, N+1))
    #     Y = list(range(1, N+1))
    #     shuffle(X)
    #     shuffle(Y)
    #     XY = list(zip(X, Y))
    #     # XY = [(2, 5), (1, 3), (3, 2), (5, 1), (4, 4)]
    #     a = ref(N, XY)
    #     b = slv(N, XY)
    #     if a != b:
    #         ep('-----')
    #         ep(N)
    #         ep(XY)
    #         ep('a', a)
    #         ep('b', b)
    #         break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
belong=list()
group=list()
def init(X):
  global belong
  global group
  belong=list(range(X))
  group=[[i] for i in range(X)]

def unite(x,y):
  if len(group[belong[x]])<len(group[belong[y]]):
    x,y=y,x
  if belong[x]==belong[y]:
    return True
  z=belong[y]
  for i in range(len(group[z])):
    belong[group[z][-1]]=belong[x]
    group[belong[x]].append(group[z][-1])
    del group[z][-1]
  return False

N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
for i in range(N):
  X[i].append(i)
X.sort()
init(N)
Q=[]
heapify(Q)
v=0
heappush(Q,(X[0][1],X[0][2]))
for i in range(1,N):
  v=Q[0]
  while len(Q):
    if Q[0][0]<X[i][1]:
      unite(X[i][2],Q[0][1])
      heappop(Q)
    else:
      break
  if len(Q)==0:
    heappush(Q,v)
  if Q[0]!=v:
    heappush(Q,v)
  heappush(Q,(X[i][1],X[i][2]))
for i in range(N):
  print(len(group[belong[i]]))

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return self.sum(r-1) - self.sum(l-1)
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

    def bisearch_fore(self, l, r, x):
        """ 区間[l, r]を左から右に向かってx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF

    def bisearch_back(self, l, r, x):
        """ 区間[l, r]を右から左に向かってx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -INF

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
        self.tree = [True] * n
        self.grpcnt = n

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

    def union(self, x, y):
        """ 併合 """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        self.grpcnt -= 1
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N = INT()
XY = []
XtoY = [0] * (N+1)
YtoI = [0] * (N+1)
for i in range(N):
    x, y = MAP()
    XY.append((x, y))
    XtoY[x] = (y, i)
    YtoI[y] = i

bit = BIT(N+1)
uf = UnionFind(N)
for i in range(1, N+1):
    bit.add(i, 1)
for x in range(1, N+1):
    y, i = XtoY[x]
    cury = y
    while 1:
        nxty = bit.bisearch_fore(cury+1, N, 1)
        if nxty == INF:
            break
        else:
            j = YtoI[nxty]
            if uf.is_same(i, j):
                break
            else:
                uf.union(i, j)
                cury = nxty
    bit.add(y, -1)
    if uf.get_size() == 1:
        break

for i in range(N):
    ans = uf.get_size(i)
    print(ans)

Submission status: Accepted

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n=int(input())
points=[]
uf=UnionFind(n)
for i in range(n):
  x,y=map(int,input().split())
  points.append([x,y,i])
points=sorted(points, key=lambda student: student[0])
minimum=n+1
index=-1
for i in range(n):
  if points[i][1]<minimum:
    minimum=points[i][1]
    index=i
  else:
    uf.union(points[index][2],points[i][2])
maximum=0
index=-1
for i in range(n-1,-1,-1):
  if points[i][1]>maximum:
    maximum=points[i][1]
    index=i
  else:
    uf.union(points[index][2],points[i][2])
points=sorted(points, key=lambda student: student[1])
minimum=n+1
index=-1
for i in range(n):
  if points[i][0]<minimum:
    minimum=points[i][0]
    index=i
  else:
    uf.union(points[index][2],points[i][2])
maximum=0
index=-1
for i in range(n-1,-1,-1):
  if points[i][0]>maximum:
    maximum=points[i][0]
    index=i
  else:
    uf.union(points[index][2],points[i][2])
for i in range(n):
  print(uf.size(i))

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return x

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1


max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(points):
    N = len(points)
    XI = [0]*N
    YI = [0]*N

    for i,(x,y) in enumerate(points):
        XI[x] = i
        YI[y] = i

    ds = DisjointSet(N)

    offset = N
    y_max_connected = -1
    rep = -1
    for i in YI:
        x0,y0 = points[i]
        if x0 >= offset:
            continue

        t = y0
        for j in XI[x0+1:offset]:
            x,y = points[j]
            if y >= y0:
                ds.union(i,j)
                t = max2(t, y)
        offset = x0

        if y_max_connected >= y0:
            ds.union(rep, i)
            y_max_connected = max2(y_max_connected,t)
        else:
            y_max_connected = t
            rep = i
        # print(y0, y_max_connected)


    cnt = [0]*N
    for i in range(N):
        cnt[ds.find(i)] += 1

    return [cnt[ds.find(i)] for i in range(N)]

# import numpy as np
# from itertools import combinations
# def naive(points):
#     N = len(points)
#     grid = np.zeros((N,N), dtype=bool)
#     for x,y in points:
#         grid[x,y] = True
#     ds = DisjointSet(N)
#     for i,j in combinations(range(N),2):
#         x0,y0 = points[i]
#         x1,y1 = points[j]
#         if np.any(grid[max(x0,x1):,max(y0,y1):]) or np.any(grid[:min(x0,x1),:min(y0,y1)]):
#             ds.union(i,j)

#     cnt = [0]*N
#     for i in range(N):
#         cnt[ds.find(i)] += 1

#     return [cnt[ds.find(i)] for i in range(N)]

# from random import shuffle

if __name__ == '__main__':
    N = int(readline())
    m = map(lambda x: int(x)-1, read().split())

    points = tuple(zip(m,m))

    print(*solve(points), sep='\n')

    # N = 12

    # X = list(range(N))
    # for k in range(100000):
    #     if k % 10000:
    #         print(k)
    #     Y = list(range(N))
    #     shuffle(Y)
    #     points = [(x,y) for x,y in zip(X,Y)]
    #     r1,r2 = solve(points),naive(points)
    #     if r1 != r2:
    #         print(Y)
    #         print(r1)
    #         print(r2)
    #         break

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

uf_t = numba.types.UniTuple(i8[:], 2)


@njit((uf_t, i8), cache=True)
def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


@njit((uf_t, i8, i8), cache=True)
def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8[:], ), cache=True)
def main(XY):
    N = len(XY) // 2
    root = np.arange(N + 1, dtype=np.int64)
    size = np.ones_like(root)
    uf = (root, size)

    XtoY = np.zeros(N + 1, np.int64)
    YtoX = np.zeros(N + 1, np.int64)
    for i in range(0, N + N, 2):
        x, y = XY[i:i + 2]
        XtoY[x] = y
        YtoX[y] = x

    # 残してある y 座標集合を bit で管理
    bit_raw = np.ones(N + 1, np.int64)
    bit_raw[0] = 0
    bit = build(bit_raw)
    rest_Y = np.ones(N + 1, np.int64)
    rest_Y_cnt = N
    for x in range(1, N + 1):
        y = XtoY[x]
        if not rest_Y[y]:
            continue
        k = get_sum(bit, y)
        largest_x = x
        for i in range(k + 1, rest_Y_cnt + 1):
            y1 = find_kth_element(bit, i)
            x1 = YtoX[y1]
            merge(uf, x, x1)
            largest_x = max(largest_x, x1)
        for i in range(k + 1, rest_Y_cnt + 1):
            y1 = find_kth_element(bit, k + 1)
            x1 = YtoX[y1]
            if x1 != largest_x:
                rest_Y[y1] = 0
                rest_Y_cnt -= 1
                add(bit, y1, -1)
        rest_Y[y] = 0
        rest_Y_cnt -= 1
        add(bit, y, -1)
    for i in range(0, N + N, 2):
        x, y = XY[i:i + 2]
        rx = find_root(uf, x)
        print(size[rx])

N = int(readline())
XY = np.array(read().split(), np.int64)

main(XY)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

        
class SegTree:
    
    __slots__ = ["n", "data", "f", "id"]
    
    def __init__(self, li, func, identity):
        self.n = len(li)
        self.f = func
        self.id = identity
        self.data = [self.id]*self.n + li
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def get(self, i):
        return self.data[i+self.n]
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i //= 2
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = self.id
        while l < r:
            if l % 2:
                res = self.f(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = self.f(res, self.data[r])
            l //= 2
            r //= 2
        return res
    
    def max_right(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l % 2:
                left_li.append(l)
                l += 1
            if r % 2:
                r -= 1
                right_li.append(r)
            l //= 2
            r //= 2
        temp = self.id
        for idx in (left_li + right_li[::-1]):
            if not check(self.f(temp, self.data[idx])):
                temp = self.f(temp, self.data[idx])
            else:
                break
        else:
            return -1
        while idx < self.n:
            if check(self.f(temp, self.data[2*idx])):
                idx = 2*idx
            else:
                temp = self.f(temp, self.data[2*idx])
                idx = 2*idx+1
        return idx - self.n
    
    def min_left(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l % 2:
                left_li.append(l)
                l += 1
            if r % 2:
                r -= 1
                right_li.append(r)
            l //= 2
            r //= 2
        temp = self.id
        for idx in (right_li + left_li[::-1]):
            if not check(self.f(self.data[idx], temp)):
                temp = self.f(self.data[idx], temp)
            else:
                break
        else:
            return -1
        while idx < self.n:
            if check(self.f(self.data[2*idx+1], temp)):
                idx = 2*idx+1
            else:
                temp = self.f(temp, self.data[2*idx+1], temp)
                idx = 2*idx
        return idx - self.n


n = int(input())
XY = [list(map(int, input().split())) for _ in range(n)]
uf = UnionFind(n)
def f(XY):
  
  Y = [-1]*n
  for i, (x, y) in enumerate(XY):
      Y[x-1] = (i, y)
  seg_max = SegTree([-1]*n, max, -1)
  seg_min = SegTree([n+1]*n, min, n+1)
  idx = dict()
  for x, (i, y) in enumerate(Y):
      t = seg_max.fold(0, y-1)
      if t != -1:
          j = idx[t]
          uf.unite(i, j)
      seg_max.update(y-1, x)
      idx[x] = i
  for x in range(n-1, -1, -1):
      i, y = Y[x]
      t = seg_min.fold(y-1, n)
      if  t != n+1:
          j = idx[t]
          uf.unite(i, j)
      seg_min.update(y-1, x)
        
f(XY)
YX = [(y, x) for x, y in XY]
f(YX)
for i in range(n):
  print(uf.size(i))