Kazaee (Codeforces 1746F)
Tags: Others, hashing

You have an array $$$a$$$ consisting of $$$n$$$ positive integers and you have to handle $$$q$$$ queries of the following types:  $$$1$$$ $$$i$$$ $$$x$$$: change $$$a_{i}$$$ to $$$x$$$,  $$$2$$$ $$$l$$$ $$$r$$$ $$$k$$$: check if the number of occurrences of every positive integer in the subarray $$$a_{l}, a_{l+1}, \ldots a_{r}$$$ is a multiple of $$$k$$$ (check the example for better understanding). 

Input: The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n , q \le 3 \cdot 10^5$$$), the length of $$$a$$$ and the number of queries.Next line contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots a_{n}$$$ ($$$1 \le a_{i} \le 10^9$$$) — the elements of $$$a$$$.Each of the next $$$q$$$ lines describes a query. It has one of the following forms.  $$$1$$$ $$$i$$$ $$$x$$$, ($$$1 \le i \le n$$$ , $$$1 \le x \le 10^9$$$), or  $$$2$$$ $$$l$$$ $$$r$$$ $$$k$$$, ($$$1 \le l \le r \le n$$$ , $$$1 \le k \le n$$$). 

Output: For each query of the second type, if answer of the query is yes, print "YES", otherwise print "NO".

Note: In the first query, requested subarray is $$$[1234, 2, 3, 3, 2, 1]$$$, and it's obvious that the number of occurrence of $$$1$$$ isn't divisible by $$$k = 2$$$. So the answer is "NO".In the third query, requested subarray is $$$[1, 2, 3, 3, 2, 1]$$$, and it can be seen that the number of occurrence of every integer in this sub array is divisible by $$$k = 2$$$. So the answer is "YES".In the sixth query, requested subarray is $$$[1, 2, 3, 3, 2, 1, 1, 2, 3]$$$, and it can be seen that the number of occurrence of every integer in this sub array is divisible by $$$k = 3$$$. So the answer is "YES".

Sample Inputs:
10 8
1234 2 3 3 2 1 1 2 3 4
2 1 6 2
1 1 1
2 1 6 2
2 1 9 2
1 10 5
2 1 9 3
1 3 5
2 3 10 2

Sample Outputs:
NO
YES
NO
YES
YES

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import random

class Bit:

    def __init__(self, n):
        self.size = n
        self.n0 = 1 << n.bit_length() - 1
        self.tree = [0] * (n + 1)

    def range_sum(self, l, r):
        return self.sum(r - 1) - self.sum(l - 1)

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def get(self, i):
        return self.sum(i) - self.sum(i - 1)

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        pos = 0
        plus = self.n0
        while plus > 0:
            if pos + plus <= self.size and self.tree[pos + plus] < x:
                x -= self.tree[pos + plus]
                pos += plus
            plus //= 2
        return pos

def solve():
    (n, Q) = map(int, input().split())
    A = list(map(int, input().split()))
    query = []
    se = set(A)
    ind = 0
    ans = ['YES'] * Q
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 2:
            (l, r, k) = q[1:]
            if (r - l + 1) % k != 0:
                ans[ind] = 'NO'
                ind += 1
                continue
            q.append(ind)
            ind += 1
        else:
            q[1] -= 1
        query.append(q)
        if q[0] == 1:
            se.add(q[2])
    ans = ans[:ind]
    dic = {a: i for (i, a) in enumerate(sorted(se))}
    A = [dic[a] for a in A]
    for q in query:
        if q[0] == 1:
            q[2] = dic[q[2]]
    m = len(se)
    itr = 8
    for _ in range(itr):
        P = random.choices(range(8), k=m)
        bit = Bit(n)
        B = A[:]
        for (i, a) in enumerate(A):
            add = 0
            if P[a] & 1:
                add |= 1
            if P[a] & 2:
                add |= 1 << 20
            if P[a] & 4:
                add |= 1 << 40
            if add != 0:
                bit.add(i, add)
        for q in query:
            if q[0] == 1:
                (i, x) = q[1:]
                b = B[i]
                B[i] = x
                add = 0
                if P[b] & 1:
                    add -= 1
                if P[b] & 2:
                    add -= 1 << 20
                if P[b] & 4:
                    add -= 1 << 40
                if P[x] & 1:
                    add += 1
                if P[x] & 2:
                    add += 1 << 20
                if P[x] & 4:
                    add += 1 << 40
                if add != 0:
                    bit.add(i, add)
            else:
                (l, r, k, i) = q[1:]
                if ans[i] == 'NO':
                    continue
                c = bit.range_sum(l - 1, r)
                if c % k != 0:
                    ans[i] = 'NO'
                elif (c >> 20) % k != 0:
                    ans[i] = 'NO'
                elif (c >> 40) % k != 0:
                    ans[i] = 'NO'
    print(*ans, sep='\n')
T = 1
for t in range(1, T + 1):
    solve()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import random

class Bit:

    def __init__(self, n):
        self.size = n
        self.n0 = 1 << n.bit_length() - 1
        self.tree = [0] * (n + 1)

    def range_sum(self, l, r):
        return self.sum(r - 1) - self.sum(l - 1)

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def get(self, i):
        return self.sum(i) - self.sum(i - 1)

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        pos = 0
        plus = self.n0
        while plus > 0:
            if pos + plus <= self.size and self.tree[pos + plus] < x:
                x -= self.tree[pos + plus]
                pos += plus
            plus //= 2
        return pos

def solve():
    (n, Q) = map(int, input().split())
    A = list(map(int, input().split()))
    query = []
    se = set(A)
    ind = 0
    ans = ['YES'] * Q
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 2:
            (l, r, k) = q[1:]
            if (r - l + 1) % k != 0:
                ans[ind] = 'NO'
                ind += 1
                continue
            q.append(ind)
            ind += 1
        else:
            q[1] -= 1
        query.append(q)
        if q[0] == 1:
            se.add(q[2])
    ans = ans[:ind]
    dic = {a: i for (i, a) in enumerate(sorted(se))}
    A = [dic[a] for a in A]
    for q in query:
        if q[0] == 1:
            q[2] = dic[q[2]]
    m = len(se)
    itr = 12
    for _ in range(itr):
        P = random.choices(range(4), k=m)
        bit = Bit(n)
        B = A[:]
        for (i, a) in enumerate(A):
            add = 0
            if P[a] & 1:
                add |= 1
            if P[a] & 2:
                add |= 1 << 30
            if add != 0:
                bit.add(i, add)
        for q in query:
            if q[0] == 1:
                (i, x) = q[1:]
                b = B[i]
                B[i] = x
                add = 0
                if P[b] & 1:
                    add -= 1
                if P[b] & 2:
                    add -= 1 << 30
                if P[x] & 1:
                    add += 1
                if P[x] & 2:
                    add += 1 << 30
                if add != 0:
                    bit.add(i, add)
            else:
                (l, r, k, i) = q[1:]
                if ans[i] == 'NO':
                    continue
                c = bit.range_sum(l - 1, r)
                if c % k != 0:
                    ans[i] = 'NO'
                elif (c >> 30) % k != 0:
                    ans[i] = 'NO'
    print(*ans, sep='\n')
T = 1
for t in range(1, T + 1):
    solve()

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

class segtree:

    def __init__(self, init, func, ide):
        self.n = len(init)
        self.func = func
        self.ide = ide
        self.size = 1 << (self.n - 1).bit_length()
        self.tree = [self.ide for i in range(2 * self.size)]
        for i in range(self.n):
            self.tree[self.size + i] = init[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.func(self.tree[2 * i], self.tree[2 * i | 1])

    def update(self, k, x):
        k += self.size
        self.tree[k] = x
        k >>= 1
        while k:
            self.tree[k] = self.func(self.tree[2 * k], self.tree[k * 2 | 1])
            k >>= 1

    def get(self, i):
        return self.tree[i + self.size]

    def query(self, l, r):
        l += self.size
        r += self.size
        l_res = self.ide
        r_res = self.ide
        while l < r:
            if l & 1:
                l_res = self.func(l_res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_res = self.func(self.tree[r], r_res)
            l >>= 1
            r >>= 1
        return self.func(l_res, r_res)

    def debug(self, s=10):
        print([self.get(i) for i in range(min(self.n, s))])
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
use = {}
id = 0
for i in range(n):
    if a[i] not in use:
        use[a[i]] = id
        id += 1
    a[i] = use[a[i]]
query = []
for _ in range(q):
    tmp = list(map(int, input().split()))
    if tmp[0] == 1:
        (t, i, x) = tmp
        if x not in use:
            use[x] = id
            id += 1
        query.append((t, i, use[x], 0))
    else:
        query.append(tuple(tmp))
m = 6
import random

def make_hash():
    x = random.randint(0, 1)
    y = random.randint(0, 1)
    z = random.randint(0, 1)
    return x | y << 20 | z << 40
M = id

def conv(x, y):
    return y * m + x
hash = [make_hash() for i in range(m * M)]
hash_xor = [random.randint(10 ** 3, 1 << 60) for i in range(M)]
segs = []
for i in range(m):
    x = [hash[conv(i, j)] for j in a]
    seg = segtree(x, lambda p, q: p + q, 0)
    segs.append(seg)
seg_xor = segtree([hash_xor[i] for i in a], lambda p, q: p ^ q, 0)
ans = []
tmp = 0
mask = (1 << 20) - 1
for ii in range(q):
    query_tmp = query[ii]
    if query_tmp[0] == 1:
        (x, y, _) = query_tmp[1:]
        x -= 1
        for i in range(m):
            segs[i].update(x, hash[conv(i, y)])
        seg_xor.update(x, hash_xor[y])
    else:
        (l, r, k) = query_tmp[1:]
        l -= 1
        flag = True
        if k == 2:
            if seg_xor.query(l, r) == 0:
                print('YES')
            else:
                print('NO')
        else:
            for i in range(m):
                w = segs[i].query(l, r)
                x = w & mask
                y = w >> 20 & mask
                z = w >> 40 & mask
                if x % k != 0 or y % k != 0 or z % k != 0:
                    flag = False
                    break
            if flag:
                print('YES')
            else:
                print('NO')