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 sys



from copy import *
from bisect import *	

from math import gcd,ceil,sqrt
from itertools import permutations as prm,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 

if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<m and a[i][j]!="."
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)

t=1

def updatepoint(point,val,bit):

	while point<=4*n:
		bit[point]+=val
		point+=(point&-point)
def query(point,bit):
	ans=0
	while point>0:
		ans+=bit[point]
		point-=(point&-point)
	return ans	

def update(l,r,val,bit):

	updatepoint(l,val,bit)
	updatepoint(r+1,-val,bit)


while t>0:
	t-=1
	n,q=mi()
	ans=(n-2)**2
	bitc=[0]*(4*n)
	bitr=[0]*(4*n)
	r={}
	c={}
	for i in range(q):
		x,y=mi()
		if x==1 and y not in c:
			c[y]=1
			p=query(y,bitc)
			ans-=(n-1+p)-1
			if n-1+bitr[2]>=y:
				update(2,n-1+bitc[2],y-1-(n-1+bitr[2]),bitr)
		elif x==2 and y not in r:
			r[y]=1
			p=query(y,bitr)
			ans-=(n-1+p)-1
			if n-1+bitc[2]>=y:
				update(2,n-1+bitr[2],y-1-(n-1+bitc[2]),bitc)

	print(ans)

Solution (Python):


def input_int_array():
    return map(int, input().split())


class Board:
    def __init__(self, w, h, parent):
        self.w = w
        self.h = h
        self.parent = parent


def answer(n, q):
    min_board = Board(n-2, n-2, None)
    black = (n - 2) * (n - 2)
    for i in range(q):
        a, pos = input_int_array()
        pos -= 1
        board = min_board
        use_min = True
        if a == 1:
            while pos > board.w:
                board = board.parent
                use_min = False
            black -= board.h
            if use_min:
                b = Board(pos - 1, board.h, board)
                min_board = b
        else:
            while pos > board.h:
                board = board.parent
                use_min = False
            black -= board.w
            if use_min:
                b = Board(board.w, pos - 1, board)
                min_board = b
    print(black)


n, q = input_int_array()
answer(n, q)

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    Q = [tuple(read_index()) for _ in range(M)]
    S = [N - 1] * N
    T = [N - 1] * N
    W, H = N - 1, N - 1
    res = (N - 2) ** 2
    for d, x in Q:
        if d == 0:
            if x < W:
                for i in range(x, W):
                    S[i] = H
                W = x
            res -= S[x] - 1
        if d == 1:
            if x < H:
                for i in range(x, H):
                    T[i] = W
                H = x
            res -= T[x] - 1
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):

n,q=map(int,input().split())
*qu,=[tuple(map(int, input().split())) for _ in range(q)]
w=n-2;h=n-2
wwh=[n-2]*(n-2)
hhw=[n-2]*(n-2)
b=0
for t,x in qu:
    x-=2
    if t==1:
        
        if x<w:
            b+=h
            for i in range(x,w):
                wwh[i]=h
            w=x
        else:
            b+=wwh[x]

    else:
        if x<h:
            b+=w
            for i in range(x,h):
                hhw[i]=w
            h=x
        else:
            b+=hhw[x]

ans=(n-2)*(n-2)-b
print(ans)

Solution (Python):
from collections import deque
def bisect(arr,x):
    l,r=-1,len(arr)
    while(r-l>1):
        mid=(l+r)//2
        if x>arr[mid][0]:
            l=mid
        else:
            r=mid
    return arr[l]

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

h=deque([(N-1,N-1)])
w=deque([(N-1,N-1)])
Black=(N-2)**2
for i in range(Q):
    t,x=map(int,input().split())
    x-=1
    if t==1:
        if x<h[0][0]:
            h.appendleft((x,w[0][0]))
            Black-=(w[0][0]-1)
        else:
            b=bisect(h,x)
            Black-=(b[1]-1)
    else:
        if x<w[0][0]:
            w.appendleft((x,h[0][0]))
            Black-=(h[0][0]-1)
        else:
            b=bisect(w,x)
            Black-=(b[1]-1)
print(Black)

Solution (Python):
import sys
import numpy as np


def main():
    N, Q = map(int, sys.stdin.readline().rstrip().split())

    H = np.array([0] * (N - 1))
    W = np.array([0] * (N - 1))

    black = (N - 2)**2  

    Hmin = N - 1
    Wmin = N - 1

    for i in range(Q):
        n, x = map(int, sys.stdin.readline().rstrip().split())
        if n == 1:  
            if x - 1 <= Wmin:
                W[x - 1:Wmin] = Hmin - 1
                Wmin = x - 1
            
            black -= W[x - 1]
        else:
            if x - 1 <= Hmin:
                H[x - 1:Hmin] = Wmin - 1
                Hmin = x - 1
            
            black -= H[x - 1]

    print(black)


main()

Solution (Python):
def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                rows[x:min_col] = [min_row] * (min_col - x)
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                cols[x:min_row] = [min_col] * (min_row - x)
                min_row = x
            black -= cols[x] - 1

    print(black)

main()

Solution (Python):
def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                for j in range(x, min_col):
                    rows[j] = min_row
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                for j in range(x, min_row):
                    cols[j] = min_col
                min_row = x
            black -= cols[x] - 1

    print(black)

main()

Solution (Python):
class LazyPropSegmentTree:
    def __init__(self, a):
        self.padding = float('inf')        
        self.n = len(a)
        self.N = 1 << (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        self.lazy = [self.padding] * (2*self.N - 1)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)>>1] = min(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def indices_generator(self, i, j):
        
        
        idx1 = self.N + i
        idx2 = self.N + j
        lm = (idx1 // (idx1 & -idx1)) >> 1
        rm = (idx2 // (idx2 & -idx2)) >> 1
        while 0 < idx1 < idx2:
            if idx2 <= rm:
                yield idx2-1
            if idx1 <= lm:
                yield idx1-1
            idx1 >>= 1
            idx2 >>= 1
        while idx1:
            yield idx1-1
            idx1 >>= 1
    
    def propagate_down(self, indices):
        
        
        for idx in indices:
            v = self.lazy[idx]
            if v < self.padding:
                idx1, idx2 = 2*idx + 1, 2*idx + 2
                self.lazy[idx1] = min(self.lazy[idx1], v)
                self.lazy[idx2] = min(self.lazy[idx2], v)                
                self.seg_data[idx1] = min(self.seg_data[idx1], v)
                self.seg_data[idx2] = min(self.seg_data[idx2], v)
                self.lazy[idx] = self.padding
    
    def propagate_up(self, indices):
        for idx in indices:
            idx1, idx2 = 2*idx + 1, 2*idx + 2
            self.seg_data[idx] = min(self.seg_data[idx1], self.seg_data[idx2])
    
    def propagate_all(self):
        indices = [i for i in range(self.N-1)]
        self.propagate_down(indices)
        self.propagate_up(indices[::-1])
    
    def update(self, i, j, x):
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        while idx1 < idx2 + 1:
            if idx1&1 == 0: 
                self.seg_data[idx1] = min(x, self.seg_data[idx1])
                self.lazy[idx1] = min(x, self.lazy[idx1])
            if idx2&1 == 1: 
                self.seg_data[idx2] = min(x, self.seg_data[idx2])
                self.lazy[idx2] = min(x, self.lazy[idx2])
            idx1 >>= 1
            idx2 >>= 1
            idx2 -= 1
        self.propagate_up(should_prop)
    
    def query(self, i, j):
        
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        result = self.padding
        while idx1 < idx2 + 1:
                if idx1&1 == 0: 
                    result = min(result, self.seg_data[idx1])
                if idx2&1 == 1: 
                    result = min(result, self.seg_data[idx2])                
                idx1 >>= 1
                idx2 >>= 1
                idx2 -= 1
        return result
    

N, Q = map(int, input().split())
query = [tuple(map(int, input().split())) for i in range(Q)]
row = LazyPropSegmentTree([N]*(N+1))
column = LazyPropSegmentTree([N]*(N+1))

ans = (N-2) ** 2
for t, x in query:
    if t == 1:
        n = row.query(x, x+1)
        
        ans -= n - 2
        column.update(2, n+1, x)
    else:
        n = column.query(x, x+1)
        
        ans -= n - 2
        row.update(2, n+1, x)

print(ans)

Solution (Python):
class LazyPropSegmentTree:
    def __init__(self, a):
        self.padding = float('inf')        
        self.n = len(a)
        self.N = 1 << (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        self.lazy = [None] * (2*self.N - 1)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)>>1] = min(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def indices_generator(self, i, j):
        
        
        idx1 = self.N + i
        idx2 = self.N + j
        lm = (idx1 // (idx1 & -idx1)) >> 1
        rm = (idx2 // (idx2 & -idx2)) >> 1
        while 0 < idx1 < idx2:
            if idx2 <= rm:
                yield idx2-1
            if idx1 <= lm:
                yield idx1-1
            idx1 >>= 1
            idx2 >>= 1
        while idx1:
            yield idx1-1
            idx1 >>= 1
    
    def propagate_down(self, indices):
        
        
        for idx in indices:
            v = self.lazy[idx]
            if v is not None:
                idx1, idx2 = 2*idx + 1, 2*idx + 2
                if self.lazy[idx1] is None:
                    self.lazy[idx1] = v
                else:
                    self.lazy[idx1] = min(self.lazy[idx1], v)
                
                if self.lazy[idx2] is None:
                    self.lazy[idx2] = v
                else:
                    self.lazy[idx2] = min(self.lazy[idx2], v)
                
                self.seg_data[idx1] = min(self.seg_data[idx1], v)
                self.seg_data[idx2] = min(self.seg_data[idx2], v)
                self.lazy[idx] = None
    
    def propagate_up(self, indices):
        for idx in indices:
            idx1, idx2 = 2*idx + 1, 2*idx + 2
            self.seg_data[idx] = min(self.seg_data[idx1], self.seg_data[idx2])
    
    def propagate_all(self):
        indices = [i for i in range(self.N-1)]
        self.propagate_down(indices)
        self.propagate_up(indices[::-1])
    
    def update(self, i, j, x):
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        while idx1 < idx2 + 1:
            if idx1&1 == 0: 
                self.seg_data[idx1] = min(x, self.seg_data[idx1])
                if self.lazy[idx1] is None:
                    self.lazy[idx1] = x
                else:
                    self.lazy[idx1] = min(x, self.lazy[idx1])
            if idx2&1 == 1: 
                self.seg_data[idx2] = min(x, self.seg_data[idx2])
                if self.lazy[idx2] is None:
                    self.lazy[idx2] = x
                else:
                    self.lazy[idx2] = min(x, self.lazy[idx2])
            idx1 >>= 1
            idx2 >>= 1
            idx2 -= 1
        self.propagate_up(should_prop)
    
    def query(self, i, j):
        
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        result = self.padding
        while idx1 < idx2 + 1:
                if idx1&1 == 0: 
                    result = min(result, self.seg_data[idx1])
                if idx2&1 == 1: 
                    result = min(result, self.seg_data[idx2])                
                idx1 >>= 1
                idx2 >>= 1
                idx2 -= 1
        return result
    

N, Q = map(int, input().split())
query = [tuple(map(int, input().split())) for i in range(Q)]
row = LazyPropSegmentTree([N]*(N+1))
column = LazyPropSegmentTree([N]*(N+1))

ans = (N-2) ** 2
for t, x in query:
    if t == 1:
        n = row.query(x, x+1)
        
        ans -= n - 2
        column.update(2, n+1, x)
    else:
        n = column.query(x, x+1)
        
        ans -= n - 2
        row.update(2, n+1, x)

print(ans)

Solution (Python):
import sys


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = self.__dot(node[i], c)
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

flagH = [N - 1] * N
flagW = [N - 1] * N

stH = SegmentTree([N - 1] * N, min, N - 1)
stW = SegmentTree([N - 1] * N, min, N - 1)

cnt = 0
for t, x in query:
    if t == 1:
        stX, stY = stW, stH
    else:
        stX, stY = stH, stW

    cnt += max(0, stX.get(x - 1, N) - 1)
    
    stY.update(stX.get(x - 1, N), x - 1)

print(pow(N - 2, 2) - cnt)

Solution (Python):
import sys


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = self.__dot(node[i], c)
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

flagH = [N - 1] * N
flagW = [N - 1] * N

stH = SegmentTree([N - 1] * N, min, N - 1)
stW = SegmentTree([N - 1] * N, min, N - 1)

cnt = 0
for t, x in query:
    if t == 1:
        flagX, flagY = flagW, flagH
        stX, stY = stW, stH
    else:
        flagX, flagY = flagH, flagW
        stX, stY = stH, stW

    cnt += max(0, min(stX.get(x - 1, N), flagX[x - 1]) - 1)
    
    stY.update(stX.get(x - 1, N), x - 1)

print(pow(N - 2, 2) - cnt)

Solution (Python):
import sys


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = self.__dot(node[i], c)
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

flagH = [N - 1] * N
flagW = [N - 1] * N

stH = SegmentTree([N - 1] * N, min, N - 1)
stW = SegmentTree([N - 1] * N, min, N - 1)

cnt = 0
for t, x in query:
    if t == 1:
        flagX, flagY = flagW, flagH
        stX, stY = stW, stH
    else:
        flagX, flagY = flagH, flagW
        stX, stY = stH, stW

    cnt += max(0, min(stX.get(x - 1, N), flagX[x - 1]) - 1)
    flagX[x - 1] = 0
    stY.update(stX.get(x - 1, N), x - 1)

print(pow(N - 2, 2) - cnt)

Solution (Python):
import sys


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = self.__dot(node[i], c)
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]





flagH = [N - 1] * N
flagW = [N - 1] * N

stH = SegmentTree([N - 1] * N, min, N - 1)
stW = SegmentTree([N - 1] * N, min, N - 1)

cnt = 0
for t, x in query:
    if t == 1:
        
        
        cnt += max(0, min(stW.get(x - 1, N), flagW[x - 1]) - 1)
        
        
        
        
        flagW[x - 1] = 0
        stH.update(stW.get(x - 1, N), x - 1)

    else:
        
        
        cnt += max(0, min(stH.get(x - 1, N), flagH[x - 1]) - 1)
        
        
        
        
        flagH[x - 1] = 0
        stW.update(stH.get(x - 1, N), x - 1)

print(pow(N - 2, 2) - cnt)

Solution (Python):
N, Q = map(int, input().split())
rcx = [tuple(map(int, input().split())) for _ in range(Q)]

thres_1, thres_2 = N-2, N-2
nearest_white_1 = [0] * (N-2)
nearest_white_2 = [0] * (N-2)

reverse_count = 0
for rc, x in rcx:
    x = x-2
    if rc == 1:
        if x < thres_1:
            for i in range(x+1, thres_1):
                nearest_white_1[i] = thres_2
            thres_1 = x
            reverse_count += thres_2
        else:
            reverse_count += nearest_white_1[x]
    else:
        if x < thres_2:
            for i in range(x+1, thres_2):
                nearest_white_2[i] = thres_1
            reverse_count += thres_1
            thres_2 = x
        else:
            reverse_count += nearest_white_2[x]

    
    
    
    

print((N-2)**2 - reverse_count)

Solution (Python):
import sys

input = sys.stdin.readline
n, q = map(int, input().split())

nm2 = n - 2
ans = (nm2) ** 2
a = [-1] * (nm2)
b = [-1] * (nm2)
waku_h = nm2
waku_w = nm2

for _ in range(q):
    t, x = map(int, input().split())
    x -= 2
    if t == 1:
        if x < waku_w:
            ans -= waku_h
            for i in range(x + 1, waku_w):
                b[i] = waku_h
            waku_w = x
        else:
            ans -= b[x]
    else:
        if x < waku_h:
            ans -= waku_w
            for i in range(x + 1, waku_h):
                a[i] = waku_w
            waku_h = x
        else:
            ans -= a[x]

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
verti = [N-2]*(N-1)
horiz = [N-2]*(N-1)

left, top = N-2, N-2
ans = (N-2)**2
last_top = (N-2, N-2)
last_left = (N-2, N-2)
for _ in range(Q):
    c, x = mapint()
    x -= 1
    if c==1:
        if x<=left:
            ans -= top
            left = x-1
            for i in range(left, last_left[0]+1):
                horiz[i] = last_top[1]
            last_left = (left, x-1)
        else:
            ans -= horiz[x-1]
    if c==2:
        if x<=top:
            ans -= left
            top = x-1
            for i in range(top, last_top[0]+1):
                verti[i] = last_left[1]
            last_top = (top, x-1)
        else:
            ans -= verti[x-1]
print(ans)

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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


@njit
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return min(x, y)


@njit
def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit
def fold(seg, l, r):
    vl = vr = None
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)


@njit((i8, i8[:]), cache=True)
def main(N, TX):
    dp1 = np.full(N, N - 2, np.int64)
    dp2 = np.full(N, N - 2, np.int64)
    seg1 = np.full(N + N, N - 2, np.int64)
    seg2 = np.full(N + N, N - 2, np.int64)
    filled1 = np.zeros(N, np.int64)
    filled2 = np.zeros(N, np.int64)

    ans = 0
    for i in range(0, len(TX), 2):
        t, x = TX[i:i + 2]
        x -= 2
        if t == 1 and filled1[x]:
            continue
        if t == 2 and filled2[x]:
            continue
        if t == 1:
            n = fold(seg2, x, N)
            ans += n
            if n:
                dp1[n - 1] = min(dp1[n - 1], x)
                set_val(seg1, n - 1, dp1[n - 1])
        elif t == 2:
            n = fold(seg1, x, N)
            ans += n
            if n:
                dp2[n - 1] = min(dp2[n - 1], x)
                set_val(seg2, n - 1, dp2[n - 1])
    return (N - 2) * (N - 2) - ans


N, Q = map(int, readline().split())
TX = np.array(read().split(), np.int64)

print(main(N, TX))

Solution (Python):

class SegmentTree:
  def __init__(self,N):
    self.N0 = 2**(N-1).bit_length()
    self.data = [None]*(2*self.N0)
    self.INF = (-1, 2**31-1)
  
  
  def update(self, l, r, v):
    L = l + self.N0; R = r + self.N0
    while L < R:
      if R & 1:
        R -= 1
        self.data[R-1] = v
      if L & 1:
        self.data[L-1] = v
        L += 1
      L >>= 1; R >>= 1
  
  def _query(self, k):
    k += self.N0-1
    s = self.INF
    while k >= 0:
      if self.data[k]:
        s = max(s, self.data[k])
      k = (k - 1) // 2
    return s
  
  def query(self,k):
    return self._query(k)[1]

N, Q = map(int, input().split())
row = SegmentTree(N-2)
col = SegmentTree(N-2)
ans = (N-2)*(N-2)
row.update(0,N-2,(0,N-2))
col.update(0,N-2,(0,N-2))
min_row = N
min_col = N
for i in range(1,Q+1):
  t,x = map(int, input().split())
  if t==1:
    num = col.query(x-2)
    ans -= num
    if x<min_col:
      row.update(0,num,(i,x-2))
      min_col = x
  else:
    num = row.query(x-2)
    ans -= num
    if x<min_row:
      col.update(0,num,(i,x-2))
      min_row = x
print(ans)

Solution (Python):
import numpy as np


i8 = np.int64



def solve(n, qr):
    col = np.zeros(n - 1, i8)
    col[0] = 0
    col_min = n - 1
    row = np.zeros(n - 1, i8)
    row[0] = 0
    row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            if j < col_min:
                white += row_min - 1
                for m in range(j + 1, col_min):
                    col[m] = row_min - 1
                col_min = j
            else:
                white += col[j]
        else:
            if j < row_min:
                white += col_min - 1
                for m in range(j + 1, row_min):
                    row[m] = col_min - 1
                row_min = j
            else:
                white += row[j]
    return white


def main():
    f = open(0)
    n, q = [int(x) for x in f.readline().split()]
    qr = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2))
    white = solve(n, qr)
    print((n - 2) ** 2 - white)

main()

Solution (Python):
import numpy as np
from numba import njit
from numba.types import int64
i8 = np.int64


@njit((int64, int64[:,::-1]), cache=True)
def solve(n, qr):
    col = np.zeros(n - 1, i8)
    col[0] = 0
    col_min = n - 1
    row = np.zeros(n - 1, i8)
    row[0] = 0
    row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            if j < col_min:
                white += row_min - 1
                for m in range(j + 1, col_min):
                    col[m] = row_min - 1
                col_min = j
            else:
                white += col[j]
        else:
            if j < row_min:
                white += col_min - 1
                for m in range(j + 1, row_min):
                    row[m] = col_min - 1
                row_min = j
            else:
                white += row[j]
    return white


def main():
    f = open(0)
    n, q = [int(x) for x in f.readline().split()]
    qr = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2))
    white = solve(n, qr)
    print((n - 2) ** 2 - white)

main()