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):
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * (n + 1)
r = [n] * (n + 1)
mc = n
mr = n
for _ in range(q):
    m,q = list(map(int, input().split()))
    if m == 1:
        if q <= mc:
            count -= mr -2
            for p in range(q+1, mc):
                c[p] = mr
            c[q] = 0
            mc = q
        else:
            count -= c[q] - 2
    else:
        if q <= mr:
            count -= mc -2
            for p in range(q+1, mr):
                r[p] = mc
            r[q] = 0
            mr = q
        else:
            count -= r[q] - 2
print(count)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq


import bisect
n,q=map(int,input().split())
tate=[n]*(n+1)
yoko=[n]*(n+1)
black=(n-2)*(n-2)
h=n
w=n
for i in range(q):
    ty,x=map(int,input().split())
    if ty==1:
        if x<=w:
            black-=h-2
            for j in range(w-1,x,-1):
                tate[j]=h   
            w=x
            tate[x]=0
        else:
            black-=tate[x]-2
    else:
        if x<=h:
            black-=w-2
            for j in range(h-1,x,-1):
                yoko[j]=w
            h=x
            yoko[x]=0
        else:
            black-=yoko[x]-2
print(black)

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")



def main():
    N, Q = map(int, input().split())
    
    h = N
    w = N
    a = [N]*N
    b = [N]*N
    ans = (N-2)**2
    for _ in range(Q):
        q, x = map(int, input().split())
        if q == 1:
            if x < w:
                for i in range(x, w):
                    b[i] = h
                w = x
            ans -= b[x] - 2
        elif q == 2:
            if x < h:
                for i in range(x, h):
                    a[i] = w
                h = x
            ans -= a[x] - 2
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n, q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(q)]

ans = (n - 2)** 2
cnt, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if cnt[num] > x:
        wh[num][x:cnt[num]] = [cnt[1 - num]] * (cnt[num] - x)
        cnt[num] = x
    ans -= wh[num][x]
    wh[num][x] = 0
print(ans)

Solution (Python):
n, q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(q)]

ans = (n - 2)** 2
cnt, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if cnt[num] > x:
        for i in range(x, cnt[num]):
            wh[num][i] = cnt[1 - num]
        cnt[num] = x
    ans -= wh[num][x]
    wh[num][x] = 0
print(ans)

Solution (Python):
n, q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(q)]

ans = (n - 2)** 2
c, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if c[num] > x:
        for i in range(x, c[num]):
            wh[num][i] = c[1 - num]
        c[num] = x
    ans -= wh[num][x]
    wh[num][x] = 0
print(ans)

Solution (Python):
n, q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(q)]

ans = (n - 2)** 2
c, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if c[num] > x:
        ans -= c[1 - num]
        for i in range(x, c[num]):
            wh[num][i] = c[1 - num]
        c[num] = x
    elif c[num] <= x:
        ans -= wh[num][x]
    wh[num][x] = 0
print(ans)

Solution (Python):
N, Q = map(int, input().split())
left = N
up = N
ans = (N-2)**2
lefts = [N]*(N+1)
ups = [N]*(N+1)

for _ in range(Q):
    num, x = map(int, input().split())
    if num == 1:
        if x < left:
            for i in range(x, left):
                ups[i] = up
            left = x
        ans -= ups[x] - 2
    else:
        if x < up:
            for i in range(x, up):
                lefts[i] = left
            up = x
        ans -= lefts[x] - 2
    

print(ans)

Solution (Python):

import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000


def binary_search(list, item):
    
    mode = 2
    low = 0
    high = len(list) - 1
    upper = len(list) - 1
    lower = 0
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
            upper = mid
        else:
            low = mid + 1
            lower = mid
    if mode == 1:
        return upper
    elif mode == 2:
        return lower

def main():
    
    N, Q = list(map(int, input().split()))     

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

    
    black = (N-2)**2
    m = [N, N]
    chList = [[-1] * N for _ in range(2)]
    for que in queList:
        x = que[1]
        y = que[0]-1
        ch = chList[y][x]
        if ch == -1:
            ch = m[1-y] - 2
            m[y] = x
            i = 0
            while x+i <= N-1 and chList[y][x+i] == -1:
                chList[y][x+i] = m[1-y] - 2
                i = i + 1
        black -= ch

    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    print("{}".format(black))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

class BIT():
    
    
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    
    def add(self,i,x):
        
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    
    def sum(self,i):
        s = 0
        
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    
    
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            
            
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1

def main():
    N, Q = MI()
    X, Y = BIT(N), BIT(N)
    xmin = N-2
    ymin = N-2
    X.add(1, N-2)
    X.add(N-1, -(N-2))
    Y.add(1, N-2)
    Y.add(N-1, -(N-2))

    res = (N-2)**2
    for i in range(Q):
        a, b = MI()
        if a == 1:
            x = X.sum(b-1)
            if ymin > b-2:
                temp = Y.sum(1)
                Y.add(1, b-2-temp)
                Y.add(x+1, -(b-2-temp))
                ymin = b-2
            res -= x
        else:
            y = Y.sum(b-1)
            if xmin > b-2:
                temp = X.sum(1)
                X.add(1, b-2-temp)
                X.add(y+1, -(b-2-temp))
                xmin = b-2
            res -= y
            
    print(res)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

class BIT():
    
    
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    
    def add(self,i,x):
        
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    
    def sum(self,i):
        s = 0
        
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    
    
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            
            
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1

def main():
    N, Q = MI()
    X, Y = BIT(N), BIT(N)
    xmin = N-2
    ymin = N-2
    X.add(1, N-2)
    X.add(N-1, -(N-2))
    Y.add(1, N-2)
    Y.add(N-1, -(N-2))

    res = (N-2)**2
    for i in range(Q):
        a, b = MI()
        if a == 1:
            x = X.sum(b-1)
            if ymin > b-2:
                temp = Y.sum(1)
                Y.add(1, b-2-temp)
                Y.add(xmin+1, -(b-2-temp))
                ymin = b-2
            res -= x
        else:
            y = Y.sum(b-1)
            if xmin > b-2:
                temp = X.sum(1)
                X.add(1, b-2-temp)
                X.add(ymin+1, -(b-2-temp))
                xmin = b-2
            res -= y
            
    print(res)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

class BIT():
    
    
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    
    def add(self,i,x):
        
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    
    def sum(self,i):
        s = 0
        
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    
    
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            
            
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1

def main():
    N, Q = MI()
    X, Y = BIT(N), BIT(N)
    xmin = N-2
    ymin = N-2
    X.add(1, N-2)
    X.add(N-1, -(N-2))
    Y.add(1, N-2)
    Y.add(N-1, -(N-2))

    res = (N-2)**2
    for i in range(Q):
        a, b = MI()
        if a == 1:
            x = X.sum(b-1)
            if ymin > b-2:
                temp = Y.sum(1)
                Y.add(1, b-2-temp)
                Y.add(xmin+1, -(b-2-temp))
                ymin = b-2
            res -= x
        else:
            y = Y.sum(b-1)
            if xmin > b-2:
                temp = X.sum(1)
                X.add(1, b-2-temp)
                X.add(ymin+1, -(b-2-temp))
                xmin = b-2
            res -= y
            
    print(res)
    
if __name__ == "__main__":
    main()

Solution (Python):
n , q = map(int,input().split())
kuro = (n-2)**2
nowy = n - 1
nowt = n - 1
yoko = [n-1 for i in range(n-1)]
tate = [n-1 for i in range(n-1)]

for _ in range(q):
    p = list(map(lambda x:int(x)-1,input().split()))
    if p[0] == 0:
        if p[1] < nowt:
            kuro -= nowy - 1
            for i in range(p[1],nowt):
                yoko[i] = nowy
            nowt = p[1]
        elif p[1] > nowt:
            kuro -= yoko[p[1]] - 1
    elif p[0] == 1:
        if p[1] < nowy:
            kuro -= nowt - 1
            for i in range(p[1],nowy):
                tate[i] = nowt
            nowy = p[1]
        elif p[1] > nowy:
            kuro -= tate[p[1]] - 1
print(kuro)

Solution (Python):
class SegmentTreeDual():
    def __init__(self, n, op, id, commutative=False):
        self.n = n
        self.op = op
        self.id = id
        self.commutative = commutative
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [id] * self.size
        self.lz = [id] * (2 * self.size)

    def build(self, arr):
        for i, a in enumerate(arr):
            self.d[i] = a

    def propagate(self, k):
        if self.lz[k] == self.id: return
        if k < self.size:
            self.lz[2 * k] = self.op(self.lz[k], self.lz[2 * k], )
            self.lz[2 * k + 1] = self.op(self.lz[k], self.lz[2 * k + 1])
        else:
            self.d[k - self.size] = self.op(self.lz[k], self.d[k - self.size])
        self.lz[k] = self.id

    def get(self, p):
        res = self.d[p]
        p += self.size
        for i in range(self.log):
            res = self.op(self.lz[p >> i], res)
        return res

    def range_apply(self, l, r, f):
        if l == r: return
        l += self.size
        r += self.size
        if not self.commutative:
            for i in range(self.log)[::-1]:
                self.propagate(l >> i)
                self.propagate(r >> i)
        while l < r:
            if l & 1:
                self.lz[l] = self.op(f, self.lz[l])
                l += 1
            if r & 1:
                r -= 1
                self.lz[r] = self.op(f, self.lz[r])
            l >>= 1
            r >>= 1

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())

stx = SegmentTreeDual(N, min, 10**18, True)
sty = SegmentTreeDual(N, min, 10**18, True)

x = [N - 1] * (N - 1) + [0]
y = [N - 1] * (N - 1) + [0]

stx.build(x)
sty.build(y)

res = (N - 2) * (N - 2)

for _ in range(Q):
    q, k = map(int, input().split())
    if q == 1:
        g = stx.get(k - 1)
        res -= g - 1
        sty.range_apply(1, g, k - 1)
    if q == 2:
        g = sty.get(k - 1)
        res -= g - 1
        stx.range_apply(1, g, k - 1)

print(res)

Solution (Python):
class SegmentTreeDual():
    def __init__(self, n, op, id, commutative=False):
        self.n = n
        self.op = op
        self.id = id
        self.commutative = commutative
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [id] * self.size
        self.lz = [id] * (2 * self.size)

    def build(self, arr):
        for i, a in enumerate(arr):
            self.d[i] = a

    def propagate(self, k):
        if self.lz[k] == self.id: return
        if k < self.size:
            self.lz[2 * k] = self.op(self.lz[k], self.lz[2 * k], )
            self.lz[2 * k + 1] = self.op(self.lz[k], self.lz[2 * k + 1])
        else:
            self.d[k - self.size] = self.op(self.lz[k], self.d[k - self.size])
        self.lz[k] = self.id

    def get(self, p):
        res = self.d[p]
        p += self.size
        for i in range(self.log):
            res = self.op(self.lz[p >> i], res)
        return res

    def range_apply(self, l, r, f):
        if l == r: return
        l += self.size
        r += self.size
        if not self.commutative:
            for i in range(self.log)[::-1]:
                self.propagate(l >> i)
                self.propagate(r >> i)
        while l < r:
            if l & 1:
                self.lz[l] = self.op(f, self.lz[l])
                l += 1
            if r & 1:
                r -= 1
                self.lz[r] = self.op(f, self.lz[r])
            l >>= 1
            r >>= 1

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())

stx = SegmentTreeDual(N, min, 10**18, False)
sty = SegmentTreeDual(N, min, 10**18, False)

x = [N - 1] * (N - 1) + [0]
y = [N - 1] * (N - 1) + [0]

stx.build(x)
sty.build(y)

res = (N - 2) * (N - 2)

for _ in range(Q):
    q, k = map(int, input().split())
    if q == 1:
        g = stx.get(k - 1)
        res -= g - 1
        sty.range_apply(1, g, k - 1)
    if q == 2:
        g = sty.get(k - 1)
        res -= g - 1
        stx.range_apply(1, g, k - 1)

print(res)

Solution (Python):
class SegmentTreeDual():
    def __init__(self, arr, op=lambda x, y: y if y != -1 else x, ie=-1):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]

    def propagate(self, k):
        if self.laz[k] == self.ie: return
        if self.n <= k:
            self.val[k - self.n] = self.op(self.val[k - self.n], self.laz[k])
        else:
            self.laz[2 * k] = self.op(self.laz[2 * k], self.laz[k])
            self.laz[2 * k + 1] = self.op(self.laz[2 * k + 1], self.laz[k])
        self.laz[k] = self.ie

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

    def get(self, idx):
        res = self.val[idx]
        idx += self.n
        while idx:
            res = self.op(res, self.laz[idx])
            idx >>= 1
        return res

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())

x = [N - 1] * (N - 1) + [0]
y = [N - 1] * (N - 1) + [0]

stx = SegmentTreeDual(x, min, 10**18)
sty = SegmentTreeDual(y, min, 10**18)

res = (N - 2) * (N - 2)

for _ in range(Q):
    q, k = map(int, input().split())
    if q == 1:
        g = stx.get(k - 1)
        res -= g - 1
        sty.update(1, g, k - 1)
    if q == 2:
        g = sty.get(k - 1)
        res -= g - 1
        stx.update(1, g, k - 1)

print(res)

Solution (Python):
class SegTree:
    X_unit = 1 << 30
    X_f = min

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)
      
N, Q=map(int,input().split())
S1=SegTree(N)
S2=SegTree(N)

S1.build([N]*N)
S2.build([N]*N)
ans=(N-2)**2

for i in range(Q):
  j, x=map(int,input().split())
  if j==1:
    l=S2.fold(x-1,N)
    ans-=l-2
    S1.set_val(l-1,min(x,S1.X[l-1+N]))
  if j==2:
    l=S1.fold(x-1,N)
    ans-=l-2
    S2.set_val(l-1,min(x,S2.X[l-1+N]))
    
print(ans)

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


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    
    def update(self, k: int, x):
        k += self.N0 - 1
        
        self.data[k] = x
        
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def get(self, k):
        return self.query(k,k+1)
    
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        
        return res



"""
     .
 
 
 
 
......

"""


segW=SegmentTree([N-1]*N, min, float("INF"))
segH=SegmentTree([N-1]*N, min, float("INF"))
ans=(N-2)**2
for i in range(Q):
    q,x=map(int, input().split())
    if q==1:
        res=segW.query(x-1,N)
        now=segH.get(res-1)
        segH.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    else:
        res=segH.query(x-1,N)
        now=segW.get(res-1)
        segW.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    


print(ans)

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


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    
    def update(self, k: int, x):
        k += self.N0 - 1
        
        self.data[k] = x
        
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def get(self, k):
        return self.query(k,k+1)
    
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        
        return res



"""
     .
 
 
 
 
......

"""


segW=SegmentTree([N-2]*N, min, 10**18)
segH=SegmentTree([N-2]*N, min, 10**18)
ans=(N-2)**2
for i in range(Q):
    q,x=map(int, input().split())
    if q==1:
        res=segW.query(x-1,N)
        
        segH.update(res, min(x-2, segH.query(res,N)))
        ans-=res
    else:
        res=segH.query(x-1,N)
        now=segW.get(res-1)
        segW.update(res, min(x-2, segW.query(res,N)))
        ans-=res
    


print(ans)

Solution (Python):
N,Q = map(int,input().split())
a,b = [N]*(N+1),[N]*(N+1)

H,W = N,N

black = (N-2)**2

for _ in range(Q):
  t,x = map(int,input().split())
  if t == 1:
    if x < W:
      for i in range(x,W):
        b[i] = H
      W = x

    black -= b[x] - 2
  
  else:
    if x < H:
      for i in range(x,H):
        a[i] = W
      H = x

    black -= a[x] - 2
  

print(black)

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

class BIT2:
    def __init__(self, N):
        self.N = (N+1)
        self.data0 = [0] * (N+1)
        self.data1 = [0] * (N+1)
        
    def _add(self, data, k, x):
        while k < self.N: 
            data[k] += x
            k += k & -k

    def _sum(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def sum(self, l, r):
        return self._sum(self.data1, r-1) * (r-1) + self._sum(self.data0, r-1) \
                - self._sum(self.data1, l-1) * (l-1) - self._sum(self.data0, l-1) 

N, Q = map(int, readline().split())
bit1 = BIT2(N)
bit1.add(1,N+1,N-2)
bit2 = BIT2(N)
bit2.add(1,N+1,N-2)
total = (N-2)**2

right = N
low = N
cnt = 0
for _ in range(Q):
    cmd,t = map(int,readline().split())
    if cmd == 1:
        tmp = bit1.sum(t,t+1)
        cnt += tmp
        bit1.add(t,t+1,-tmp)
        if t < right:
            bit2.add(1,low,t-right) 
            right = t
    else:
        tmp = bit2.sum(t,t+1)
        cnt += tmp
        bit2.add(t,t+1,-tmp)
        if t < low:
            bit1.add(1,right,t-low)  
            low = t

ans = total - cnt
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, Q, *query = map(int, read().split())

    N -= 2
    row = [N] * N
    col = [N] * N
    R = C = N

    ans = N * N
    for q, x in zip(*[iter(query)] * 2):
        x -= 2
        if q == 1:
            if x < C:
                ans -= R
                for i in range(x + 1, C):
                    col[i] = R
                C = x
            else:
                ans -= col[x]
        else:
            if x < R:
                ans -= C
                for i in range(x + 1, R):
                    row[i] = C
                R = x
            else:
                ans -= row[x]
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
class SegTree():
    def __init__(self, initial, operation, identity):
        n = len(initial)
        self.initial = initial
        self.operation = operation
        self.identity = identity
        self.num = 1 << (len(bin(n - 1)) - 2)
        self.tree = [identity] * (2 * self.num - 1)
        for i in range(n):
            self.tree[i + self.num - 1] = self.initial[i]
        for i in reversed(range(self.num - 1)):
            self.tree[i] = min(self.tree[2*i + 1], self.tree[2*i + 2])
    
    def update(self, k, x):
        k += self.num - 1
        self.tree[k] = x
        while k >= 1:
            k = (k - 1) // 2
            self.tree[k] = self.operation(self.tree[2*k + 1], self.tree[2*k + 2])
    
    def query(self, l, r):
        res = self.identity
        l += self.num - 1
        r += self.num - 1
        while l < r:
            if l % 2 == 0:
                res = self.operation(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = self.operation(res, self.tree[r - 1])
            l = (l - 1) // 2
            r = (r - 1) // 2
        return res

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

H, W = SegTree([N]*N, min, N), SegTree([N]*N, min, N)
revd = 0
for _ in range(Q):
    t, x = [int(i) for i in input().split()]
    if t == 1:
        h = H.query(x, N + 1)
        w = W.query(h, N + 1)
        revd += h - 2
        W.update(h, min(x, w))
    else:
        w = W.query(x, N + 1)
        h = H.query(w, N + 1)
        revd += w - 2
        H.update(w, min(x, h))

ans = (N - 2)*(N - 2) - revd
print(ans)

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)