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:
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

#####ide_ele#####
ide_ele = float('inf')
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


N, Q = map(int, input().split())
black = (N - 2) * (N - 2)
tate = [N - 1] * (N)
yoko = [N - 1] * (N)
seg_t = SegTree(tate, segfunc, ide_ele)
seg_y = SegTree(yoko, segfunc, ide_ele)
#2 - N - 1
for i in range(Q):
  x, y = map(int, input().split())
  if x == 1:
    xx = seg_t.query(y - 1, N)
    if seg_y.query(xx - 1, xx) > y - 1:
      seg_y.update(xx - 1, y - 1)
    black -= xx - 1
  else:#x == 2
    xx = seg_y.query(y - 1, N)
    if seg_t.query(xx - 1, xx) > y - 1:  
      seg_t.update(xx - 1, y - 1)
    black -= xx - 1
  
  
  #print(xx, black)
print(black)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
c = [(n - 1, -1)]
r = [(n - 1, -1)]
t = 0
for i in range(q):
    k, x = map(int, input().split())
    if k == 1:
        c.append((x - 1, t))
    else:
        r.append((x - 1, t))
        t += 1
c.sort()
r.sort()
idx = 0
ans = (len(c) - 1) * (r[0][0])
for i in range(len(r) - 1):
    x, t = r[i]
    tmp = idx
    while idx < len(c) and c[idx][1] > t:
        idx += 1
    ans += c[idx][0]
    ans += (len(c) - idx - 1) * (r[i + 1][0] - x)
print((n - 2) * (n - 2) - ans + len(c) + len(r) - 2)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

v_lay = [(-(n-1),n-2)]
h_lay = [(-(n-1),n-2)]

ans = (n-2)*(n-2)
for _ in range(q):
    case,lay_pos = map(int,input().split())
    
    ref_lay = (v_lay if case==1 else h_lay)
    
    index = bisect_right(ref_lay, (-lay_pos,n))
    _, lay = ref_lay[index-1]
    
    ans -= lay

    if index==len(ref_lay):
        ref_lay = (h_lay if case==1 else v_lay)
        laid_pos, num = ref_lay[-1]
        if laid_pos == -(lay+1):
            ref_lay[-1] = (-(lay+1), min(lay_pos-2,num))
        else:
            ref_lay.append((-(lay+1), lay_pos-2))
            
print(ans)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
yoko = [-n]
yoko2 = [-n]
yokol = 1
tate = [-n]
tate2 = [-n]
tatel = 1
last = [n,n]
import bisect
ans = (n-2)**2
#print(ans)
for _ in range(q):
  a,c = map(int,input().split())
  if a == 1:
    b = bisect.bisect_left(yoko,-c)
    if b == yokol:
      yoko.append(-c)
      yoko2.append(-last[0])
      yokol += 1
      last[1] = c
      ans -= last[0]-2
    else:
      ans -= -yoko2[b] - 2
  if a == 2:
    b = bisect.bisect_left(tate,-c)
    if b == tatel:
      tate.append(-c)
      tate2.append(-last[1])
      tatel += 1
      last[0] = c
      ans -= last[1]-2
    else:
      ans -= -tate2[b] - 2
  #print(yoko)
  #print(yoko2)
  #print(tate)
  #print(tate2)
print(ans)

Submission status: Accepted

Solution code:
class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x

        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2 * self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i + self.size] = a

        for i in range(self.size - 1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log + 1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r - 1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r - 1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def __all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def __push(self, k):
        self.__all_apply(2 * k, self.lz[k])
        self.__all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.im()




def op(x,y):
    return x+y


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


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


def im():
    return 100000000000


def a():
    # https://atcoder.jp/contests/practice2/submissions/16842314
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())

    def e():
        return N - 2
    ans = (N-2) * (N-2)
    ssss = [N-2] * (N-1)
    st = LazySegmentTree(op, e, mapping, composition, im,ssss)
    sa = LazySegmentTree(op, e, mapping, composition, im,ssss)
    for _ in range(Q):
        t, l = map(int, input().split())
        if t == 1:
            t = st.__getitem__(l-1) + 1
            sa.apply(1, t, l-2)
            ans -= t-1
        else:
            t = sa.__getitem__(l-1) + 1
            st.apply(1, t, l-2)
            ans -= t-1
    print(ans)

if __name__ == "__main__":
    a()

Submission status: Accepted

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

N -= 2

BIT = [[0 for i in range(N+1)] for _ in range(2)]
n = N
def BIT_query(idx,BIT):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x,BIT):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

now = N * N
max_x = [0, 0]
for _ in range(Q):
  s, x = map(int, input().split())
  s -= 1
  x -= 1
  x = N+1 - x
  #print()
  depth = N + BIT_query(x, BIT[s])
  now -= depth
  #print(x, s, depth, now, BIT_query(x, BIT[s]), max_x[s])
  
  if x > max_x[s]:
    BIT_update(N-depth+1, max_x[s] - x, BIT[1-s])
    max_x[s] = x
    
print(now)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
ans = (N-2)**2
H = [N for i in range(N+1)]
W = [N for i in range(N+1)]

last_ignored_H= N
last_ignored_W=N

ignoredH = [False for i in range(N+1)]
ignoredH[N] = True

ignoredW=[False for i in range(N+1)]
ignoredW[N] = True

for i in range(Q):
    command ,where = map(int,input().split())
    if command == 1:
        
        if ignoredH[where] == True:
            ans -=H[where] - 2
            continue
            
        elif ignoredH[where] == False:
            H[where] = last_ignored_W
            ans -=H[where] - 2
            for j in range(where,last_ignored_H):
                ignoredH[j] = True
                H[j] = H[where]
            last_ignored_H = where
  
  
    else:
        
        if ignoredW[where] == True:
            ans -=W[where] - 2
            continue
        elif ignoredW[where] == False:   
            W[where] = last_ignored_H
            ans -=W[where] -2
            for j in range(where,last_ignored_W):
                ignoredW[j] = True
                W[j] = W[where]
            last_ignored_W = where
            
print(ans)

Submission status: Accepted

Solution code:
# Modified from https://raw.githubusercontent.com/cheran-senthil/PyRival/master/pyrival/data_structures/LazySegmentTree.py
class LazySegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the lazy segment tree with data"""
        self._default = default
        self._func = func

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        # Let the children know of the queries
        q, self._lazy[idx] = self._lazy[idx], 0

        self._lazy[2 * idx] = max(self._lazy[2 * idx], q)
        self._lazy[2 * idx + 1] = max(self._lazy[2 * idx + 1], q)
        self.data[2 * idx] = max(self.data[2 * idx], q)
        self.data[2 * idx + 1] = max(self.data[2 * idx + 1], q)

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            self.data[idx] = max(
                self._func(self.data[2 * idx], self.data[2 * idx + 1]), self._lazy[idx]
            )
            idx >>= 1

    def add(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] = max(self._lazy[start], value)
                self.data[start] = max(self.data[start], value)
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] = max(self._lazy[stop], value)
                self.data[stop] = max(self.data[stop], value)
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=0):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        # Apply all the lazily stored queries
        self._update(start)
        self._update(stop - 1)

        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)


def solve(N, Q, queries):
    N -= 2
    total = N * N
    rows = LazySegmentTree([0] * (N + 1), 0, max)
    cols = LazySegmentTree([0] * (N + 1), 0, max)
    for t, x in queries:
        assert x >= 2
        x -= 2
        if t == 1:
            c = x
            removed = N - cols.query(c, c + 1)
            assert removed >= 0
            total -= removed
            cols.add(c, c + 1, N)
            if removed:
                rows.add(0, removed, N - c)

        elif t == 2:
            r = x
            removed = N - rows.query(r, r + 1)
            assert removed >= 0
            total -= removed
            rows.add(r, r + 1, N)
            if removed:
                cols.add(0, removed, N - r)
    return total


if False:
    import random

    random.seed(0)
    for _ in range(100):
        print(_)
        N = random.randint(3, 10)
        queries = []
        for i in range(2, N):
            queries.append((1, i))
            queries.append((2, i))

        random.shuffle(queries)
        Q = random.randint(0, min(2 * N - 4, 10))
        queries = queries[:Q]
        print(queries)
        solve(N, len(queries), queries)


N, Q = [int(x) for x in input().split()]
queries = [[int(x) for x in input().split()] for i in range(Q)]

print(solve(N, Q, queries))

Submission status: Accepted

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

black = (n-2)**2
left_most = n-1
down_most = n-1

L = [n-2] * n
D = [n-2] * n

for _ in range(q):
  x,c = list(map(int,input().split()))
  c -= 1
  
  if x==1:
    if c<left_most:
      for j in range(c, left_most):
        D[j] = down_most - 1
     
      left_most = c
    black -= D[c]
 
  if x==2:
    if c<down_most:
      for j in range(c, down_most):
        L[j] = left_most - 1
      
      down_most = c
    black -= L[c]
    

  #print(black)
print(black)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def debug(N, st):
    print(*[st.query(i, i+1) for i in range(N)], sep=" ")

def solve(N, Q, Queries):
    from itertools import accumulate
    row = SegmentTreeLazy([float("inf")]*N, float("inf"), float("inf"), min, min, min)
    col = SegmentTreeLazy([float("inf")]*N, float("inf"), float("inf"), min, min, min)
    rmin = list(accumulate([N if c == 2 else x for c, x in Queries], min))
    cmin = list(accumulate([N if c == 1 else x for c, x in Queries], min))
    ans = 0
    def f(st, emin, i, step):
        st.update(i, N, step)
        idx = st.query(i, i+1)
        return emin[idx] - 2
    for step, (c, x) in enumerate(Queries):
        if c == 1:
            ans += f(row, cmin, x-1, step)
        else:
            ans += f(col, rmin, x-1, step)
    return (N-2)**2 - ans

# https://judge.yosupo.jp/submission/9146
class SegmentTreeLazy():
    def __init__(self, arr, ti, ei, func, op, merge):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.func = func
        self.op = op
        self.merge = merge
        self.ti = ti
        self.ei = ei
        self.val = [ti for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
        self.laz = [ei for _ in range(2 * self.n)]

    def reflect(self, k):
        if self.laz[k] == self.ei:
            return self.val[k]
        return self.op(self.val[k], self.laz[k])

    def propagate(self, k):
        if self.laz[k] == self.ei: return
        self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
        self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
        self.val[k] = self.reflect(k)
        self.laz[k] = self.ei

    def thrust(self, k):
        for i in range(1, self.h + 1)[::-1]:
            self.propagate(k >> i)

    def recalc(self, k):
        while k:
            k >>= 1
            self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        vl = lt
        vr = rt
        self.thrust(lt)
        self.thrust(rt - 1)
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.merge(self.laz[lt], x)
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.merge(self.laz[rt], x)
            lt >>= 1
            rt >>= 1
        self.recalc(vl)
        self.recalc(vr - 1)

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        self.thrust(lt)
        self.thrust(rt - 1)
        vl = vr = self.ti
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.reflect(lt))
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.reflect(rt), vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    N, Q = map(int, input().split())
    Queries = [list(map(int, input().split())) for _ in range(Q)]
    print(solve(N, Q, Queries))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl

N, Q = map(int, input().split())
ans = 0
q1 = []
q2 = []
query = []
for _ in range(Q):
    n, p = map(int, input().split())
    query.append((n, p))
    if n == 1:
        q1.append(p)
    else:
        q2.append(p)
q1.sort()
q2.sort()
board = [N - 2, N - 2]
count1 = len(q1)
count2 = len(q2)
for n, p in query:
    if n == 1:
        if p > board[1] + 1:
            continue
        index = bl(q1, p)
        ans += board[0] * (count1 - index)
        board[1] = p - 2
        count1 = index
    else:
        if p > board[0] + 1:
            continue
        index = bl(q2, p)
        ans += board[1] * (count2 - index)
        board[0] = p - 2
        count2 = index
print((N - 2) ** 2 - ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()

class LazySegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f # (X, X) -> X
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
            i >>= 1
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getrange(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        
        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
        
        self.calc_above(l0)
        self.calc_above(r0)
    
    # Find r s.t. calc(l, ..., r-1) = True and calc(l, ..., r) = False
    def max_right(self, l, z):
        if l >= self.n: return self.n
        l += self.n
        s = self.unitX
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.calc(l))):
                while l < self.n:
                    l *= 2
                    if z(self.f(s, self.calc(l))):
                        s = self.f(s, self.calc(l))
                        l += 1
                return l - self.n
            s = self.f(s, self.calc(l))
            l += 1
            if l & -l == l: break
        return self.n
    
    # Find l s.t. calc(l, ..., r-1) = True and calc(l-1, ..., r-1) = False
    def min_left(self, r, z):
        if r <= 0: return 0
        r += self.n
        s = self.unitX
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.calc(r), s)):
                while r < self.n:
                    r = r * 2 + 1
                    if z(self.f(self.calc(r), s)):
                        s = self.f(self.calc(r), s)
                        r -= 1
                return r + 1 - self.n
            s = self.f(self.calc(r), s)
            if r & -r == r: break
        return 0

f = lambda x, y: (x + y) 
g = lambda x, a, s: min(x,a)
h = lambda a, b: min(a,b)
unitX = 0
unitA = 10**10
N, Q = map(int, input().split())
A = [N-2]*(N-2)
sttate = LazySegmentTree(A, unitX, unitA, f, g, h)
styoko = LazySegmentTree(A, unitX, unitA, f, g, h)
ans=(N-2)**2
for _ in range(Q):
    q1,q2=map(int, input().split())
    if q1==1:
        horu=sttate.getrange(q2-2, q2-1)
        ans-=horu
        sttate.operate_range(q2-2,q2-1,0)
        styoko.operate_range(0,horu,q2-2)
    if q1==2:
        horu=styoko.getrange(q2-2, q2-1)
        ans-=horu
        styoko.operate_range(q2-2,q2-1,0)
        sttate.operate_range(0,horu,q2-2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


class Segtree_op():
    # 単位元及び操作を設定して使うこと
    # queryでは、区間の(l, r)を指定する ex: (0, 5) => [0, 1, 2, 3, 4]
    # 特定の1点は (i, i+1)
    def __init__(self, n):
        self.n = n

        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        # update min with holding index
        return min(lch, rch)

    def unit(self):
        return self.n

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def show(self):
        idx = 1
        while (idx <= self.size):
            print(self.arr[idx - 1:idx * 2 - 1])
            idx *= 2


def solve():
    n, q = getList()

    st_tate = Segtree_op(n)
    st_yoko = Segtree_op(n)

    reversed = 0
    for _ in range(q):
        op, idx = getList()
        if op == 1:
            border = st_tate.query(idx, n+1)
            reversed += border - 2
            val = min(st_yoko.query(border, border+1), idx)
            st_yoko.update(border, val)
        else:
            border = st_yoko.query(idx, n+1)
            reversed += border - 2
            val = min(st_tate.query(border, border + 1), idx)
            st_tate.update(border, val)

        # st_tate.show()
        # st_yoko.show()
        # print(reversed)
        # print("=========")

    print((n-2) ** 2 - reversed)








def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
import bisect
N,Q = map(int, input().split())
L = [0]*Q
L1 = []
L2 = []
for i in range(Q):
    a,b = map(int, input().split())
    L[i] = (a, b)
    if a == 1:
        L1.append(b)
    else:
        L2.append(b)

L1.sort()
L2.sort()
M1 = len(L1)
M2 = len(L2)
ans = (N-2)**2
up = N
left = N
for l in L:
    a = l[0]
    b = l[1]
    if a == 1:
        if b > left:
            continue
        idx = bisect.bisect_left(L1, b)
        ans -= (M1-idx)*(up-2)
        M1 = idx
        left = b
    else:
        if b > up:
            continue
        idx = bisect.bisect_left(L2, b)
        ans -= (M2-idx)*(left-2)
        M2 = idx
        up = b
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

hori_cnt = [n-2]*(n+2) # 2から

ql = []
for _ in range(q):
    c,x = map(int, input().split())
    ql.append((c,x))

tate_min = n
yoko_min = n
yoko_kyokai = []
ans1 = 0
for c,x in ql:
    if c == 1:
        if x < tate_min: 
            hori_cnt[yoko_min] = x-2
            yoko_kyokai.append(yoko_min*(-1))
            tate_min = x
    else:
        # print(c,x,'---------')
        if x < yoko_min:
            yoko_min = x
        # print(yoko_kyokai)
        ind = bisect_left(yoko_kyokai, x*(-1))-1
        # print(x,ind)
        if ind == -1:
            if x < yoko_min:
                ans1 += (tate_min-2)
            else:
                ans1 += (n-2)
            # print(tate_min-2,'++')
        else:
            val = yoko_kyokai[ind]
            ans1 += hori_cnt[val*(-1)]
            # print(hori_cnt[val*(-1)],'++s')


tate_cnt = [n-2]*(n+2) # 2から
yoko_min = n
tate_min = n
tate_kyokai = []
ans2 = 0
for c,x in ql:
    if c == 2:
        if x < yoko_min: 
            tate_cnt[tate_min] = x-2
            tate_kyokai.append(tate_min*(-1))
            yoko_min =x
            
    else:
        # print(c,x,'---------')

        if x < tate_min:
            tate_min = x

        ind = bisect_left(tate_kyokai, x*(-1))-1
        # print(tate_kyokai,'aaa')
        if ind == -1:
            if x < tate_min:
                ans2 += (yoko_min-2)
            else:
                ans2 += (n-2)
            # print(yoko_min-2,'+++')
        else:
            val = tate_kyokai[ind]
            ans2 += tate_cnt[val*(-1)]
            # print(tate_cnt[val*(-1)],'+++s')

print((n-2)*(n-2)-ans1-ans2)