Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

 切り取り線(Cutting)

JOI 君はペーパークラフトが趣味である．今日もJOI 君はペーパークラフトの作品を作ろうとしている．まず，JOI 君は設計図にしたがって1 枚の長方形の紙に $N$ 本の切り取り線を印刷した．各切り取り線は，紙の縦または横の辺に平行な線分である．

紙を切り出してできるすべての部分は作品の中で何らかの部品として用いられる．当然のことながら，
部品数の多い作品は製作が大変である．JOI 君は，すべての切り取り線にしたがって紙を切り出したとき，
紙がいくつの部分に分かれるかを知りたい．

課題

紙の大きさと，$N$ 本の切り取り線の情報が与えられる．これらの切り取り線にしたがって紙を切り分けたとき，紙がいくつの部分に分かれるかを求めるプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

 1 行目には，整数 $W, H, N$ が空白を区切りとして書かれている．$W$ は紙の横の辺の長さを，$H$ は紙の縦の辺の長さを，$N$ は切り取り線の本数をそれぞれ表す．紙の左下，右下，左上，右上を，それぞれ座標 $(0, 0), (W, 0), (0, H), (W, H)$ で表す．

 続く $N$ 行のうちの $i$ 行目 $(1 \leq i \leq N)$ には，整数 $A_i, B_i, C_i, D_i (0 \leq A_i \leq C_i \leq W, 0 \leq B_i \leq D_i \leq H)$ が空白を区切りとして書かれている．これは $i$ 番目の切り取り線が$(A_i, B_i)$ と$(C_i, D_i)$ を結ぶ線分であることを表す．この線分は紙のいずれかの辺に平行な線分である．すなわち，$A_i = C_i$ と $B_i = D_i$ のうちのちょうど1 つが成り立つ．また，ある切り取り線と，それに平行な他の切り取り線が共有点を持つことはなく，ある切り取り線と，それに平行な紙の辺が共有点を持つこともない．

出力

標準出力に，紙がいくつの部分に分かれるかを表す整数を1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

$ 1 \leq W \leq 1000000 000$

$ 1 \leq H \leq 1000000 000$

$ 1 \leq N \leq 100000$

入出力例

  
入力例 1 
  

  

10 10 5
6 0 6 7
0 6 7 6
2 3 9 3
2 3 2 10
1 9 8 9

  
出力例 1 
  

  

4

この入力の場合，切り取り線は下図のようになる．

よって，切り取り線によって紙は4 つの部分に分かれる．

  
入力例 2 
  

  

13 7 28
1 1 4 1
1 1 1 3
2 2 3 2
2 2 2 3
1 3 2 3
3 2 3 6
4 1 4 6
3 6 4 6
5 1 8 1
5 1 5 6
6 2 7 2
6 2 6 5
7 2 7 5
6 5 7 5
8 1 8 6
5 6 8 6
9 1 12 1
9 1 9 2
9 2 10 2
12 1 12 2
11 2 12 2
10 2 10 5
9 5 10 5
9 5 9 6
11 2 11 5
11 5 12 5
12 5 12 6
9 6 12 6

  
出力例 2 
  

  

5

この入力の場合，切り取り線は次ページの図のようになる．

よって，切り取り線によって紙は5 つの部分に分かれる．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
10 10 5
6 0 6 7
0 6 7 6
2 3 9 3
2 3 2 10
1 9 8 9


Sample output:
4

Submission status: Wrong Answer

Solution code:
import math
class segmentTree:
    def __init__(self, n):
        self.pad = 2 ** math.ceil(math.log(n, 2))
        self.bit = [0] * self.pad * 2

    def __add(self, i, v):
        i += self.pad
        while i:
            self.bit[i] += v
            i >>= 1        
    def delete(self, i):
        self.__add(i,-1)
    def add(self, i):
        self.__add(i, 1)

    def crossing(self, l, r):
        l += self.pad
        r += self.pad
        ret = 0
        while l < r:
            if r & 1:
                r -= 1
                ret += self.bit[r]
            if l & 1:
                ret += self.bit[l]
                l += 1
            l >>= 1
            r >>= 1
        return ret
    # rの左直近で立つbitのindexを返す
    def lower_bound(self, r):
        l = self.pad
        r += self.pad
        while l < r:
            if r & 1:
                r -= 1
                if self.bit[r]:
                    while r < self.pad:
                        r <<= 1
                        if self.bit[r + 1]:
                            r += 1
                    return r - self.pad
            if l & 1:
                l += 1            
            l >>= 1
            r >>= 1
        return -1
    # iの右直近で立つbitのindexを返す
    def upper_bound(self, l):
        l += self.pad + 1
        r = len(self.bit) - 1
        while l <= r:
            if r & 1:
                r -= 1
            if l & 1:
                if self.bit[l]:
                    while l < self.pad:
                        l <<= 1
                        if self.bit[l] == 0:
                            l += 1
                    return l - self.pad
                l += 1            
            l >>= 1
            r >>= 1
        return -1
                
class delay_force_segment_no:
    def __init__(self, n):
        self.pad = 2 ** math.ceil(math.log(n, 2))
        self.delay = [0] * self.pad * 2
        self.dat = [0] * n
        self.seg_no_max = 0
    def mark_delay(self, l, r):
        l += self.pad
        r += self.pad
        while l < r:
            if r & 1:
                r -= 1
                self.delay[r] = 1
            if l & 1:
                self.delay[l] = 1
                l += 1
            l >>= 1
            r >>= 1
    def update(self, i, v):
        self.__force(i)
        self.dat[i] = v
    def get(self, i):
        self.__force(i)
        return self.dat[i]
    def __is_marked(self, i):
        i += self.pad
        while i:
            if self.delay[i]:
                return True
            i >>= 1
        return False
    def __force(self, i):
        if not self.__is_marked(i):
            return
        self.seg_no_max += 1
        self.dat[i] = self.seg_no_max
        i += self.pad
        for j in range(int(math.log(i, 2)), 0, -1):
            if self.delay[i >> j]:
                self.delay[i >> j] = 0
                self.delay[(i >> j) * 2] = self.delay[(i >> j) * 2 + 1] = 1
        self.delay[i] = 0

import sys
f = sys.stdin

w,h,n = map(int,f.readline().split())
#abcd = [[0,0,0,h],[w,0,w,h],[0,0,w,0]] + [list(map(int,line.split())) for line in f] + [[0,h,w,h]]#a<=c and b<=d is True ※問の条件
abcd = [[0,0,w,0],[0,h,w,h]] + [list(map(int,line.split())) for line in f] #a<=c and b<=d is True ※問の条件

# X軸を圧縮
def bisect(a,v):
    l,r = 0,len(a)-1    
    while l != r:
        m = (l + r) // 2
        if a[m] < v:
            l = m + 1
        else:
            r = m
    return l
x_set = sorted({abcdi[0] for abcdi in abcd} | {abcdi[2] for abcdi in abcd})
action = []
VERTICAL_LINE_TOP,HORIZONTAL_LINE,VERTICAL_LINE_BOTTOM = 0,1,2
for a,b,c,d in abcd:
    a = bisect(x_set,a) #X座標圧縮
    c = bisect(x_set,c)
    if a == c:
        action.append((VERTICAL_LINE_TOP,a,b,-1))
        action.append((VERTICAL_LINE_BOTTOM,a,d,-1))
    else:
        action.append((HORIZONTAL_LINE,a,b,c))
    
# 2:Y座標でソート,0:action_typeでソート
from operator import itemgetter
action.sort(key=itemgetter(2,0))

ret = 0
vertical_line = segmentTree(len(x_set))
vertical_line.add(0) #左の縦線
vertical_line.add(len(x_set) - 1) # 右の縦線
segment_no = delay_force_segment_no(len(x_set))
for action_type,x1,y1,x2 in action:
    if action_type == VERTICAL_LINE_TOP:
        vertical_line.add(x1)
        left_line = vertical_line.lower_bound(x1)
        segment_no.update(x1, segment_no.get(left_line))
    elif action_type == HORIZONTAL_LINE:
        count = vertical_line.crossing(x1,x2 + 1)
        if count < 2:
            continue
        ret += count - 1
        segment_no.mark_delay(x1, x2)
    else:
        left_line = vertical_line.lower_bound(x1)
        l_no = segment_no.get(left_line)
        x_no = segment_no.get(x1)
        if l_no != x_no:
            ret -= 1
            if l_no < x_no:
                segment_no.update(x1, l_no)
            else:
                segment_no.update(left_line, x_no)
        vertical_line.delete(x1)
print(ret - 1)

Submission status: Wrong Answer

Solution code:
import math
class segmentTree:
    def __init__(self, n):
        self.pad = 2 ** math.ceil(math.log(n, 2))
        self.bit = [0] * self.pad * 2

    def __add(self, i, v):
        i += self.pad
        while i:
            self.bit[i] += v
            i >>= 1        
    def delete(self, i):
        self.__add(i,-1)
    def add(self, i):
        self.__add(i, 1)

    def crossing(self, l, r):
        l += self.pad
        r += self.pad
        ret = 0
        while l < r:
            if r & 1:
                r -= 1
                ret += self.bit[r]
            if l & 1:
                ret += self.bit[l]
                l += 1
            l >>= 1
            r >>= 1
        return ret
    # rの左直近で立つbitのindexを返す
    def lower_bound(self, r):
        l = self.pad
        r += self.pad
        while l < r:
            if r & 1:
                r -= 1
                if self.bit[r]:
                    while r < self.pad:
                        r <<= 1
                        if self.bit[r + 1]:
                            r += 1
                    return r - self.pad
            if l & 1:
                l += 1            
            l >>= 1
            r >>= 1
        return 0
class delay_force_union_find:
    def __init__(self, n):
        self.pad = 2 ** math.ceil(math.log(n, 2))
        self.delay = [0] * self.pad * 2
        self.dat = [-1] * (n + 1)
    def mark_delay(self, l, r):
        l += self.pad
        r += self.pad
        while l < r:
            if r & 1:
                r -= 1
                self.delay[r] = 1
            if l & 1:
                self.delay[l] = 1
                l += 1
            l >>= 1
            r >>= 1
    def update(self, i, v):
        self.__force(i)
        self.dat[i] = v
    def find(self, i):
        self.__force(i)
        while self.dat[i] >= 0:
            i = self.dat[i]
        return i
    def union(self,a,b):
        s1 = self.find(a)
        s2 = self.find(b)
        if s1 != s2:
            if self.dat[s1] >= self.dat[s2]:
                # 小さいほうが個数が多い
                self.dat[s1] += self.dat[s2]
                self.dat[s2] = s1
            else:
                self.dat[s2] += self.dat[s1]
                self.dat[s1] = s2
            return True
        return False
    
    def __is_marked(self, i):
        i += self.pad
        while i:
            if self.delay[i]:
                return True
            i >>= 1
        return False
    def __force(self, i):
        if not self.__is_marked(i):
            return
        self.dat[i] = -1
        i += self.pad
        for j in range(int(math.log(i, 2)), 0, -1):
            if self.delay[i >> j]:
                self.delay[i >> j] = 0
                self.delay[(i >> j) * 2] = self.delay[(i >> j) * 2 + 1] = 1
        self.delay[i] = 0

import sys
f = sys.stdin
w,h,n = map(int,f.readline().split())
abcd = [[0,0,0,h],[w,0,w,h],[0,0,w,0]] + [list(map(int,line.split())) for line in f] + [[0,h,w,h]]#a<=c and b<=d is True ※問の条件

# X軸を圧縮
def bisect(a,v):
    l,r = 0,len(a)-1    
    while l != r:
        m = (l + r) // 2
        if a[m] < v:
            l = m + 1
        else:
            r = m
    return l
x_set = sorted({abcdi[0] for abcdi in abcd} | {abcdi[2] for abcdi in abcd})
action = []
VERTICAL_LINE_TOP,HORIZONTAL_LINE,VERTICAL_LINE_BOTTOM = 0,1,2
for a,b,c,d in abcd:
    a = bisect(x_set,a) #X座標圧縮
    c = bisect(x_set,c)
    if a == c:
        action.append((VERTICAL_LINE_TOP,a,b,-1))
        action.append((VERTICAL_LINE_BOTTOM,a,d,-1))
    else:
        action.append((HORIZONTAL_LINE,a,b,c))
    
# 2:Y座標でソート,0:action_typeでソート
from operator import itemgetter
action.sort(key=itemgetter(2,0))
ret = 0
vertical_line = segmentTree(len(x_set))
segment_no = delay_force_union_find(len(x_set))
for action_type,x1,y1,x2 in action:
    if action_type == VERTICAL_LINE_TOP:
        vertical_line.add(x1)
        left_line = vertical_line.lower_bound(x1)
        segment_no.union(left_line,x1)
    elif action_type == HORIZONTAL_LINE:
        count = vertical_line.crossing(x1,x2 + 1)
        if count < 2:
            continue
        ret += count - 1
        segment_no.mark_delay(x1, x2)
    else:
        left_line = vertical_line.lower_bound(x1)
        if segment_no.union(left_line,x1):
            ret -= 1
        vertical_line.delete(x1)
print(ret - 1)

Submission status: Accepted

Solution code:
import math
class seg_tree:
    def __init__(self, n):
        self.depth = math.ceil(math.log(n, 2))
        self.size = 1 << self.depth
        self.bit = [0] * 2 * self.size
        self.renew = [0] * 2 * self.size
 
    def add(self, p, v):
        p += self.size;
        while p:
            self.bit[p] += v
            p >>= 1
 
    def query(self, l, r):
        l += self.size
        r += self.size
        ret = 0
 
        while l < r:
            if l & 1:
                ret += self.bit[l]
                l += 1
            if r & 1:
                r -= 1
                ret += self.bit[r]
            l >>= 1
            r >>= 1
        return ret
 
    def set_renew(self, l, r):
        l += self.size
        r += self.size
 
        while l < r:
            if l & 1:
                self.renew[l] = 1
                l += 1
            if r & 1:
                r -= 1
                self.renew[r] = 1
            l >>= 1
            r >>= 1
 
    def is_renew(self, p):
        p += self.size
        while p:
            if self.renew[p]:
                return True
            p >>= 1
        return False
 
    def unset_renew(self, p):
        p += self.size
        for i in range(self.depth - 1,0,-1):
            if self.renew[p >> i]:
                self.renew[p >> i] = 0
                self.renew[(p>>i)*2] = self.renew[(p>>i)*2+1] = 1
        self.renew[p] = 0
    def get_lf(self, r):
        l = self.size
        r += self.size
        while l < r:
            if r & 1:
                r -= 1
                if self.bit[r]:
                    while r < self.size:
                        r <<= 1
                        if self.bit[r + 1]:
                            r += 1
                    return r - self.size
            if l & 1:
                l += 1            
            l >>= 1
            r >>= 1
        return -1
from collections import UserList
class union_find(UserList):
    def __init__(self):
        UserList.__init__(self)
    def root(self, p):
        if self.data[p] < 0:
            return p
        self.data[p] = self.root(self.data[p])
        return self.data[p]
    def join(self, p, q):
        p, q = self.root(p), self.root(q)
 
        if p == q:
            return False
        if self.data[p] < self.data[q]:
            p, q = q, p
        self.data[p], self.data[q] = self.data[q], p
        return True
def bisect(a,v):
    l, r = 0, len(a)
    while l < r:
        m = (l + r) // 2
        if a[m] < v:
            l = m + 1
        else:
            r = m
    return l
def adjust(seg, uf, target, p):
    if seg.is_renew(p):
        uf.append(-1)
        seg.unset_renew(p)
        target[p] = len(uf) - 1
from operator import itemgetter
#@profile
def main(f):    
    w,h,n = map(int,f.readline().split())
    abcd = [list(map(int,line.split())) for line in f]
 
    abcd.extend([[0,0,w,0],
                 [0,0,0,h],
                 [w,0,w,h],
                 [0,h,w,h]])
 
    xs = {x:i for i, x in enumerate(sorted(set([abcdi[0] for abcdi in abcd] +[abcdi[2] for abcdi in abcd] + [-1])))}
    abcd =[(xs[a],b,xs[c],d) for a,b,c,d in abcd]
 
    target = [-1] * n * 2
    target[0] = 0
    uf = union_find()
    uf.append(-1)
    seg = seg_tree(len(xs))
    seg.add(0, 1) #
 
    a = []
    for x1,y1,x2,y2 in abcd:
        if x1 == x2:
            a.append((y1, 0, x1, -1))
            a.append((y2, 2, x1, -1))
        else:
            a.append((y1, 1, x1, x2))
    a.sort(key=itemgetter(0,1))
    ret = 0
    for _, act, left, right in a:
        if act == 0:
            lf = seg.get_lf(left)
 
            adjust(seg, uf, target, lf)
            adjust(seg, uf, target, left)
            target[left] = target[lf]
 
            seg.add(left, 1)
        elif act == 1:
            count = seg.query(left, right+1)
            if count < 2:
               continue
            ret += count - 1;
 
            seg.set_renew(left, seg.get_lf(right + 1))
        elif act == 2:
            lf = seg.get_lf(left)
            adjust(seg, uf, target, lf)
            adjust(seg, uf, target, left)
            if uf.join(target[lf], target[left]):
                ret -= 1
            seg.add(left, -1)
    print(ret)
import sys
f = sys.stdin

main(f)

Submission status: Runtime Error

Solution code:
import math
class seg_tree:
    def __init__(self, n):
        self.depth = math.ceil(math.log(n, 2))
        self.size = 1 << self.depth
        self.bit = [0] * 2 * self.size
        self.renew = [0] * 2 * self.size

    def add(self, p, v):
        p += self.size;
        while p:
            self.bit[p] += v
            p >>= 1

    def query(self, l, r):
        l += self.size
        r += self.size
        ret = 0

        while l < r:
            if l & 1:
                ret += self.bit[l]
                l += 1
            if r & 1:
                r -= 1
                ret += self.bit[r]
            l >>= 1
            r >>= 1
        return ret

    def set_renew(self, l, r):
        l += self.size
        r += self.size

        while l < r:
            if l & 1:
                self.renew[l] = 1
                l += 1
            if r & 1:
                r -= 1
                self.renew[r] = 1
            l >>= 1
            r >>= 1

    def is_renew(self, p):
        p += self.size
        while p:
            if self.renew[p]:
                return True
            p >>= 1
        return False

    def unset_renew(self, p):
        p += self.size
        for i in range(self.depth - 1,0,-1):
            if self.renew[p >> i]:
                self.renew[p >> i] = 0
                self.renew[(p>>i)*2] = self.renew[(p>>i)*2+1] = 1
        self.renew[p] = 0
from collections import UserList
class sorted_set(UserList):
    def __init__(self):
        UserList.__init__(self)
    # 左隣の縦線の位置を取得
    def get_lf(self, v):
        return self.data[bisect(self.data, v) - 1]
        
    def insert(self, v):
        i = bisect(self.data, v)
        if len(self.data) <= i or self.data[i] != v:
            self.data.insert(i, v)
    def erase(self, v):
        self.data.remove(v)
class union_find(UserList):
    def __init__(self):
        UserList.__init__(self)
    def root(self, p):
        if self.data[p] < 0:
            return p
        self.data[p] = self.root(self.data[p])
        return self.data[p]
    def join(self, p, q):
        p, q = self.root(p), self.root(q)

        if p == q:
            return False
        if self.data[p] < self.data[q]:
            p, q = q, p
        self.data[p], self.data[q] = self.data[q], p
        return True
def bisect(a,v):
    l, r = 0, len(a)
    while l < r:
        m = (l + r) // 2
        if a[m] < v:
            l = m + 1
        else:
            r = m
    return l
def adjust(seg, uf, target, p):
    if seg.is_renew(p):
        uf.append(-1)
        seg.unset_renew(p)
        target[p] = len(uf) - 1
from operator import itemgetter
def main(f):    
    w,h,n = map(int,f.readline().split())
    abcd = [list(map(int,line.split())) for line in f]

    abcd.extend([[0,0,w,0],
                 [0,0,0,h],
                 [w,0,w,h],
                 [0,h,w,h]])

    xs = sorted({abcdi[0] for abcdi in abcd} | {abcdi[2] for abcdi in abcd} | {-1})

    for abcdi in abcd:
        abcdi[0] = bisect(xs,abcdi[0])
        abcdi[2] = bisect(xs,abcdi[2])

    s = sorted_set()
    s.insert(0)
    target = [-1] * n * 2
    target[0] = 0
    uf = union_find()
    uf.append(-1)
    seg = seg_tree(len(xs))

    a = []
    for x1,y1,x2,y2 in abcd:
        if x1 == x2:
            a.append((y1, 0, x1, -1))
            a.append((y2, 2, x1, -1))
        else:
            a.append((y1, 1, x1, x2))
    a.sort(key=itemgetter(0,1))
    ret = 0
    for _, act, left, right in a:
        if act == 0:
            lf = s.get_lf(left)

            adjust(seg, uf, target, lf)
            adjust(seg, uf, target, left)
            target[left] = target[lf]

            s.insert(left)
            seg.add(left, 1)
        elif act == 1:
            count = seg.query(left, right+1)
            if count < 2:
               continue
            ret += count - 1;

            seg.set_renew(left, s.get_lf(right + 1))
        elif act == 2:
            lf = s.get_lf(left)
            adjust(seg, uf, target, lf)
            adjust(seg, uf, target, left)
            if uf.join(target[lf], target[left]):
                ret -= 1
            s.erase(left)
            seg.add(left, -1)
    print(ret)
import sys
f = sys.stdin
main(f)

Submission status: Runtime Error

Solution code:
import math
class seg_tree:
    def __init__(self, n):
        self.depth = math.ceil(math.log(n, 2))
        self.size = 1 << self.depth
        self.bit = [0] * 2 * self.size
        self.renew = [0] * 2 * self.size
 
    def add(self, p, v):
        p += self.size;
        while p:
            self.bit[p] += v
            p >>= 1
 
    def query(self, l, r):
        l += self.size
        r += self.size
        ret = 0
 
        while l < r:
            if l & 1:
                ret += self.bit[l]
                l += 1
            if r & 1:
                r -= 1
                ret += self.bit[r]
            l >>= 1
            r >>= 1
        return ret
 
    def set_renew(self, l, r):
        l += self.size
        r += self.size
 
        while l < r:
            if l & 1:
                self.renew[l] = 1
                l += 1
            if r & 1:
                r -= 1
                self.renew[r] = 1
            l >>= 1
            r >>= 1
 
    def is_renew(self, p):
        p += self.size
        while p:
            if self.renew[p]:
                return True
            p >>= 1
        return False
 
    def unset_renew(self, p):
        p += self.size
        for i in range(self.depth - 1,0,-1):
            if self.renew[p >> i]:
                self.renew[p >> i] = 0
                self.renew[(p>>i)*2] = self.renew[(p>>i)*2+1] = 1
        self.renew[p] = 0
    def get_lf(self, r):
        l = self.size
        r += self.size
        while l < r:
            if r & 1:
                r -= 1
                if self.bit[r]:
                    while r < self.size:
                        r <<= 1
                        if self.bit[r + 1]:
                            r += 1
                    return r - self.size
            if l & 1:
                l += 1            
            l >>= 1
            r >>= 1
        return -1
from collections import UserList
class union_find(UserList):
    def __init__(self):
        UserList.__init__(self)
    def root(self, p):
        if self.data[p] < 0:
            return p
        self.data[p] = self.root(self.data[p])
        return self.data[p]
    def join(self, p, q):
        p, q = self.root(p), self.root(q)
 
        if p == q:
            return False
        if self.data[p] < self.data[q]:
            p, q = q, p
        self.data[p], self.data[q] = self.data[q], p
        return True
def bisect(a,v):
    l, r = 0, len(a)
    while l < r:
        m = (l + r) // 2
        if a[m] < v:
            l = m + 1
        else:
            r = m
    return l
def adjust(seg, uf, target, p):
    if seg.is_renew(p):
        uf.append(-1)
        seg.unset_renew(p)
        target[p] = len(uf) - 1
from operator import itemgetter
@profile
def main(f):    
    w,h,n = map(int,f.readline().split())
    abcd = [list(map(int,line.split())) for line in f]
 
    abcd.extend([[0,0,w,0],
                 [0,0,0,h],
                 [w,0,w,h],
                 [0,h,w,h]])
 
    xs = {x:i for i, x in enumerate(sorted(set([abcdi[0] for abcdi in abcd] +[abcdi[2] for abcdi in abcd] + [-1])))}
    abcd =[(xs[a],b,xs[c],d) for a,b,c,d in abcd]
 
    target = [-1] * n * 2
    target[0] = 0
    uf = union_find()
    uf.append(-1)
    seg = seg_tree(len(xs))
    seg.add(0, 1) #
 
    a = []
    for x1,y1,x2,y2 in abcd:
        if x1 == x2:
            a.append((y1, 0, x1, -1))
            a.append((y2, 2, x1, -1))
        else:
            a.append((y1, 1, x1, x2))
    a.sort(key=itemgetter(0,1))
    ret = 0
    for _, act, left, right in a:
        if act == 0:
            lf = seg.get_lf(left)
 
            adjust(seg, uf, target, lf)
            adjust(seg, uf, target, left)
            target[left] = target[lf]
 
            seg.add(left, 1)
        elif act == 1:
            count = seg.query(left, right+1)
            if count < 2:
               continue
            ret += count - 1;
 
            seg.set_renew(left, seg.get_lf(right + 1))
        elif act == 2:
            lf = seg.get_lf(left)
            adjust(seg, uf, target, lf)
            adjust(seg, uf, target, left)
            if uf.join(target[lf], target[left]):
                ret -= 1
            seg.add(left, -1)
    print(ret)
import sys
f = sys.stdin

main(f)