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:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI()+[i] for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1


    n = I()
    p = LIR(n)
    p.sort()
    par = list(range(n))
    rank = [0]*n
    q = []
    q2 = []
    for x,y,i in p:
        f = 0
        while q:
            yy,j = heappop(q)
            if y < yy:
                heappush(q,(yy,j))
                break
            f = 1
            unite(i,j)
            q2.append((yy,j))
        while q2:
            yy,j = q2.pop()
            heappush(q,(yy,j))
        if not f:
            heappush(q,(y,i))
    s = [0]*(n+1)
    for _,_,i in p:
        s[root(i)] += 1
    ans = [None]*n
    for _,_,i in p:
        ans[i] = s[root(i)]
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
class Unionfind():  # 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)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xysort = [None] * n
for x, y in xy:
    xysort[x - 1] = y - 1

# 解説AC O(n)
uf = Unionfind(n)
cnt, yflag = 0, [0] * n
for x, y in enumerate(xysort[:n - 1]):
    yflag[y] = 1
    cnt += yflag[n - x - 1] + (y > n - x - 1)
    if cnt < x + 1:
        uf.union(x, x + 1)

for x, y in xy:
    print(uf.size(x - 1))

Submission status: Accepted

Solution code:
class Unionfind():  # 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)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xysort = [None] * n
for x, y in xy:
    xysort[x - 1] = y - 1

# 解説AC O(n)
uf = Unionfind(n)
tmp, yfrag = 0, [0] * n
for x, y in enumerate(xysort[:n - 1]):
    yfrag[y] = 1
    tmp += yfrag[n - x - 1] + (y > n - x - 1)
    if tmp < x + 1:
        uf.union(x, x + 1)

for x, y in xy:
    print(uf.size(x - 1))

Submission status: Accepted

Solution code:
class Unionfind():  # 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)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xysort = [None] * n
for x, y in xy:
    xysort[x - 1] = y - 1

# 解説AC
uf = Unionfind(n)
tmp, yfrag = 0, [0] * n
for x, y in enumerate(xysort[:n - 1], 1):
    yfrag[y] = 1
    tmp += yfrag[n - x] + (y > n - x)
    if tmp < x:
        uf.union(x, x - 1)

for x, y in xy:
    print(uf.size(x - 1))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def getsize(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]


# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n = int(readline())
xyi = []

for i in range(n):
    x,y = map(int,readline().split())
    xyi.append((x,y,i))

UF = UnionFind(n)
xyi.sort(key = lambda p:p[0])
#print(xyi)

q = []
for x,y,i in xyi:
    #print(q)
    if q and q[-1][0] < y: Y,I = q[-1]
    else: Y,I = y,i
    while q and q[-1][0] < y:
        yy,ii = q.pop()
        UF.merge(i,ii)
    q.append((Y,I))
    #print(i,idx)

for i in range(n):
    print(UF.getsize(i))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])
        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)
        if u == v:
            return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
N = int(input())
IXY = []
for i in range(N):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    IXY.append((i, x, y))

IXY.sort(key=itemgetter(1))

B = [IXY[0][2]]
uf = UnionFind(N)
for i, _, y in IXY[1:]:
    if B[-1] < y:
        bl = B.pop()
        uf.unite(bl, y)
        while B and B[-1] < y:
            uf.unite(bl, B.pop())
        B.append(bl)
    else:
        B.append(y)

Ans = [-100] * N
for i, _, y in IXY:
    Ans[i] = uf.count(y)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
# 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 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()

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

Submission status: Accepted

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

def solve():
    INF = 10**10

    # Union-Findデータ構造
    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 = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
    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)

    # x昇順
    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))

    # x降順
    #pts.sort(key=lambda x: x[0])
    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))

    # y昇順
    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))

    # y降順
    #pts.sort(key=lambda x: x[1])
    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()
    #print('# UF.pars:', UF.pars, file=sys.stderr)

    cnt = Counter(UF.pars)
    #print('# cnt:', cnt, file=sys.stderr)

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

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


solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:


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

Submission status: Accepted

Solution code:

class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    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):  # 初期値を[N,2N)に格納
        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番目(0-index)の値を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,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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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)

    # ノードxが属する木のサイズ
    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))

Submission status: Accepted

Solution code:
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):
		# minimum index i such that x <= self.sum(i)
		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):
		# minimum index i such that x <= i and i-th element
		return self.search(self.sum(x-1)+1)

	def upperbound(self, x):
		# minimum index i such that self.x < sum(i)
		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):
		# i-th smallest element
		return self.bit.search(i+1)

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

	def count(self, key):
		# number of keys
		return self.bit.sum(key)-self.bit.sum(key-1)

	def lower_bound(self, key):
		# minimum key k no less than key (key <= k)
		return self.bit.search(self.bit.sum(key-1)+1)

	def upper_bound(self, key):
		# minimum key k greater than key (key < k)
		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:
	# uf = UnionFind(N)
	# for x, y in pairs: uf.unite(x, y)
	# ans = max([uf.size(i) for i in range(N)])
	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))