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

Solution (Python):
class LazySegmentTree:
    def __init__(self, op_X, e_X, mapping, compose, id_M, N, array=None):
        __slots__ = ["op_X","e_X","mapping","compose","id_M","N","log","N0","data","lazy"]
        
        self.e_X = e_X; self.op_X = op_X; self.mapping = mapping; self.compose = compose; self.id_M = id_M
        self.N = N
        self.log = (N-1).bit_length()
        self.N0 = 1<<self.log
        self.data = [e_X]*(2*self.N0)
        self.lazy = [id_M]*self.N0
        if array is not None:
            assert N == len(array)
            self.data[self.N0:self.N0+self.N] = array
            for i in range(self.N0-1,0,-1): self.update(i)

    
    def point_set(self, p, x):
        p += self.N0
        for i in range(self.log, 0,-1):
            self.push(p>>i)
        self.data[p] = x
        for i in range(1, self.log + 1):
            self.update(p>>i)
 
    
    def point_get(self, p):
        p += self.N0
        for i in range(self.log, 0, -1):
            self.push(p>>i)
        return self.data[p]
 
    
    def prod(self, l, r):
        if l == r: return self.e_X
        l += self.N0
        r += self.N0
        for i in range(self.log, 0, -1):
            if (l>>i)<<i != l:
                self.push(l>>i)
            if (r>>i)<<i != r:
                self.push(r>>i)

        sml = smr = self.e_X
        while l < r:
            if l & 1: 
                sml = self.op_X(sml, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op_X(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.op_X(sml, smr)
 
    
    def all_prod(s): return self.data[1]
 
    
    def apply(self, p, f):
        p += self.N0
        for i in range(self.log, 0, -1):
            self.push(p>>i)
        self.data[p] = self.mapping(f, self.data[p])
        for i in range(1, self.log + 1):
            self.update(p>>i)
 
    
    def apply(self, l, r, f):
        if l == r: return
        l += self.N0
        r += self.N0
        for i in range(self.log, 0, -1):
            if (l>>i)<<i != l:
                self.push(l>>i)
            if (r>>i)<<i != r:
                self.push((r-1)>>i)

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

        l, r = l2, r2
        for i in range(1, self.log + 1):
            if (l>>i)<<i != l:
                self.update(l>>i)
            if (r>>i)<<i != r:
                self.update((r-1)>>i)
     
    """
    始点 l を固定
    f(x_l*...*x_{r-1}) が True になる最大の r 
    つまり TTTTFFFF となるとき、F となる最小の添え字
    存在しない場合 n が返る
    f(e_M) = True でないと壊れる
    """
    def max_right(self, l, g):
        if l == self.N: return self.N
        l += self.N0
        for i in range(self.log, 0, -1): self.push(l>>i)
        sm = self.e_X
        while True:
            while l&1 == 0:
                l >>= 1
            if not g(self.op_X(sm, self.data[l])):
                while l < self.N0:
                    self.push(l)
                    l *= 2
                    if g(self.op_X(sm, self.data[l])):
                        sm = self.op_X(sm, self.data[l])
                        l += 1
                return l - self.N0
            sm = self.op_X(sm, self.data[l])
            l += 1
            if l&-l == l: break
        return self.N
 
    """
    終点 r を固定
    f(x_l*...*x_{r-1}) が True になる最小の l
    つまり FFFFTTTT となるとき、T となる最小の添え字
    存在しない場合 r が返る
    f(e_M) = True でないと壊れる
    """
    def min_left(self, r, g):
        if r == 0: return 0
        r += self.N0
        for i in range(self.log, 0, -1): self.push((r-1)>>i)
        sm = self.e_X
        while True:
            r -= 1
            while r>1 and r&1:
                r >>= 1
            if not g(self.op_X(self.data[r], sm)):
                while r < self.N0:
                    self.push(r)
                    r = 2*r + 1
                    if g(self.op_X(self.data[r], sm)):
                        sm = self.op_X(self.data[r], sm)
                        r -= 1
                return r + 1 - self.N0
            sm = self.op_X(self.data[r], sm)
            if r&-r == r: break
        return 0
        
    
    def update(self, k):
        self.data[k] = self.op_X(self.data[2*k], self.data[2*k+1])
    
    def all_apply(self, k, f):
        self.data[k] = self.mapping(f, self.data[k])
        if k < self.N0:
            self.lazy[k] = self.compose(f, self.lazy[k])

    def push(self, k): 
        if self.lazy[k] is self.id_M: return
        self.data[2*k  ] = self.mapping(self.lazy[k], self.data[2*k])
        self.data[2*k+1] = self.mapping(self.lazy[k], self.data[2*k+1])
        if 2*k < self.N0:
            self.lazy[2*k]   = self.compose(self.lazy[k], self.lazy[2*k])
            self.lazy[2*k+1] = self.compose(self.lazy[k], self.lazy[2*k+1])
        self.lazy[k] = self.id_M





e_X = 0
id_M = 1<<32
def op_X(X,Y):
    return ((((X+Y)>>32)%MOD)<<32) + ((X+Y)&MASK)
def compose(D,C):
    a = C>>32; b = C&MASK
    c = D>>32; d = D&MASK
    return (a*c%MOD<<32) + (c*b + d)%MOD
def mapping(C,X):
    x = X>>32; v = X&MASK
    a = C>>32; b = C&MASK
    return ((x*a + v*b)%MOD<<32) + v




import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,q = map(int, readline().split())
lr = [list(map(int, readline().split())) for _ in range(q)]

op_X = min
e_X = n-1
mapping = min
compose = min
id_M = n-1

sh = LazySegmentTree(op_X, e_X, mapping, compose, id_M, n, array=[n-1]*(n-1)+[0])
sw = LazySegmentTree(op_X, e_X, mapping, compose, id_M, n, array=[n-1]*(n-1)+[0])


ans = (n-2)**2
for t,x in lr:
    x -= 1
    if t==1:
        
        idx = sw.point_get(x)
        sh.apply(1,idx,x)
        ans -= idx-1
        
        
    else:
        idx = sh.point_get(x)
        sw.apply(1,idx,x)
        ans -= idx-1
        
        

print(ans)

Solution (Python):
from copy import *
from bisect import *
N,Q=map(int,input().split())
P=(N-2)*(N-2)
X=[N-2]
Y=[N-2]
V=[]
W=[]
a,b,c=0,0,0
for i in range(Q):
  a,b=map(int,input().split())
  b=N-b
  if a==1:
    c=bisect_left(V,b)
    if c==len(V):
      P-=Y[c]
      Y.append(Y[-1])
      X[-1]=N-b-2
      V.append(b)
    else:
      P-=Y[c]
  else:
    c=bisect_left(W,b)
    if c==len(W):
      P-=X[c]
      X.append(X[-1])
      Y[-1]=N-b-2
      W.append(b)
    else:
      P-=X[c]
print(P)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]
def SR(n):
    return [S() for _ in range(n)]
def LSR(n):
    return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
from math import log2, ceil


class SegmentTree:
    def __init__(self, n, default):
        self.n = n
        tn = 2 ** ceil(log2(n))
        self.a = [default] * (tn * 2)
        self.tn = tn

    def find(self, s, t):
        return self.__find(1, 0, self.tn - 1, s, t)

    def __find(self, c, l, r, s, t):
        if self.a[c] == -1:
            return self.a[c // 2]
        if s <= l and r <= t:
            return self.a[c]
        mid = (l + r) // 2
        if t <= mid:
            return self.__find(c * 2, l, mid, s, t)
        elif s > mid:
            return self.__find(c * 2 + 1, mid + 1, r, s, t)
        else:
            return min(
                self.__find(c * 2, l, mid, s, mid),
                self.__find(c * 2 + 1, mid + 1, r, mid + 1, t))

    def update(self, s, t, x):
        self.__update(1, 0, self.tn - 1, s, t, x)

    def __update(self, c, l, r, s, t, x, f=None):

        if f is None and self.a[c] == -1:
            f = self.a[c // 2]

        if l == s and r == t:
            return self.__set(c, x)

        mid = (l + r) // 2
        if t <= mid:
            rv, f = self.__get_child(c, c * 2 + 1, f)
            u = min(self.__update(c * 2, l, mid, s, t, x, f), rv)
        elif s > mid:
            lv, f = self.__get_child(c, c * 2, f)
            u = min(lv, self.__update(c * 2 + 1, mid + 1, r, s, t, x, f))
        else:
            u = min(
                self.__update(c * 2, l, mid, s, mid, x, f),
                self.__update(c * 2 + 1, mid + 1, r, mid + 1, t, x, f))
            if f is not None:
                u = min(f, u)
        self.a[c] = u

        return u

    def __set(self, c, x):
        self.a[c] = x
        if c < self.tn:
            self.a[c * 2] = self.a[c * 2 + 1] = -1
        return x

    def __get_child(self, c, child, f):
        if f is not None:
            return self.__set(child, f), f
        v = self.a[child]
        if v == -1:
            f = self.a[c]
            v = self.__set(child, f)
        return v, f

def solve():
    n,q = LI()
    ans = (n-2)*(n-2)
    right = SegmentTree(n+1,n)
    down = SegmentTree(n+1,n)
    for _ in range(q):
        t,x = LI()
        if t == 1:
            d = down.find(x,x)
            ans -= d-2
            k = right.find(0,0)
            if k > x:
                right.update(0,d,x)
        else:
            r = right.find(x,x)
            ans -= r-2
            k = down.find(0,0)
            if k > x:
                down.update(0,r,x)
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    SEGTREE_TABLES = []
    COMMON_STACK = np.zeros(10 ** 7, dtype=np.int64)
    INF = 10 ** 18

    def bit_length(n):
        ret = 0
        while n:
            n >>= 1
            ret += 1
        return ret

    def segtree_init(n):
        n2 = 1 << bit_length(n)
        table = np.full((n2 << 1, 2), INF, dtype=np.int64)
        SEGTREE_TABLES.append(table)
        return len(SEGTREE_TABLES) - 1

    def segtree_build(ins, arr):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        table[offset:offset + len(arr), 0] = arr
        for i in range(offset - 1, 0, -1):
            ch = i << 1
            table[i, 0] = min(table[ch, 0], table[ch + 1, 0])

    def segtree_eval(table, offset, i):
        lazy_min = table[i, 1]
        if i < offset:
            ch = i << 1
            table[ch, 1] = min(table[ch, 1], lazy_min)
            table[ch + 1, 1] = min(table[ch + 1, 1], lazy_min)
        table[i, 0] = min(table[i, 0], lazy_min)
        table[i, 1] = INF

    def segtree_bottomup(table, i):
        lch = i << 1
        rch = lch + 1
        l_dat = min(table[lch, 0], table[lch, 1])
        r_dat = min(table[rch, 0], table[rch, 1])
        table[i, 0] = min(l_dat, r_dat)

    def segtree_range_update(ins, l, r, mn):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        stack = COMMON_STACK
        stack[:3] = (1, 0, offset)
        si = 3
        updated = []
        while si:
            i, a, b = stack[si - 3:si]

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 3
                continue

            if l <= a and b <= r:
                table[i, 1] = min(table[i, 1], mn)
                si -= 3
                continue

            updated.append(i)

            m = (a + b) // 2
            stack[si - 3:si] = (i << 1, a, m)
            stack[si:si + 3] = ((i << 1) + 1, m, b)
            si += 3

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

    def segtree_query(ins, l, r):
        """ sum [l, r) """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        stack = COMMON_STACK
        stack[:3] = (1, 0, offset)
        si = 3
        res = INF
        updated = []

        while si:
            i, a, b = stack[si - 3:si]

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 3
                continue

            if l <= a and b <= r:
                res = min(res, table[i, 0])
                si -= 3
                continue

            updated.append(i)

            m = (a + b) // 2
            stack[si - 3:si] = (i << 1, a, m)
            stack[si:si + 3] = ((i << 1) + 1, m, b)
            si += 3

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

        return res

    def segtree_debug_print(ins):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        for t in range(2):
            i = 1
            while i <= offset:
                print(table[i:2 * i, t])
                i <<= 1

    n = inp[0]
    q = inp[1]
    ops = inp[2::2]
    xxx = inp[3::2]

    ins1 = segtree_init(n - 2)
    ins2 = segtree_init(n - 2)
    init = np.full(n - 2, n - 2, dtype=np.int64)
    segtree_build(ins1, init)
    segtree_build(ins2, init)

    ans = (n - 2) * (n - 2)
    for qi in range(q):
        o = ops[qi]
        x = xxx[qi]
        if o == 1:
            k = segtree_query(ins1, x - 2, x - 1)
            ans -= k
            segtree_range_update(ins2, 0, k + 1, x - 2)
        else:
            k = segtree_query(ins2, x - 2, x - 1)
            ans -= k
            segtree_range_update(ins1, 0, k + 1, x - 2)
        
        
        

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,Q = IL()

class RUQ:
  def __init__(self, N, default = None):
    self.N0 = 2**(N-1).bit_length()
    self.data = [(-1,N-1)]*(2*self.N0)
    self.INF = (-1, default)
  
  
  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]
    
TATE = RUQ(N-1,N-2)
YOKO = RUQ(N-1,N-2)

hidari = N
ue = N

ans = (N-2)**2

for t in range(Q):
  c,x = IL()
  if c == 1:
    ans -= TATE.query(x-2)
    
    if x<hidari:
      hidari = x
      YOKO.update(0,TATE.query(x-2),(t,x-2))
    TATE.update(x-2,x-1,(t,0))
  else:
    ans -= YOKO.query(x-2)
    
    if x<ue:
      ue = x
      TATE.update(0,YOKO.query(x-2),(t,x-2))
    YOKO.update(x-2,x-1,(t,0))
  
  
print(ans)

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


class LazySegmentTree:
    def __init__(self, n, unitX, unitA, X_f, A_f, XA_map):
        self.n = n
        self.unitX = unitX
        self.unitA = unitA
        self.X_f = X_f  
        self.A_f = A_f  
        self.XA_map = XA_map  
        self.X = [unitX] * (n + n)
        self.A = [unitA] * (n + n)

    def __getitem__(self, i):
        i += self.n
        self._propagate_above(i)
        return self.X[i]

    def __setitem__(self, i, x):
        i += self.n
        self._propagate_above(i)
        self.X[i] = x
        self._calc_above(i)

    def build(self, array):
        for i, val in enumerate(array, self.n):
            self.X[i] = val
        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 _calc_above(self, i):
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _propagate_above(self, i):
        k = i >> 1
        H = k.bit_length() - 1
        for h in range(H, -1, -1):
            i = k >> h
            if self.A[i] == self.unitA:
                continue
            self.X[i << 1] = self.XA_map(self.X[i << 1], self.A[i])
            self.X[i << 1 | 1] = self.XA_map(self.X[i << 1 | 1], self.A[i])
            self.A[i << 1] = self.A_f(self.A[i << 1], self.A[i])
            self.A[i << 1 | 1] = self.A_f(self.A[i << 1 | 1], self.A[i])
            self.A[i] = self.unitA

    def fold(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        xl = self.unitX
        xr = self.unitX
        while l < r:
            if l & 1:
                xl = self.X_f(xl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                xr = self.X_f(self.X[r], xr)
            l >>= 1
            r >>= 1
        return self.X_f(xl, xr)

    def apply(self, i, a):
        i += self.n
        self._propagate_above(i)
        self.X[i] = self.XA_map(self.X[i], a)
        self.A[i] = self.A_f(self.A[i], a)
        self._calc_above(i)

    def apply_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        while l < r:
            if l & 1:
                self.X[l] = self.XA_map(self.X[l], a)
                self.A[l] = self.A_f(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.X[r] = self.XA_map(self.X[r], a)
                self.A[r] = self.A_f(self.A[r], a)
            l >>= 1
            r >>= 1
        self._calc_above(l0)
        self._calc_above(r0)


n, q = map(int, input().split())
queries = [list(map(int, input().split())) for i in range(q)]
INF = 10 ** 18


nokori_1 = LazySegmentTree(n, INF, INF, min, min, min)
nokori_2 = LazySegmentTree(n, INF, INF, min, min, min)
nokori_1.build([n - 2] * n)
nokori_2.build([n - 2] * n)
                           
ans = (n - 2) * (n - 2)

for flag, x in queries:
    x -= 1
    if flag == 1:
        ans -= nokori_1[x]
        nokori_2.apply_range(0, nokori_1[x] + 1, x - 1)
        
        
        nokori_1[x] = 0
    else:
        ans -= nokori_2[x]
        nokori_1.apply_range(0, nokori_2[x] + 1, x - 1)
        
        
        nokori_2[x] = 0

print(ans)

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

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

seg_el=1<<((N+1).bit_length()) 

SEG=[N-2]*(2*seg_el) 
SEG2=[N-2]*(2*seg_el)

def getvalue(n,seg_el): 
    i=n+seg_el
    ANS=N-2
    
    ANS=min(SEG[i],ANS)
    i>>=1
    
    while i!=0:
        ANS=min(SEG[i],ANS)
        i>>=1

    return ANS

def getvalue2(n,seg_el): 
    i=n+seg_el
    ANS=N-2
    
    ANS=min(SEG2[i],ANS)
    i>>=1
    
    while i!=0:
        ANS=min(SEG2[i],ANS)
        i>>=1

    return ANS

def updates(l,r,x): 
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG[L]=min(x,SEG[L])
            L+=1

        if R & 1:
            R-=1
            SEG[R]=min(x,SEG[R])
        L>>=1
        R>>=1

def updates2(l,r,x): 
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG2[L]=min(x,SEG2[L])
            L+=1

        if R & 1:
            R-=1
            SEG2[R]=min(x,SEG2[R])
        L>>=1
        R>>=1

ANS=(N-2)*(N-2)

MINX=N
MINY=N

for queries in range(Q):
    t,x=map(int,input().split())

    if t==1:
        v=getvalue(x,seg_el)
        ANS-=v
        updates2(1,MINY,x-2)
        MINX=min(MINX,x)

    else:
        v=getvalue2(x,seg_el)
        ANS-=v
        updates(1,MINX,x-2)
        MINY=min(MINY,x)

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((numba.types.optional(i8), ) * 2, cache=True)
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return min(x, y)


@njit((i8[:], i8[:]), cache=True)
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((i8[:], i8, i8), cache=True)
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((i8[:], i8, i8), cache=True)
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, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        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 __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

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

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

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

import sys
input = sys.stdin.readline

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

stl = SegmentTree([n] * (n+1),default = n, func = min)
st_r = SegmentTree([n] * (n+1),default = n, func = min)

for _ in range(q):
    t, x = map(int, input().split())
    if t == 1:
        rFin = st_r.query(x, n+1)
        out += rFin - 2
        
        stl[rFin] = min(stl[rFin], x)
    else:
        lFin = stl.query(x, n+1)
        out += lFin - 2
        
        st_r[lFin] = min(st_r[lFin], x)
    
print((n - 2) * (n - 2) - out)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class SegmentTree:
        def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)

        def update(self, i, x):
            i += self.N0 - 1
            self.data[i] = x
            for _ in range(self.LV):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

        
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            ret_l = self.ident
            ret_r = self.ident
            while l < r:
                if l & 1:
                    ret_l = self.segfunc(ret_l, self.data[l])
                    l += 1
                if r & 1:
                    ret_r = self.segfunc(self.data[r - 1], ret_r)
                    r -= 1
                l >>= 1
                r >>= 1
            return self.segfunc(ret_l, ret_r)

        
        def binsearch(self, l, r, check):
            if not check(self.query(l, r)):
                return r
            l += self.N0 - 1
            val = self.ident
            while True:
                if check(self.segfunc(val, self.data[l])):
                    break
                if l & 1:
                    val = self.segfunc(val, self.data[l])
                    l += 1
                l >>= 1
            while l < self.N0:
                newval = self.segfunc(val, self.data[l * 2])
                if not check(newval):
                    val = newval
                    l = (l << 1) + 1
                else:
                    l <<= 1
            return l - self.N0 + 1

    N, Q = map(int, input().split())
    ST1 = SegmentTree([N] * N)
    ST2 = SegmentTree([N] * N)
    ans = (N-2) * (N-2)
    for _ in range(Q):
        t, x = map(int, input().split())
        if t == 1:
            k = ST1.query(x, N + 1)
            ans -= k-2
            if x < ST2.query(k, k+1):
                ST2.update(k, x)
        else:
            k = ST2.query(x, N + 1)
            ans -= k - 2
            if x < ST1.query(k, k + 1):
                ST1.update(k, x)
        
    print(ans)


if __name__ == '__main__':
    main()