The Untended Antiquity (Codeforces 869E)
Tags: Others, hashing

Adieu l'ami.Koyomi is helping Oshino, an acquaintance of his, to take care of an open space around the abandoned Eikou Cram School building, Oshino's makeshift residence.The space is represented by a rectangular grid of n × m cells, arranged into n rows and m columns. The c-th cell in the r-th row is denoted by (r, c).Oshino places and removes barriers around rectangular areas of cells. Specifically, an action denoted by "1 r1 c1 r2 c2" means Oshino's placing barriers around a rectangle with two corners being (r1, c1) and (r2, c2) and sides parallel to squares sides. Similarly, "2 r1 c1 r2 c2" means Oshino's removing barriers around the rectangle. Oshino ensures that no barriers staying on the ground share any common points, nor do they intersect with boundaries of the n × m area.Sometimes Koyomi tries to walk from one cell to another carefully without striding over barriers, in order to avoid damaging various items on the ground. "3 r1 c1 r2 c2" means that Koyomi tries to walk from (r1, c1) to (r2, c2) without crossing barriers.And you're here to tell Koyomi the feasibility of each of his attempts.

Input: The first line of input contains three space-separated integers n, m and q (1 ≤ n, m ≤ 2 500, 1 ≤ q ≤ 100 000) — the number of rows and columns in the grid, and the total number of Oshino and Koyomi's actions, respectively.The following q lines each describes an action, containing five space-separated integers t, r1, c1, r2, c2 (1 ≤ t ≤ 3, 1 ≤ r1, r2 ≤ n, 1 ≤ c1, c2 ≤ m) — the type and two coordinates of an action. Additionally, the following holds depending on the value of t:   If t = 1: 2 ≤ r1 ≤ r2 ≤ n - 1, 2 ≤ c1 ≤ c2 ≤ m - 1;  If t = 2: 2 ≤ r1 ≤ r2 ≤ n - 1, 2 ≤ c1 ≤ c2 ≤ m - 1, the specified group of barriers exist on the ground before the removal.  If t = 3: no extra restrictions. 

Output: For each of Koyomi's attempts (actions with t = 3), output one line — containing "Yes" (without quotes) if it's feasible, and "No" (without quotes) otherwise.

Note: For the first example, the situations of Koyomi's actions are illustrated below.  

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

2500 2500 8
1 549 1279 1263 2189
1 303 795 1888 2432
1 2227 622 2418 1161
3 771 2492 1335 1433
1 2017 2100 2408 2160
3 48 60 798 729
1 347 708 1868 792
3 1940 2080 377 1546

Sample Outputs:
No
Yes

No
Yes
No

Solution (Python):
import sys
readline = sys.stdin.readline

class Segment_Tree2:

    def __init__(self, N, M, f, e, lst=None):
        self.N = N
        self.M = M
        self.f = f
        self.e = e
        if lst == None:
            self.segment_tree = [[self.e] * 2 * self.M for i in range(2 * self.N)]
        else:
            assert len(lst) <= self.N
            assert all((len(lst[i]) <= self.M for i in range(self.N)))
            self.segment_tree = [[self.e] * 2 * self.M for i in range(self.N)] + [[self.e] * self.M + lst[i] + [self.e] * (self.M - len(lst[i])) for i in range(len(lst))] + [[self.e] * 2 * self.M for i in range(self.N - len(lst))]
            for i in range(self.N - 1, 0, -1):
                for j in range(2 * self.M - 1, self.M - 1, -1):
                    self.segment_tree[i][j] = self.f(self.segment_tree[i << 1][j], self.segment_tree[i << 1 | 1][j])
            for i in range(2 * self.N - 1, -1, -1):
                for j in range(self.M - 1, 0, -1):
                    self.segment_tree[i][j] = self.f(self.segment_tree[i][j << 1], self.segment_tree[i][j << 1 | 1])

    def Build(self, lst):
        assert len(lst) <= self.N
        assert all(len((lst[i] for i in range(self.N))) <= self.M)
        for i in range(len(lst)):
            for j in range(len(lst[i])):
                self.segment_tree[i + self.N][j + self.M] = lst[i][j]
        for i in range(self.N - 1, 0, -1):
            for j in range(2 * self.M - 1, self.M - 1, -1):
                self.segment_tree[i][j] = self.f(self.segment_tree[i << 1][j], self.segment_tree[i << 1 | 1][j])
        for i in range(2 * self.N - 1, -1, -1):
            for j in range(self.M - 1, 0, -1):
                self.segment_tree[i][j] = self.f(self.segment_tree[i][j << 1], self.segment_tree[i][j << 1 | 1])

    def Fold(self, LN=None, RN=None, LM=None, RM=None):
        if LN == None:
            LN = self.N
        else:
            LN += self.N
        if RN == None:
            RN = self.N * 2
        else:
            RN += self.N
        if LM == None:
            LM = self.M
        else:
            LM += self.M
        if RM == None:
            RM = self.M * 2
        else:
            RM += self.M
        idxN = []
        idxM = []
        while LN < RN:
            if LN & 1:
                idxN.append(LN)
                LN += 1
            if RN & 1:
                RN -= 1
                idxN.append(RN)
            LN >>= 1
            RN >>= 1
        while LM < RM:
            if LM & 1:
                idxM.append(LM)
                LM += 1
            if RM & 1:
                RM -= 1
                idxM.append(RM)
            LM >>= 1
            RM >>= 1
        retu = self.e
        for i in idxN:
            for j in idxM:
                retu = self.f(retu, self.segment_tree[i][j])
        return retu

    def Fold_Index(self, LN=None, RN=None, LM=None, RM=None):
        if LN == None:
            LN = self.N
        else:
            LN += self.N
        if RN == None:
            RN = self.N * 2
        else:
            RN += self.N
        if LM == None:
            LM = self.M
        else:
            LM += self.M
        if RM == None:
            RM = self.M * 2
        else:
            RM += self.M
        if LN == RN and LM == RM:
            return None
        idxN = []
        idxM = []
        while LN < RN:
            if LN & 1:
                idxN.append(LN)
                LN += 1
            if RN & 1:
                RN -= 1
                idxN.append(RN)
            LN >>= 1
            RN >>= 1
        while LM < RM:
            if LM & 1:
                idxM.append(LM)
                LM += 1
            if RM & 1:
                RM -= 1
                idxM.append(RM)
            LM >>= 1
            RM >>= 1
        v = self.e
        for i in idxN:
            for j in idxM:
                v = self.f(v, self.segment_tree[i][j])
        for i in idxN:
            for j in idxM:
                if v == self.f(v, self.segment_tree[i][j]):
                    break
            else:
                continue
            break
        while i < self.N:
            if self.segment_tree[i << 1][j] == v:
                i <<= 1
            else:
                i <<= 1
                i |= 1
        while j < self.M:
            if self.segment_tree[i][j << 1] == v:
                j <<= 1
            else:
                j <<= 1
                j |= 1
        return (i, j)

    def __getitem__(self, tpl):
        (i, j) = tpl
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        if -self.M <= j < 0:
            j += self.M * 2
        elif 0 <= j < self.M:
            j += self.M
        else:
            raise IndexError('list index out of range')
        return self.segment_tree[i][j]

    def __setitem__(self, tpl, x):
        (i, j) = tpl
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        if -self.M <= j < 0:
            j += self.M * 2
        elif 0 <= j < self.M:
            j += self.M
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i][j] = x
        idxN = [i]
        idxM = [j]
        while i > 1:
            i >>= 1
            idxN.append(i)
        while j > 1:
            j >>= 1
            idxM.append(j)
        i = idxN[0]
        for j in idxM[1:]:
            self.segment_tree[i][j] = self.f(self.segment_tree[i][j << 1], self.segment_tree[i][j << 1 | 1])
        for i in idxN[1:]:
            for j in idxM:
                self.segment_tree[i][j] = self.f(self.segment_tree[i << 1][j], self.segment_tree[i << 1 | 1][j])

    def __str__(self):
        m = max((len(str(self.segment_tree[i][j])) for i in range(self.N, self.N * 2) for j in range(self.M, self.M * 2)))
        return '\n'.join(['[' + ', '.join(map(lambda s: ' ' * (m - len(str(s))) + str(s), self.segment_tree[i][self.M:])) + ']' for i in range(self.N, self.N * 2)])
dct = {}
(N, M, Q) = map(int, readline().split())
ST2 = Segment_Tree2(N + 1, M + 1, lambda x, y: x ^ y, 0)
for _ in range(Q):
    (t, r1, c1, r2, c2) = map(int, readline().split())
    r1 -= 1
    c1 -= 1
    if t == 1:
        x = hash((r1, r2, c1, c2))
        ST2[r1, c1] ^= x
        ST2[r1, c2] ^= x
        ST2[r2, c1] ^= x
        ST2[r2, c2] ^= x
    elif t == 2:
        x = hash((r1, r2, c1, c2))
        ST2[r1, c1] ^= x
        ST2[r1, c2] ^= x
        ST2[r2, c1] ^= x
        ST2[r2, c2] ^= x
    else:
        if ST2.Fold(0, r1 + 1, 0, c1 + 1) == ST2.Fold(0, r2, 0, c2):
            ans = 'Yes'
        else:
            ans = 'No'
        print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

class Segment_Tree2:

    def __init__(self, N, M, f, e, lst=None):
        self.N = N
        self.M = M
        self.f = f
        self.e = e
        if lst == None:
            self.segment_tree = [[self.e] * 2 * self.M for i in range(2 * self.N)]
        else:
            assert len(lst) <= self.N
            assert all((len(lst[i]) <= self.M for i in range(self.N)))
            self.segment_tree = [[self.e] * 2 * self.M for i in range(self.N)] + [[self.e] * self.M + lst[i] + [self.e] * (self.M - len(lst[i])) for i in range(len(lst))] + [[self.e] * 2 * self.M for i in range(self.N - len(lst))]
            for i in range(self.N - 1, 0, -1):
                for j in range(2 * self.M - 1, self.M - 1, -1):
                    self.segment_tree[i][j] = self.f(self.segment_tree[i << 1][j], self.segment_tree[i << 1 | 1][j])
            for i in range(2 * self.N - 1, -1, -1):
                for j in range(self.M - 1, 0, -1):
                    self.segment_tree[i][j] = self.f(self.segment_tree[i][j << 1], self.segment_tree[i][j << 1 | 1])

    def Build(self, lst):
        assert len(lst) <= self.N
        assert all(len((lst[i] for i in range(self.N))) <= self.M)
        for i in range(len(lst)):
            for j in range(len(lst[i])):
                self.segment_tree[i + self.N][j + self.M] = lst[i][j]
        for i in range(self.N - 1, 0, -1):
            for j in range(2 * self.M - 1, self.M - 1, -1):
                self.segment_tree[i][j] = self.f(self.segment_tree[i << 1][j], self.segment_tree[i << 1 | 1][j])
        for i in range(2 * self.N - 1, -1, -1):
            for j in range(self.M - 1, 0, -1):
                self.segment_tree[i][j] = self.f(self.segment_tree[i][j << 1], self.segment_tree[i][j << 1 | 1])

    def Fold(self, LN=None, RN=None, LM=None, RM=None):
        if LN == None:
            LN = self.N
        else:
            LN += self.N
        if RN == None:
            RN = self.N * 2
        else:
            RN += self.N
        if LM == None:
            LM = self.M
        else:
            LM += self.M
        if RM == None:
            RM = self.M * 2
        else:
            RM += self.M
        idxN = []
        idxM = []
        while LN < RN:
            if LN & 1:
                idxN.append(LN)
                LN += 1
            if RN & 1:
                RN -= 1
                idxN.append(RN)
            LN >>= 1
            RN >>= 1
        while LM < RM:
            if LM & 1:
                idxM.append(LM)
                LM += 1
            if RM & 1:
                RM -= 1
                idxM.append(RM)
            LM >>= 1
            RM >>= 1
        retu = self.e
        for i in idxN:
            for j in idxM:
                retu = self.f(retu, self.segment_tree[i][j])
        return retu

    def Fold_Index(self, LN=None, RN=None, LM=None, RM=None):
        if LN == None:
            LN = self.N
        else:
            LN += self.N
        if RN == None:
            RN = self.N * 2
        else:
            RN += self.N
        if LM == None:
            LM = self.M
        else:
            LM += self.M
        if RM == None:
            RM = self.M * 2
        else:
            RM += self.M
        if LN == RN and LM == RM:
            return None
        idxN = []
        idxM = []
        while LN < RN:
            if LN & 1:
                idxN.append(LN)
                LN += 1
            if RN & 1:
                RN -= 1
                idxN.append(RN)
            LN >>= 1
            RN >>= 1
        while LM < RM:
            if LM & 1:
                idxM.append(LM)
                LM += 1
            if RM & 1:
                RM -= 1
                idxM.append(RM)
            LM >>= 1
            RM >>= 1
        v = self.e
        for i in idxN:
            for j in idxM:
                v = self.f(v, self.segment_tree[i][j])
        for i in idxN:
            for j in idxM:
                if v == self.f(v, self.segment_tree[i][j]):
                    break
            else:
                continue
            break
        while i < self.N:
            if self.segment_tree[i << 1][j] == v:
                i <<= 1
            else:
                i <<= 1
                i |= 1
        while j < self.M:
            if self.segment_tree[i][j << 1] == v:
                j <<= 1
            else:
                j <<= 1
                j |= 1
        return (i, j)

    def __getitem__(self, tpl):
        (i, j) = tpl
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        if -self.M <= j < 0:
            j += self.M * 2
        elif 0 <= j < self.M:
            j += self.M
        else:
            raise IndexError('list index out of range')
        return self.segment_tree[i][j]

    def __setitem__(self, tpl, x):
        (i, j) = tpl
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        if -self.M <= j < 0:
            j += self.M * 2
        elif 0 <= j < self.M:
            j += self.M
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i][j] = x
        idxN = [i]
        idxM = [j]
        while i > 1:
            i >>= 1
            idxN.append(i)
        while j > 1:
            j >>= 1
            idxM.append(j)
        i = idxN[0]
        for j in idxM[1:]:
            self.segment_tree[i][j] = self.f(self.segment_tree[i][j << 1], self.segment_tree[i][j << 1 | 1])
        for i in idxN[1:]:
            for j in idxM:
                self.segment_tree[i][j] = self.f(self.segment_tree[i << 1][j], self.segment_tree[i << 1 | 1][j])

    def __str__(self):
        m = max((len(str(self.segment_tree[i][j])) for i in range(self.N, self.N * 2) for j in range(self.M, self.M * 2)))
        return '\n'.join(['[' + ', '.join(map(lambda s: ' ' * (m - len(str(s))) + str(s), self.segment_tree[i][self.M:])) + ']' for i in range(self.N, self.N * 2)])
(N, M, Q) = map(int, readline().split())
ST2 = Segment_Tree2(N + 1, M + 1, lambda x, y: x ^ y, 0)
for _ in range(Q):
    (t, r1, c1, r2, c2) = map(int, readline().split())
    r1 -= 1
    c1 -= 1
    if t == 1:
        x = hash((r1, r2, c1, c2))
        ST2[r1, c1] ^= x
        ST2[r1, c2] ^= x
        ST2[r2, c1] ^= x
        ST2[r2, c2] ^= x
    elif t == 2:
        x = hash((r1, r2, c1, c2))
        ST2[r1, c1] ^= x
        ST2[r1, c2] ^= x
        ST2[r2, c1] ^= x
        ST2[r2, c2] ^= x
    else:
        if ST2.Fold(0, r1 + 1, 0, c1 + 1) == ST2.Fold(0, r2, 0, c2):
            ans = 'Yes'
        else:
            ans = 'No'
        print(ans)

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 1)
(dfs, hashing, read_from_file) = (0, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        inf = float('inf')

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import math
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import merge, heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        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.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

class Fenwick2D:

    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.bit = [[0] * m for _ in range(n)]

    def update(self, x, y, z):
        while x < self.n:
            j = y
            while j < self.m:
                self.bit[x][j] ^= z
                j |= j + 1
            x |= x + 1

    def pref(self, x, y):
        res = 0
        while x >= 0:
            j = y
            while j >= 0:
                res ^= self.bit[x][j]
                j = (j & j + 1) - 1
            x = (x & x + 1) - 1
        return res

def main():
    d = {}
    (n, m, q) = MII()
    fen = Fenwick2D(n + 1, m + 1)
    for _ in range(q):
        (t, r1, c1, r2, c2) = GMI()
        if t <= 1:
            if (r1, c1, r2, c2) not in d:
                d[r1, c1, r2, c2] = random.getrandbits(30)
            rnd = d[r1, c1, r2, c2]
            fen.update(r1, c1, rnd)
            fen.update(r1, c2 + 1, rnd)
            fen.update(r2 + 1, c1, rnd)
            fen.update(r2 + 1, c2 + 1, rnd)
        else:
            print('No' if fen.pref(r1, c1) ^ fen.pref(r2, c2) else 'Yes')
    return
t = 1
for _ in range(t):
    main()