Bicolored Segments (Codeforces 1389F)
Tags: DP, graph matchings

You are given $$$n$$$ segments $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$. Each segment has one of two colors: the $$$i$$$-th segment's color is $$$t_i$$$.Let's call a pair of segments $$$i$$$ and $$$j$$$ bad if the following two conditions are met:  $$$t_i \ne t_j$$$;  the segments $$$[l_i, r_i]$$$ and $$$[l_j, r_j]$$$ intersect, embed or touch, i. e. there exists an integer $$$x$$$ such that $$$x \in [l_i, r_i]$$$ and $$$x \in [l_j, r_j]$$$. Calculate the maximum number of segments that can be selected from the given ones, so that there is no bad pair among the selected ones.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of segments.The next $$$n$$$ lines contains three integers $$$l_i, r_i, t_i$$$ ($$$1 \le l_i \le r_i \le 10^9; t_i \in \{1, 2\}$$$) — description of the $$$i$$$-th segment.

Output: Print the maximum number of segments that can be selected, so that there is no bad pair among the selected segments.


Sample Inputs:
3
1 3 1
4 6 2
2 5 1

5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2

7
19 20 1
13 15 2
6 11 2
4 10 1
14 17 1
13 13 2
5 9 1

Sample Outputs:
2

4

5

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def update(l, r, s, tree, lazy):
    (q, ll, rr, i) = ([1], [0], [l1 - 1], 0)
    while len(q) ^ i:
        j = q[i]
        (l0, r0) = (ll[i], rr[i])
        if l <= l0 and r0 <= r:
            lazy[j] += s
            i += 1
            continue
        m0 = l0 + r0 >> 1
        if j < l1 and lazy[j]:
            lazy[j << 1] += lazy[j]
            lazy[j << 1 ^ 1] += lazy[j]
            lazy[j] = 0
        if l <= m0 and l0 <= r:
            q.append(j << 1)
            ll.append(l0)
            rr.append(m0)
        if l <= r0 and m0 + 1 <= r:
            q.append(j << 1 ^ 1)
            ll.append(m0 + 1)
            rr.append(r0)
        i += 1
    for i in reversed(q):
        if i < l1:
            (j, k) = (i << 1, i << 1 ^ 1)
            tree[i] = max(tree[j] + lazy[j], tree[k] + lazy[k])
    return

def update0(i, s, tree, lazy):
    i += l1
    lazy[i] += s
    i >>= 1
    while i:
        (j, k) = (i << 1, i << 1 ^ 1)
        tree[i] = max(tree[j] + lazy[j], tree[k] + lazy[k])
        i >>= 1
    return

def get_max(s, t, tree, lazy):
    update(s, t, 0, tree, lazy)
    s += l1
    t += l1
    ans = 0
    while s <= t:
        if s % 2:
            ans = max(ans, tree[s] + lazy[s])
            s += 1
        s >>= 1
        if not t % 2:
            ans = max(ans, tree[t] + lazy[t])
            t -= 1
        t >>= 1
    return ans
n = int(input())
s = set()
x = []
for _ in range(n):
    (l, r, t) = map(int, input().split())
    s.add(l)
    s.add(r)
    x.append((l, r, t))
s = list(s)
s.sort()
d = dict()
m = len(s)
for i in range(m):
    d[s[i]] = i + 1
u = [[] for _ in range(m + 1)]
for (l, r, t) in x:
    u[d[r]].append((d[l], t))
l1 = pow(2, (m + 2).bit_length())
l2 = 2 * l1
(tree1, lazy1) = ([0] * l2, [0] * l2)
(tree2, lazy2) = ([0] * l2, [0] * l2)
(dp1, dp2) = ([0] * (m + 1), [0] * (m + 1))
for r in range(1, m + 1):
    for (l, t) in sorted(u[r], reverse=True):
        if t == 1:
            update(1, l, 1, tree1, lazy1)
        else:
            update(1, l, 1, tree2, lazy2)
    dp1[r] = max(dp1[r - 1], tree1[1] + lazy1[1])
    dp2[r] = max(dp2[r - 1], tree2[1] + lazy2[1])
    update0(r + 1, dp1[r], tree2, lazy2)
    update0(r + 1, dp2[r], tree1, lazy1)
ans = max(dp1[m], dp2[m])
print(ans)

Solution (Python):
class LazySegmentTree:

    def __init__(self, n, init, merge_func=max, ide_ele=-10 ** 18):
        self.n = (n - 1).bit_length()
        self.merge_func = merge_func
        self.ide_ele = ide_ele
        self.data = [0 for i in range(1 << self.n + 1)]
        self.lazy = [0 for i in range(1 << self.n + 1)]
        for i in range(n):
            self.data[2 ** self.n + i] = init[i]
        for i in range(2 ** self.n - 1, 0, -1):
            self.data[i] = self.merge_func(self.data[2 * i], self.data[2 * i + 1])

    def propagate_above(self, i):
        m = i.bit_length() - 1
        for bit in range(m, 0, -1):
            v = i >> bit
            add = self.lazy[v]
            self.lazy[v] = 0
            self.data[2 * v] += add
            self.data[2 * v + 1] += add
            self.lazy[2 * v] += add
            self.lazy[2 * v + 1] += add

    def remerge_above(self, i):
        while i:
            i >>= 1
            self.data[i] = self.merge_func(self.data[2 * i], self.data[2 * i + 1]) + self.lazy[i]

    def update(self, l, r, x):
        l += 1 << self.n
        r += 1 << self.n
        l0 = l // (l & -l)
        r0 = r // (r & -r) - 1
        while l < r:
            self.data[l] += x * (l & 1)
            self.lazy[l] += x * (l & 1)
            l += l & 1
            self.data[r - 1] += x * (r & 1)
            self.lazy[r - 1] += x * (r & 1)
            l >>= 1
            r >>= 1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self, l, r):
        l += 1 << self.n
        r += 1 << self.n
        l0 = l // (l & -l)
        r0 = r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res = self.ide_ele
        while l < r:
            if l & 1:
                res = self.merge_func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.merge_func(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res
import sys
input = sys.stdin.buffer.readline
n = int(input())
a = []
b = []
val = set()
for i in range(n):
    (l, r, t) = map(int, input().split())
    if t == 1:
        a.append((l, r))
    else:
        b.append((l, r))
    val.add(l)
    val.add(r)
val = sorted(list(val))
comp = {i: e for (e, i) in enumerate(val)}
N = len(val)
querya = [[] for i in range(N)]
queryb = [[] for i in range(N)]
for i in range(len(a)):
    (l, r) = a[i]
    a[i] = (comp[l], comp[r])
    querya[comp[r]].append(comp[l])
for i in range(len(b)):
    (l, r) = b[i]
    b[i] = (comp[l], comp[r])
    queryb[comp[r]].append(comp[l])
init = [0] * N
LSTA = LazySegmentTree(N, init)
LSTB = LazySegmentTree(N, init)
dp = [0] * N
for i in range(N):
    for l in querya[i]:
        LSTA.update(0, l + 1, 1)
    for l in queryb[i]:
        LSTB.update(0, l + 1, 1)
    temp1 = LSTA.query(0, i + 1)
    temp2 = LSTB.query(0, i + 1)
    dp[i] = max(temp1, temp2)
    if i != N - 1:
        LSTA.update(i + 1, i + 2, dp[i])
        LSTB.update(i + 1, i + 2, dp[i])
print(dp[N - 1])

Solution (Python):
from operator import add

class LazySegmentTree:

    def __init__(self, n, init, merge=max, merge_unit=-10 ** 18, operate=add, operate_unit=0):
        self.merge = merge
        self.merge_unit = merge_unit
        self.operate = operate
        self.operate_unit = operate_unit
        self.n = (n - 1).bit_length()
        self.data = [0 for i in range(1 << self.n + 1)]
        self.lazy = [0 for i in range(1 << self.n + 1)]
        for i in range(n):
            self.data[2 ** self.n + i] = init[i]
        for i in range(2 ** self.n - 1, 0, -1):
            self.data[i] = self.merge(self.data[2 * i], self.data[2 * i + 1])

    def propagate_above(self, i):
        m = i.bit_length() - 1
        for bit in range(m, 0, -1):
            v = i >> bit
            add = self.lazy[v]
            self.lazy[v] = 0
            self.data[2 * v] = self.operate(self.data[2 * v], add)
            self.data[2 * v + 1] = self.operate(self.data[2 * v + 1], add)
            self.lazy[2 * v] = self.operate(self.lazy[2 * v], add)
            self.lazy[2 * v + 1] = self.operate(self.lazy[2 * v + 1], add)

    def remerge_above(self, i):
        while i:
            i >>= 1
            self.data[i] = self.operate(self.merge(self.data[2 * i], self.data[2 * i + 1]), self.lazy[i])

    def update(self, l, r, x):
        l += 1 << self.n
        r += 1 << self.n
        l0 = l // (l & -l)
        r0 = r // (r & -r) - 1
        while l < r:
            if l & 1:
                self.data[l] = self.operate(self.data[l], x)
                self.lazy[l] = self.operate(self.lazy[l], x)
                l += 1
            if r & 1:
                self.data[r - 1] = self.operate(self.data[r - 1], x)
                self.lazy[r - 1] = self.operate(self.lazy[r - 1], x)
            l >>= 1
            r >>= 1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self, l, r):
        l += 1 << self.n
        r += 1 << self.n
        l0 = l // (l & -l)
        r0 = r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res = self.merge_unit
        while l < r:
            if l & 1:
                res = self.merge(res, self.data[l])
                l += 1
            if r & 1:
                res = self.merge(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res
import sys
input = sys.stdin.buffer.readline
n = int(input())
a = []
b = []
val = set()
for i in range(n):
    (l, r, t) = map(int, input().split())
    if t == 1:
        a.append((l, r))
    else:
        b.append((l, r))
    val.add(l)
    val.add(r)
val = sorted(list(val))
comp = {i: e for (e, i) in enumerate(val)}
N = len(val)
querya = [[] for i in range(N)]
queryb = [[] for i in range(N)]
for i in range(len(a)):
    (l, r) = a[i]
    a[i] = (comp[l], comp[r])
    querya[comp[r]].append(comp[l])
for i in range(len(b)):
    (l, r) = b[i]
    b[i] = (comp[l], comp[r])
    queryb[comp[r]].append(comp[l])
init = [0] * N
LSTA = LazySegmentTree(N, init)
LSTB = LazySegmentTree(N, init)
dp = [0] * N
for i in range(N):
    for l in querya[i]:
        LSTA.update(0, l + 1, 1)
    for l in queryb[i]:
        LSTB.update(0, l + 1, 1)
    temp1 = LSTA.query(0, i + 1)
    temp2 = LSTB.query(0, i + 1)
    dp[i] = max(temp1, temp2)
    if i != N - 1:
        LSTA.update(i + 1, i + 2, dp[i])
        LSTB.update(i + 1, i + 2, dp[i])
print(dp[N - 1])