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):
n=int(input())
import sys
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as frac  






class UnionFind():
    def __init__(self,num):
        self.n = num         
        self.parents = [-1 for i in range(self.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):
        xx=self.find(x)  
        yy=self.find(y)  
        if xx==yy:
            return     
        else:
            size_xx=abs(self.parents[xx]) 
            size_yy=abs(self.parents[yy]) 
            if size_xx>size_yy:
                xx,yy=yy,xx  

            self.parents[yy]+=self.parents[xx] 
            self.parents[xx]=yy   

    
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

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

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

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

    
    def state_grouping(self):
        return list(self.all_group_members().values())

uf=UnionFind(n)
A=[0]*n 
for i in range(n):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[b]=(a,i)
M= deque([])
for i in range(n):
    if not M: M.append(A[i]);continue
    h,num = A[i]
    cnt=0
    while M:
        xx,nownum = M.pop()
        if not cnt: xori,nowori= xx,nownum
        if xx> h: 
            M.append((xx,nownum));break
        uf.union(nownum,num)
        cnt+=1
    if cnt==0:
        M.append((xori,nowori))
        M.append((h,num))
    else:
        M.append((h,num))
        M.append((xori,nowori))
for i  in range(n):
    print(uf.size(i))

Solution (Python):


def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):

    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

def main():
    N = int( input())
    XY = []
    for i in range(N):
        x, y = map( int, input().split())
        XY.append( (x,y,i))
    
    XY.sort(key=lambda x:x[0])
    A = [ i for i in range(N)]
    my = N+1
    myi = N+1
    for x,y,i in XY:
        if y < my:
            my = y
            myi = i
            continue
        union(A, i , myi)
    My = 0
    Myi = N+1
    for x, y, i in XY[::-1]:
        if y > My:
            My = y
            Myi = i
            continue
        union(A, i, Myi)

    XY.sort(key=lambda x:x[1])
    mx = N+1
    mxi = N+1
    for x,y,i in XY:
        if x < mx:
            mx = x
            mxi = i
            continue
        union(A, i , mxi)
    Mx = 0
    Mxi = N+1
    for x, y, i in XY[::-1]:
        if x > Mx:
            Mx = x
            Mxi = i
            continue
        union(A, i, Mxi)
 
    T = [0]*N
    for i in range(N):
        T[find(A,i)] += 1
   
    
    ANS = [0]*N
    for i in range(N):
        ANS[i] = T[ find(A,i)]
    print("\n".join( map( str, ANS)))
                 
if __name__ == '__main__':
    main()

Solution (Python):

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

    
    def find(self, x):
        history = []
        while self.parents[x] >= 0:
            history.append(x)
            x = self.parents[x]
        for node in history:
            self.parents[node] = x
        return 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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

from bisect import bisect
from sys import stdin
input = stdin.buffer.readline

def main():
    n = int(input())

    l = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        l[x-1] = (y - 1, i)

    
    uf = UnionFind(n)
    roots = []

    for y, i in l:
        if len(roots) == 0 or -roots[-1][0] > y:
            roots.append((-y, i))
        else:
            ind = bisect(roots, (-y, i))
            new_y = roots[-1][0]
            for old_y, old_i in roots[ind:]:
                uf.union(i, old_i)
            roots = roots[:ind]
            roots.append((new_y, i))

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

main()

Solution (Python):
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict








def solve(grid, n):  
    console("----- solving ------")
    grid = [(x-1, y-1) for x,y in grid]

    m = {}
    for i,(x,y) in enumerate(grid):
        m[x] = i
    
    grid = sorted(grid)
    console(grid)

    g = defaultdict(list)
    y_heap = []
    heapq.heapify(y_heap)

    for x,y in grid:
        if y_heap:
            ymin,xmin = y_heap[0]
            if ymin < y:
                while y_heap and y_heap[0] < (y,x):
                    ycur,xcur = heapq.heappop(y_heap)
                    g[x].append(xcur)
                    g[xcur].append(x)
                heapq.heappush(y_heap, (ymin,xmin))
        heapq.heappush(y_heap, (y,x))
        
    console(g)

    res = [0 for _ in grid]
    visited_1 = [0 for _ in grid]
    visited_2 = [0 for _ in grid]

    for i in range(n):
        if res[i]:  
            continue
        visited_1[i] = 1
        stack = [i]
        cnt = 1
        while stack:
            cur = stack.pop()
            for nex in g[cur]:
                if not visited_1[nex]:
                    cnt += 1
                    visited_1[nex] = 1
                    stack.append(nex)
                
        
        visited_2[i] = 1
        stack = [i]
        while stack:
            cur = stack.pop()
            res[cur] = cnt
            for nex in g[cur]:
                if not visited_2[nex]:
                    visited_2[nex] = 1
                    stack.append(nex)

    console(res)
    console(visited_1)
    console(visited_2)
    res2 = [0 for _ in grid]
    for i,x in m.items():
        res2[x] = res[i]

    return res2




def console(*args):  
    
    return


inp = sys.stdin.readlines()

for case_num in [1]:
    
    

    
    nrows = int(inp[0])
    
    
    

    
    

    
    
    
    grid = []
    for n in range(nrows):
        grid.append(list(map(int,inp[n+1].split())))

    res = solve(grid, nrows)  
    
    res = "\n".join(str(x) for x in res)
    
    

    
    print(res)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

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

        def find_root(self, x):
            while self.root[x] >= 0:
                x = self.root[x]
            return 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 size(self, x):
            return -self.root[self.find_root(x)]

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N = int(input())
    XY = []
    x2i = [0] * (N+1)
    y2i = [0] * (N+1)
    for i in range(1, N+1):
        x, y = map(int, input().split())
        XY.append((x, y))
        x2i[x] = i
        y2i[y] = i
    bit = Bit(N)
    UF = UnionFind(N)

    XY.sort(key=lambda z: z[1])
    r = N+1
    for i in range(N):
        x, y = XY[i]
        bit.add(x, 1)
        
        if x < r:
            for xx in range(x, r-1):
                UF.unite(x2i[xx], x2i[xx+1])
            if bit.sum(N) - bit.sum(r-1) != N - r + 1:
                UF.unite(x2i[r-1], x2i[r])
            r = x
            if r == 1:
                break
    for i in range(1, N+1):
        print(UF.size(i))


if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    UNIONFIND_TABLE = []

    def unionfind_init(n):
        UNIONFIND_TABLE.append(np.full(n, -1, dtype=np.int64))
        return len(UNIONFIND_TABLE) - 1

    def unionfind_getroot(ins, x):
        table = UNIONFIND_TABLE[ins]
        stack = []
        while table[x] >= 0:
            stack.append(x)
            x = table[x]
        for y in stack:
            table[y] = x
        return x

    def unionfind_unite(ins, x, y):
        table = UNIONFIND_TABLE[ins]
        r1 = unionfind_getroot(ins, x)
        r2 = unionfind_getroot(ins, y)
        if r1 == r2:
            return
        d1 = table[r1]
        d2 = table[r2]
        if d1 <= d2:
            table[r2] = r1
            table[r1] += d2
        else:
            table[r1] = r2
            table[r2] += d1

    def unionfind_find(ins, x, y):
        return unionfind_getroot(ins, x) == unionfind_getroot(ins, y)

    def unionfind_getsize(ins, x):
        table = UNIONFIND_TABLE[ins]
        return -table[unionfind_getroot(ins, x)]

    FENWICK_TREE = []
    FENWICK_LOGN = []

    def fenwick_init(n):
        log_n = 0
        m = n
        while m:
            log_n += 1
            m >>= 1
        FENWICK_TREE.append(np.zeros(n + 1, dtype=np.int64))
        FENWICK_LOGN.append(log_n)
        return len(FENWICK_TREE) - 1

    def fenwick_add(ins, i, x):
        arr = FENWICK_TREE[ins]
        n = arr.size - 1
        while i <= n:
            arr[i] += x
            i += i & -i

    def fenwick_sum(ins, i):
        arr = FENWICK_TREE[ins]
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    def fenwick_lower_bound(ins, x):
        arr = FENWICK_TREE[ins]
        log_n = FENWICK_LOGN[ins]
        n = arr.size - 1
        sum_ = 0
        pos = 0
        for i in range(log_n, -1, -1):
            k = pos + (1 << i)
            if k < n and sum_ + arr[k] < x:
                sum_ += arr[k]
                pos += 1 << i
        return pos + 1

    n = inp[0]

    bit = fenwick_init(n + 2)
    uft = unionfind_init(n)
    xxx = inp[1::2]
    yyy = inp[2::2]
    idx = np.argsort(xxx)

    y_dict = np.zeros(n + 1, np.int64)
    for i in range(n):
        y_dict[yyy[i]] = i

    for i in idx:
        y = yyy[i]
        k = fenwick_sum(bit, y + 1)

        if k == 0:
            fenwick_add(bit, y + 1, 1)
            continue

        while k > 0:
            u = fenwick_lower_bound(bit, k) - 1
            j = y_dict[u]
            unionfind_unite(uft, i, j)
            k -= 1

    ans = np.zeros(n, np.int64)
    for i in range(n):
        ans[i] = unionfind_getsize(uft, i)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

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):
class UnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
    
    def find(self, a):
        path = []
        while self.parent[a] > 0:
            path.append(a)
            a = self.parent[a]
        for child in path:
            self.parent[child] = a
        return a

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)

        if a == b:
            return
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
            elif self.parent[a] < self.parent[b]: 
                self.parent[b] = a
            else:
                self.parent[a] = b 
        
    def same(self, a, b):
        return self.find(a) == self.find(b)




class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    基本的に閉区間で管理する。
    内部では受け取った数を +1 したものをindexとして持っているので注意。
    """

    __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue, counter = None):
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)
        if counter is not None:
            self.update(counter)
        
    def update(self, counter):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        if isinstance(counter, list):
            self.data = [0] + counter + [0] * (self.n - len(counter))
        else:
            self.data = [0] * (self.n + 1)
            for k, v in counter.items():
                self.data[k + 1] = v
        for i in range(1, self.n + 1):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]

    def add(self, value, count = 1):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += count
            value += value & -value

    def pop(self, value, count = 1):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= count
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.count(index.start, index.stop - 1)
        else:
            return self.count(index, index)

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k //= 2
        return ret

    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


N = int(input())
xys = [tuple(map(int, input().split())) for i in range(N)]
x2i = {x: i for i, (x, y) in enumerate(xys)}

xys.sort(key=lambda t: t[0])

splitted = [True] * (N - 1)

mbit = MultisetBIT(N + 1)
for n, (x, y) in enumerate(xys[:-1]):
    mbit.add(y)
    if mbit.count_le(N - n - 1):
        splitted[n] = False



mbit = MultisetBIT(N + 1)
for n, (x, y) in enumerate(xys[:0:-1]):
    mbit.add(y)
    if mbit.count(n + 2, N + 1):
        splitted[N - 2 - n] = False



ans = [0] * N
s = set()
for (x, y), flg in zip(xys, splitted):
    i = x2i[x]
    s.add(i)
    if flg:
        for i in s:
            ans[i] = len(s)
        s = set()

s.add(x2i[xys[-1][0]])
for i in s:
    ans[i] = len(s)
print(*ans, sep='\n')

Solution (Python):
class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

uni = Union(N)

xyn = [[0] * 3 for _ in range(N)]
for i in range(N):
  x, y = xy[i]
  xyn[i] = [x, y, i]

xyn.sort()
x, y, n = xyn[0]
push(q, (y << 20) + n)
for i in range(1, N):
  x, y, n = xyn[i]
  m = pop(q)
  yy, nn = m >> 20, m % (1 << 20)
  if yy < y:
    uni.merge(nn, n)
    while q:
      p = pop(q)
      yy, nn = p >> 20, p % (1 << 20)
      if yy < y:
        uni.merge(nn, n)
      else:
        push(q, (yy << 20) + nn)
        break
  else:
    push(q, (y << 20) + n)
  push(q, m)

for i in range(N):
  print(uni.root(i)[1])

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())
xy = [0] * N
i_to_x = {}
for i in range(N):
    x, y = map(int, input().split())
    xy[i] = (x-1, y-1)
    i_to_x[i] = x-1

xy.sort(key=lambda x: x[1])

uf = UnionFind(N)

max_x = N-1
x_set = set()
hist_x_min = N
for x, y in xy:
    x_set.add(x)
    if x == max_x:
        while max_x in x_set:
            max_x -= 1
    else:
        uf.union(x, max_x)

        if x < hist_x_min:
            for x_ in range(x+1, hist_x_min):
                uf.union(x, x_)

    hist_x_min = min(hist_x_min, x)



ans = [0] * N
for i in range(N):
    ans[i] = uf.size(uf.find(i_to_x[i]))
print('\n'.join(map(str, ans)))

Solution (Python):
N = int(input())
X = [tuple(map(int,input().split())) for _ in range(N)]

par = [-1 for _ in range(N)]
def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x]) 
            return par[x]
def same(x,y):
        return find(x) == find(y)
def unite(x,y):
        x = find(x)
        y = find(y)
        
        if x == y:
            return 0
        else:
          if par[x] > par[y]:
            x,y = y,x
          par[x] += par[y]
          par[y] = x
def size(x):
        return -par[find(x)]
    


y_list = [0 for _ in range(N)]
for x, y in X:
  y_list[x-1] = y-1


tp = N
rest = N
for i in range(N):
  y = y_list[i]
  if y > tp:
    continue
  rest -= 1
  
  if i + rest < N-1: 
    unite(y, tp)
  
  j = y + 1
  while j < tp:
    rest -= 1
    unite(y, j) 
    
    j += 1
  tp = y

for x, y in X:
  print(size(y-1))

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.size = [1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			if self.table[self.table[x]] >= 0:
				self.table[x] = self.table[self.table[x]]
			x = self.table[x]
		return x

	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
		return

n = int(input())
d = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[x-1, y-1, i] for x, y, i in d]
d.sort()
uf = UnionFind(n)
cum = [0 for _ in range(n)]
for i in range(n-1):
	if d[i][1] < d[i+1][1]:
		cum[d[i][1]] += 1
		cum[d[i+1][1]] -= 1
for i in range(n):
	if i > 0:
		cum[i] += cum[i-1]
	if cum[i] > 0:
		uf.unite(i, i+1)

ans = [0 for _ in range(n)]
for i in range(n):
	ans[d[i][2]] = uf.size[uf.find(d[i][1])]

print(*ans, sep="\n")

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter

N=int(input())
T=[list(map(int,input().split()))+[i] for i in range(N)]

YtoN=[-1]*(N+1)
for x,y,n in T:
    YtoN[y]=n

T.sort(key=itemgetter(0))
MAX=N
MAXUSE=0
MIN=10**6
left=0

ANS=[-1]*N

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

    if y==MAX:
        MAXUSE=1
        
    MIN=min(y,MIN)

    

    if MAXUSE==1 and MAX-MIN==i-left:
        for j in range(left,i+1):
            ANS[T[j][2]]=MAX-MIN+1

        MAX=MIN-1
        MAXUSE=0
        left=i+1

for ans in ANS:
    print(ans)

Solution (Python):
import sys
import bisect
from collections import deque

input = sys.stdin.readline
N = int(input())
xy = sorted([[i] + list(map(int, input().split())) for i in range(N)], key=lambda x: x[1])


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

uf = UnionFind(N)
ys = deque([(xy[0][2], xy[0][0])])  
for i, x, y in xy[1:]:
    if ys[0][0] >= y:
        ys.appendleft((y, i))
        continue
    miny, minj = ys[0]
    while len(ys)>0:
        y_, j = ys.popleft()
        if y_ >= y:
            ys.appendleft((y_, j))
            break
        uf.union(i, j)
    ys.appendleft((miny, minj))
for i in range(N):
    print(uf.size(i))

Solution (Python):
import sys
readline = sys.stdin.readline
from operator import itemgetter

class UF():
    def __init__(self, num):
        self.par = [-1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            stack = []
            while self.par[x] >= 0:
                stack.append(x)
                x = self.par[x]
            for xi in stack:
                self.par[xi] = x
            return x
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
        return rx

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

_, _, Y = map(list, zip(*XY))

XY.sort(key = itemgetter(1))

T = UF(N)

stack = []
for i, _, y in XY:
    my = i
    while stack and Y[stack[-1]] < y:
        if Y[stack[-1]] < Y[my]:
            my = stack[-1]
        T.union(stack.pop(), i)
    stack.append(my)
ans = [-T.par[T.find(i)] for i in range(N)]
    
print('\n'.join(map(str, ans)))