Machine Learning (Codeforces 940F)
Tags: Others, data structures

You come home and fell some unpleasant smell. Where is it coming from?You are given an array a. You have to answer the following queries:   You are given two integers l and r. Let ci be the number of occurrences of i in al: r, where al: r is the subarray of a from l-th element to r-th inclusive. Find the Mex of {c0, c1, ..., c109}  You are given two integers p to x. Change ap to x. The Mex of a multiset of numbers is the smallest non-negative integer not in the set.Note that in this problem all elements of a are positive, which means that c0 = 0 and 0 is never the answer for the query of the second type.

Input: The first line of input contains two integers n and q (1 ≤ n, q ≤ 100 000) — the length of the array and the number of queries respectively.The second line of input contains n integers — a1, a2, ..., an (1 ≤ ai ≤ 109).Each of the next q lines describes a single query.The first type of query is described by three integers ti = 1, li, ri, where 1 ≤ li ≤ ri ≤ n — the bounds of the subarray.The second type of query is described by three integers ti = 2, pi, xi, where 1 ≤ pi ≤ n is the index of the element, which must be changed and 1 ≤ xi ≤ 109 is the new value.

Output: For each query of the first type output a single integer  — the Mex of {c0, c1, ..., c109}.

Note: The subarray of the first query consists of the single element — 1. The subarray of the second query consists of four 2s, one 3 and two 1s.The subarray of the fourth query consists of three 1s, three 2s and one 3.

Sample Inputs:
10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8

Sample Outputs:
2
3
2

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

def f(u, v, w):
    return u << 40 ^ v << 20 ^ w
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
(d, c) = (dict(), 0)
for i in range(n):
    if not a[i] in d:
        d[a[i]] = c
        c += 1
    a[i] = d[a[i]]
(m1, m2) = (40, 2500)
(l0, r0) = ([0] * m2, [0] * m2)
ans = []
while q:
    q0 = min(q, m2)
    z = []
    ans1 = [-1] * q0
    u = []
    for i in range(q0):
        (t, l, r) = map(int, input().split())
        if t == 1:
            (l, r) = (l - 1, r - 1)
            x = l // m2
            y = r if not x & 1 else n - r - 1
            z.append(f(x, y, i))
        else:
            l -= 1
            if not r in d:
                d[r] = c
                c += 1
            r = d[r]
            u.append(i)
        (l0[i], r0[i]) = (l, r)
    z = [i & 1048575 for i in sorted(z)]
    (l, r) = (0, 0)
    cnt = [0] * (c + 1)
    now = [0] * (n + 2)
    if z:
        (l, r) = (l0[z[0]], l0[z[0]])
        (cnt[a[l]], now[1]) = (1, 1)
    v = -1
    for j in z:
        (ll, rr) = (l0[j], r0[j])
        while ll < l:
            l -= 1
            al = a[l]
            now[cnt[al]] -= 1
            cnt[al] += 1
            now[cnt[al]] += 1
        while r < rr:
            r += 1
            ar = a[r]
            now[cnt[ar]] -= 1
            cnt[ar] += 1
            now[cnt[ar]] += 1
        while l < ll:
            al = a[l]
            now[cnt[al]] -= 1
            cnt[al] -= 1
            now[cnt[al]] += 1
            l += 1
        while rr < r:
            ar = a[r]
            now[cnt[ar]] -= 1
            cnt[ar] -= 1
            now[cnt[ar]] += 1
            r -= 1
        while v + 1 < len(u) and u[v + 1] < j:
            v += 1
            k = u[v]
            (p, x) = (l0[k], r0[k])
            r0[k] = a[p]
            if l <= p <= r:
                ap = a[p]
                now[cnt[ap]] -= 1
                cnt[ap] -= 1
                now[cnt[ap]] += 1
                now[cnt[x]] -= 1
                cnt[x] += 1
                now[cnt[x]] += 1
            a[p] = x
        while v >= 0 and (not u[v] < j):
            k = u[v]
            (p, x) = (l0[k], r0[k])
            r0[k] = a[p]
            v -= 1
            if l <= p <= r:
                ap = a[p]
                now[cnt[ap]] -= 1
                cnt[ap] -= 1
                now[cnt[ap]] += 1
                now[cnt[x]] -= 1
                cnt[x] += 1
                now[cnt[x]] += 1
            a[p] = x
        ans0 = 1
        while now[ans0]:
            ans0 += 1
        ans1[j] = ans0
    for i in range(q0):
        if ans1[i] ^ -1:
            ans.append(ans1[i])
    v += 1
    for i in u[v:]:
        (p, x) = (l0[i], r0[i])
        a[p] = x
    q -= q0
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(u, v, w):
    return u << 40 ^ v << 20 ^ w
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
(d, c) = (dict(), 0)
for i in range(n):
    if not a[i] in d:
        d[a[i]] = c
        c += 1
    a[i] = d[a[i]]
(m1, m2) = (50, 2000)
(l0, r0) = ([0] * m2, [0] * m2)
ans = []
while q:
    q0 = min(q, m2)
    z = []
    ans1 = [-1] * q0
    u = []
    for i in range(q0):
        (t, l, r) = map(int, input().split())
        if t == 1:
            (l, r) = (l - 1, r - 1)
            x = l // m2
            y = r if not x & 1 else n - r - 1
            z.append(f(x, y, i))
        else:
            l -= 1
            if not r in d:
                d[r] = c
                c += 1
            r = d[r]
            u.append(i)
        (l0[i], r0[i]) = (l, r)
    z = [i & 1048575 for i in sorted(z)]
    (l, r) = (0, 0)
    cnt = [0] * (c + 1)
    now = [0] * (n + 2)
    if z:
        (l, r) = (l0[z[0]], l0[z[0]])
        (cnt[a[l]], now[1]) = (1, 1)
    v = -1
    for j in z:
        (ll, rr) = (l0[j], r0[j])
        while ll < l:
            l -= 1
            al = a[l]
            now[cnt[al]] -= 1
            cnt[al] += 1
            now[cnt[al]] += 1
        while r < rr:
            r += 1
            ar = a[r]
            now[cnt[ar]] -= 1
            cnt[ar] += 1
            now[cnt[ar]] += 1
        while l < ll:
            al = a[l]
            now[cnt[al]] -= 1
            cnt[al] -= 1
            now[cnt[al]] += 1
            l += 1
        while rr < r:
            ar = a[r]
            now[cnt[ar]] -= 1
            cnt[ar] -= 1
            now[cnt[ar]] += 1
            r -= 1
        while v + 1 < len(u) and u[v + 1] < j:
            v += 1
            k = u[v]
            (p, x) = (l0[k], r0[k])
            r0[k] = a[p]
            if l <= p <= r:
                ap = a[p]
                now[cnt[ap]] -= 1
                cnt[ap] -= 1
                now[cnt[ap]] += 1
                now[cnt[x]] -= 1
                cnt[x] += 1
                now[cnt[x]] += 1
            a[p] = x
        while v >= 0 and (not u[v] < j):
            k = u[v]
            (p, x) = (l0[k], r0[k])
            r0[k] = a[p]
            v -= 1
            if l <= p <= r:
                ap = a[p]
                now[cnt[ap]] -= 1
                cnt[ap] -= 1
                now[cnt[ap]] += 1
                now[cnt[x]] -= 1
                cnt[x] += 1
                now[cnt[x]] += 1
            a[p] = x
        ans0 = 1
        while now[ans0]:
            ans0 += 1
        ans1[j] = ans0
    for i in range(q0):
        if ans1[i] ^ -1:
            ans.append(ans1[i])
    v += 1
    for i in u[v:]:
        (p, x) = (l0[i], r0[i])
        a[p] = x
    q -= q0
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(u, v, w):
    return u << 40 ^ v << 20 ^ w
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
(d, c) = (dict(), 0)
for i in range(n):
    if not a[i] in d:
        d[a[i]] = c
        c += 1
    a[i] = d[a[i]]
(m1, m2) = (50, 2000)
(l0, r0) = ([0] * m2, [0] * m2)
ans = []
while q:
    q0 = min(q, m2)
    z = []
    ans1 = [-1] * q0
    s0 = [0] * (m1 + 1)
    u = []
    for i in range(q0):
        (t, l, r) = map(int, input().split())
        if t == 1:
            (l, r) = (l - 1, r - 1)
            x = l // m2
            y = r if not x & 1 else n - r - 1
            z.append(f(x, y, i))
            s0[x + 1] += 1
        else:
            l -= 1
            if not r in d:
                d[r] = c
                c += 1
            r = d[r]
            if a[l] ^ r:
                u.append(i)
        (l0[i], r0[i]) = (l, r)
    for i in range(1, m1 + 1):
        s0[i] += s0[i - 1]
    z.sort()
    (l, r) = (0, 0)
    cnt = [0] * (c + 1)
    now = [0] * (n + 2)
    (cnt[a[0]], now[1]) = (1, 1)
    for s in range(m1):
        for i in range(s0[s], s0[s + 1]):
            j = z[i] & 1048575
            (ll, rr) = (l0[j], r0[j])
            while ll < l:
                l -= 1
                al = a[l]
                now[cnt[al]] -= 1
                cnt[al] += 1
                now[cnt[al]] += 1
            while r < rr:
                r += 1
                ar = a[r]
                now[cnt[ar]] -= 1
                cnt[ar] += 1
                now[cnt[ar]] += 1
            while l < ll:
                al = a[l]
                now[cnt[al]] -= 1
                cnt[al] -= 1
                now[cnt[al]] += 1
                l += 1
            while rr < r:
                ar = a[r]
                now[cnt[ar]] -= 1
                cnt[ar] -= 1
                now[cnt[ar]] += 1
                r -= 1
            (st1, st2) = ([], [])
            for k in u:
                if k > j:
                    break
                if l <= l0[k] <= r:
                    (p, x) = (l0[k], r0[k])
                    ap = a[p]
                    now[cnt[ap]] -= 1
                    cnt[ap] -= 1
                    now[cnt[ap]] += 1
                    st1.append(p)
                    st2.append(ap)
                    a[p] = x
                    now[cnt[x]] -= 1
                    cnt[x] += 1
                    now[cnt[x]] += 1
            ans0 = 1
            while now[ans0]:
                ans0 += 1
            ans1[j] = ans0
            for (p, x) in zip(st1[::-1], st2[::-1]):
                ap = a[p]
                now[cnt[ap]] -= 1
                cnt[ap] -= 1
                now[cnt[ap]] += 1
                a[p] = x
                now[cnt[x]] -= 1
                cnt[x] += 1
                now[cnt[x]] += 1
    for i in range(q0):
        if ans1[i] ^ -1:
            ans.append(ans1[i])
    for i in u:
        (p, x) = (l0[i], r0[i])
        a[p] = x
    q -= q0
sys.stdout.write('\n'.join(map(str, ans)))