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:

    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data * 2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe] * (self.n * 2)


    def replace(self, index, value):
        index += self.n

        
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        
        self.data[index] = value
        self.lazy[index] = self.oe

        
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def effect(self, l, r, operator):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        
        i = l0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
        i = r0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
            
        
    def folded(self, l, r):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)

import sys
input = sys.stdin.readline
def fmo(m1, o1):
    if o1 == -1:
        return m1
    return o1
def foo(o1, o2):
    if o2 == -1:
        return o1
    return o2
        

n, q = map(int, input().split())
ans = (n-2)*(n-2)
h = n-2
w = n-2
LR = LazySegmentTree([-2]*n, h, -1, min, fmo, foo)
DU = LazySegmentTree([-2]*n, w, -1, min, fmo, foo)
for _ in range(q):
    t, x = map(int, input().split())
    x -= 1
    if t == 1:
        temp = LR.folded(x, x+1)
        if temp == -2:
            ans -= h
            LR.effect(x+1, w+1, h)
            w = x-1
        else:
            ans -= temp
    else:
        temp = DU.folded(x, x+1)
        if temp == -2:
            ans -= w
            DU.effect(x+1, h+1, w)
            h = x-1
        else:
            ans -= temp
print(ans)

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

area_W = N - 2
area_H = N - 2

walls_H = []
walls_V = []

count = (N - 2) * (N - 2)


def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

for _ in range(Q):
	q, i = input().split()
	i = int(i) - 2
	if q == "1":
		if i < area_W:
			area_W = i
			count -= area_H
			walls_H.append((i, area_H))
		else:
			j = bisearch_smallest(lambda j: walls_H[j][0] < i, 0, len(walls_H))
			count -= walls_H[j][1]
	else:
		if i < area_H:
			area_H = i
			count -= area_W
			walls_V.append((i, area_W))
		else:
			j = bisearch_smallest(lambda j: walls_V[j][0] < i, 0, len(walls_V))
			count -= walls_V[j][1]


print(count)

Solution (Python):
class F:
    def __init__(self, x):
        self.bit = x
        for i in range(len(x)):
            j = i | (i + 1)
            if j < len(x):
                x[j] += x[i]
    def update(self, idx, x):
        while idx < len(self.bit):
            self.bit[idx] += x
            idx |= idx + 1
    def query(self, end):
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x
    def findkth(self, k):
        idx = -1
        for d in reversed(range(len(self.bit).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(self.bit) and k >= self.bit[right_idx]:
                idx = right_idx
                k -= self.bit[idx]
        return idx + 1
import sys
z=sys.stdin.readline
y=lambda:map(int,z().split())
n,q=y()
v=F([0]*(n-2))
h=F([0]*(n-2))
w=j=n-2
s=0
for _ in range(q):
    a,b=y()
    if a<2:
        if b-2<w:h.update(n-2-j,w-b+2);w=b-2
        s+=n-2-v.query(n-b)
    else:
        if b-2<j:v.update(n-2-w,j-b+2);j=b-2
        s+=n-2-h.query(n-b)
print((n-2)*(n-2)-s)

Solution (Python):
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

class SegTree:
  def segfunc(self, x, y):
    return min(x, y)
  def __init__(self, n, ide_ele, init_val):
    
    self.ide_ele = ide_ele
    
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

lseg = SegTree(N, N, [N] * N)
useg = SegTree(N, N, [N] * N)
res = (N - 2) * (N - 2)
for _ in range(Q):
  q, x = map(int, input().split())
  x -= 1
  if q == 1:
    u = useg.query(x, N)
    res -= u - 2
    l = lseg.query(u - 1, u)
    lseg.update(u - 1, min(l, x + 1))
    
  else:
    l = lseg.query(x, N)
    res -= l - 2
    u = useg.query(l - 1, l)
    useg.update(l - 1, min(u, x + 1))
    
print(res)

Solution (Python):
from bisect import bisect_left, bisect_right
N, Q = map(int, input().split())

ans = 0
tate = [[-N, N-2]]
tateL = 1
yoko = [[-N, N-2]]
yokoL = 1
ans = (N-2) * (N-2)
for _ in range(Q):
    s, x = input().split()
    x = int(x)
    if s == '1':
        idx = bisect_left(tate, [-x, 0])
        ans -= tate[idx-1][1]
        if idx == tateL:
            tate.append([-x, tate[idx-1][1]])
            tateL += 1
            yoko[-1][1] = x - 2
    else:
        idx = bisect_left(yoko, [-x, 0])
        ans -= yoko[idx-1][1]
        if idx == yokoL:
            yoko.append([-x, yoko[idx-1][1]])
            yokoL += 1
            tate[-1][1] = x - 2
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

class segtree():
    def __init__(self,A,ide=1000000000):
        n=len(A)
        num=2**(n-1).bit_length()
        seg=[ide]*(2*num-1)
        segfunc=self.segfunc
        self.ide,self.n,self.num,self.seg = ide, n, num, seg
        for i in range(n): seg[i+num-1]=A[i]
        for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
    def segfunc(self,x,y):return min(x,y) 
    
    def update(self,k,x):
        k += self.num-1
        seg,segfunc=self.seg,self.segfunc
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
    def query(self,p,q):
        if q<=p: return self.ide
        num,segfunc,seg=self.num,self.segfunc,self.seg
        p += num-1; q += num-2
        res=self.ide
        while q-p>1:
            if p&1 == 0: res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p,q = p//2, (q-1)//2
        if p == q: res = segfunc(res,seg[p])
        else: res = segfunc(segfunc(res,seg[p]),seg[q])
        return res 
def main():
    mod = 1000000007
    

    
    N, Q = map(int, input().split())
    
    
    S = tuple(tuple(map(int, input().split())) for i in range(Q)) 

    tot=(N-2)*(N-2)
    seg1=segtree([N]*(N+1))
    seg2=segtree([N]*(N+1))
    l1=[N]*(N+1)
    l2=[N]*(N+1)
    for t,x in S:
        if t==1:
            place=seg2.query(x,N+1)
            tot-=place-2
            l1[place]=min(l1[place],x)
            seg1.update(place,l1[place])
        else:
            place=seg1.query(x,N+1)
            tot-=place-2
            l2[place]=min(l2[place],x)
            seg2.update(place,l2[place])
        
    print(tot)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]


class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = self.op(x,self.node[k])
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res
    
def smin(a,b):
    if a>b:
        return b
    else:
        return a

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

    ST1 = SegmentTree([N-2]*(N-2),smin,N-2)
    ST2 = SegmentTree([N-2]*(N-2),smin,N-2)

    ans = 0
    for i in range(Q):
        a,b = list(map(int,input().split()))
        b-=2
        if a==1:
            c = ST1.get(b,N-3)
            ans+=c
            ST2.substitute(c-1,b)
        else:
            c = ST2.get(b,N-3)
            ans+=c
            ST1.substitute(c-1,b)
        
        
        


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



if __name__ == '__main__':
    main()

Solution (Python):

from itertools import accumulate
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def solve(N,queries):
    N -= 2
    X = [0]*(N+1)
    Y = [0]*(N+1)

    for a,b in queries:
        if b == 0:
            continue
        if a == 0:
            X[b] += 1
        else:
            Y[b] += 1
    X = tuple(accumulate(X))
    Y = tuple(accumulate(Y))
    w = N
    h = N

    res = 0
    for a,b in queries:
        
        b -= 1
        if a == 0:
            if w > b:
                
                res += (X[w]-X[b])*h
                w = b
        else:
            if h > b:
                
                res += (Y[h]-Y[b])*w
                h = b
    return N*N - res



if __name__ == '__main__':
    N,Q = map(int, readline().split())
    m = map(lambda x: int(x)-1, read().split())

    queries = tuple(zip(m,m))

    print(solve(N,queries))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
ans = (N - 2) * (N - 2)

n = N - 2
fixed1 = [-1] * (N + 1)
fixed2 = [-1] * (N + 1)

cand1 = n
cand2 = n

ans = 0
for _ in range(Q):
    x, y = map(int, input().split())
    y -= 1
    if x == 1:
        if fixed1[y] != -1:
            ans += fixed1[y]
        else:
            ans += cand1
            for i in range(y + 1, n + 1):
                if fixed1[i] != -1:
                    break
                fixed1[i] = cand1
            cand2 = min(cand2, y - 1)
    else:
        if fixed2[y] != -1:
            ans += fixed2[y]
        else:
            ans += cand2
            for i in range(y + 1, n + 1):
                if fixed2[i] != -1:
                    break
                fixed2[i] = cand2
            cand1 = min(cand1, y - 1)

print(n * n - ans)

Solution (Python):
n,q=map(int,input().split())
query=[list(input().split()) for _ in range(q)]
from bisect import bisect_right as bl
ax=[-n]
vx=[n-2]
ay=[-n]
vy=[n-2]
ans=(n-2)**2
for t,i in query:
  i=int(i)
  if t=='1':
    idx=bl(ax,-i)
    if idx==len(ax):
      ax.append(-i)
      vx.append(vx[-1])
      vy[-1]=i-2
    ans-=vx[idx-1]
  else:
    idx=bl(ay,-i)
    if idx==len(ay):
      ay.append(-i)
      vy.append(vy[-1])
      vx[-1]=i-2
    ans-=vy[idx-1]
print(ans)

Solution (Python):
def main():
    examF()

def examA():
    S = SI()
    if S[-1]=="s":
        ans = S+"es"
    else:
        ans = S+"s"
    print(ans)
    return

def examB():
    N = I()
    D = [LI()for _ in range(N)]
    current = 0
    for d1,d2 in D:
        if d1==d2:
            current += 1
        else:
            current = 0
        if current==3:
            print("Yes")
            return
    print("No")
    return

def examC():
    N = I()
    cnt = 0
    for i in range(1,N):
        for j in range(1,1+N//i-(N%i==0)):
            cnt += 1
    ans = cnt
    print(ans)
    return

def examD():
    N, K = LI()
    LR = [LI()for _ in range(K)]
    dp = [0]*N
    S = [0]*N
    dp[0] = 1
    S[0] = 1
    for i in range(1,N):
        cur = 0
        for l,r in LR:
            if i<l:
                continue
            cur += S[i-l]
            if i<r+1:
                continue
            cur -= S[i-r-1]
            cur += mod2
            cur %= mod2

        dp[i] = cur
        S[i] = S[i-1] + cur
        S[i] %= mod2

    ans = dp[-1]
    print(ans)
    return

def examE():
    N, X, M = LI()
    cnt = 0
    L = []
    used = [-1]*(M+1)

    for i in range(N):
        used[X] = i
        L.append(X)
        cnt += X
        X = pow(X,2,M)
        if X==1 or X==0:
            cnt += (N-i-1)*X
            break
        if used[X]>=0:
            loop = i - used[X] + 1
            S = sum(L[used[X]:i+1])
            rest = N-i-1
            cnt += (rest//loop) * S + sum(L[used[X]:used[X]+rest%loop])
            break
    
    
    ans = cnt
    print(ans)
    return
def examF():
    
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            
            self.ide_ele = ele
            self.segfun = segfun
            
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2

        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret
    N, Q = LI()
    SH = SegmentTree(N,N-2,lambda a, b: min(a,b))
    SW = SegmentTree(N,N-2,lambda a, b: min(a,b))
    cnt = 0
    for q in range(Q):
        t, x = LI()
        if t==1:
            up_w_0 = SH.query(x - 2)
            cnt += up_w_0
            SW.update(0, up_w_0, x - 2)
            
        elif t==2:
            left_h_0 = SW.query(x-2)
            cnt += left_h_0
            SH.update(0,left_h_0,x-2)
            
        
    
    ans = (N-2)**2 - cnt
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
10 4 6 
"""

Solution (Python):
N, Q = map(int, input().split())
Query = [list(map(int, input().split())) for _ in range(Q)]
ans = 0

for T in range(1, 3):
    Depth = [N-2]*N
    left = N
    up = N-2
    for t, x in Query:
        if t == T:  
            if left < x:
                ans += Depth[x]
            else:
                for i in range(x, left):
                    Depth[i] = up
                left = x
                ans += up
        else:  
            up = min(up, x-2)
        
    

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    def f(self,i):
        return self.sum(i,i+1)
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

ly,lx=N-1,N-1
by,bx=RangeBIT(N),RangeBIT(N)
ans=0
for _ in range(Q):
    a,x=map(int1,input().split())
    if a==0:
        if x>lx:
            res=bx.f(x)
            ans+=res
        else:
            ans+=ly-1
            bx.add(x,lx,ly-1)
            lx=x
    else:
        if x>ly:
            res=by.f(x)
            ans+=res
        else:
            ans+=lx-1
            by.add(x,ly,lx-1)
            ly=x
print((N-2)**2-ans)

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

class Dualsegtree:
    def __init__(self, A, intv, initialize = True):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
    
    def segf(self, a, b):
        return min(a, b)
    
    def query(self, k):
        k += self.N0
        s = self.data[k]
        while k > 0:
            k >>= 1
            s = self.segf(s, self.data[k])
        return s
    
    def update(self, l, r, x):
        L, R = l+self.N0, r+self.N0
        while L < R:
            if R & 1:
                R -= 1
                self.data[R] = x
            if L & 1:
                self.data[L] = x
                L += 1
            L >>= 1
            R >>= 1

N, Q = map(int, readline().split())
INF = 10**9+7
H, W = Dualsegtree([N-1]*(N-1), INF, initialize = True), Dualsegtree([N-1]*(N-1), INF, initialize = True)

ans = 0


mw = N
mb = N

for _ in range(Q):
    t, x = map(int, readline().split())
    x -= 1
    if t == 1:
        st = H.query(x)
        ans += st-1
        if mw > x:
            mw = x
            W.update(0, st, x)
    else:
        st = W.query(x)
        ans += st-1
        if mb > x:
            mb = x
            H.update(0, st, x)
print((N-2)*(N-2)-ans)

Solution (Python):
n, Q = [int(i) for i in input().split(" ")]
deepx = [-1] * (n-2)
deepy = [-1] * (n-2)
queries = [[0, 0] for i in range(Q)]
for i in range(Q):
  queries[i] = [int(j) for j in input().split(" ")]

curx = n-2
cury = n-2
ans = 0

for q in queries:
  d = q[0]
  pos = q[1]-2
  if d == 1:
    if curx < pos:
      ans += deepx[pos]
    else:
      ans += cury
      for i in range(pos+1, curx):
        deepx[i] = cury
      curx = pos
  else:
    if cury < pos:
      ans += deepy[pos]
    else:
      ans += curx
      for i in range(pos+1, cury):
        deepy[i] = curx
      cury = pos
  
  
  
print((n-2)**2-ans)