Ezzat and Grid (Codeforces 1557D)
Tags: Greedy, data structures

Moamen was drawing a grid of $$$n$$$ rows and $$$10^9$$$ columns containing only digits $$$0$$$ and $$$1$$$. Ezzat noticed what Moamen was drawing and became interested in the minimum number of rows one needs to remove to make the grid beautiful.A grid is beautiful if and only if for every two consecutive rows there is at least one column containing $$$1$$$ in these two rows.Ezzat will give you the number of rows $$$n$$$, and $$$m$$$ segments of the grid that contain digits $$$1$$$. Every segment is represented with three integers $$$i$$$, $$$l$$$, and $$$r$$$, where $$$i$$$ represents the row number, and $$$l$$$ and $$$r$$$ represent the first and the last column of the segment in that row.For example, if $$$n = 3$$$, $$$m = 6$$$, and the segments are $$$(1,1,1)$$$, $$$(1,7,8)$$$, $$$(2,7,7)$$$, $$$(2,15,15)$$$, $$$(3,1,1)$$$, $$$(3,15,15)$$$, then the grid is:  Your task is to tell Ezzat the minimum number of rows that should be removed to make the grid beautiful.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3\cdot10^5$$$).Each of the next $$$m$$$ lines contains three integers $$$i$$$, $$$l$$$, and $$$r$$$ ($$$1 \le i \le n$$$, $$$1 \le l \le r \le 10^9$$$). Each of these $$$m$$$ lines means that row number $$$i$$$ contains digits $$$1$$$ in columns from $$$l$$$ to $$$r$$$, inclusive.Note that the segments may overlap.

Output: In the first line, print a single integer $$$k$$$ — the minimum number of rows that should be removed.In the second line print $$$k$$$ distinct integers $$$r_1, r_2, \ldots, r_k$$$, representing the rows that should be removed ($$$1 \le r_i \le n$$$), in any order.If there are multiple answers, print any.

Note: In the first test case, the grid is the one explained in the problem statement. The grid has the following properties:   The $$$1$$$-st row and the $$$2$$$-nd row have a common $$$1$$$ in the column $$$7$$$.  The $$$2$$$-nd row and the $$$3$$$-rd row have a common $$$1$$$ in the column $$$15$$$.  As a result, this grid is beautiful and we do not need to remove any row.In the second test case, the given grid is as follows:   

Sample Inputs:
3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15

5 4
1 2 3
2 4 6
3 3 5
5 1 1

Sample Outputs:
0

3
2 4 5

Solution (Python):
import array
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
x = [[] for _ in range(n + 1)]
s = set()
for j in range(m):
    (i, l, r) = map(int, input().split())
    s.add(l)
    s.add(r)
    x[i].append((l, r))
s = list(s)
s.sort()
d = dict()
l = len(s)
for i in range(l):
    d[s[i]] = i
(u, v) = (600500, 500)
c = array.array('i', [0] * u)
c0 = array.array('i', [0] * (u // v))
c1 = array.array('i', [0] * (u // v))
dp = [[] for _ in range(n + 1)]
ml = array.array('i', [0] * (n + 1))
mr = array.array('i', [0] * (n + 1))
ma = 0
for i in range(1, n + 1):
    mai = 1
    for (l, r) in x[i]:
        (dl, dr) = (d[l], d[r])
        while dl % v and dl <= dr and (ma >= mai):
            c[dl] = max(c[dl], c1[dl // v])
            if mai < c[dl] + 1:
                ml[i] = l
                mr[i] = r
                mai = c[dl] + 1
            dl += 1
        if ma < mai:
            break
        while dr % v ^ v - 1 and dl <= dr and (ma >= mai):
            c[dr] = max(c[dr], c1[dr // v])
            if mai < c[dr] + 1:
                ml[i] = l
                mr[i] = r
                mai = c[dr] + 1
            dr -= 1
        if ma < mai:
            break
        while dl <= dr and ma >= mai:
            dlv = dl // v
            c0[dlv] = max(c0[dlv], c1[dlv])
            if mai < c0[dlv] + 1:
                ml[i] = l
                mr[i] = r
                mai = c0[dlv] + 1
            dl += v
        if ma < mai:
            break
    for (l, r) in x[i]:
        (dl, dr) = (d[l], d[r])
        while dl % v and dl <= dr:
            c[dl] = max(c[dl], mai)
            c0[dl // v] = max(c[dl], c0[dl // v])
            dl += 1
        while dr % v ^ v - 1 and dl <= dr:
            c[dr] = max(c[dr], mai)
            c0[dr // v] = max(c[dr], c0[dr // v])
            dr -= 1
        while dl <= dr:
            c1[dl // v] = max(c1[dl // v], mai)
            dl += v
    dp[mai].append(i)
    ma = max(ma, mai)
s = set()
i = dp[ma][0]
c = ma
s.add(i)
for _ in range(ma - 1):
    (mli, mri) = (ml[i], mr[i])
    for j in dp[c - 1]:
        if j > i:
            continue
        ok = 0
        for (l, r) in x[j]:
            if l <= mri and mli <= r:
                ok = 1
                break
        if ok:
            s.add(j)
            i = j
            break
    c -= 1
k = n - len(s)
r = []
for i in range(1, n + 1):
    if not i in s:
        r.append(i)
sys.stdout.write(str(k) + '\n')
sys.stdout.write(' '.join(map(str, r)))

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class lazy_segtree:

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.identity

    def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
        self.n = len(V)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        self.lz = [ID for i in range(self.size)]
        self.e = E
        self.op = OP
        self.mapping = MAPPING
        self.composition = COMPOSITION
        self.identity = ID
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return self.e
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r >> i)
        (sml, smr) = (self.e, self.e)
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply_point(self, p, f):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def apply(self, l, r, f):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r - 1 >> i)
        (l2, r2) = (l, r)
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        (l, r) = (l2, r2)
        for i in range(1, self.log + 1):
            if l >> i << i != l:
                self.update(l >> i)
            if r >> i << i != r:
                self.update(r - 1 >> i)

    def max_right(self, l, g):
        assert 0 <= l and l <= self.n
        assert g(self.e)
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l:
                break
        return self.n

    def min_left(self, r, g):
        assert 0 <= r and r <= self.n
        assert g(self.e)
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push(r - 1 >> i)
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r:
                break
        return 0
(n, m) = map(int, input().split())
row = [[] for i in range(n)]
s = set()
for _ in range(m):
    (i, l, r) = map(int, input().split())
    i -= 1
    row[i].append((l, r))
    s.add(l)
    s.add(r + 1)
s = sorted(list(s))
M = len(s)
idx = {}
for i in range(M):
    idx[s[i]] = i

def op(a, b):
    return max(a, b)
e = -1

def mapping(f, x):
    if f == ID:
        return x
    return f

def composition(f, g):
    if f == ID:
        return g
    return f
ID = -1
par = [-1] * n
mask20 = (1 << 20) - 1
MX = [1] * n
seg = lazy_segtree([0] * M, op, e, mapping, composition, ID)
for i in range(n):
    mx = 0
    for (l, r) in row[i]:
        mx = max(mx, seg.prod(idx[l], idx[r + 1]))
    if mx != 0:
        mx1 = mx >> 20
        mx1 += 1
        p = mx & mask20
        par[i] = p
        MX[i] = mx1
    else:
        mx1 = 1
    for (l, r) in row[i]:
        seg.apply(idx[l], idx[r + 1], mx1 << 20 | i)
use = [1] * n
res = MX.index(max(MX))
while res != -1:
    use[res] = 0
    res = par[res]
ans = []
for i in range(n):
    if use[i]:
        ans.append(i + 1)
print(len(ans))
print(*ans)

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class lazy_segtree:

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.identity

    def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
        self.n = len(V)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        self.lz = [ID for i in range(self.size)]
        self.e = E
        self.op = OP
        self.mapping = MAPPING
        self.composition = COMPOSITION
        self.identity = ID
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return self.e
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r >> i)
        (sml, smr) = (self.e, self.e)
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply_point(self, p, f):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def apply(self, l, r, f):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r - 1 >> i)
        (l2, r2) = (l, r)
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        (l, r) = (l2, r2)
        for i in range(1, self.log + 1):
            if l >> i << i != l:
                self.update(l >> i)
            if r >> i << i != r:
                self.update(r - 1 >> i)

    def max_right(self, l, g):
        assert 0 <= l and l <= self.n
        assert g(self.e)
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l:
                break
        return self.n

    def min_left(self, r, g):
        assert 0 <= r and r <= self.n
        assert g(self.e)
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push(r - 1 >> i)
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r:
                break
        return 0
(n, m) = map(int, input().split())
row = [[] for i in range(n)]
s = set()
for _ in range(m):
    (i, l, r) = map(int, input().split())
    i -= 1
    row[i].append((l, r))
    s.add(l)
    s.add(r + 1)
s = sorted(list(s))
M = len(s)
idx = {}
for i in range(M):
    idx[s[i]] = i

def op(a, b):
    return max(a, b)
e = -1

def mapping(f, x):
    if f == ID:
        return x
    return f

def composition(f, g):
    if f == ID:
        return g
    return f
ID = -1
par = [-1] * n
mask20 = (1 << 20) - 1
MX = [1] * n
seg = lazy_segtree([0] * M, op, e, mapping, composition, ID)
for i in range(n):
    mx = 0
    for (l, r) in row[i]:
        mx = max(mx, seg.prod(idx[l], idx[r + 1]))
    if mx != 0:
        mx1 = mx >> 20
        mx1 += 1
        p = mx & mask20
        par[i] = p
        MX[i] = mx1
    else:
        mx1 = 1
    for (l, r) in row[i]:
        seg.apply(idx[l], idx[r + 1], mx1 << 20 | i)
use = [1] * n
res = MX.index(max(MX))
while res != -1:
    use[res] = 0
    res = par[res]
ans = []
for i in range(n):
    if use[i]:
        ans.append(i + 1)
print(len(ans))
print(*ans)