Staircases (Codeforces 1598E)
Tags: Math, dfs and similar

You are given a matrix, consisting of $$$n$$$ rows and $$$m$$$ columns. The rows are numbered top to bottom, the columns are numbered left to right.Each cell of the matrix can be either free or locked.Let's call a path in the matrix a staircase if it:   starts and ends in the free cell;  visits only free cells;  has one of the two following structures:   the second cell is $$$1$$$ to the right from the first one, the third cell is $$$1$$$ to the bottom from the second one, the fourth cell is $$$1$$$ to the right from the third one, and so on;  the second cell is $$$1$$$ to the bottom from the first one, the third cell is $$$1$$$ to the right from the second one, the fourth cell is $$$1$$$ to the bottom from the third one, and so on.  In particular, a path, consisting of a single cell, is considered to be a staircase.Here are some examples of staircases:  Initially all the cells of the matrix are free.You have to process $$$q$$$ queries, each of them flips the state of a single cell. So, if a cell is currently free, it makes it locked, and if a cell is currently locked, it makes it free.Print the number of different staircases after each query. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.

Input: The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 1000$$$; $$$1 \le q \le 10^4$$$) — the sizes of the matrix and the number of queries.Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \le n$$$; $$$1 \le y \le m$$$) — the description of each query.

Output: Print $$$q$$$ integers — the $$$i$$$-th value should be equal to the number of different staircases after $$$i$$$ queries. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.


Sample Inputs:
2 2 8
1 1
1 1
1 1
2 2
1 1
1 2
2 1
1 1

3 4 10
1 4
1 2
2 3
1 2
2 3
3 2
1 3
3 4
1 3
3 1

1000 1000 2
239 634
239 634

Sample Outputs:
5
10
5
2
5
3
1
0

49
35
24
29
49
39
31
23
29
27

1332632508
1333333000

Solution (Python):
class SplayTree:

    def __init__(self):
        self.children = {}
        self.parents = {}
        self.root = None

    def insert(self, x):
        if self.root is None:
            self.root = x
            self.children[x] = [None, None]
            self.parents[x] = None
        else:
            curr = self.root
            while True:
                if curr == x:
                    self.splay(x)
                    return None
                elif x < curr:
                    if self.children[curr][0] is None:
                        self.children[curr][0] = x
                        self.children[x] = [None, None]
                        self.parents[x] = curr
                        self.splay(x)
                        return None
                    else:
                        curr = self.children[curr][0]
                elif self.children[curr][1] is None:
                    self.children[curr][1] = x
                    self.children[x] = [None, None]
                    self.parents[x] = curr
                    self.splay(x)
                    return None
                else:
                    curr = self.children[curr][1]

    def find(self, x):
        return x in self.parents

    def delete(self, x, show=False):
        if self.children[x][0] is None and self.children[x][1] is None:
            if self.root == x:
                self.root = None
            del self.children[x]
            p = self.parents[x]
            del self.parents[x]
            for i in range(2):
                if self.children[p][i] == x:
                    self.children[p][i] = None
            self.splay(p)
        elif self.children[x][0] is None or self.children[x][1] is None:
            if self.children[x][0] is None:
                ind = 1
            else:
                ind = 0
            child = self.children[x][ind]
            if self.root == x:
                self.root = child
                del self.children[x]
                del self.parents[x]
                self.parents[child] = None
            else:
                p = self.parents[x]
                self.parents[child] = p
                for i in range(2):
                    if self.children[p][i] == x:
                        self.children[p][i] = child
                del self.parents[x]
                del self.children[x]
                self.splay(p)
        else:
            s = self.successor(x)
            if self.parents[s] == x:
                skids = self.children[s][:]
                xkid = self.children[x][0]
                xpar = self.parents[x]
                self.children[s] = [xkid, x]
                self.parents[s] = xpar
                self.children[x] = skids
                self.parents[x] = s
                for i in skids:
                    if i is not None:
                        self.parents[i] = x
                if xkid is not None:
                    self.parents[xkid] = s
                if xpar is not None:
                    for i in range(2):
                        if self.children[xpar][i] == x:
                            self.children[xpar][i] = s
                if self.root == x:
                    self.root = s
                self.delete(x)
                if xpar is not None:
                    self.splay(xpar)
            else:
                skids = self.children[s][:]
                spar = self.parents[s]
                xkids = self.children[x][:]
                xpar = self.parents[x]
                self.children[s] = xkids
                self.parents[s] = xpar
                self.children[x] = skids
                self.parents[x] = spar
                for i in skids:
                    if i is not None:
                        self.parents[i] = x
                for i in xkids:
                    if i is not None:
                        self.parents[i] = s
                for i in range(2):
                    if spar is not None and self.children[spar][i] == s:
                        self.children[spar][i] = x
                    if xpar is not None and self.children[xpar][i] == x:
                        self.children[xpar][i] = s
                if self.root == x:
                    self.root = s
                if show:
                    print(self.children)
                    print(self.parents)
                    print(self.root)
                self.delete(x)
                if xpar is not None:
                    self.splay(xpar)

    def successor(self, x):
        if self.find(x):
            if self.children[x][1] is None:
                curr = x
                while self.parents[curr] is not None:
                    if self.parents[curr] > curr:
                        return self.parents[curr]
                    curr = self.parents[curr]
                return None
            else:
                curr = self.children[x][1]
            while self.children[curr][0] is not None:
                curr = self.children[curr][0]
            return curr
        else:
            curr = self.root
            prev = None
            while True:
                if x < curr:
                    if self.children[curr][0] is None:
                        self.splay(curr)
                        return curr
                    else:
                        prev = curr
                        curr = self.children[curr][0]
                elif self.children[curr][1] is None:
                    if prev is not None:
                        self.splay(prev)
                    return prev
                else:
                    curr = self.children[curr][1]

    def predecessor(self, x):
        if self.find(x):
            if self.children[x][0] is None:
                curr = x
                while self.parents[curr] is not None:
                    if self.parents[curr] < curr:
                        return self.parents[curr]
                    curr = self.parents[curr]
                return None
            else:
                curr = self.children[x][0]
            while self.children[curr][1] is not None:
                curr = self.children[curr][1]
            return curr
        else:
            curr = self.root
            prev = None
            while True:
                if x > curr:
                    if self.children[curr][1] is None:
                        self.splay(curr)
                        return curr
                    else:
                        prev = curr
                        curr = self.children[curr][1]
                elif self.children[curr][0] is None:
                    if prev is not None:
                        self.splay(prev)
                    return prev
                else:
                    curr = self.children[curr][0]

    def splay(self, x):
        while self.parents[x] is not None:
            p = self.parents[x]
            gp = self.parents[p]
            if gp is None:
                if p > x:
                    (a, b) = self.children[x]
                    c = self.children[p][1]
                    self.children[x] = [a, p]
                    self.children[p] = [b, c]
                    self.parents[x] = None
                    self.parents[p] = x
                    self.parents[b] = p
                    self.root = x
                else:
                    a = self.children[p][0]
                    (b, c) = self.children[x]
                    self.children[x] = [p, c]
                    self.children[p] = [a, b]
                    self.parents[x] = None
                    self.parents[p] = x
                    self.parents[b] = p
                    self.root = x
            else:
                ggp = self.parents[gp]
                if p > x and gp > x:
                    (a, b) = self.children[x]
                    c = self.children[p][1]
                    d = self.children[gp][1]
                    self.children[x] = [a, p]
                    self.children[p] = [b, gp]
                    self.children[gp] = [c, d]
                    self.parents[x] = ggp
                    self.parents[p] = x
                    self.parents[gp] = p
                    self.parents[b] = p
                    self.parents[c] = gp
                elif p < x and gp < x:
                    (c, d) = self.children[x]
                    b = self.children[p][0]
                    a = self.children[gp][0]
                    self.children[x] = [p, d]
                    self.children[p] = [gp, c]
                    self.children[gp] = [a, b]
                    self.parents[x] = ggp
                    self.parents[p] = x
                    self.parents[gp] = p
                    self.parents[b] = gp
                    self.parents[c] = p
                elif p < x and gp > x:
                    (b, c) = self.children[x]
                    a = self.children[p][0]
                    d = self.children[gp][1]
                    self.children[x] = [p, gp]
                    self.children[p] = [a, b]
                    self.children[gp] = [c, d]
                    self.parents[x] = ggp
                    self.parents[p] = x
                    self.parents[gp] = x
                    self.parents[b] = p
                    self.parents[c] = gp
                else:
                    (b, c) = self.children[x]
                    d = self.children[p][1]
                    a = self.children[gp][0]
                    self.children[x] = [gp, p]
                    self.children[p] = [c, d]
                    self.children[gp] = [a, b]
                    self.parents[x] = ggp
                    self.parents[p] = x
                    self.parents[gp] = x
                    self.parents[b] = gp
                    self.parents[c] = p
                if ggp is not None:
                    for i in range(2):
                        if self.children[ggp][i] == gp:
                            self.children[ggp][i] = x
                else:
                    self.root = x
            if None in self.parents:
                del self.parents[None]
(n, m, q) = map(int, input().split())
diag = {}
for i in range(-m, n + 1):
    diag[i] = SplayTree()
    diag[i].insert(max(0, i))
    diag[i].insert(min(n + 1, m + 1 + i))
total = 0
j = n
k = m
while j > 0 and k > 0:
    total += 2 * j * k
    total += j * (k - 1)
    total += k * (j - 1)
    j -= 1
    k -= 1
total -= n * m
for _ in range(q):
    (x, y) = map(int, input().split())
    diff = x - y
    pred = diag[diff].predecessor(x)
    succ = diag[diff].successor(x)
    predup = diag[diff - 1].predecessor(x)
    succup = diag[diff - 1].successor(x - 1)
    preddown = diag[diff + 1].predecessor(x + 1)
    succdown = diag[diff + 1].successor(x)
    beforeup = min(2 * (x - pred) - 1, 2 * (x - predup) - 2)
    afterup = min(2 * (succ - x) - 1, 2 * (succup - x))
    beforedown = min(2 * (x - pred) - 1, 2 * (x - preddown))
    afterdown = min(2 * (succ - x) - 1, 2 * (succdown - x) - 2)
    change = (beforeup + 1) * (afterup + 1) + (beforedown + 1) * (afterdown + 1) - 1
    if diag[diff].find(x):
        total += change
        diag[diff].delete(x)
    else:
        total -= change
        diag[diff].insert(x)
    print(total)

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

def main():
    (H, W, Q) = map(int, input().split())
    A = [[] for _ in range(H + W)]
    for i in range(H):
        for j in range(W):
            A[(i + j + 1) // 2 * 2].append(0)
            A[(i + j) // 2 * 2 + 1].append(0)
    RawAns = H * W
    Diff = [0] * (H + W)
    for i in range(H + W):
        K = len(A[i]) * (len(A[i]) - 1) // 2
        Diff[i] = K
        RawAns += K
    for _ in range(Q):
        (h, w) = map(int, input().split())
        h -= 1
        w = W - w
        i1 = (h + w + 1) // 2 * 2
        j1 = h * 2 + (h + w) % 2 if i1 < W else (W - w - 1) * 2 + (h + w + 1) % 2
        i2 = (h + w) // 2 * 2 + 1
        j2 = h * 2 + (h + w + 1) % 2 if i2 < W else (W - w - 1) * 2 + (h + w) % 2
        if A[i1][j1]:
            RawAns += 1
        else:
            RawAns -= 1
        A[i1][j1] ^= 1
        A[i2][j2] ^= 1
        Tmp1 = 0
        Count = -1
        for a in A[i1]:
            if a:
                Tmp1 += Count * (Count + 1) // 2
                Count = -1
            else:
                Count += 1
        Tmp1 += Count * (Count + 1) // 2
        Tmp2 = 0
        Count = -1
        for a in A[i2]:
            if a:
                Tmp2 += Count * (Count + 1) // 2
                Count = -1
            else:
                Count += 1
        Tmp2 += Count * (Count + 1) // 2
        RawAns -= Diff[i1] - Tmp1 + Diff[i2] - Tmp2
        Diff[i1] = Tmp1
        Diff[i2] = Tmp2
        print(RawAns)
if __name__ == '__main__':
    main()

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

def main():
    (H, W, Q) = map(int, input().split())
    A = [[] for _ in range(H + W)]
    for i in range(H):
        for j in range(W):
            A[(i + j + 1) // 2 * 2].append(0)
            A[(i + j) // 2 * 2 + 1].append(0)
    RawAns = H * W
    Diff = [0] * (H + W)
    for i in range(H + W):
        K = len(A[i]) * (len(A[i]) - 1) // 2
        Diff[i] = K
        RawAns += K
    for _ in range(Q):
        (h, w) = map(int, input().split())
        h -= 1
        w = W - w
        i1 = (h + w + 1) // 2 * 2
        if i1 < W:
            j1 = h * 2 + (h + w) % 2
        else:
            j1 = (W - w - 1) * 2 + (h + w + 1) % 2
        i2 = (h + w) // 2 * 2 + 1
        if i2 < W:
            j2 = h * 2 + (h + w + 1) % 2
        else:
            j2 = (W - w - 1) * 2 + (h + w) % 2
        if A[i1][j1]:
            RawAns += 1
        else:
            RawAns -= 1
        A[i1][j1] ^= 1
        A[i2][j2] ^= 1
        Tmp1 = 0
        Count = -1
        for a in A[i1]:
            if a:
                Tmp1 += Count * (Count + 1) // 2
                Count = -1
            else:
                Count += 1
        Tmp1 += Count * (Count + 1) // 2
        Tmp2 = 0
        Count = -1
        for a in A[i2]:
            if a:
                Tmp2 += Count * (Count + 1) // 2
                Count = -1
            else:
                Count += 1
        Tmp2 += Count * (Count + 1) // 2
        RawAns -= Diff[i1] - Tmp1 + Diff[i2] - Tmp2
        Diff[i1] = Tmp1
        Diff[i2] = Tmp2
        print(RawAns)
if __name__ == '__main__':
    main()