Minimum Difference (Codeforces 1476G)
Tags: Others, hashing

You are given an integer array $$$a$$$ of size $$$n$$$.You have to perform $$$m$$$ queries. Each query has one of two types:   "$$$1$$$ $$$l$$$ $$$r$$$ $$$k$$$" — calculate the minimum value $$$dif$$$ such that there are exist $$$k$$$ distinct integers $$$x_1, x_2, \dots, x_k$$$ such that $$$cnt_i > 0$$$ (for every $$$i \in [1, k]$$$) and $$$|cnt_i - cnt_j| \le dif$$$ (for every $$$i \in [1, k], j \in [1, k]$$$), where $$$cnt_i$$$ is the number of occurrences of $$$x_i$$$ in the subarray $$$a[l..r]$$$. If it is impossible to choose $$$k$$$ integers, report it;  "$$$2$$$ $$$p$$$ $$$x$$$" — assign $$$a_{p} := x$$$. 

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the size of the array $$$a$$$ and the number of queries.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).Next $$$m$$$ lines contain queries (one per line). Each query has one of two types:   "$$$1$$$ $$$l$$$ $$$r$$$ $$$k$$$" ($$$1 \le l \le r \le n; 1 \le k \le 10^5$$$)  "$$$2$$$ $$$p$$$ $$$x$$$" ($$$1 \le p \le n; 1 \le x \le 10^5$$$). It's guaranteed that there is at least one query of the first type.

Output: For each query of the first type, print the minimum value of $$$dif$$$ that satisfies all required conditions, or $$$-1$$$ if it is impossible to choose $$$k$$$ distinct integers.


Sample Inputs:
12 11
2 1 1 2 1 1 3 2 1 1 3 3
1 2 10 3
1 2 11 3
2 7 2
1 3 9 2
1 1 12 1
1 1 12 4
2 12 4
1 1 12 4
2 1 5
1 3 12 2
1 1 4 3

Sample Outputs:
5
4
1
0
-1
5
0
1

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()))
pow2 = [1]
for _ in range(62):
    pow2.append(2 * pow2[-1])
b = 63
m = 100005
m0 = m // b + 1
(m1, m2) = (40, 2500)
(l0, r0, k0) = ([0] * m2, [0] * m2, [0] * m2)
inf = pow(10, 9) + 1
ans = []
while q:
    q0 = min(q, m2)
    z = []
    ans1 = [-2] * q0
    u = []
    for i in range(q0):
        t0 = list(map(int, input().split()))
        t = t0[0]
        if t == 1:
            (l, r, k) = (t0[1] - 1, t0[2] - 1, t0[3])
            x = l // m2
            y = r if not x & 1 else n - r - 1
            z.append(f(x, y, i))
            (l0[i], r0[i], k0[i]) = (l, r, k)
        else:
            (p, x) = (t0[1] - 1, t0[2])
            u.append(i)
            (l0[i], r0[i]) = (p, x)
    z = [i & 1048575 for i in sorted(z)]
    cnt = [0] * m
    now = [0] * m
    ok = [0] * m0
    if z:
        (l, r) = (l0[z[0]], l0[z[0]])
        (cnt[a[l]], now[1], ok[0]) = (1, 1, 2)
    u0 = -1
    for j in z:
        (ll, rr) = (l0[j], r0[j])
        while ll < l:
            l -= 1
            i = cnt[a[l]]
            now[i] -= 1
            if not now[i]:
                ok[i // b] ^= pow2[i % b]
            cnt[a[l]] += 1
            i += 1
            now[i] += 1
            ok[i // b] |= pow2[i % b]
        while r < rr:
            r += 1
            i = cnt[a[r]]
            now[i] -= 1
            if not now[i]:
                ok[i // b] ^= pow2[i % b]
            cnt[a[r]] += 1
            i += 1
            now[i] += 1
            ok[i // b] |= pow2[i % b]
        while l < ll:
            i = cnt[a[l]]
            now[i] -= 1
            if not now[i]:
                ok[i // b] ^= pow2[i % b]
            cnt[a[l]] -= 1
            i -= 1
            now[i] += 1
            ok[i // b] |= pow2[i % b]
            l += 1
        while rr < r:
            i = cnt[a[r]]
            now[i] -= 1
            if not now[i]:
                ok[i // b] ^= pow2[i % b]
            cnt[a[r]] -= 1
            i -= 1
            now[i] += 1
            ok[i // b] |= pow2[i % b]
            r -= 1
        while u0 + 1 < len(u) and u[u0 + 1] < j:
            u0 += 1
            k = u[u0]
            (p, x) = (l0[k], r0[k])
            r0[k] = a[p]
            if l <= p <= r:
                i = cnt[a[p]]
                now[i] -= 1
                if not now[i]:
                    ok[i // b] ^= pow2[i % b]
                cnt[a[p]] -= 1
                i -= 1
                now[i] += 1
                ok[i // b] |= pow2[i % b]
                i = cnt[x]
                now[i] -= 1
                if not now[i]:
                    ok[i // b] ^= pow2[i % b]
                cnt[x] += 1
                i += 1
                now[i] += 1
                ok[i // b] |= pow2[i % b]
            a[p] = x
        while u0 >= 0 and (not u[u0] < j):
            k = u[u0]
            (p, x) = (l0[k], r0[k])
            r0[k] = a[p]
            u0 -= 1
            if l <= p <= r:
                i = cnt[a[p]]
                now[i] -= 1
                if not now[i]:
                    ok[i // b] ^= pow2[i % b]
                cnt[a[p]] -= 1
                i -= 1
                now[i] += 1
                ok[i // b] |= pow2[i % b]
                i = cnt[x]
                now[i] -= 1
                if not now[i]:
                    ok[i // b] ^= pow2[i % b]
                cnt[x] += 1
                i += 1
                now[i] += 1
                ok[i // b] |= pow2[i % b]
            a[p] = x
        v = []
        for k in range(m0 - 1, -1, -1):
            p = ok[k]
            while p:
                c = p.bit_length() - 1
                v.append(b * k + c)
                p ^= pow2[c]
        if not v[-1]:
            v.pop()
        ans0 = inf
        (ll, lv, c, k) = (0, len(v), 0, k0[j])
        for rr in range(lv):
            c += now[v[rr]]
            while ll ^ lv and c - now[v[ll]] >= k:
                c -= now[v[ll]]
                ll += 1
            if c >= k:
                ans0 = min(ans0, v[ll] - v[rr])
        ans1[j] = (ans0 + 1) % (inf + 1) - 1
    for i in range(q0):
        if ans1[i] ^ -2:
            ans.append(ans1[i])
    u0 += 1
    for i in u[u0:]:
        (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()))
pow2 = [1]
for _ in range(62):
    pow2.append(2 * pow2[-1])
b = 63
m = 100005
m0 = m // b + 1
(m1, m2) = (40, 2500)
(l0, r0, k0) = ([0] * m2, [0] * m2, [0] * m2)
inf = pow(10, 9) + 1
ans = []
while q:
    q0 = min(q, m2)
    z = []
    ans1 = [-2] * q0
    u = []
    for i in range(q0):
        t0 = list(map(int, input().split()))
        t = t0[0]
        if t == 1:
            (l, r, k) = (t0[1] - 1, t0[2] - 1, t0[3])
            x = l // m2
            y = r if not x & 1 else n - r - 1
            z.append(f(x, y, i))
            (l0[i], r0[i], k0[i]) = (l, r, k)
        else:
            (p, x) = (t0[1] - 1, t0[2])
            u.append(i)
            (l0[i], r0[i]) = (p, x)
    z = [i & 1048575 for i in sorted(z)]
    cnt = [0] * m
    now = [0] * m
    ok = [0] * m0
    if z:
        (l, r) = (l0[z[0]], l0[z[0]])
        (cnt[a[l]], now[1], ok[0]) = (1, 1, 2)
    u0 = -1
    for j in z:
        (ll, rr) = (l0[j], r0[j])
        while ll < l:
            l -= 1
            i = cnt[a[l]]
            now[i] -= 1
            if not now[i]:
                ok[i // b] ^= pow2[i % b]
            cnt[a[l]] += 1
            i += 1
            now[i] += 1
            ok[i // b] |= pow2[i % b]
        while r < rr:
            r += 1
            i = cnt[a[r]]
            now[i] -= 1
            if not now[i]:
                ok[i // b] ^= pow2[i % b]
            cnt[a[r]] += 1
            i += 1
            now[i] += 1
            ok[i // b] |= pow2[i % b]
        while l < ll:
            i = cnt[a[l]]
            now[i] -= 1
            if not now[i]:
                ok[i // b] ^= pow2[i % b]
            cnt[a[l]] -= 1
            i -= 1
            now[i] += 1
            ok[i // b] |= pow2[i % b]
            l += 1
        while rr < r:
            i = cnt[a[r]]
            now[i] -= 1
            if not now[i]:
                ok[i // b] ^= pow2[i % b]
            cnt[a[r]] -= 1
            i -= 1
            now[i] += 1
            ok[i // b] |= pow2[i % b]
            r -= 1
        while u0 + 1 < len(u) and u[u0 + 1] < j:
            u0 += 1
            k = u[u0]
            (p, x) = (l0[k], r0[k])
            r0[k] = a[p]
            if l <= p <= r:
                i = cnt[a[p]]
                now[i] -= 1
                if not now[i]:
                    ok[i // b] ^= pow2[i % b]
                cnt[a[p]] -= 1
                i -= 1
                now[i] += 1
                ok[i // b] |= pow2[i % b]
                i = cnt[x]
                now[i] -= 1
                if not now[i]:
                    ok[i // b] ^= pow2[i % b]
                cnt[x] += 1
                i += 1
                now[i] += 1
                ok[i // b] |= pow2[i % b]
            a[p] = x
        while u0 >= 0 and (not u[u0] < j):
            k = u[u0]
            (p, x) = (l0[k], r0[k])
            r0[k] = a[p]
            u0 -= 1
            if l <= p <= r:
                i = cnt[a[p]]
                now[i] -= 1
                if not now[i]:
                    ok[i // b] ^= pow2[i % b]
                cnt[a[p]] -= 1
                i -= 1
                now[i] += 1
                ok[i // b] |= pow2[i % b]
                i = cnt[x]
                now[i] -= 1
                if not now[i]:
                    ok[i // b] ^= pow2[i % b]
                cnt[x] += 1
                i += 1
                now[i] += 1
                ok[i // b] |= pow2[i % b]
            a[p] = x
        v = []
        for k in range(m0 - 1, -1, -1):
            p = ok[k]
            while p:
                c = p.bit_length() - 1
                v.append(b * k + c)
                p ^= pow2[c]
        if not v[-1]:
            v.pop()
        ans0 = inf
        (ll, lv, c, k) = (0, len(v), 0, k0[j])
        for rr in range(lv):
            c += now[v[rr]]
            while ll ^ lv and c - now[v[ll]] >= k:
                c -= now[v[ll]]
                ll += 1
            if c >= k:
                ans0 = min(ans0, v[ll] - v[rr])
        ans1[j] = (ans0 + 1) % (inf + 1) - 1
    for i in range(q0):
        if ans1[i] ^ -2:
            ans.append(ans1[i])
    u0 += 1
    for i in u[u0:]:
        (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()))
pow2 = [1]
for _ in range(62):
    pow2.append(2 * pow2[-1])
b = 63
m = 100005
m0 = m // b + 1
(m1, m2) = (40, 2500)
(l0, r0, k0) = ([0] * m2, [0] * m2, [0] * m2)
inf = pow(10, 9) + 1
ans = []
while q:
    q0 = min(q, m2)
    z = []
    ans1 = [-2] * q0
    u = []
    for i in range(q0):
        t0 = list(map(int, input().split()))
        t = t0[0]
        if t == 1:
            (l, r, k) = (t0[1] - 1, t0[2] - 1, t0[3])
            x = l // m2
            y = r if not x & 1 else n - r - 1
            z.append(f(x, y, i))
            (l0[i], r0[i], k0[i]) = (l, r, k)
        else:
            (p, x) = (t0[1] - 1, t0[2])
            u.append(i)
            (l0[i], r0[i]) = (p, x)
    z = [i & 1048575 for i in sorted(z)]
    cnt = [0] * m
    now = [0] * m
    ok = [0] * m0
    if z:
        (l, r) = (l0[z[0]], l0[z[0]])
        (cnt[a[l]], now[1], ok[0]) = (1, 1, 2)
    u0 = -1
    st = []
    for j in z:
        (ll, rr) = (l0[j], r0[j])
        while ll < l:
            l -= 1
            al = a[l]
            now[cnt[al]] -= 1
            if not now[cnt[al]]:
                ok[cnt[al] // b] ^= pow2[cnt[al] % b]
            cnt[al] += 1
            now[cnt[al]] += 1
            ok[cnt[al] // b] |= pow2[cnt[al] % b]
        while r < rr:
            r += 1
            ar = a[r]
            now[cnt[ar]] -= 1
            if not now[cnt[ar]]:
                ok[cnt[ar] // b] ^= pow2[cnt[ar] % b]
            cnt[ar] += 1
            now[cnt[ar]] += 1
            ok[cnt[ar] // b] |= pow2[cnt[ar] % b]
        while l < ll:
            al = a[l]
            now[cnt[al]] -= 1
            if not now[cnt[al]]:
                ok[cnt[al] // b] ^= pow2[cnt[al] % b]
            cnt[al] -= 1
            now[cnt[al]] += 1
            ok[cnt[al] // b] |= pow2[cnt[al] % b]
            l += 1
        while rr < r:
            ar = a[r]
            now[cnt[ar]] -= 1
            if not now[cnt[ar]]:
                ok[cnt[ar] // b] ^= pow2[cnt[ar] % b]
            cnt[ar] -= 1
            now[cnt[ar]] += 1
            ok[cnt[ar] // b] |= pow2[cnt[ar] % b]
            r -= 1
        while u0 + 1 < len(u) and u[u0 + 1] < j:
            u0 += 1
            k = u[u0]
            (p, x) = (l0[k], r0[k])
            (ap, i) = (a[p], cnt[a[p]])
            st.append(ap)
            if l <= p <= r:
                now[cnt[ap]] -= 1
                if not now[cnt[ap]]:
                    ok[cnt[ap] // b] ^= pow2[cnt[ap] % b]
                cnt[ap] -= 1
                now[cnt[ap]] += 1
                ok[cnt[ap] // b] |= pow2[cnt[ap] % b]
                a[p] = x
                now[cnt[x]] -= 1
                if not now[cnt[x]]:
                    ok[cnt[x] // b] ^= pow2[cnt[x] % b]
                cnt[x] += 1
                now[cnt[x]] += 1
                ok[cnt[x] // b] |= pow2[cnt[x] % b]
            else:
                a[p] = x
        while u0 >= 0 and (not u[u0] < j):
            k = u[u0]
            (p, x) = (l0[k], st.pop())
            (ap, i) = (a[p], cnt[a[p]])
            u0 -= 1
            if l <= p <= r:
                now[cnt[ap]] -= 1
                if not now[cnt[ap]]:
                    ok[cnt[ap] // b] ^= pow2[cnt[ap] % b]
                cnt[ap] -= 1
                now[cnt[ap]] += 1
                ok[cnt[ap] // b] |= pow2[cnt[ap] % b]
                a[p] = x
                now[cnt[x]] -= 1
                if not now[cnt[x]]:
                    ok[cnt[x] // b] ^= pow2[cnt[x] % b]
                cnt[x] += 1
                now[cnt[x]] += 1
                ok[cnt[x] // b] |= pow2[cnt[x] % b]
            else:
                a[p] = x
        v = []
        for k in range(m0 - 1, -1, -1):
            p = ok[k]
            while p:
                c = p.bit_length() - 1
                v.append(b * k + c)
                p ^= pow2[c]
        if not v[-1]:
            v.pop()
        ans0 = inf
        (ll, lv, c, k) = (0, len(v), 0, k0[j])
        for rr in range(lv):
            c += now[v[rr]]
            while ll ^ lv and c - now[v[ll]] >= k:
                c -= now[v[ll]]
                ll += 1
            if c >= k:
                ans0 = min(ans0, v[ll] - v[rr])
        ans1[j] = (ans0 + 1) % (inf + 1) - 1
    for i in range(q0):
        if ans1[i] ^ -2:
            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)))