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

Solution (Python):
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
        
        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)

Solution (Python):
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))

Solution (Python):
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n=int(input())
uf=UnionFind(n)
arr=[list(map(int,input().split()))+[i+1] for i in range(n)]
arr=sorted(arr,key=lambda x:x[0])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if y<=ty:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if ty2<=ty:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
arr=sorted(arr,key=lambda x:x[1])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if x<=tx:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if tx2<=tx:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
arr=sorted(arr,reverse=True,key=lambda x:x[0])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if y>=ty:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if ty2>=ty:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
arr=sorted(arr,reverse=True,key=lambda x:x[1])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if x>=tx:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if tx2>=tx:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
for i in range(1,n+1):
  print(uf.Count(i))

Solution (Python):
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
        


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

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























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')

Solution (Python):
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

    
    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)

Solution (Python):
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))

Solution (Python):
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

N = int(input())
XYI = sorted([(*map(int, input().split()), i) for i in range(N)])

uf = UF(N)

pi = None
py = N+1
for x, y, i in XYI:
    if y>py: uf.union(i, pi)
    else:
        pi = i
        py = y

pi = None
py = 0
for x, y, i in reversed(XYI):
    if y<py: uf.union(i, pi)
    else:
        pi = i
        py = y

XYI = [(y, x, i) for x, y, i in XYI]
XYI.sort()

pi = None
py = N+1
for x, y, i in XYI:
    if y>py: uf.union(i, pi)
    else:
        pi = i
        py = y

pi = None
py = 0
for x, y, i in reversed(XYI):
    if y<py: uf.union(i, pi)
    else:
        pi = i
        py = y

for i in range(N):
    print(uf.size(i))

Solution (Python):
class DisjointSetUnion():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n

    def merge(self, a, b):
        
        
        x = self.leader(a)
        y = self.leader(b)
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]: x, y = y, x
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        return x

    def same(self, a, b):
        
        
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        
        x = a
        while self.par_size[x] >= 0:
            x = self.par_size[x]
        while self.par_size[a] >= 0:
            self.par_size[a] = x
            a = self.par_size[a]
        return x

    def size(self, a):
        
        return -self.par_size[self.leader(a)]

    def groups(self):
        leader_buf = [0] * self.n
        group_size = [0] * self.n
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            leader_buf[i] = self.leader(i)
            group_size[leader_buf[i]] += 1
        for i in range(self.n):
            res[leader_buf[i]].append(i)
        res = [res[i] for i in range(self.n) if res[i]]
        return res

class BinaryIndexedTree():  
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        idx += 1
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        idx += 1
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res



N = int(input())
T = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

uf = DisjointSetUnion(N)


X = [0] * N


Y = [0] * N

for i in range(N):
    x, y = T[i]
    X[x] = i
    Y[y] = i

bit1 = BinaryIndexedTree(N)





for i in range(N):
    
    sm = bit1.sum(T[X[i]][1])
    s = bit1.bisect_left(sm)
    if sm > 0 and s < T[X[i]][1]:
        uf.merge(Y[s], X[i]) 
    s = bit1.bisect_left(1)
    if s < T[X[i]][1]:
        uf.merge(Y[s], X[i])
    bit1.add(T[X[i]][1], 1) 

R = []

for i in range(N):
    x, y = T[i]
    R.append((N - 1 - x, N - 1 - y))

X2 = [0] * N
Y2 = [0] * N

for i in range(N):
    x, y = R[i]
    X2[x] = i
    Y2[y] = i

bit2 = BinaryIndexedTree(N)

for i in range(N):
    sm = bit2.sum(R[X2[i]][1])
    s = bit2.bisect_left(sm)
    if sm > 0 and s < R[X2[i]][1]:
        uf.merge(Y2[s], X2[i])
    s = bit2.bisect_left(1)
    if s < R[X2[i]][1]:
        uf.merge(Y2[s], X2[i])
    bit2.add(R[X2[i]][1], 1)

res = []

for i in range(N):
    res.append(uf.size(i))

print('\n'.join(map(str, res)))

Solution (Python):
from heapq import heappop, heappush


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


def solve(n, xy_list):

    
    xy_list_s = sorted(xy_list, key=lambda x: x[0])
    y_list_s = [xy[1] for xy in xy_list_s]

    
    uf = UnionFind(n)

    
    h = []
    for y in y_list_s:
        yp_list = [y]
        while len(h):
            p = heappop(h)
            if p < y:
                yp_list.append(p)
                uf.union(p, y)
            else:
                heappush(h, p)
                break
        heappush(h, min(yp_list))

    
    parent_n = [0] * n
    parent_cnt = [0] * (n + 1)
    for i in range(n):
        p = uf.find(xy_list[i][1])
        parent_n[i] = p
        parent_cnt[p] += 1

    return [parent_cnt[parent_n[i]] for i in range(n)]


def main():
    n = int(input())
    xy_list = [[0] * 2 for _ in range(n)]
    for i in range(n):
        x, y = map(int, input().split())
        xy_list[i][0] = x
        xy_list[i][1] = y
    res = solve(n, xy_list)
    for r in res:
        print(r)


def test():
    assert solve(4, [[1, 4], [2, 3], [3, 1], [4, 2]]) == [1, 1, 2, 2]
    assert solve(7, [[6, 4], [4, 3], [3, 5], [7, 1], [2, 7], [5, 2], [1, 6]]) == [3, 3, 1, 1, 2, 3, 2]


if __name__ == "__main__":
    test()
    main()

Solution (Python):
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)
        self.rank = [0] * (n + 1)

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N = int(input())
uf = UF_tree(N)
pos = []
for i in range(N):
    x, y = map(int, input().split())
    pos.append((x, y, i))

inf = N + 10  


stack = [(inf, N)]
pos.sort()
for _, y, i in pos:
    while stack[-1][0] < y:
        _, j = stack.pop()
        uf.unite(j, i)
    stack.append((y, i))
stack = [(-inf, N)]
for _, y, i in pos[::-1]:
    while stack[-1][0] > y:
        _, j = stack.pop()
        uf.unite(i, j)
    stack.append((y, i))



stack = [(inf, N)]
pos.sort(key=itemgetter(1))
for x, _, i in pos:
    while stack[-1][0] < x:
        _, j = stack.pop()
        uf.unite(i, j)
    stack.append((x, i))
stack = [(-inf, N)]
for x, _, i in pos[::-1]:
    while stack[-1][0] > x:
        _, j = stack.pop()
        uf.unite(i, j)
    stack.append((x, i))

for i in range(N):
    print(uf.size(i))

Solution (Python):
N, *XY = [int(_) for _ in open(0).read().split()]
X = XY[::2]
Y = XY[1::2]
y_k = {}
k_y = {}
for y, k in zip(Y, range(N)):
    y_k[y] = k
    k_y[k] = y


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rank = [0] * (n + 1)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

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


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


XY = sorted(zip(X, Y))
uf = UnionFind(N + 1)
stmin = SegmentTree([10**10] * (N + 1), min, 10**10)
stmax = SegmentTree([-10**10] * (N + 1), max, -10**10)
for x, y in XY:
    ymin = stmin.query(0, x)
    ymax = stmax.query(0, y)
    stmin.update(x, y)
    stmax.update(y, y)
    for y2 in (ymin, ymax):
        if abs(y2) != 10**10 and y > y2:
            uf.unite(y, y2)
stmin = SegmentTree([10**10] * (N + 1), min, 10**10)
stmax = SegmentTree([-10**10] * (N + 1), max, -10**10)
for x, y in XY[::-1]:
    ymin = stmin.query(y + 1, N + 1)
    ymax = stmax.query(x + 1, N + 1)
    stmax.update(x, y)
    stmin.update(y, y)
    for y2 in (ymin, ymax):
        if abs(y2) != 10**10 and y < y2:
            uf.unite(y, y2)
print('\n'.join(str(uf.size(k_y[k])) for k in range(N)))