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
def input(): return sys.stdin.readline().strip()

class SegTree():
    """
    0-indexedの配列[a0, a1, a2, ..., a(N-1)]に対して以下のクエリをそれぞれO(logx)で行う：
        1. i番目の要素にxを代入
        2. 半開区間[i, j)内の最小値を返す
    self.id_elemとself.funcを変えることでRmQ以外にも例えばRMQに対応可能。
    参考：https://juppy.hatenablog.com/entry/2019/05/02/蟻本_python_セグメント木_競技プログラミング_Atcoder
    """
    def __init__(self, N):
        
        self.id_elem = 10**10
        self.func = min

        
        self.num_max = 2 ** ((N - 1).bit_length())
        self.x = [self.id_elem] * (2 * self.num_max - 1)

    def get_elem(self, i):
        """
        i番目の要素を返す
        """
        return self.x[self.num_max + i - 1]

    def update(self, i, x):
        """
        i番目の要素にxを代入
        """
        i += self.num_max - 1
        self.x[i] = x
        while (i > 0):
            i = (i - 1) // 2
            self.x[i] = self.func(self.x[i * 2 + 1], self.x[i * 2 + 2])

    def query(self, i=0, j=-1, k=0, l=0, r=-1):
        """
        半開区間[i, j)内の最小値を返す
        [l, r)はノードkに対応づく区間を与える
        query()で配列全体に対してクエリを実行する
        """
        if j == -1: j = self.num_max
        if r == -1: r = self.num_max

        
        if (r <= i or j <= l): return self.id_elem
        
        if (i <= l and r <= j): return self.x[k]
        
        vl = self.query(i, j, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(i, j, k * 2 + 2, (l + r) // 2, r)
        return self.func(vl, vr)

def main():
    N, Q = map(int, input().split())
    black = (N - 2) * (N - 2)
    """
    クエリの管理にセグ木をどう使うかわからず止まってしまった。。。
    （区間minをとるのにどこからどこまでの区間を取るか効率的に取得する方法がわからなかった）

    結論としては自分自身の位置から「末尾まで」のminを取れば良い。
    というのも白マスの取れる個数はjの位置に対して単調増加だから。
    """
    tree_width = SegTree(N)
    tree_height = SegTree(N)
    tree_width.update(N - 2, N - 2)
    tree_height.update(N - 2, N - 2)
    reversed = 0
    for _ in range(Q):
        q, x= map(int, input().split())
        x -= 1
        if q == 1:
            new_reversed = tree_width.query(x, N)
            if tree_height.query(new_reversed, N) > x - 1:
                tree_height.update(new_reversed, x - 1)
        else:
            new_reversed = tree_height.query(x, N)
            if tree_width.query(new_reversed, N) > x - 1:
                tree_width.update(new_reversed, x - 1)
        reversed += new_reversed
    print((N - 2) * (N - 2) - reversed)


if __name__ == "__main__":
    main()

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

row = [N - 2] * (N + 2)
col = [N - 2] * (N + 2)
ans = (N - 2)**2

miRow = N
miCol = N

for _ in range(Q):
    q, x = map(int, input().split())

    if q == 1:
        for i in range(x, miRow + 1):
            row[i] = min(row[i], miCol - 2)
        miRow = min(x, miRow)
        ans -= row[x]

    if q == 2:
        for i in range(x, miCol + 1):
            col[i] = min(col[i], miRow - 2)
        miCol = min(x, miCol)
        ans -= col[x]

print(ans)

Solution (Python):
def search(L, x):
    low, high = 0, len(L)-1
    while low < high:
        mid = (low+high)//2
        if L[mid+1] < x < L[mid]:
            return mid
        elif x < L[mid+1]:
            low = mid+1
        else:
            high = mid
    return low

N, Q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(Q)]
B = [N-1]
Bv = [N-2]
R = [N-1]
Rv = [N-2]
ans = (N-2)**2
for f, x in query:
    x -= 1
    if f == 1:
        a = search(R, x)
        ans -= Rv[a]
        if R[-1] >= x:
            Bv[-1] = x-1
            R.append(x)
            Rv.append(Rv[-1])
    else:
        a = search(B, x)
        ans -= Bv[a]
        if B[-1] >= x:
            Rv[-1] = x-1
            B.append(x)
            Bv.append(Bv[-1])
    
print(ans)

Solution (Python):
class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        if self.data[index] <= value:
            return
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, Q = map(int, input().split())
INF = N - 2
treeRow = MinSegTree(N + 2)
treeCol = MinSegTree(N + 2)

miRow = N - 1
miCol = N - 1
ans = (N - 2)**2

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

    if q == 1:
        col = x
        ans -= treeRow.query(col, N)
        miCol = min(col, miCol)
        treeCol.update(miRow, col - 2)
    if q == 2:
        row = x
        ans -= treeCol.query(row, N)
        miRow = min(row, miRow)
        treeRow.update(miCol, row - 2)

print(ans)

Solution (Python):

import sys


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush


sys.setrecursionlimit(10 ** 7)
import math








INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

class segtree:
    '''init_val : 1-indexed (init_val[0] = self.bin[1])'''
    def __init__(self, n, init = 0, init_val=None):
        self.n = n
        self.init = init
        self.k = math.ceil(math.log2(n))
        self.add_val = 1 << self.k

        self.bins = [self.init] * (1 << (self.k + 1))
        if init_val != None:
            self.update_set(init_val)
        self.caliculate()

    def __getitem__(self, idx):  
        return self.bins[idx + self.add_val]

    def update_set(self, vals):
        for idx, i in enumerate(range(self.add_val, self.add_val * 2)):
            if len(vals) > idx:
                self.bins[i] = vals[idx]
            else:continue

    def compare(self, l, r):
        return min(l ,r)

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val, by=True):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        if by:
            self.bins[k] += val
        else:
            self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        if l == r:
            return self.bins[l + self.add_val]
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        
        while True:
            
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        
        return ret


def run():
    N, Q = mapline()
    X = segtree(N+1, init = INF)
    Y = segtree(N+1, init = INF)
    sub = 0
    for _ in range(Q):
        q, x = mapline()
        x -= 1
        if q == 1:
            v = X.eval(x, N-2)
            if v == INF:
                sub += N-2
                if Y[N-2] > x:
                    Y.update(N-2, x,by = False)
            else:
                sub += v-1
                if Y[v] > x:
                    Y.update(v, x, by = False)
        else:
            v = Y.eval(x, N - 2)
            if v == INF:
                sub += N - 2
                if X[N - 2] > x:
                    X.update(N - 2, x, by=False)
            else:
                sub += v - 1
                if X[v] > x:
                    X.update(v, x, by=False)
    print((N-2) ** 2 - sub)






if __name__ == "__main__":
    run()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    
    left = top = N
    row, col = [N] * (N + 1), [N] * (N + 1)
    
    ans = (N - 2) ** 2
    for _ in range(Q):
        com, x = map(int, rl().split())
        if com == 1:
            if x < left:
                for i in range(x, left):
                    col[i] = top
                left = x
            ans -= col[x] - 2
        else:
            if x < top:
                for i in range(x, top):
                    row[i] = left
                top = x
            ans -= row[x] - 2
    print(ans)


if __name__ == '__main__':
    solve()

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

def main():
    n, q = map(int, input().split())

    height, width = n, n
    mark1 = [0] * n
    mark2 = [0] * n
    ans = (n - 2) * (n - 2)

    for _ in range(q):
        typ, x = map(int, input().split())

        if typ == 1:
            if x < width:
                ans -= height - 2
                for i in range(x, width):
                    mark1[i] = height - 2
                width = x
            else:
                ans -= mark1[x]

        else:
            if x < height:
                ans -= width - 2
                for i in range(x, height):
                    mark2[i] = width - 2
                height = x
            else:
                ans -= mark2[x]

    print(ans)

main()

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

ans = (n-2)**2
rm = n
um = n
ruse = [-1]*(n+1)
uuse = [-1]*(n+1)

for _ in range(q):
    a,x = map(int,input().split())
    if a == 1:
        if uuse[x] >= 0:
            ans -= uuse[x]-2
        else:
            dif = um - 2
            ans -= dif
            for i in range(x,n+1):
                if uuse[i] >= 0:
                    break
                uuse[i] = um
            rm = min(rm,x)
    else:
        if ruse[x] >= 0:
            ans -= ruse[x]-2
        else:
            dif = rm - 2
            ans -= dif
            for i in range(x,n+1):
                if ruse[i] >= 0:
                    break
                ruse[i] = rm
            um = min(um,x)
print(ans)

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

ans = (n-2)**2
rm = n
um = n
ruse = [-1]*(n+1)
uuse = [-1]*(n+1)

for _ in range(q):
    a,x = map(int,input().split())
    if a == 1:
        if uuse[x] >= 0:
            ans -= uuse[x]-2
        else:
            dif = um - 2
            ans -= dif
            for i in range(x,n+1):
                if uuse[i] >= 0:
                    break
                uuse[i] = um
            rm = min(rm,x)
    else:
        if ruse[x] >= 0:
            ans -= ruse[x]-2
        else:
            dif = rm - 2
            ans -= dif
            for i in range(x,n+1):
                if ruse[i] >= 0:
                    break
                ruse[i] = rm
            um = min(um,x)
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq



def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N, Q = LI()

    N0 = 2 ** (N-1).bit_length()

    stx = [N-1] * (N0*2)
    sty = [N-1] * (N0*2)

    def update(l,r,x,st):
        l += N0 - 1
        r += N0 - 1
        while l < r:
            st[l] = min(st[l],x)
            st[r] = min(st[r],x)

            l //= 2
            r = r // 2 - 1

        st[l] = min(st[l],x)

    def get_data(i,st):
        i += N0-1
        ret = N-1
        while i >= 0:
            ret = min(ret,st[i])
            i = (i-1) // 2
        return ret


    ans = (N-2) ** 2
    for _ in range(Q):
        c,p = LI()
        p -= 1
        if c == 1:
            s = get_data(p,sty)
            ans -= s - 1
            update(0,s-1,p,stx)
        else:
            s = get_data(p,stx)
            ans -= s - 1
            update(0,s-1,p,sty)

    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):



codecpp = r"""

using namespace std;
using ll = long long;
 
// Segment Tree Beats
// - l<=i<r について、 A_i の値を min(A_i, x) に更新
// - l<=i<r について、 A_i の値を max(A_i, x) に更新
// - l<=i<r の中の A_i の最大値を求める
// - l<=i<r の中の A_i の最小値を求める
// - l<=i<r の A_i の和を求める
// - l<=i<r について、 A_i の値に x を加える
// - l<=i<r について、 A_i の値を x に更新
 

 
class SegmentTree {
  const ll inf = 1e18;
  int n, n0;
  ll max_v[4*N], smax_v[4*N], max_c[4*N];
  ll min_v[4*N], smin_v[4*N], min_c[4*N];
  ll sum[4*N];
  ll len[4*N], ladd[4*N], lval[4*N];
 
  void update_node_max(int k, ll x) {
    sum[k] += (x - max_v[k]) * max_c[k];
 
    if(max_v[k] == min_v[k]) {
      max_v[k] = min_v[k] = x;
    } else if(max_v[k] == smin_v[k]) {
      max_v[k] = smin_v[k] = x;
    } else {
      max_v[k] = x;
    }
 
    if(lval[k] != inf && x < lval[k]) {
      lval[k] = x;
    }
  }
  void update_node_min(int k, ll x) {
    sum[k] += (x - min_v[k]) * min_c[k];
 
    if(max_v[k] == min_v[k]) {
      max_v[k] = min_v[k] = x;
    } else if(smax_v[k] == min_v[k]) {
      min_v[k] = smax_v[k] = x;
    } else {
      min_v[k] = x;
    }
 
    if(lval[k] != inf && lval[k] < x) {
      lval[k] = x;
    }
  }
 
  void push(int k) {
 
    if(n0-1 <= k) return;
 
    if(lval[k] != inf) {
      updateall(2*k+1, lval[k]);
      updateall(2*k+2, lval[k]);
      lval[k] = inf;
      return;
    }
 
    if(ladd[k] != 0) {
      addall(2*k+1, ladd[k]);
      addall(2*k+2, ladd[k]);
      ladd[k] = 0;
    }
 
    if(max_v[k] < max_v[2*k+1]) {
      update_node_max(2*k+1, max_v[k]);
    }
    if(min_v[2*k+1] < min_v[k]) {
      update_node_min(2*k+1, min_v[k]);
    }
 
    if(max_v[k] < max_v[2*k+2]) {
      update_node_max(2*k+2, max_v[k]);
    }
    if(min_v[2*k+2] < min_v[k]) {
      update_node_min(2*k+2, min_v[k]);
    }
  }
 
  void update(int k) {
    sum[k] = sum[2*k+1] + sum[2*k+2];
 
    if(max_v[2*k+1] < max_v[2*k+2]) {
      max_v[k] = max_v[2*k+2];
      max_c[k] = max_c[2*k+2];
      smax_v[k] = max(max_v[2*k+1], smax_v[2*k+2]);
    } else if(max_v[2*k+1] > max_v[2*k+2]) {
      max_v[k] = max_v[2*k+1];
      max_c[k] = max_c[2*k+1];
      smax_v[k] = max(smax_v[2*k+1], max_v[2*k+2]);
    } else {
      max_v[k] = max_v[2*k+1];
      max_c[k] = max_c[2*k+1] + max_c[2*k+2];
      smax_v[k] = max(smax_v[2*k+1], smax_v[2*k+2]);
    }
 
    if(min_v[2*k+1] < min_v[2*k+2]) {
      min_v[k] = min_v[2*k+1];
      min_c[k] = min_c[2*k+1];
      smin_v[k] = min(smin_v[2*k+1], min_v[2*k+2]);
    } else if(min_v[2*k+1] > min_v[2*k+2]) {
      min_v[k] = min_v[2*k+2];
      min_c[k] = min_c[2*k+2];
      smin_v[k] = min(min_v[2*k+1], smin_v[2*k+2]);
    } else {
      min_v[k] = min_v[2*k+1];
      min_c[k] = min_c[2*k+1] + min_c[2*k+2];
      smin_v[k] = min(smin_v[2*k+1], smin_v[2*k+2]);
    }
  }
 
  void _update_min(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a || max_v[k] <= x) {
      return;
    }
    if(a <= l && r <= b && smax_v[k] < x) {
      update_node_max(k, x);
      return;
    }
 
    push(k);
    _update_min(x, a, b, 2*k+1, l, (l+r)/2);
    _update_min(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }
 
  void _update_max(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a || x <= min_v[k]) {
      return;
    }
    if(a <= l && r <= b && x < smin_v[k]) {
      update_node_min(k, x);
      return;
    }
 
    push(k);
    _update_max(x, a, b, 2*k+1, l, (l+r)/2);
    _update_max(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }
 
  void addall(int k, ll x) {
    max_v[k] += x;
    if(smax_v[k] != -inf) smax_v[k] += x;
    min_v[k] += x;
    if(smin_v[k] != inf) smin_v[k] += x;
 
    sum[k] += len[k] * x;
    if(lval[k] != inf) {
      lval[k] += x;
    } else {
      ladd[k] += x;
    }
  }
 
  void updateall(int k, ll x) {
    max_v[k] = x; smax_v[k] = -inf;
    min_v[k] = x; smin_v[k] = inf;
    max_c[k] = min_c[k] = len[k];
 
    sum[k] = x * len[k];
    lval[k] = x; ladd[k] = 0;
  }
 
  void _add_val(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      addall(k, x);
      return;
    }
 
    push(k);
    _add_val(x, a, b, 2*k+1, l, (l+r)/2);
    _add_val(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }
 
  void _update_val(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      updateall(k, x);
      return;
    }
 
    push(k);
    _update_val(x, a, b, 2*k+1, l, (l+r)/2);
    _update_val(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }
 
  ll _query_max(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return -inf;
    }
    if(a <= l && r <= b) {
      return max_v[k];
    }
    push(k);
    ll lv = _query_max(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_max(a, b, 2*k+2, (l+r)/2, r);
    return max(lv, rv);
  }
 
  ll _query_min(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return inf;
    }
    if(a <= l && r <= b) {
      return min_v[k];
    }
    push(k);
    ll lv = _query_min(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_min(a, b, 2*k+2, (l+r)/2, r);
    return min(lv, rv);
  }
 
  ll _query_sum(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return 0;
    }
    if(a <= l && r <= b) {
      return sum[k];
    }
    push(k);
    ll lv = _query_sum(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_sum(a, b, 2*k+2, (l+r)/2, r);
    return lv + rv;
  }
 
public:
  SegmentTree(int n) {
    SegmentTree(n, nullptr);
  }
 
  SegmentTree(int n, ll *a) : n(n) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;
 
    for(int i=0; i<2*n0; ++i) ladd[i] = 0, lval[i] = inf;
    len[0] = n0;
    for(int i=0; i<n0-1; ++i) len[2*i+1] = len[2*i+2] = (len[i] >> 1);
 
    for(int i=0; i<n; ++i) {
      max_v[n0-1+i] = min_v[n0-1+i] = sum[n0-1+i] = (a != nullptr ? a[i] : 0);
      smax_v[n0-1+i] = -inf;
      smin_v[n0-1+i] = inf;
      max_c[n0-1+i] = min_c[n0-1+i] = 1;
    }
 
    for(int i=n; i<n0; ++i) {
      max_v[n0-1+i] = smax_v[n0-1+i] = -inf;
      min_v[n0-1+i] = smin_v[n0-1+i] = inf;
      max_c[n0-1+i] = min_c[n0-1+i] = 0;
    }
    for(int i=n0-2; i>=0; i--) {
      update(i);
    }
  }
 
  // range minimize query
  void update_min(int a, int b, ll x) {
    _update_min(x, a, b, 0, 0, n0);
  }
 
  // range maximize query
  void update_max(int a, int b, ll x) {
    _update_max(x, a, b, 0, 0, n0);
  }
 
  // range add query
  void add_val(int a, int b, ll x) {
    _add_val(x, a, b, 0, 0, n0);
  }
 
  // range update query
  void update_val(int a, int b, ll x) {
    _update_val(x, a, b, 0, 0, n0);
  }
 
  // range minimum query
  ll query_max(int a, int b) {
    return _query_max(a, b, 0, 0, n0);
  }
 
  // range maximum query
  ll query_min(int a, int b) {
    return _query_min(a, b, 0, 0, n0);
  }
 
  // range sum query
  ll query_sum(int a, int b) {
    return _query_sum(a, b, 0, 0, n0);
  }
};
"""
codecy = r"""

from libcpp.vector cimport vector
ctypedef long long ll
cdef extern from "_segtreebeats.cpp":
    cdef cppclass SegmentTree:
        SegmentTree(int n, ll *a)
        void update_min(int a, int b, ll x)
        void update_max(int a, int b, ll x)
        void add_val(int a, int b, ll x)
        void update_val(int a, int b, ll x)
        ll query_max(int a, int b)
        ll query_min(int a, int b)
        ll query_sum(int a, int b)
cdef class segtreebeats:
    cdef SegmentTree *ptr
    def __cinit__(self, list a):
        cdef vector[ll] p = a
        cdef int n = p.size()
        self.ptr = new SegmentTree(n, &p[0])
    cpdef void update_min(self, int a, int b, ll x):
        self.ptr.update_min(a, b, x)
    cpdef void update_max(self, int a, int b, ll x):
        self.ptr.update_max(a, b, x)
    cpdef void add_val(self, int a, int b, ll x):
        self.ptr.add_val(a, b, x)
    cpdef void update_val(self, int a, int b, ll x):
        self.ptr.update_val(a, b, x)
    cpdef ll query_max(self, int a, int b):
        return self.ptr.query_max(a, b)
    cpdef ll query_min(self, int a, int b):
        return self.ptr.query_min(a, b)
    cpdef ll query_sum(self, int a, int b):
        return self.ptr.query_sum(a, b)
"""
try: from yaketake08 import segtreebeats
except:
    import os, sys
    open('_segtreebeats.cpp', 'w').write(codecpp)
    open('yaketake08.pyx', 'w').write(codecy)
    os.system('cythonize -i -3 -b yaketake08.pyx')
    from yaketake08 import segtreebeats
import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
row = segtreebeats([n - 1] * n)
col = segtreebeats([n - 1] * n)
s = (n - 2) ** 2
for i in range(q):
    p, x = map(int, input().split())
    if p - 1:
        y = row.query_min(x - 1, x)
        s -= y - 1
        col.update_min(0, y, x - 1)
    else:
        y = col.query_min(x - 1, x)
        s -= y - 1
        row.update_min(0, y, x - 1)
print(s)

Solution (Python):
from collections import deque
n, q = map(int, input().split())
query = []
for _ in range(q):
    t, x = map(int, input().split())
    query.append((t-1, x))
black = (n-2)**2
rc = [deque([(n, n)]), deque([(n, n)])]
mrc = [n, n]

def bisect(li, x):
    ok = -1
    ng = len(li)
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if li[mid][0]<x:
            ok = mid
        else:
            ng = mid
    return ok+1

for t, x in query:
    tmp = rc[t][bisect(rc[t], x)][1]
    black -= tmp-2
    if x < mrc[t]:
        mrc[t] = x
        rc[1-t].appendleft((tmp, x))
print(black)

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('segtreebeats.cpython-38-x86_64-linux-gnu.so', 'wb').write(zlib.decompress(base64.b85decode('c%1CLd3+Q_7C1hW0|Ep(Trwy}(4Y|n6BWsbXhss~(FsHWMFkTKfgo3eiGU)YNrZM7$f^jdqNuCldZ8`~C@~?NDiRJg+>x`JaD+1n*ZkglRoz|F$?SLc`}_R<`fYY)re4?a>eZ`vRlS~Bsh<8}cDqgg3%A{8!%}4uD<^Zf`a_ISC)t){YX<*zwZ&202wUhsM||+7jdz3XBJoQChg&`)lk7pCVmlfym%}ZeLps`mKE-y8;6Hf@t0
from segtreebeats import segtreebeats
(n,q),*t=[[*map(int,t.split())]for t in open(0)]
a=segtreebeats([n]*-~n)
b=segtreebeats([n]*-~n)
s=(n-2)**2
for i,x in t:
    if i-1:
        y=a.query_min(x,x+1)
        s-=y-2
        b.update_min(1,y+1,x)
    else:
        y=b.query_min(x,x+1)
        s-=y-2
        a.update_min(1,y+1,x)
print(s)