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



Sample input:
5 5
1 3
2 3
1 4
2 2
1 2


Sample output:
1

Submission status: Accepted

Solution code:
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)
  # 区間[l, r+1)の値をvに書き換える
  # vは(t, value)という値にする (新しい値ほどtは大きくなる)
  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
  # a_iの現在の値を取得
  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)

Submission status: Accepted

Solution code:
class LazySegTree:
    # RMQ and RUQ
    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

        # seg, lazy: 1-indexed
        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, r: 1-indexed
        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):
        # ids: 1-indexed
        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):
        # l, r: 0-indexed
        # change x to [l, r)
        *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:
            # i: 1-indexed
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])

    def query(self, l, r):
        # l, r: 0-indexed
        # query for [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 = sys.stdin.buffer.readline
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)
            #print(i+1, r)
            ans -= (r-1)
            if x < l:
                C.update(0, r+1, x)
                l = x
        else:
            c = C.query(x, x+1)
            #print(i+1, c)
            ans -= (c-1)
            if x < u:
                R.update(0, c+1, x)
                u = x

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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

    #[l, r] をxで更新
    def update(self,l,r,x):
        #[l, r)に変更
        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])

    #[l, r]のクエリに答える
    def query(self,l,r):
        #[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()

Submission status: Accepted

Solution code:
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):
        #set_val
        for i in range(len(init_val)):
            self.seg[i+self.num-1] = init_val[i]
        #built
        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)

Submission status: Accepted

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

# ACLに伴い0-indexedに直した
class Bit:  # Fenwick Tree と同じ
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, l, r):  # [l,r)の合計を求める
        # 内部的には[l+1,r+1)の合計つまり(rまでの合計-lまでの合計)
        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番目にxを足す
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# Bitの内部状態をindex順に出力
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

# print("A",[A.sum(0,i+1) for i in range(n)])
# print("B",[B.sum(0,i+1) for i in range(n)])
for i in range(q):
    c1 = C[i][1]-1
    if C[i][0] == 1:
        BC[c1] = 1
        if minbc > c1:
            # print(1,c1)
            minbc=c1
            # print("A",[A.sum(0,i+1) for i in range(n)])
            oku = B.sum(0,c1+1)
            # print("oku",oku)
            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))
            # print("A",[A.sum(0,i+1) for i in range(n)])
    elif C[i][0] == 2:
        AC[c1] = 1
        if minac > c1:
            # print(2,c1)
            minac = c1
            # print("B",[B.sum(0,i+1) for i in range(n)])
            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))

            # print("B",[B.sum(0,i+1) for i in range(n)])


# print("FINAL")
# print("A",[A.sum(0,i+1) for i in range(n)])
# print("B",[B.sum(0,i+1) for i in range(n)])
# print("AC",AC)
# print("BC",BC)
for i in range(1, n-1):
    if AC[i] == 0:
        # print(i,A.sum(i,i+1))
        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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

    # N: 処理する区間の長さ

    N0 = 2 ** (N - 1).bit_length()
    data1 = [None] * (2 * N0)
    data2 = [None] * (2 * N0)
    INF = (-1, 2 ** 31 - 1)
    # 区間[l, r+1)の値をvに書き換える
    # vは(t, value)という値にする (新しい値ほどtは大きくなる)
    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

    # a_iの現在の値を取得
    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()

Submission status: Accepted

Solution code:
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


# ------------------- fast io --------------------
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")

# ------------------- fast io --------------------
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
    #print(black, first_in_row, first_in_column)
    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:
            # go down
            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:
            # go right
            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, first_in_row, first_in_column)
    print(black)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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):  # build
            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):  # set value at position [a, b) (0-indexed)
        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):  # result on interval [a, b) (0-indexed)
        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)


#RSQ and RUQ
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)

Submission status: Accepted

Solution code:
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))
  #print(Qs)
  M = (N-2) ** 2
  #print(M)

  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))
    #print(i, q, j, current_mins)
    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)
  print(M)
  
solve()