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):

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

 

ide_ele = 10**9

 
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
 
    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1
 
    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele
 
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


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



ans = (N-2)**2
yoko = [N-2 for _ in range(N-2)]
tate = [N-2 for _ in range(N-2)] 
yoko = SegTree(yoko, segfunc, ide_ele)
tate = SegTree(tate, segfunc, ide_ele)
miny = N-2
minx = N-2
for k in range(Q):
	n, x = map(int, input().split())
	if n == 1:
		y = x -2
		if y < miny:
			ans -= minx
			miny = y
			yoko.update(min(minx, N-3), miny)
		else:
			ans -= tate.query(y, N-1)
	else:
		x = x - 2
		if x < minx:
			ans -= miny
			minx = x
			tate.update(min(miny, N-3), minx)
		else:
			ans -= yoko.query(x, N-1)
print(ans)

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

yoko=[0 for i in range(n+1)]
tate=[0 for i in range(n+1)]
yokobig=n
tatebig=n
ans=0

for _ in range(q):
    a,b=map(int,input().split())
    if a==1:
        if b<yokobig:
            ans+=tatebig-2
            
            for i in range(b,yokobig):
                yoko[i]=tatebig
            yokobig=b
        else:
            ans+=yoko[b]-2
    if a==2:
        if b<tatebig:
            ans+=yokobig-2
            
            for i in range(b,tatebig):
                tate[i]=yokobig
            tatebig=b
        else:
            ans+=tate[b]-2
    
    
print((n-2)**2-ans)

Solution (Python):
n, q = map(int, input().split())
l = [0]*n; u = [0]*n; lmin = n-2; umin = n-2; lgoal = n; ugoal = n
for _ in range(q):
    s, t = map(int, input().split())
    if s == 1:
        if t > ugoal: u[t-1] = 0
        else:
            for i in range(t, ugoal-1):u[i] = umin
            lmin = t-2; ugoal = t
    else:
        if t > lgoal: l[t-1] = 0
        else:
            for i in range(t, lgoal-1):l[i] = lmin
            umin = t-2; lgoal = t
print(sum(l)+sum(u)+lmin*umin)

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

n, q = map(int, input().split())
ans = (n-2) * (n-2)
v, h = [(n, n)], [(n, n)]
for _ in range(q):
	k, x = map(int, input().split())
	if k == 1:
		l, r = 0, len(h)
		while r-l > 1:
			m = (l + r) //2
			if h[m][0] >= x:
				l = m
			else:
				r = m
		ans -= h[l][1] - 2
		
		if x < v[-1][1]:
			v.append((h[l][1] - 1, x))

	else:
		l, r = 0, len(v)
		while r-l > 1:
			m = (l + r) //2
			if v[m][0] >= x:
				l = m
			else:
				r = m
		ans -= v[l][1] - 2
		
		if x < h[-1][1]:
			h.append((v[l][1] - 1, x))

print(ans)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

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

class lazySegTree(object):
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.data = [N - 1] * (2 * self.N0)
		self.lazy = [INF] * (2 * self.N0)

	
	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	
	def propagates(self, *ids):
		for i in reversed(ids):
			v = self.lazy[i - 1]
			if v == INF:
				continue
			self.lazy[2 * i - 1] = min(self.lazy[2 * i - 1], v)
			self.lazy[2 * i] = min(self.lazy[2 * i], v)
			self.data[2 * i - 1] = min(self.data[2 * i - 1], v)
			self.data[2 * i] = min(self.data[2 * i], v)
			self.lazy[i - 1] = INF

	def update(self, l, r, x):
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		while L < R:
			if R & 1:
				R -= 1
				self.lazy[R - 1] = min(self.lazy[R - 1], x)
				self.data[R - 1] = min(self.data[R - 1], x)
			if L & 1:
				self.lazy[L - 1] = min(self.lazy[L - 1], x)
				self.data[L - 1] = min(self.data[L - 1], x)
				L += 1
			L >>= 1; R >>= 1
		for i in ids:
			self.data[i - 1] = min(self.data[2 * i - 1], self.data[2 * i])

	
	def pointQuery(self, k):
		*ids, = self.gindex(k, k + 1)
		self.propagates(*ids)
		return self.data[k + self.N0 - 1]

	
	def debug(self):
		ids = [i for i in range(self.N0, 0, -1)]
		self.propagates(*ids)
		print(self.data[self.N0 - 1:])

def main():
	N, Q = getlist()
	lSeg_low = lazySegTree(N + 1)
	lSeg_col = lazySegTree(N + 1)
	ans = (N - 2) ** 2
	for i in range(Q):
		n, x = getlist()
		if n == 1:
			itr = lSeg_col.pointQuery(x)
			ans -= itr - 2
			lSeg_low.update(2, itr - 1, x)
		else:
			itr = lSeg_low.pointQuery(x)
			ans -= itr - 2
			lSeg_col.update(2, itr - 1, x)
		
		
		
	print(ans)
	


if __name__ == '__main__':
	main()

Solution (Python):
n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        if x < w:
            tmp = h
            for i in range(x, w+1):
                t1[i] = h
            w = x
        else:
            tmp = t1[x]
        ans -= tmp - 2
    else:
        if x < h:
            tmp = w
            for i in range(x, h+1):
                t2[i] = w
            h = x
        else:
            tmp = t2[x]
        ans -= tmp - 2
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N,Q = LI()

a = [N-1]*N  
b = [N-1]*N  

a[-1] = 0
b[-1] = 0

x1 = N-1  
x2 = N-1  

ans = (N-2)**2
for i in range(Q):
    j,k = LI()
    k -= 1
    if j == 1:
        if k > x2:
            ans -= (b[k]-1)
        else:
            for n in range(k+1,x2):
                b[n] = x1
            ans -= max(0,(x1-1))
            x2 = k
    else:
        if k > x1:
            ans -= (a[k]-1)
        else:
            for n in range(k+1,x1):
                a[n] = x2
            ans -= max(0,(x2-1))
            x1 = k

print(ans)

Solution (Python):


from collections import deque
from bisect import bisect_left

def main():
    N, Q = map( int, input().split())
    Query = [ tuple( map( int, input().split())) for _ in range(Q)]
    LX = 1
    X = deque([N])
    VX = deque([N])
    LY = 1
    Y = deque([N])
    VY = deque([N])
    mx = N
    my = N
    ans = 0
    
    for i, x in Query:
        if i == 1:
            if x < my:
                ans += mx-2
                
                
                X.appendleft(x)
                VX.appendleft(mx)
                my = x
            else:
                ans += VX[bisect_left(X,x)-1]-2
                
                
        else:
            if x < mx:
                ans += my-2
                Y.appendleft(x)
                VY.appendleft(my)

                
                
                mx = x
            else:
                ans += VY[bisect_left(Y,x)-1]-2
                
                

        
        
        
    
    
    
    print((N-2)**2-ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class BIT():
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N,Q = MI()

A,B = [0]*N,[0]*N
A[0],B[0] = N-2,N-2
A[N-1],B[N-1] = -(N-2),-(N-2)

I,J = BIT(A),BIT(B)
i_min,j_min = N,N
ans = (N-2)**2

for _ in range(Q):
    a,x = MI()
    if a == 1:
        ans -= I.query(x)
        if x < i_min:
            i_min = x
            y = J.tree[1]
            J.update(1,x-2-y)
            J.update(j_min,-(x-2-y))
    else:
        ans -= J.query(x)
        if x < j_min:
            j_min = x
            y = I.tree[1]
            I.update(1,x-2-y)
            I.update(i_min,-(x-2-y))

print(ans)

Solution (Python):


import sys
input=sys.stdin.readline

n,q=map(int,input().split())
left=n
up=n
ans=(n-2)*(n-2)
fixed_yoko=[0]*(n+1)
fixed_tate=[0]*(n+1)
post_process=[]
for _ in range(q):
    t,x=map(int,input().split())
    if t==1:
        if x>left:
            post_process.append((t,x))
        else:
            fixed_yoko[left]+=-up
            fixed_yoko[x+1]+=up
            ans-=up-2
            left=x
    elif t==2:
        if x>up:
            post_process.append((t,x))
        else:
            fixed_tate[up]+=-left
            fixed_tate[x+1]+=left
            ans-=left-2
            up=x
for i in range(1,n+1):
    fixed_yoko[i]+=fixed_yoko[i-1]
    fixed_tate[i]+=fixed_tate[i-1]
for t,x in post_process:
    if t==1:
        ans-=fixed_yoko[x]-2
    elif t==2:
        ans-=fixed_tate[x]-2
print(ans)

Solution (Python):
import sys

def solve():
      input = sys.stdin.readline
      N, Q = map(int, input().split())
      total = (N - 2) ** 2
      rb = N
      db = N
      D = [N] * (N + 1)
      R = [N] * (N + 1)
      for _ in range(Q):
            a, b = map(int, input().split())
            if a == 1: 
                  if b < db:
                        total -= (rb - 2)
                        for i in range(b, db): R[i] = rb
                        db = b
                  else:
                        total -= (R[b] - 2)
            else: 
                  if b < rb:
                        total -= (db - 2)
                        for i in range(b, rb): D[i] = db
                        rb = b
                  else:
                        total -= (D[b] - 2)

      print(total)

      return 0

if __name__ == "__main__":
      solve()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class BIT():
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N,Q = MI()

A,B = [0]*N,[0]*N
A[0],B[0] = N-2,N-2
A[N-1],B[N-1] = -(N-2),-(N-2)

I,J = BIT(A),BIT(B)
i_min,j_min = N,N
ans = (N-2)**2

for _ in range(Q):
    a,x = MI()
    if a == 1:
        ans -= I.query(x)
        if x < i_min:
            i_min = x
            y = J.tree[1]
            J.update(1,x-2-y)
            J.update(j_min,-(x-2-y))
    else:
        ans -= J.query(x)
        if x < j_min:
            j_min = x
            y = I.tree[1]
            I.update(1,x-2-y)
            I.update(i_min,-(x-2-y))

print(ans)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)












class Segtree:
    

    

    
    
    

    

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res





n,q = inm()
b = (n-2)**2
minx = x = n-1
miny = y = n-1
sx = Segtree(n,n-1,lambda x,y: min(x,y))
sy = Segtree(n,n-1,lambda x,y: min(x,y))
z = [n-1]*n
sx.setary(z)
sy.setary(z)


for i in range(q):
    t,k = inm()
    k -= 1
    if t==1:
        b -= sy.query(k,n)-1
        if k<minx:
            sx.set(miny,k)
            minx = k
    else:
        b -= sx.query(k,n)-1
        if k<miny:
            sy.set(minx,k)
            miny = k
    
    
    
print(b)

Solution (Python):
f=lambda:map(int,input().split())
N,Q=f()
a,b=N,N
black=(N-2)*(N-2)
B=[-1]*(N+1)
W=[-1]*(N+1)
for _ in range(Q):
    q,x=f()
    if q==1:
        if B[x]>0:
            black-=B[x]
            B[x]=0
        else:
            black-=b-2
            a=x
            for j in range(a+1,N+1):
                if B[j]==-1:
                    B[j]=b-2
                else:
                    break
                if j==N-1:
                    break
    else:
        if W[x]>0:
            black-=W[x]
            W[x]=0
        else:
            black-=a-2
            b=x
            for j in range(b+1,N+1):
                if W[j]==-1:
                    W[j]=a-2
                else:
                    break
                if j==N-1:
                    break
print(black)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, q = LI()
ans = (n-2) * (n-2)
min_x_list = [-n]
min_x_idx = [0]
min_y_list = [-n]
min_y_idx = [0]
idx = 1
for _ in range(q):
    a, b = LI()
    min_x = -min_x_list[-1]
    min_y = -min_y_list[-1]
    if a == 1:
        if min_x > b:
            min_x_list.append(-b)
            min_x_idx.append(idx)
            idx += 1
            ans -= min_y - 2
        else:
            r = br(min_x_list, -b)
            i = min_x_idx[r]
            r = br(min_y_idx, i)
            ans -= -min_y_list[r-1] - 2

    elif a == 2:
        if min_y > b:
            min_y_list.append(-b)
            min_y_idx.append(idx)
            idx += 1
            ans -= min_x - 2
        else:
            r = br(min_y_list, -b)
            i = min_y_idx[r]
            r = br(min_x_idx, i)
            ans -= -min_x_list[r-1] - 2
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] = self._func(self._lazy[2 * idx], q)
        self._lazy[2 * idx + 1] = self._func(self._lazy[2 * idx + 1], q)
        self.data[2 * idx] = self._func(self.data[2 * idx], q)
        self.data[2 * idx + 1] = self._func(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] = self._func(
                self._func(self.data[2 * idx], self.data[2 * idx + 1]), self._lazy[idx]
            )
            idx >>= 1

    def update(self, start, stop, value):
        """lazily update [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] = self._func(self._lazy[start], value)
                self.data[start] = self._func(self.data[start], value)
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] = self._func(self._lazy[stop], value)
                self.data[stop] = self._func(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, 0, max)
    cols = LazySegmentTree([0] * N, 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
            assert total >= 0
            cols.update(c, c + 1, N)
            rows.update(0, removed, N - c)
        elif t == 2:
            r = x
            removed = N - rows.query(r, r + 1)
            assert removed >= 0
            total -= removed
            assert total >= 0
            rows.update(r, r + 1, N)
            cols.update(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):
from collections import deque
from bisect import bisect_left, bisect_right

n, q = map(int, input().split())
list_x = deque()
list_y = deque()
memo_x = deque()
memo_y = deque()
x_now, y_now = n-1, n-1

ans = (n-2) ** 2


for i in range(q):
    flg, x = map(int, input().split())
    if flg == 1:
        if x_now >= x:
            ans -= y_now - 1
            x_now = x - 1
            list_x.appendleft(x)
            memo_x.appendleft(y_now - 1)
        else:
            tmp = bisect_left(list_x, x) - 1
            ans -= memo_x[tmp]
    
    else:
        y = x
        if y_now >= y:
            ans -= x_now - 1
            y_now = y - 1
            list_y.appendleft(y)
            memo_y.appendleft(x_now - 1)
        else:
            tmp = bisect_left(list_y, y) - 1
            ans -= memo_y[tmp]

print(ans)

Solution (Python):
import sys
from operator import ge

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class SegTree:
    """
    セグメント木
    1.update: i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        
        if A:
            
            for i in range(n):
                self.tree[n2+i] = A[i]
            
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def add(self, i, x):
        self.update(i, self.get(i) + x)

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

    def bisearch_fore(self, l, r, x, func):
        """ 区間[l,r]で左から最初にxに対して比較の条件を満たすような値が出現する位置 """

        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if func(self.query(l, mid+1), x):
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N, Q = MAP()
ans = (N-2) * (N-2)
seg1 = SegTree(N+1, max, -INF, [0]*(N+1))
seg2 = SegTree(N+1, max, -INF, [0]*(N+1))
seg1.update(N, N)
seg2.update(N, N)
for _ in range(Q):
    t, x = MAP()
    if t == 1:
        res = seg1.bisearch_fore(0, N, x, ge)
        ans -= res - 2
        seg2.update(x, res)
    else:
        res = seg2.bisearch_fore(0, N, x, ge)
        ans -= res - 2
        seg1.update(x, res)
print(ans)

Solution (Python):

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



ide_ele = float('inf')


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


N, Q = map(int, input().split())
black = (N - 2) * (N - 2)
tate = [N - 1] * (N)
yoko = [N - 1] * (N)
seg_t = SegTree(tate, segfunc, ide_ele)
seg_y = SegTree(yoko, segfunc, ide_ele)

for i in range(Q):
  x, y = map(int, input().split())
  if x == 1:
    xx = seg_t.query(y - 1, N)
    if seg_y.query(xx - 1, xx) > y - 1:
      seg_y.update(xx - 1, y - 1)
    black -= xx - 1
  else:
    xx = seg_y.query(y - 1, N)
    if seg_t.query(xx - 1, xx) > y - 1:  
      seg_t.update(xx - 1, y - 1)
    black -= xx - 1
  
  
  
print(black)

Solution (Python):
n, q = map(int, input().split())
c = [(n - 1, -1)]
r = [(n - 1, -1)]
t = 0
for i in range(q):
    k, x = map(int, input().split())
    if k == 1:
        c.append((x - 1, t))
    else:
        r.append((x - 1, t))
        t += 1
c.sort()
r.sort()
idx = 0
ans = (len(c) - 1) * (r[0][0])
for i in range(len(r) - 1):
    x, t = r[i]
    tmp = idx
    while idx < len(c) and c[idx][1] > t:
        idx += 1
    ans += c[idx][0]
    ans += (len(c) - idx - 1) * (r[i + 1][0] - x)
print((n - 2) * (n - 2) - ans + len(c) + len(r) - 2)

Solution (Python):
from bisect import bisect_right

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

v_lay = [(-(n-1),n-2)]
h_lay = [(-(n-1),n-2)]

ans = (n-2)*(n-2)
for _ in range(q):
    case,lay_pos = map(int,input().split())
    
    ref_lay = (v_lay if case==1 else h_lay)
    
    index = bisect_right(ref_lay, (-lay_pos,n))
    _, lay = ref_lay[index-1]
    
    ans -= lay

    if index==len(ref_lay):
        ref_lay = (h_lay if case==1 else v_lay)
        laid_pos, num = ref_lay[-1]
        if laid_pos == -(lay+1):
            ref_lay[-1] = (-(lay+1), min(lay_pos-2,num))
        else:
            ref_lay.append((-(lay+1), lay_pos-2))
            
print(ans)

Solution (Python):
n,q = map(int,input().split())
yoko = [-n]
yoko2 = [-n]
yokol = 1
tate = [-n]
tate2 = [-n]
tatel = 1
last = [n,n]
import bisect
ans = (n-2)**2

for _ in range(q):
  a,c = map(int,input().split())
  if a == 1:
    b = bisect.bisect_left(yoko,-c)
    if b == yokol:
      yoko.append(-c)
      yoko2.append(-last[0])
      yokol += 1
      last[1] = c
      ans -= last[0]-2
    else:
      ans -= -yoko2[b] - 2
  if a == 2:
    b = bisect.bisect_left(tate,-c)
    if b == tatel:
      tate.append(-c)
      tate2.append(-last[1])
      tatel += 1
      last[0] = c
      ans -= last[1]-2
    else:
      ans -= -tate2[b] - 2
  
  
  
  
print(ans)