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 = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        self.ls = [0]*(2*self.num-1)
        self.rs = [0]*(2*self.num-1)
        self.ls[0] = 0
        self.rs[0] = self.num
        for i in range(self.num-1):
            self.ls[2*i+1] = self.ls[i]
            self.rs[2*i+1] = (self.ls[i] + self.rs[i])//2
            self.ls[2*i+2] = (self.ls[i] + self.rs[i])//2
            self.rs[2*i+2] = self.rs[i]
        if a is not None:
            
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k]==f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            
            f = lambda y: x
        k = 0
        q = [k] 
        
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append(~k)
                    q.append(2*k+1)
                    q.append(2*k+2)
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [k]
        ans = ninf
        
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                q.append(2*k+2)
                q.append(2*k+1)

        return ans

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

ninf = 10**15
op = lambda x,y: min(x,y)
mapping = lambda f,x: min(f,x) if f is not None else x
def composition(f1,f2):
    if f1 is not None:
        if f2 is not None:
            return min(f1,f2)
        else:
            return f1
    else:
        return f2

f0 = None
sgr = LazySegmentTree(n-2, [n]*(n-2))
sgc = LazySegmentTree(n-2, [n]*(n-2))
ans = 0
for _ in range(q):
    t,x = map(int, input().split())
    x -= 2
    if t==1:
        v = sgc.query(x,x+1)
        ans += (v-2)
        sgr.update(0,v-2,f=x+2)
    else:
        v = sgr.query(x,x+1)
        ans += (v-2)
        sgc.update(0,v-2,f=x+2)

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

Solution (Python):
N,Q = map(int, input().split())
answer = (N-2)**2

q1 = [(N,N-2)]
q2 = [(N,N-2)]

def binary_search(q,n):
  left = 0
  right = len(q) - 1
  while right > left:
    index = (left + right) // 2
    if q[index+1][0] > n:
      left = index + 1
    else:
      right = index
  return left

for _ in range(Q):
  n,x = map(int, input().split())
  if n == 1:
    index = binary_search(q1,x)
    q = q1[index]
    answer -= q[1]
    if index == len(q1)-1:
      q1.append((x,q[1]))
      q2_last = q2[-1]
      q2[-1] = (q2_last[0],x-2)
  if n == 2:
    index = binary_search(q2,x)
    q = q2[index]
    answer -= q[1]
    if index == len(q2)-1:
      q2.append((x,q[1]))
      q1_last = q1[-1]
      q1[-1] = (q1_last[0],x-2)
      
print(answer)

Solution (Python):
from bisect import bisect

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

ans = (N-2)*(N-2)
wx = wy = 0
Ax = []
Ay = []

for _ in range(Q):
    t, p = map(int, input().split())
    p = N-p
    
    if t==1:
        i = bisect(Ax, (p, 0))
        if i==len(Ax):
            Ax.append((p, wy))
            wx = p
            rev = N-2-wy
        else:
            rev = N-2-Ax[i][1]
    else:
        i = bisect(Ay, (p, 0))
        if i==len(Ay):
            Ay.append((p, wx))
            wy = p
            rev = N-2-wx
        else:
            rev = N-2-Ay[i][1]

    ans -= rev

print(ans)