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

segtreebeats = 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);
  }
};
"""
lib = r"""

cdef extern from "segtreebeats.cpp":
    cdef cppclass SegmentTree:
        SegmentTree(int n, long long *a)
        void update_min(int a, int b, long long x)
        void update_max(int a, int b, long long x)
        void add_val(int a, int b, long long x)
        void update_val(int a, int b, long long x)
        long long query_max(int a, int b)
        long long query_min(int a, int b)
        long long query_sum(int a, int b)
from libc.stdio cimport scanf, printf
cdef long long[200001] l
cdef int n, q, i, p
scanf('%d%d', &n, &q)
for i in range(n + 1): l[i] = n
cdef SegmentTree *a = new SegmentTree(n + 1, l)
cdef SegmentTree *b = new SegmentTree(n + 1, l)
cdef long long s = n - 2, x, y
s **= 2
for i in range(q):
    scanf('%d%lld', &p, &x)
    if p - 1:
        y = a.query_min(x, x + 1)
        s -= y - 2
        b.update_min(0, y + 1, x)
    else:
        y = b.query_min(x, x + 1)
        s -= y - 2
        a.update_min(0, y + 1, x)
printf('%lld\n', s)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('segtreebeats.cpp', 'w').write(segtreebeats)
    open('solve.pyx', 'w').write(lib)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
n,q=map(int,input().split())
x= n-2
y= n-2
dx={}
dy={}

for _ in range(q):
    a,b=map(int,input().split())
    b-=1
    if a==1:
        if y< b:
            dy[b]=0;continue
        
        for i in range(b+1,y+1):
            dy[i] = x
        y=b-1

    if a==2:
        if x < b:
            dx[b]=0;continue
        
        for i in range(b+1,x+1):
            dx[i] =y
        x=b-1
print(x*y + sum(dx.values()) + sum(dy.values()) )

Solution (Python):
import sys

input = sys.stdin.buffer.readline

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


class SegmentTree:
    ele = 10 ** 10
    func = min
    
    

    def __init__(self, n):  
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        
        
        
        
        
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


ans = 0

tate = SegmentTree(n)
yoko = SegmentTree(n)

for i in range(q):
    s, x = map(int, input().split())
    x -= 1
    if s == 1:
        temp = tate.query(x, n)
        
        if temp == 10 ** 10:
            temp = n - 1
        now = yoko.search(temp)
        now = min(now, x)
        yoko.update(temp, now)
        ans += temp - 1
    else:
        temp = yoko.query(x, n)
        
        if temp == 10 ** 10:
            temp = n - 1
        now = tate.search(temp)
        now = min(now, x)
        tate.update(temp, now)
        ans += temp - 1
    
ans = (n - 2) ** 2 - ans
assert ans >= 0
print(ans)

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

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal
from argparse import ArgumentParser

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

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

class segtree():
    def __init__(self,A,ide=1000000000):
        n=len(A)
        num=2**(n-1).bit_length()
        seg=[ide]*(2*num-1)
        segfunc=self.segfunc
        self.ide,self.n,self.num,self.seg = ide, n, num, seg
        self.A=deepcopy(A)
        for i in range(n): 
            seg[i+num-1]=A[i]
        for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
    def segfunc(self,x,y):return min(x,y) 
    
    def get(self,i): return self.A[i]

    def update(self,k,x):
        self.A[k]=x
        k += self.num-1
        seg,segfunc=self.seg,self.segfunc
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
    def query(self,p,q):
        if q<=p: return self.ide
        num,segfunc,seg=self.num,self.segfunc,self.seg
        p += num-1; q += num-2
        res=self.ide
        while q-p>1:
            if p&1 == 0: res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p,q = p//2, (q-1)//2
        if p == q: res = segfunc(res,seg[p])
        else: res = segfunc(segfunc(res,seg[p]),seg[q])
        return res 
def main():
    mod = 1000000007
    

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

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


if __name__ == "__main__":
    main()

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

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal
from argparse import ArgumentParser

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

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

class segtree():
    def __init__(self,A,ide=1000000000):
        n=len(A)
        num=2**(n-1).bit_length()
        seg=[ide]*(2*num-1)
        segfunc=self.segfunc
        self.ide,self.n,self.num,self.seg = ide, n, num, seg
        for i in range(n): seg[i+num-1]=A[i]
        for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
    def segfunc(self,x,y):return min(x,y) 
    
    def get(self,i): return self.seg[i+self.num-1]

    def update(self,k,x):
        k += self.num-1
        seg,segfunc=self.seg,self.segfunc
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
    def query(self,p,q):
        if q<=p: return self.ide
        num,segfunc,seg=self.num,self.segfunc,self.seg
        p += num-1; q += num-2
        res=self.ide
        while q-p>1:
            if p&1 == 0: res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p,q = p//2, (q-1)//2
        if p == q: res = segfunc(res,seg[p])
        else: res = segfunc(segfunc(res,seg[p]),seg[q])
        return res 
def main():
    mod = 1000000007
    

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

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


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n,q=map(int,input().split())
    H,V=[0]*(n+1),[0]*(n+1)
    h,v=n,n
    cnt=0
    for _ in range(q):
        s,x=map(int,input().split())
        if s==1:
            if x<v:
                cnt+=h-2
                for i in range(x,v):
                    H[i]=h
                v=x
            else:
                cnt+=H[x]-2
        if s==2:
            if x<h:
                cnt+=v-2
                for i in range(x,h):
                    V[i]=v
                h=x
            else:
                cnt+=V[x]-2
    print((n-2)**2-cnt)
    
if __name__=='__main__':
    main()

Solution (Python):


import sys

input = sys.stdin.buffer.readline

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


class SegmentTree:
    ele = 10 ** 10
    func = min
    
    

    def __init__(self, n):  
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        if self.search(idx) < val:
        	return
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        
        
        
        
        
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


ans = 0

tate = SegmentTree(n)
yoko = SegmentTree(n)

for i in range(q):
    s, x = map(int, input().split())
    x -= 1
    if s == 1:
        temp = tate.query(x, n)
        
        if temp == 10 ** 10:
            temp = n - 1
        yoko.update(temp, x)
        ans += max(0, temp - 1)
    else:
        temp = yoko.query(x, n)
        
        if temp == 10 ** 10:
            temp = n - 1
        tate.update(temp, x)
        ans += max(0, temp - 1)
    
print((n - 2) ** 2 - ans)

Solution (Python):


import sys

input = sys.stdin.buffer.readline

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


class SegmentTree:
    ele = 10 ** 10
    func = min
    
    

    def __init__(self, n):  
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        
        
        
        
        
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


ans = 0

tate = SegmentTree(n)
yoko = SegmentTree(n)

for i in range(q):
    s, x = map(int, input().split())
    x -= 1
    if s == 1:
        temp = tate.query(x, n)
        
        if temp == 10 ** 10:
            temp = n - 1
        now = yoko.search(temp)
        now = min(now, x)
        yoko.update(temp, now)
        ans += max(0, temp - 1)
    else:
        temp = yoko.query(x, n)
        
        if temp == 10 ** 10:
            temp = n - 1
        now = tate.search(temp)
        now = min(now, x)
        tate.update(temp, now)
        ans += max(0, temp - 1)
    
print((n - 2) ** 2 - ans)

Solution (Python):
import sys

input = sys.stdin.buffer.readline

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


class SegmentTree:
    ele = 10 ** 10
    func = min
    
    

    def __init__(self, n):  
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        
        
        
        
        
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


ans = 0

tate = SegmentTree(n)
yoko = SegmentTree(n)

for i in range(q):
    s, x = map(int, input().split())
    x -= 1
    if s == 1:
        temp = tate.query(x, n)
        
        if temp == 10 ** 10:
            temp = n - 1
        now = yoko.search(temp)
        now = min(now, x)
        yoko.update(temp, now)
        ans += max(0, temp - 1)
    else:
        temp = yoko.query(x, n)
        
        if temp == 10 ** 10:
            temp = n - 1
        now = tate.search(temp)
        now = min(now, x)
        tate.update(temp, now)
        ans += max(0, temp - 1)
    
print((n - 2) ** 2 - ans)

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

N, Q = map(int, input().split())
row = [-1] * (N - 2)
col = [-1] * (N - 2)
a = b = N - 2
ans = (N - 2)**2
for _ in range(Q):
    t, x = map(int, input().split())
    x -= 2
    if t == 1:
        if col[x] == -1:
            ans -= b
        else:
            ans -= col[x]
        a = min(a, x)
        for i in range(x, N - 2):
            if col[i] != -1:
                break
            col[i] = b
    else:
        if row[x] == -1:
            ans -= a
        else:
            ans -= row[x]
        b = min(b, x)
        for i in range(x, N - 2):
            if row[i] != -1:
                break
            row[i] = a
print(ans)

Solution (Python):
def f_simplified_reversi():
    N, Q = [int(i) for i in input().split()]
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    a, b = [N] * N, [N] * N  
    black_stone = (N - 2)**2
    row, col = N, N

    for type, x in Queries:
        if type == 1:
            if x < col:
                for i in range(x, col):
                    b[i] = row
                col = x
            black_stone -= b[x] - 2
        else:
            if x < row:
                for i in range(x, row):
                    a[i] = col
                row = x
            black_stone -= a[x] - 2
    return black_stone

print(f_simplified_reversi())

Solution (Python):
class LazyPropSegmentTree:
	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 = [float('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 == float('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] = float('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 point_query(self, k):
		*ids, = self.gindex(k, k + 1)
		self.propagates(*ids)
		return self.data[k + self.N0 - 1]

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

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

print(ans)

Solution (Python):
N, Q, *QX = map(int, open(0).read().split())

A = [N] * (N + 1)
B = [N] * (N + 1)

ans = (N - 2) ** 2
h = w = N
for q, x in zip(*[iter(QX)] * 2):
    if q == 1:
        if x < w:
            B[x:w] = [h] * (w - x)
            w = x
        ans -= B[x] - 2
    else:
        if x < h:
            A[x:h] = [w] * (h - x)
            h = x
        ans -= A[x] - 2

print(ans)

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,q = ma()
black = [[n-2]*(n+1) for i in range(2)] 
inner =[n,n] 
innerbl = [n-2,n-2] 
ans=(n-2)**2
for _ in range(q):
    t,x = ma();t-=1
    if x>inner[t]:
        ans-=black[t][x]
    elif x<inner[t]:
        ans-=innerbl[t]
        innerbl[1-t]=x-2
        for i in range(x,inner[t]):
            black[t][i]=innerbl[t]
        inner[t]=x
print(ans)