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
input = sys.stdin.readline

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

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 = list(map(int,input().split()))
  if c == 1:
    ans -= TATE.query(x-2)
    if x<hidari:
      hidari = x
      YOKO.update(0,TATE.query(x-2),(t,x-2))
  else:
    ans -= YOKO.query(x-2)
    if x<ue:
      ue = x
      TATE.update(0,YOKO.query(x-2),(t,x-2))
print(ans)

Solution (Python):
class LazySegTree:
    
    def __init__(self, init_val, seg_ide, lazy_ide, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()

        self.seg_ide = seg_ide
        self.lazy_ide = lazy_ide

        self.segfunc = segfunc

        
        self.seg = [seg_ide]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])

        self.lazy = [lazy_ide]*2*self.num

    def gindex(self, l, r):
        
        L = l + self.num
        R = r + self.num
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L = L >> 1
            R = R >> 1
        while L:
            yield L
            L = L >> 1

    def propagate(self, *ids):
        
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2*i] = self.lazy[2*i+1] = self.seg[2*i] = self.seg[2*i+1] = v
            self.lazy[i] = None

    def update(self, l, r, x):
        
        
        *ids, = self.gindex(l, r)
        self.propagate(*ids)
        L = l + self.num
        R = r + self.num
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R] = self.seg[R] = x
            if L & 1:
                self.lazy[L] = self.seg[L] = x
                L += 1
            L = L >> 1
            R = R >> 1
        for i in ids:
            
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])

    def query(self, l, r):
        
        
        if r <= l:
            return self.seg_ide

        self.propagate(*self.gindex(l, r))
        L = l + self.num
        R = r + self.num
        res = self.seg_ide
        while L < R:
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.seg[R])
            if L & 1:
                res = self.segfunc(res, self.seg[L])
                L += 1
            L = L >> 1
            R = R >> 1
        return res

def segfunc(x, y):
    if x <= y:
        return x
    else:
        return y

INF = 10**18

import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():

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

    R = LazySegTree([n-1]*n, INF, None, segfunc)
    C = LazySegTree([n-1]*n, INF, None, segfunc)

    ans = (n-2)**2
    l = n
    u = n
    for i in range(q):
        t, x = map(int, input().split())
        x -= 1
        if t == 1:
            r = R.query(x, x+1)
            
            ans -= (r-1)
            if x < l:
                C.update(0, r+1, x)
                l = x
        else:
            c = C.query(x, x+1)
            
            ans -= (c-1)
            if x < u:
                R.update(0, c+1, x)
                u = x

    print(ans)

if __name__ == '__main__':
    main()

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

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

class LazySegmentTree():
    def __init__(self, n):
        self.lv = (n-1).bit_length()
        self.n = 2 ** self.lv
        self.arr = [2**31-1] * (2*self.n-1)
        self.lazy = [None] * (2*self.n-1)

    
    def getidx(self, l, r):
        L = (l + self.n) >> 1
        R = (r + self.n) >> 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 propagate(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.arr[2*i-1] = self.lazy[2*i] = self.arr[2*i] = v
            self.lazy[i-1] = None

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

        L = self.n + l; R = self.n + r
        while L < R:
            if R & 1:
                R -=1
                self.lazy[R-1] = self.arr[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.arr[L-1] = x
                L += 1
            L >>= 1; R >>= 1

        for i in ids:
            self.arr[i-1] = func(self.arr[2*i-1], self.arr[2*i])

    
    def query(self,l,r):
        
        r+=1
        self.propagate(*self.getidx(l,r))
        L = self.n + l; R = self.n + r

        s = 2**31-1
        while L < R:
            if R & 1:
                R -=1
                s = func(s, self.arr[R-1])
            if L & 1:
                s = func(s, self.arr[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

def main():
    n, q = map(int, input().split())
    row = LazySegmentTree(n - 2)
    col = LazySegmentTree(n - 2)
    row.update(0, n - 3, n - 2)
    col.update(0, n - 3, n - 2)
    ans = (n - 2) ** 2
    for _ in range(q):
        que = list(map(int, input().split()))
        pos = que[1] - 2
        if que[0] == 1:
            num = row.query(pos, pos)
            ans -= num
            num2 = col.query(0, 0)
            
            if num2 > pos:
                col.update(0, num - 1, pos)
        else:
            num = col.query(pos, pos)
            ans -= num
            num2 = row.query(0, 0)
            if num2 > pos:
                row.update(0, num - 1, pos)
    print(ans)
        
main()

Solution (Python):
import sys

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


class SegmentTree:
    def __init__(self, n, segfunc=min, ele=10**10):
        self.ide_ele = ele
        self.num = pow(2, (n-1).bit_length())
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc

    def init(self, init_val):
        
        for i in range(len(init_val)):
            self.seg[i+self.num-1] = init_val[i]
        
        for i in range(self.num-2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res


cols = SegmentTree(N, ele=N - 1)
raws = SegmentTree(N, ele=N - 1)
ans = (N-2)*(N-2)
for q, x in Qs:
    x -= 1
    if q == 1:
        i = cols.query(x, N)
        raws.update(i, min(x, raws.seg[raws.num-1+i]))
        ans -= i - 1
    if q == 2:
        i = raws.query(x, N)
        cols.update(i, min(x, cols.seg[cols.num-1+i]))
        ans -= i - 1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n, q = map(int,input().split())
C = [list(map(int,input().split())) for i in range(q)]


class Bit:  
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, l, r):  
        
        s = 0
        while r > 0:
            s += self.tree[r]
            r -= r & -r
        while l > 0:
            s -= self.tree[l]
            l -= l & -l
        return s
  
    def add(self, i, x):  
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def print_bit(B):
    n = B.size
    ANS = []
    for i in range(n):
        ANS.append(B.sum(i, i+1))
    print(*ANS)

A = Bit(n)
B = Bit(n)
A.add(0, n-2)
B.add(0, n-2)
AC = [0] * n
BC = [0] * n
ans = 0
minac = n-1
minbc = n-1



for i in range(q):
    c1 = C[i][1]-1
    if C[i][0] == 1:
        BC[c1] = 1
        if minbc > c1:
            
            minbc=c1
            
            oku = B.sum(0,c1+1)
            
            a0 = A.sum(0,1)
            aoku = A.sum(0, oku+1)
            A.add(0, -a0+c1-1)
            A.add(oku+1, aoku-A.sum(0,1))
            
    elif C[i][0] == 2:
        AC[c1] = 1
        if minac > c1:
            
            minac = c1
            
            oku = A.sum(0,c1+1)
            a0 = B.sum(0,1)
            aoku = B.sum(0, oku+1)
            B.add(0, -a0+c1-1)
            B.add(oku+1, aoku-B.sum(0,1))

            







for i in range(1, n-1):
    if AC[i] == 0:
        
        ans += A.sum(0,i+1)
for i in range(1, n-1):
    if BC[i] == 0:
        ans += B.sum(0,i+1)

for i in range(1, minac):
    ans -= A.sum(0,i+1)

print(ans)

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

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

hor=[0]*(n-2)
ver=[0]*(n-2)
a=n-2
b=n-2

ans=(n-2)**2
for _ in range(q):
    y,x=map(int,input().split())
    if y==1:
        if x-1>b:
            ans-=ver[x-2]
        else:
            ans-=a
            for i in range(x-2,b):
                ver[i]=a
            b=x-2

    else:
        if x-1>a:
            ans-=hor[x-2]
        else:
            ans-=b
            for i in range(x-2,a):
                hor[i]=b
            a=x-2


print(ans)

Solution (Python):
class Binary_Indexed_Tree():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        ret = 0
        while i:
            ret += self.data[i]
            i &= i-1
        return ret

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

n,q = map(int, input().split())
yoko = Binary_Indexed_Tree(n-2)
tate = Binary_Indexed_Tree(n-2)
query = [list(map(int, input().split())) for i in range(q)]
for a,b in query:
    if a == 1:
        yoko.add(b-2, 1)
    else:
        tate.add(b-2, 1)

ans = (n-2)**2

yoko_rem = n-2
tate_rem = n-2
yoko_minimum = n-3
tate_minimum = n-3
for a,b in query:
    pos = b-2
    goodbye = 0
    f = False
    if a == 1:
        if yoko_minimum < pos:
            yoko.add(pos, -1)
            f = True
            continue
        goodbye = yoko_rem * yoko.sum_range(pos, yoko_minimum)
        ans -= goodbye
        tate_rem = pos
        yoko.add(pos, -1)
        yoko_minimum = pos
    else:
        if tate_minimum < pos:
            tate.add(pos, -1)
            f = True
            continue
        goodbye = tate_rem * tate.sum_range(pos, tate_minimum)
        ans -= goodbye
        yoko_rem = pos
        tate.add(pos, -1)
        tate_minimum = pos
print(ans)

Solution (Python):


import sys
input=sys.stdin.readline

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

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
MOD = 1000000007


def main():
    N, Q, *queries = map(int, read().split())
    queries = [(q, x) for q, x in zip(*[iter(queries)] * 2)]

    N -= 2

    

    N0 = 2 ** (N - 1).bit_length()
    data1 = [None] * (2 * N0)
    data2 = [None] * (2 * N0)
    INF = (-1, 2 ** 31 - 1)
    
    
    def update(l, r, v, data):
        L = l + N0
        R = r + N0
        while L < R:
            if R & 1:
                R -= 1
                data[R - 1] = v

            if L & 1:
                data[L - 1] = v
                L += 1
            L >>= 1
            R >>= 1

    
    def _query(k, data):
        k += N0 - 1
        s = INF
        while k >= 0:
            if data[k]:
                s = max(s, data[k])
            k = (k - 1) // 2
        return s

    
    def query(k, data):
        return _query(k, data)[1]

    update(0, N, (0, N), data1)
    update(0, N, (0, N), data2)

    min1 = min2 = N + 10
    ans = N * N

    for i, (q, x) in enumerate(queries, 1):
        x -= 2
        if q == 1:
            data = data1
            this_min = min1
        else:
            data = data2
            this_min = min2

        n = query(x, data)
        ans -= n

        if x > this_min:
            continue

        if q == 1:
            min1 = x
            update(0, n, (i, x), data2)
        else:
            min2 = x
            update(0, n, (i, x), data1)

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1



import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

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


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

from math import log2


class SegmentTree:
    def __init__(self, array):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.default = 10**18
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array

    def query(self, index):
        """Returns the value at given index!"""
        res = self.default
        index += self.size
        while index:
            res = min(res, self.data[index])
            index >>= 1
        return res

    def update(self, alpha, omega, value):
        """Increases all elements in the range (inclusive) by given value!"""
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                self.data[alpha] = min(self.data[alpha], value)
                alpha += 1
            if omega & 1:
                omega -= 1
                self.data[omega] = min(self.data[omega], value)
            alpha >>= 1
            omega >>= 1

for _ in range(int(input()) if not True else 1):
    n, q = map(int, input().split())
    black = (n-2)*(n-2)
    first_in_row = [n-1]*n
    first_in_row[n-1] = 0
    first_in_column = [n-1]*n
    first_in_column[n-1] = 0
    
    first_in_row = SegmentTree(first_in_row)
    first_in_column = SegmentTree(first_in_column)
    for __ in range(q):
        x, y = map(int, input().split())
        if x == 1:
            
            col_first = first_in_column.query(y-1)
            black -= max(col_first - 1, 0)
            first_in_row.update(0, col_first-1, y-1)
            first_in_column.update(y-1, y-1, 0)
        else:
            
            row_first = first_in_row.query(y-1)
            black -= max(row_first - 1, 0)
            first_in_column.update(0, row_first-1, y-1)
            first_in_row.update(y-1, y-1, 0)
        
    print(black)

Solution (Python):
class SegTreeBool():
    def segFunc(self, x, y):
        return x + y
    def searchIndexFunc(self, val):
        return val > 0
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segFunc(self.seg[2*i+1],self.seg[2*i+2])
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res
    def getLargestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R)//2
            if self.searchIndexFunc(self.query(P, R)):
                L = P
            else:
                R = P
        return L
    def getSmallestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R+1)//2
            if self.searchIndexFunc(self.query(L, P)):
                R = P
            else:
                L = P
        return L

def main():
    n, q = map(int, input().split())
    qry = [list(map(int, input().split())) for _ in range(q)]
    ans = (n-2)**2
    m1, m2 = n, n
    segbool1 = SegTreeBool(0, [0]*n)
    segbool2 = SegTreeBool(0, [0]*n)
    ms1 = [n]*n
    ms2 = [n]*n
    for ptn, idx in qry:
        if ptn == 1:
            tmp = None
            if segbool1.query(0, idx) == 0:
                tmp = m2 - 2
            else:
                pt = segbool1.getLargestIndex(0, idx)
                tmp = ms1[pt]
            ans -= tmp
            ms1[idx] = tmp
            segbool1.update(idx, 1)
            if idx < m1:
                m1 = idx
        else:
            tmp = None
            if segbool2.query(0, idx) == 0:
                tmp = m1 - 2
            else:
                pt = segbool2.getLargestIndex(0, idx)
                tmp = ms2[pt]
            ans -= tmp
            ms2[idx] = tmp
            segbool2.update(idx, 1)
            if idx < m2:
                m2 = idx
    print(ans)

if __name__ == "__main__":
    main()

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

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

    ans = 0
    min1, min2 = n-2, n-2
    judge1 = [-n-1]
    judge2 = [-n-1]
    dict1 = dict()
    dict2 = dict()
    dict1[-n-1] = n-2
    dict2[-n-1] = n-2

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

        if query == 1:
            index = bisect.bisect(judge1, -x)-1
            key = dict1[judge1[index]]
            ans += key
            if min1 > x-2:
                min1 = x-2
                judge1.append(-x)
                dict1[-x] = key
                dict2[judge2[-1]] = min1
        else:
            index = bisect.bisect(judge2, -x)-1
            key = dict2[judge2[index]]
            ans += key
            if min2 > x-2:
                min2 = x-2
                judge2.append(-x)
                dict2[-x] = key
                dict1[judge1[-1]] = min2

    print((n-2)**2 - ans)
    
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):
N, Q, *Query = [int(_) for _ in open(0).read().split()]
D = Query[::2]
X = Query[1::2]


class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        ti : T
            identity element of T
        ei : E
            identity element of E
        """
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def reflect(self, k):
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])

    def evaluate(self, k):
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei

    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)

    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))

    def update(self, a, b, x):  
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)

    def set_val(self, a, x):
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)

    def query(self, a, b):  
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)



array = [N] * (N + 1)
f = lambda a, b: a if b == 0 else b
g = lambda a, b: min(a, b)
h = lambda a, b: min(a, b)
ti = 0
ei = float('inf')

lst1 = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)
lst2 = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)
ans = 0
for d, x in zip(D, X):
    if d == 1:
        y = lst1.query(x, x + 1)
        ans += y - 2
        lst2.update(1, y, x)
    else:
        y = lst2.query(x, x + 1)
        ans += y - 2
        lst1.update(1, y, x)
ans = (N - 2)**2 - ans
print(ans)

Solution (Python):
import bisect
import sys
input = sys.stdin.readline
def solve():
  N, Q = map(int, input().split())
  Qs = []
  for _ in range(Q):
    i, q = map(int, input().split())
    Qs.append((i - 1, q))
  
  M = (N-2) ** 2
  

  current_mins = [[(-N, N)], [(-N, N)]]
  for i, q in Qs:
    other_min = -current_mins[not i][-1][0]
    j = bisect.bisect(current_mins[i], (-q, other_min))
    
    if j == 0:
      m = other_min - 2
    else:
      m = current_mins[i][j-1][1] - 2
    if j == len(current_mins[i]):
      current_mins[i].append((-q, other_min))
      current_mins[not i][-1] = (current_mins[not i][-1][0], q)

    M -= m
    
  print(M)
  
solve()