MEX Queries (Codeforces 817F)
Tags: Others, trees

You are given a set of integer numbers, initially it is empty. You should perform n queries.There are three different types of queries:   1 l r — Add all missing numbers from the interval [l, r]  2 l r — Remove all present numbers from the interval [l, r]  3 l r — Invert the interval [l, r] — add all missing and remove all present numbers from the interval [l, r] After each query you should output MEX of the set — the smallest positive (MEX  ≥ 1) integer number which is not presented in the set.

Input: The first line contains one integer number n (1 ≤ n ≤ 105).Next n lines contain three integer numbers t, l, r (1 ≤ t ≤ 3, 1 ≤ l ≤ r ≤ 1018) — type of the query, left and right bounds.

Output: Print MEX of the set after each query.

Note: Here are contents of the set after each query in the first example:  {3, 4} — the interval [3, 4] is added  {1, 2, 5, 6} — numbers {3, 4} from the interval [1, 6] got deleted and all the others are added  {5, 6} — numbers {1, 2} got deleted 

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

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

Sample Outputs:
1
3
1

4
4
4
1

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

def f(z, l, r):
    j = l // m
    c = 0
    if z == 0:
        return
    elif z == 1:
        for i in range(l, r):
            c += 1 - a[i]
            a[i] = 1
    elif z == 2:
        for i in range(l, r):
            c -= a[i]
            a[i] = 0
    else:
        for i in range(l, r):
            c += 1 - 2 * a[i]
            a[i] ^= 1
    cnt[j] += c
    return
n = int(input())
tlr = [list(map(int, input().split())) for _ in range(n)]
s = set()
for (_, l, r) in tlr:
    s.add(l)
    s.add(l - 1)
    s.add(r)
    s.add(r + 1)
s.add(1)
if 0 in s:
    s.remove(0)
s = list(s)
s.sort()
d = dict()
ls = len(s)
for i in range(ls):
    d[s[i]] = i
m = 357
u = (ls // m + min(ls % m, 1) + 1) * m
v = u // m
a = [0] * u
b = [0] * v
cnt = [0] * v
ans = []
for (t, l0, r0) in tlr:
    (l, r) = (d[l0], d[r0])
    (x, y) = (l // m, r // m)
    if t < 3:
        for i in range(x + 1, y):
            b[i] = t
    else:
        for i in range(x + 1, y):
            b[i] ^= 3
    if x == y:
        f(b[x], x * m, l)
        f(b[x], r + 1, (x + 1) * m)
        if t < 3:
            f(t, l, r + 1)
        else:
            f(t ^ b[x], l, r + 1)
    else:
        f(b[x], x * m, l)
        f(b[y], r + 1, (y + 1) * m)
        if t < 3:
            f(t, l, (x + 1) * m)
            f(t, y * m, r + 1)
        else:
            f(t ^ b[x], l, (x + 1) * m)
            f(t ^ b[y], y * m, r + 1)
    (b[x], b[y]) = (0, 0)
    i = 0
    while not cnt[i] ^ m and (not b[i]) or (not cnt[i] and b[i] == 3) or b[i] == 1:
        i += 1
    i *= m
    f(b[i // m], i // m * m, i // m * m + m)
    b[i // m] = 0
    while i < len(s) - 1 and a[i]:
        if b[i // m]:
            f(b[i // m], i // m * m, i // m * m + m)
            b[i // m] = 0
        i += 1
    ans0 = s[i]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

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

def f(z, l, r):
    j = l // m
    c = 0
    if z == 0:
        return
    elif z == 1:
        for i in range(l, r):
            c += 1 - a[i]
            a[i] = 1
    elif z == 2:
        for i in range(l, r):
            c -= a[i]
            a[i] = 0
    else:
        for i in range(l, r):
            c += 1 - 2 * a[i]
            a[i] ^= 1
    cnt[j] += c
    return
n = int(input())
tlr = [list(map(int, input().split())) for _ in range(n)]
s = set()
for (_, l, r) in tlr:
    s.add(l)
    s.add(l - 1)
    s.add(r)
    s.add(r + 1)
s.add(1)
if 0 in s:
    s.remove(0)
s = list(s)
s.sort()
d = dict()
ls = len(s)
for i in range(ls):
    d[s[i]] = i
m = 357
u = (ls // m + min(ls % m, 1) + 1) * m
v = u // m
a = [0] * u
b = [0] * v
cnt = [0] * v
ans = []
for (t, l0, r0) in tlr:
    (l, r) = (d[l0], d[r0])
    (x, y) = (l // m, r // m)
    if t < 3:
        for i in range(x + 1, y):
            b[i] = t
    else:
        for i in range(x + 1, y):
            b[i] ^= 3
    if x == y:
        f(b[x], x * m, l)
        f(b[x], r + 1, (x + 1) * m)
        if t < 3:
            f(t, l, r + 1)
        else:
            f(t ^ b[x], l, r + 1)
    else:
        f(b[x], x * m, l)
        f(b[y], r + 1, (y + 1) * m)
        if t < 3:
            f(t, l, (x + 1) * m)
            f(t, y * m, r + 1)
        else:
            f(t ^ b[x], l, (x + 1) * m)
            f(t ^ b[y], y * m, r + 1)
    (b[x], b[y]) = (0, 0)
    i = 0
    while not cnt[i] ^ m and (not b[i]) or (not cnt[i] and b[i] == 3) or b[i] == 1:
        i += 1
    i *= m
    f(b[i // m], i // m * m, i // m * m + m)
    b[i // m] = 0
    while i < len(s) - 1 and a[i]:
        if b[i // m]:
            f(b[i // m], i // m * m, i // m * m + m)
            b[i // m] = 0
        i += 1
    ans0 = s[i]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, 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

def operate(x, y):
    return x & y
id = 0
inf = 1 << 20

def mapping(f, x):
    if f == id:
        return x
    elif f == 1:
        return 1
    elif f == 2:
        return 2
    else:
        y = x & 1
        z = x >> 1
        return 2 * y + z

def composition(f, g):
    if f == id:
        return g
    if f != 3:
        return f
    if g == 0:
        return 3
    if g == 1:
        return 2
    if g == 2:
        return 1
    else:
        return 0
n = int(input())
query = []
s = set([1])
for _ in range(n):
    (t, l, r) = map(int, input().split())
    query.append((t, l, r))
    s.add(l)
    s.add(r + 1)
s = sorted(list(s))
m = len(s)
d = {}
for i in range(m):
    d[s[i]] = i
a = [2] * m
seg = lazy_segtree(a, operate, 3, mapping, composition, id)
for (t, l, r) in query:
    L = d[l]
    R = d[r + 1]
    seg.apply(L, R, t)

    def f(x):
        return x & 1
    print(s[seg.max_right(0, f)])