Problem:
 Score : 600 points    Problem Statement There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i -th row from the top and the j -th column from the left.  Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it.
Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.  Q queries are given. We ask you to process them in order.
There are two kinds of queries. Their input format and description are as follows:   1 x : Place a white stone on (1, x) . After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x) , replace it with a white stone.  2 x : Place a white stone on (x, 1) . After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1) , replace it with a white stone.   How many black stones are there on the grid after processing all Q queries?      Constraints  3 \leq N \leq 2\times 10^5  0 \leq Q \leq \min(2N-4,2\times 10^5)  2 \leq x \leq N-1  Queries are pairwise distinct.         Input Input is given from Standard Input in the following format:  N  Q  Query_1  \vdots  Query_Q       Output Print how many black stones there are on the grid after processing all Q queries.        Sample Input 1 5 5
1 3
2 3
1 4
2 2
1 2      Sample Output 1 1  After each query, the grid changes in the following way:        Sample Input 2 200000 0      Sample Output 2 39999200004       Sample Input 3 176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282      Sample Output 3 31159505795

Solution (Python):
class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x

        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2 * self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i + self.size] = a

        for i in range(self.size - 1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log + 1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r - 1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r - 1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def __all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def __push(self, k):
        self.__all_apply(2 * k, self.lz[k])
        self.__all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.im()




def op(x,y):
    return x+y


def mapping(x, y):
    return min(x, y)


def composition(x,y):
    return min(x, y)


def im():
    return 100000000000


def a():
    
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())

    def e():
        return N - 2
    ans = (N-2) * (N-2)
    ssss = [N-2] * (N-1)
    st = LazySegmentTree(op, e, mapping, composition, im,ssss)
    sa = LazySegmentTree(op, e, mapping, composition, im,ssss)
    for _ in range(Q):
        t, l = map(int, input().split())
        if t == 1:
            t = st.__getitem__(l-1) + 1
            sa.apply(1, t, l-2)
            ans -= t-1
        else:
            t = sa.__getitem__(l-1) + 1
            st.apply(1, t, l-2)
            ans -= t-1
    print(ans)

if __name__ == "__main__":
    a()

Solution (Python):
N, Q = map(int, input().split())

N -= 2

BIT = [[0 for i in range(N+1)] for _ in range(2)]
n = N
def BIT_query(idx,BIT):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x,BIT):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

now = N * N
max_x = [0, 0]
for _ in range(Q):
  s, x = map(int, input().split())
  s -= 1
  x -= 1
  x = N+1 - x
  
  depth = N + BIT_query(x, BIT[s])
  now -= depth
  
  
  if x > max_x[s]:
    BIT_update(N-depth+1, max_x[s] - x, BIT[1-s])
    max_x[s] = x
    
print(now)

Solution (Python):
N,Q = map(int,input().split())
ans = (N-2)**2
H = [N for i in range(N+1)]
W = [N for i in range(N+1)]

last_ignored_H= N
last_ignored_W=N

ignoredH = [False for i in range(N+1)]
ignoredH[N] = True

ignoredW=[False for i in range(N+1)]
ignoredW[N] = True

for i in range(Q):
    command ,where = map(int,input().split())
    if command == 1:
        
        if ignoredH[where] == True:
            ans -=H[where] - 2
            continue
            
        elif ignoredH[where] == False:
            H[where] = last_ignored_W
            ans -=H[where] - 2
            for j in range(where,last_ignored_H):
                ignoredH[j] = True
                H[j] = H[where]
            last_ignored_H = where
  
  
    else:
        
        if ignoredW[where] == True:
            ans -=W[where] - 2
            continue
        elif ignoredW[where] == False:   
            W[where] = last_ignored_H
            ans -=W[where] -2
            for j in range(where,last_ignored_W):
                ignoredW[j] = True
                W[j] = W[where]
            last_ignored_W = where
            
print(ans)

Solution (Python):

class LazySegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the lazy segment tree with data"""
        self._default = default
        self._func = func

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        
        q, self._lazy[idx] = self._lazy[idx], 0

        self._lazy[2 * idx] = max(self._lazy[2 * idx], q)
        self._lazy[2 * idx + 1] = max(self._lazy[2 * idx + 1], q)
        self.data[2 * idx] = max(self.data[2 * idx], q)
        self.data[2 * idx + 1] = max(self.data[2 * idx + 1], q)

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            self.data[idx] = max(
                self._func(self.data[2 * idx], self.data[2 * idx + 1]), self._lazy[idx]
            )
            idx >>= 1

    def add(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] = max(self._lazy[start], value)
                self.data[start] = max(self.data[start], value)
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] = max(self._lazy[stop], value)
                self.data[stop] = max(self.data[stop], value)
            start >>= 1
            stop >>= 1

        
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=0):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        
        self._update(start)
        self._update(stop - 1)

        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)


def solve(N, Q, queries):
    N -= 2
    total = N * N
    rows = LazySegmentTree([0] * (N + 1), 0, max)
    cols = LazySegmentTree([0] * (N + 1), 0, max)
    for t, x in queries:
        assert x >= 2
        x -= 2
        if t == 1:
            c = x
            removed = N - cols.query(c, c + 1)
            assert removed >= 0
            total -= removed
            cols.add(c, c + 1, N)
            if removed:
                rows.add(0, removed, N - c)

        elif t == 2:
            r = x
            removed = N - rows.query(r, r + 1)
            assert removed >= 0
            total -= removed
            rows.add(r, r + 1, N)
            if removed:
                cols.add(0, removed, N - r)
    return total


if False:
    import random

    random.seed(0)
    for _ in range(100):
        print(_)
        N = random.randint(3, 10)
        queries = []
        for i in range(2, N):
            queries.append((1, i))
            queries.append((2, i))

        random.shuffle(queries)
        Q = random.randint(0, min(2 * N - 4, 10))
        queries = queries[:Q]
        print(queries)
        solve(N, len(queries), queries)


N, Q = [int(x) for x in input().split()]
queries = [[int(x) for x in input().split()] for i in range(Q)]

print(solve(N, Q, queries))

Solution (Python):
n,q = list(map(int,input().split()))

black = (n-2)**2
left_most = n-1
down_most = n-1

L = [n-2] * n
D = [n-2] * n

for _ in range(q):
  x,c = list(map(int,input().split()))
  c -= 1
  
  if x==1:
    if c<left_most:
      for j in range(c, left_most):
        D[j] = down_most - 1
     
      left_most = c
    black -= D[c]
 
  if x==2:
    if c<down_most:
      for j in range(c, down_most):
        L[j] = left_most - 1
      
      down_most = c
    black -= L[c]
    

  
print(black)

Solution (Python):


def debug(N, st):
    print(*[st.query(i, i+1) for i in range(N)], sep=" ")

def solve(N, Q, Queries):
    from itertools import accumulate
    row = SegmentTreeLazy([float("inf")]*N, float("inf"), float("inf"), min, min, min)
    col = SegmentTreeLazy([float("inf")]*N, float("inf"), float("inf"), min, min, min)
    rmin = list(accumulate([N if c == 2 else x for c, x in Queries], min))
    cmin = list(accumulate([N if c == 1 else x for c, x in Queries], min))
    ans = 0
    def f(st, emin, i, step):
        st.update(i, N, step)
        idx = st.query(i, i+1)
        return emin[idx] - 2
    for step, (c, x) in enumerate(Queries):
        if c == 1:
            ans += f(row, cmin, x-1, step)
        else:
            ans += f(col, rmin, x-1, step)
    return (N-2)**2 - ans


class SegmentTreeLazy():
    def __init__(self, arr, ti, ei, func, op, merge):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.func = func
        self.op = op
        self.merge = merge
        self.ti = ti
        self.ei = ei
        self.val = [ti for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
        self.laz = [ei for _ in range(2 * self.n)]

    def reflect(self, k):
        if self.laz[k] == self.ei:
            return self.val[k]
        return self.op(self.val[k], self.laz[k])

    def propagate(self, k):
        if self.laz[k] == self.ei: return
        self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
        self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
        self.val[k] = self.reflect(k)
        self.laz[k] = self.ei

    def thrust(self, k):
        for i in range(1, self.h + 1)[::-1]:
            self.propagate(k >> i)

    def recalc(self, k):
        while k:
            k >>= 1
            self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        vl = lt
        vr = rt
        self.thrust(lt)
        self.thrust(rt - 1)
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.merge(self.laz[lt], x)
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.merge(self.laz[rt], x)
            lt >>= 1
            rt >>= 1
        self.recalc(vl)
        self.recalc(vr - 1)

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        self.thrust(lt)
        self.thrust(rt - 1)
        vl = vr = self.ti
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.reflect(lt))
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.reflect(rt), vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)


def main():
    N, Q = map(int, input().split())
    Queries = [list(map(int, input().split())) for _ in range(Q)]
    print(solve(N, Q, Queries))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
from bisect import bisect_left as bl

N, Q = map(int, input().split())
ans = 0
q1 = []
q2 = []
query = []
for _ in range(Q):
    n, p = map(int, input().split())
    query.append((n, p))
    if n == 1:
        q1.append(p)
    else:
        q2.append(p)
q1.sort()
q2.sort()
board = [N - 2, N - 2]
count1 = len(q1)
count2 = len(q2)
for n, p in query:
    if n == 1:
        if p > board[1] + 1:
            continue
        index = bl(q1, p)
        ans += board[0] * (count1 - index)
        board[1] = p - 2
        count1 = index
    else:
        if p > board[0] + 1:
            continue
        index = bl(q2, p)
        ans += board[1] * (count2 - index)
        board[0] = p - 2
        count2 = index
print((N - 2) ** 2 - ans)

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()

class LazySegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f 
        self.g = g 
        self.h = h 
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
            i >>= 1
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getrange(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        
        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
        
        self.calc_above(l0)
        self.calc_above(r0)
    
    
    def max_right(self, l, z):
        if l >= self.n: return self.n
        l += self.n
        s = self.unitX
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.calc(l))):
                while l < self.n:
                    l *= 2
                    if z(self.f(s, self.calc(l))):
                        s = self.f(s, self.calc(l))
                        l += 1
                return l - self.n
            s = self.f(s, self.calc(l))
            l += 1
            if l & -l == l: break
        return self.n
    
    
    def min_left(self, r, z):
        if r <= 0: return 0
        r += self.n
        s = self.unitX
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.calc(r), s)):
                while r < self.n:
                    r = r * 2 + 1
                    if z(self.f(self.calc(r), s)):
                        s = self.f(self.calc(r), s)
                        r -= 1
                return r + 1 - self.n
            s = self.f(self.calc(r), s)
            if r & -r == r: break
        return 0

f = lambda x, y: (x + y) 
g = lambda x, a, s: min(x,a)
h = lambda a, b: min(a,b)
unitX = 0
unitA = 10**10
N, Q = map(int, input().split())
A = [N-2]*(N-2)
sttate = LazySegmentTree(A, unitX, unitA, f, g, h)
styoko = LazySegmentTree(A, unitX, unitA, f, g, h)
ans=(N-2)**2
for _ in range(Q):
    q1,q2=map(int, input().split())
    if q1==1:
        horu=sttate.getrange(q2-2, q2-1)
        ans-=horu
        sttate.operate_range(q2-2,q2-1,0)
        styoko.operate_range(0,horu,q2-2)
    if q1==2:
        horu=styoko.getrange(q2-2, q2-1)
        ans-=horu
        styoko.operate_range(q2-2,q2-1,0)
        sttate.operate_range(0,horu,q2-2)
print(ans)

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

def main():
    n, q = map(int, input().split())

    ans = 0
    min1, min2 = n-2, n-2
    judge1 = [-n-1]
    judge2 = [-n-1]
    dict1 = dict()
    dict2 = dict()
    dict1[-n-1] = n-2
    dict2[-n-1] = n-2

    for i in range(q):
        query, x = map(int, input().split())

        if query == 1:
            index = bisect.bisect(judge1, -x)-1
            key = dict1[judge1[index]]
            ans += key
            if min1 > x-2:
                min1 = x-2
                judge1.append(-x)
                dict1[-x] = key
                dict2[judge2[-1]] = min1
        else:
            index = bisect.bisect(judge2, -x)-1
            key = dict2[judge2[index]]
            ans += key
            if min2 > x-2:
                min2 = x-2
                judge2.append(-x)
                dict2[-x] = key
                dict1[judge1[-1]] = min2

    print((n-2)**2 - ans)
    
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


class Segtree_op():
    
    
    
    def __init__(self, n):
        self.n = n

        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        
        return min(lch, rch)

    def unit(self):
        return self.n

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def show(self):
        idx = 1
        while (idx <= self.size):
            print(self.arr[idx - 1:idx * 2 - 1])
            idx *= 2


def solve():
    n, q = getList()

    st_tate = Segtree_op(n)
    st_yoko = Segtree_op(n)

    reversed = 0
    for _ in range(q):
        op, idx = getList()
        if op == 1:
            border = st_tate.query(idx, n+1)
            reversed += border - 2
            val = min(st_yoko.query(border, border+1), idx)
            st_yoko.update(border, val)
        else:
            border = st_yoko.query(idx, n+1)
            reversed += border - 2
            val = min(st_tate.query(border, border + 1), idx)
            st_tate.update(border, val)

        
        
        
        

    print((n-2) ** 2 - reversed)








def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
import bisect
N,Q = map(int, input().split())
L = [0]*Q
L1 = []
L2 = []
for i in range(Q):
    a,b = map(int, input().split())
    L[i] = (a, b)
    if a == 1:
        L1.append(b)
    else:
        L2.append(b)

L1.sort()
L2.sort()
M1 = len(L1)
M2 = len(L2)
ans = (N-2)**2
up = N
left = N
for l in L:
    a = l[0]
    b = l[1]
    if a == 1:
        if b > left:
            continue
        idx = bisect.bisect_left(L1, b)
        ans -= (M1-idx)*(up-2)
        M1 = idx
        left = b
    else:
        if b > up:
            continue
        idx = bisect.bisect_left(L2, b)
        ans -= (M2-idx)*(left-2)
        M2 = idx
        up = b
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right

n,q = map(int, input().split())

hori_cnt = [n-2]*(n+2) 

ql = []
for _ in range(q):
    c,x = map(int, input().split())
    ql.append((c,x))

tate_min = n
yoko_min = n
yoko_kyokai = []
ans1 = 0
for c,x in ql:
    if c == 1:
        if x < tate_min: 
            hori_cnt[yoko_min] = x-2
            yoko_kyokai.append(yoko_min*(-1))
            tate_min = x
    else:
        
        if x < yoko_min:
            yoko_min = x
        
        ind = bisect_left(yoko_kyokai, x*(-1))-1
        
        if ind == -1:
            if x < yoko_min:
                ans1 += (tate_min-2)
            else:
                ans1 += (n-2)
            
        else:
            val = yoko_kyokai[ind]
            ans1 += hori_cnt[val*(-1)]
            


tate_cnt = [n-2]*(n+2) 
yoko_min = n
tate_min = n
tate_kyokai = []
ans2 = 0
for c,x in ql:
    if c == 2:
        if x < yoko_min: 
            tate_cnt[tate_min] = x-2
            tate_kyokai.append(tate_min*(-1))
            yoko_min =x
            
    else:
        

        if x < tate_min:
            tate_min = x

        ind = bisect_left(tate_kyokai, x*(-1))-1
        
        if ind == -1:
            if x < tate_min:
                ans2 += (yoko_min-2)
            else:
                ans2 += (n-2)
            
        else:
            val = tate_kyokai[ind]
            ans2 += tate_cnt[val*(-1)]
            

print((n-2)*(n-2)-ans1-ans2)

Solution (Python):
class lazy_segtree:
  
  def __init__(s, op, e, mapping, composition, id, v):
    if type(v) is int: v = [e()] * v
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.lz = [id()] * s.size
    s.e = e
    s.op = op
    s.mapping = mapping
    s.composition = composition
    s.id = id
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  
  def set(s, p, x):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  
  def get(s, p):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    return s.d[p]
 
  
  def prod(s, l, r):
    if l == r: return s.e()
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push(r >> i)
    sml, smr = s.e(), s.e()
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  
  def all_prod(s): return s.d[1]
 
  
  def apply(s, p, f):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = s.mapping(f, s.d[p])
    for i in range(1, s.log + 1): s.update(p >> i)
 
  
  def apply(s, l, r, f):
    if l == r: return
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push((r - 1) >> i)
    l2, r2 = l, r
    while l < r:
      if l & 1: 
        sml = s.all_apply(l, f)
        l += 1
      if r & 1:
        r -= 1
        smr = s.all_apply(r, f)
      l >>= 1
      r >>= 1
    l, r = l2, r2
    for i in range(1, s.log + 1):
      if (((l >> i) << i) != l): s.update(l >> i)
      if (((r >> i) << i) != r): s.update((r - 1) >> i)
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def all_apply(s, k, f):
    s.d[k] = s.mapping(f, s.d[k])
    if k < s.size: s.lz[k] = s.composition(f, s.lz[k])
  def push(s, k):
    s.all_apply(2 * k, s.lz[k])
    s.all_apply(2 * k + 1, s.lz[k])
    s.lz[k] = s.id()
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x

import sys
    
def e():
  return N - 1

def op(s, t):
  return min(s, t)

def mapping(f, a):
  return min(f, a)

def composition(f, g):
  return min(f, g)

def id():
  return N - 1

N, Q = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]

v = [N - 2] * ((N - 2) * 2)


ans = (N - 2) * (N - 2)
seg = lazy_segtree(op, e, mapping, composition, id, v)

for q, x in Query:
  x -= 2
  l = 0
  r = 0
  t = 0
  if q == 1:
    t = N - 2
  if q == 2:
    l += N - 2
    r += N - 2
  g = seg.get(x + t)
  ans -= g
  r += g
  seg.apply(l, r, x)

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

inf = 10**10

class Seg_min():
    def __init__(self,x):
        
        self.ide_ele_min = inf
        self.func = min

        self.n = len(x)

        
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

n,q,*query = list(map(int,read().split()))

wall_ns = Seg_min([inf] * (n-2))
wall_ew = Seg_min([inf] * (n-2))
min_ns = [n-2] * (q+1)
min_ew = [n-2] * (q+1)

ans = (n-2)*(n-2)
for i in range(1,q+1):
    x = query[i*2-1] - 2
    if(query[i*2-2] == 1):
        last = wall_ns.query(0,x)
        if(last == inf):
            last = i-1
        ans -= min_ew[last]

        wall_ns.update(x,i)
        min_ns[i] = min(min_ns[i-1], x)
        min_ew[i] = min_ew[i-1]
    else:
        last = wall_ew.query(0,x)
        if(last == inf):
            last = i-1
        ans -= min_ns[last]

        wall_ew.update(x,i)
        min_ew[i] = min(min_ew[i-1], x)
        min_ns[i] = min_ns[i-1]

print(ans)