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
from collections import defaultdict

readline = sys.stdin.buffer.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 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):
        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


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

    l = []
    uf = UnionFind()
    for _, y, i in xyi:
        my = y
        while len(l) >= 1 and l[-1][0] < y:
            yy, j = l.pop()
            uf.union(i, j)
            my = min(my, yy)

        l.append((my, i))
    ans = [-1] * 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')


if __name__ == '__main__':
    main()

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 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())
Network = UnionFind(N)

XYi = []
for i in range(N):
    X,Y = list(map(int,input().split()))
    ind = i
    XYi.append([X,Y,ind])
XYi.sort(key=lambda x:x[0])

import heapq
q = []
heapq.heapify(q)
for i in range(N):
    X,Y,ind = XYi[i]
    minY = Y
    while q and q[0][0] < Y:
        jY, j = heapq.heappop(q)
        minY = min(jY, minY)
        Network.union(ind, j)
    heapq.heappush(q, [minY, Network.find(ind)])
for i in range(N):
    print(Network.size(i))

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = 10**10

    
    class UnionFind:
        def __init__(self, numV):
            self.pars = list(range(numV))
            self.ranks = [0] * numV
        def getRoot(self, x):
            par = self.pars[x]
            if par != x:
                self.pars[x] = par = self.getRoot(par)
            return par
        def merge(self, x, y):
            x, y = self.getRoot(x), self.getRoot(y)
            if x == y: return
            if self.ranks[x] < self.ranks[y]:
                self.pars[x] = y
            else:
                self.pars[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1
        def isSame(self, x, y):
            return self.getRoot(x) == self.getRoot(y)
        def updatePars(self):
            for v in range(len(self.pars)):
                self.getRoot(v)

    N = int(input())
    
    pts = []
    for i in range(N):
        x, y = map(int, input().split())
        x, y = x-1, y-1
        pts.append((x, y, i))

    UF = UnionFind(N)

    
    pts.sort(key=lambda x: x[0])
    stack = [(INF, INF, -1)]
    for x, y, i in pts:
        while stack[-1][1] < y:
            x0, y0, i0 = stack.pop()
            UF.merge(i0, i)
        stack.append((x, y, i))

    
    
    stack = [(-INF, -INF, -1)]
    for x, y, i in reversed(pts):
        while stack[-1][1] > y:
            x0, y0, i0 = stack.pop()
            UF.merge(i0, i)
        stack.append((x, y, i))

    
    pts.sort(key=lambda x: x[1])
    stack = [(INF, INF, -1)]
    for x, y, i in pts:
        while stack[-1][0] < x:
            x0, y0, i0 = stack.pop()
            UF.merge(i0, i)
        stack.append((x, y, i))

    
    
    stack = [(-INF, -INF, -1)]
    for x, y, i in reversed(pts):
        while stack[-1][0] > x:
            x0, y0, i0 = stack.pop()
            UF.merge(i0, i)
        stack.append((x, y, i))


    UF.updatePars()
    

    cnt = Counter(UF.pars)
    

    anss = [0] * N
    for i in range(N):
        anss[i] = cnt[UF.pars[i]]

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


solve()

Solution (Python):
N = int(input())
y= [-1 for i in range(N)]
t = []
for i in range(N):
  X, Y = map(int, input().split())
  X, Y = X -1, Y -1
  y[X] = Y
  t.append(X)
  
c = [1 for i in range(N)]
sumy = 0
comp = 0
for i in range(N-1):
  sumy += y[i]+1
  comp += N - i
  if sumy != comp:
    c[i + 1] = c[i] + 1
buf = c[-1]
for i in range(1,N+1):
  buf2 = buf
  if c[-i]==1 and i < N:
    buf2 = c[-i-1]  
  c[-i] = buf
  buf = buf2
for i in t:
  print(c[i])

Solution (Python):


from sys import stdin
import heapq

def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b,p,rank,nums):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
            nums[ap] += nums[bp]
        elif rank[ap] < rank[bp]:
            p[ap] = bp
            nums[bp] += nums[ap]
        else:
            p[bp] = ap
            nums[ap] += nums[bp]
            rank[ap] += 1

        return False

N = int(stdin.readline())

xy = []

for i in range(N):

    x,y = map(int,stdin.readline().split())
    x -= 1
    y -= 1
    xy.append((x,y,i))

xy.sort()
q = []

p = [i for i in range(N)]
rank = [0] * N
nums = [1] * N

for x,y,i in xy:

    miny = y
    while len(q) > 0 and q[0] < y:
        ny = heapq.heappop(q)
        uf_union(y,ny,p,rank,nums)
        miny = min(ny,miny,y)
    heapq.heappush(q,miny)

ans = [0] * N

for x,y,i in xy:
    ans[i] = nums[uf_find(y,p)]

print ("\n".join(map(str,ans)))

Solution (Python):

class SegTree:  
    def __init__(self ,N ,seg_func ,unit):
        self.N = 1 << ( N -1).bit_length()
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit ] *( 2 *self.N)

    def build(self ,init_value):  
        for i in range(len(init_value)):
            self.tree[ i +self.N] = init_value[i]
        for i in range(self. N -1 ,0 ,-1):
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])

    def set_val(self ,i ,x):  
        i += self.N
        self.tree[i] = x
        i >>= 1
        while i:
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])
            i >>= 1

    def fold(self ,L ,R):  
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL ,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R] ,vR)
            L >>= 1
            R >>= 1
        return self.func(vL ,vR)



class DSU:
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rank = [0] * (n + 1)
  def leader(self, x):
    rt = self.root[x]
    if rt < 0: return x
    else: self.root[x] = self.leader(rt)
    return self.root[x]
  def merge(self, x, y):
    leader = self.leader
    xrt = leader(x)
    yrt = leader(y)
    if xrt == yrt: return
    if self.rank[xrt] > self.rank[yrt]:
      self.root[xrt] += self.root[yrt]
      self.root[yrt] = xrt
    else:
      self.root[yrt] += self.root[xrt]
      self.root[xrt] = yrt
      self.rank[yrt] += self.rank[xrt] == self.rank[yrt]
  def same(self, x, y): return self.leader(x) == self.leader(y)
  def size(self, x):  return -self.root[self.leader(x)]
  def group(self):
    n = self.n
    leader = self.leader
    res = [[] for _ in range(n + 1)]
    for x in range(n + 1): res[leader(x)].append(x)
    return [res[i] for i in range(n + 1) if len(res[i])]


def main():
    n, q = map(int, input().split())
    dsu = DSU(n)
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            dsu.merge(u, v)
        else:
            print(1 if dsu.same(u, v) else 0)


def seg_func(x,y):
    if x[0] > y[0]:
        return x
    else:
        return y
def seg_func1(x,y):
    if x[0] < y[0]:
        return x
    else:
        return y

n = int(input())
X = []
for xx in range(n):

    a, b = map(int, input().split())
    X.append([xx, a, b])

X = sorted(X, key=lambda x: x[1])

dsu = DSU(n)
tree = SegTree(n+1,seg_func,[-1,-1])

for  v in X:
    tree.set_val(v[2], [v[2], v[0]])
    get = tree.fold(0, v[2])
    if get[0] != -1:
        dsu.merge(get[1], v[0])

X = sorted(X, reverse=True, key=lambda x: x[1])

tree = SegTree(n+2,seg_func,[-1,-1])

for v in X:
    tree.set_val(v[2], [v[2],v[0]])
    get = tree.fold(v[2]+1, n+2)
    if get[0] != -1:
        dsu.merge(get[1], v[0])

groups = dsu.group()
ans = [0] * (n * 2 + 10)

for a in groups:
    count = len(a)
    for v in a:
        ans[v]=count

for l, v in enumerate(ans):
    if l < n:
        print(str(v))
    else:
        exit()

Solution (Python):
import sys
import heapq
input = sys.stdin.readline

class UnionFind():
    def __init__(self, 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

n = int(input())
uf = UnionFind(n)
d = {}

for i in range(n):
    x, y = map(int, input().split())
    d[x] = (i, y)
    
q = []
heapq.heapify(q)

for x in range(n):
    i, y = d[x+1]
    ym, im = 0, 0
    while q and q[0][0] < y:
        y2, i2 = heapq.heappop(q)
        if ym == 0:
            ym = y2
            im = i2
        uf.union(i,i2)
    heapq.heappush(q, (y,i))
    if ym:
        heapq.heappush(q, (ym,im))

for i in range(n):
    p = uf.find(i)
    print(-uf.parents[p])

Solution (Python):
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans


N = int(input())
mati = []
Y = [-1 for i in range(N)]
for i in range(N):
    x,y = map(int,input().split())
    mati.append((x-1,y-1,i))
    Y[y-1] = i
mati.sort()


uf = UnionFindVerSize(N)

left = [(-1,-1)] + [(Y[i],i) for i in range(N-1)]
right = [(Y[i+1],i+1) for i in range(N-1)] + [(-1,N)]

Max = -1

for x,y,i in mati[::-1]:
    res,idx = left[y]
    if res!=-1:
        uf.unite(i,res)
        right[idx] = right[y]
    res,yyy = right[y]
    if res!=-1:
        left[yyy] = left[y]
        if yyy<Max:
            uf.unite(res,i)

    Max = max(Max,y)

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

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

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

import sys
input = sys.stdin.buffer.readline
import heapq as hp

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

XY.sort()

uni = UnionFind(N)
q = []
for x, y, i in XY:
    my = y
    while q and q[0][0] < y:
        jy, j = hp.heappop(q)
        my = min(jy, my)
        uni.Unite(i, j)
    hp.heappush(q, (my, uni.Find_Root(i)))

for i in range(N):
    print(uni.Count(i))

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

class BIT:
	def __init__(self, n):
		self.n = n
		self.nums = [0] * (n+1)
		
	def add(self, i, x):
		n, nums = self.n, self.nums
		i += 1
		while i <= n:
			nums[i] += x
			i += i & -i
	
	def sum(self, i):
		nums = self.nums
		s = 0
		i += 1
		while i:
			s += nums[i]
			i -= i & -i
		return s
	
	def search(self, x):
		
		n, nums = self.n, self.nums
		s, p = 0, 0
		for i in range(n.bit_length(), -1, -1):
			np = p + (1<<i)
			if np <= n and s+nums[np] < x:
				s += nums[np]
				p = np
		return p

	def lowerbound(self, x):
		
		return self.search(self.sum(x-1)+1)

	def upperbound(self, x):
		
		return self.search(self.sum(x)+1)


class MultiSet:
	def __init__(self, n):
		self.bit = BIT(n)

	def insert(self, key):
		self.bit.add(key, 1)

	def erase(self, key):
		self.bit.add(key, -1)

	def top(self, i=0):
		
		return self.bit.search(i+1)

	def size(self):
		return self.bit.sum(self.bit.n-1)

	def count(self, key):
		
		return self.bit.sum(key)-self.bit.sum(key-1)

	def lower_bound(self, key):
		
		return self.bit.search(self.bit.sum(key-1)+1)

	def upper_bound(self, key):
		
		return self.bit.search(self.bit.sum(key)+1)

	def left_bound(self, key):
		s = self.bit.sum(key)
		if s <= 1: return -1
		return self.bit.search(s-1)

	def right_bound(self, key):
		s = self.bit.sum(key)
		if s == self.bit.n:
			return self.bit.n
		return self.bit.search(s+1)

	def debug(self):
		vals = []
		for i in range(self.bit.n):
			key = self.top(i)
			if key == self.bit.n: break
			vals.append(key)
		print(vals)

class UnionFind:
	
	
	
	def __init__(self, n):
		self.n = n
		self.sizes = [1]*n
		self.parents = list(range(n))

	def find(self, x):
		while x != self.parents[x]:
			self.parents[x] = self.parents[self.parents[x]]
			x = self.parents[x]
		return self.parents[x]

	def unite(self, x, y):
		x, y = self.find(x), self.find(y)
		if x == y:
			return
		if self.sizes[x] < self.sizes[y]:
			x, y = y, x
		self.parents[y] = x
		self.sizes[x] += self.sizes[y]

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

N = ri()
x2y = [0] * N
y2x = [0] * N
i2x = [0] * N
x2i = [0] * N
y2i = [0] * N
for i in range(N):
	x, y = rl()
	x, y = x-1, y-1
	i2x[i] = x
	x2i[x] = i
	y2i[y] = i
	x2y[x] = y
	y2x[y] = x

uf = UnionFind(N)
ms = MultiSet(N)
for x in range(N):
	y = x2y[x]
	ms.insert(y)
	idx = ms.left_bound(y)
	while idx < N and idx >= 0:
		uf.unite(y2i[y], y2i[idx])
		ms.erase(y)
		y = idx
		idx = ms.left_bound(idx)

ms = MultiSet(N)
for x in reversed(range(N)):
	y = x2y[x]
	ms.insert(y)
	idx = ms.right_bound(y)
	while idx < N and idx >= 0:
		p = uf.find(idx)
		uf.unite(y2i[y], y2i[idx])
		ms.erase(y)
		y = idx
		idx = ms.right_bound(idx)

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

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)

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

Solution (Python):











from collections import defaultdict

import sys

readline = sys.stdin.buffer.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):
        
        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])
        

    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):
        
        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):
        
        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 = {}
    
    for x, y, i in xyi:
        y2i[y] = i
        y2x[y] = x
        x2y[x] = 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')

    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    


if __name__ == '__main__':
    main()

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