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:
class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(l, r, x): 区間[l, r)をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [None] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2 * i] = v
            self.lazy[2 * i + 1] = v
            self.data[2 * i] = v
            self.data[2 * i + 1] = v
            self.lazy[i] = None

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = x
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


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

        res = self.ide_ele

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

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

ide_ele =  10**9


N, Q = map(int, input().split())
ans = (N-2)*(N-2)
R = [N]*(N+1)
W = [N]*(N+1)
seg_r = LazySegmentTree(R, segfunc, ide_ele)
seg_w = LazySegmentTree(W, segfunc, ide_ele)
for i in range(Q):
    a, b = map(int, input().split())
    if a == 1:
        t = seg_r.query(b, b+1)
        ans -= max(0, t - 2)
        if b <= seg_w.query(1, 2):
            seg_w.update(1, t+1, b)
        seg_r.update(b, b+1, 0)
    else:
        t = seg_w.query(b, b+1)
        ans -= max(0, t - 2)
        if b <= seg_r.query(1, 2):
            seg_r.update(1, t+1, b)
        seg_w.update(b, b+1, 0)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ###
    class LazySegmentTree:
        
        __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]
    
        def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
            self.me = monoid_identity
            self.oe = operator_identity
            self.fmm = func_monoid_monoid
            self.fmo = func_monoid_operator
            self.foo = func_operator_operator
    
            self.n = len(monoid_data)
            self.data = monoid_data * 2
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
            self.lazy = [self.oe] * (self.n * 2)
            
    
        def replace(self, index, value):
            index += self.n
    
            # propagation
            for shift in range(index.bit_length()-1, 0, -1):
                i = index >> shift
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # update
            self.data[index] = value
            self.lazy[index] = self.oe
    
            # recalculation
            i = index
            while i > 1:
                i //= 2
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
    
    
        def effect(self, l, r, operator):
            l += self.n
            r += self.n
            
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
    
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # effect
            while l < r:
                if l % 2:
                    self.lazy[l] = self.foo(self.lazy[l], operator)
                    l += 1
                if r % 2:
                    r -= 1
                    self.lazy[r] = self.foo(self.lazy[r], operator)
                l //= 2
                r //= 2
    
            # recalculation
            for i in indices:
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
                
            
        def folded(self, l, r):
            l += self.n
            r += self.n
    
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
            
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # fold
            left_folded = self.me
            right_folded = self.me
            while l < r:
                if l % 2:
                    left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                    l += 1
                if r % 2:
                    r -= 1
                    right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
                l //= 2
                r //= 2
            return self.fmm(left_folded, right_folded)
        
    ####




    mod=10**9+7
    N,Q=MI()
    
    monoid_data=[N-1]*N
    def fmm(m1, m2):
        return min(m1,m2)
    def fmo(m1,o1):
        return min(m1,o1)
    def foo(o1,o2):
        return min(o1,o2)
    
    inf=10**6
    seg_row=LazySegmentTree(monoid_data, inf, inf, fmm, fmo, foo)#横向きに伸びる白のラインを管理，次の白は何列目？
    seg_col=LazySegmentTree(monoid_data, inf, inf, fmm, fmo, foo)
 
    bl=(N-2)*(N-2)
    
    for _ in range(Q):
        q,x=MI()
        x-=1
        if q==1:
            row=seg_row.folded(x,x+1)
            bl-=row-1
            seg_col.effect(0,row,x)
            
        else:
            col=seg_col.folded(x,x+1)
            bl-=col-1
            seg_row.effect(0,col,x)
            
    print(bl)
            
            

main()

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
ANS = (N-2)**2
R,C=N,N
RLEN=[]
CLEN=[]
for i in range(Q):
    RC,num = map(int, input().split())
    if RC==1:
        if R>num:
            for j in range(R-num):
                RLEN.append(C)
            ANS-=C-2
            R=num
        else:
            if len(RLEN)>0:
                ANS-=RLEN[N-num-1]-2
            else:
                ANS-=R-2
    else:
        if C>num:
            for j in range(C-num):
                CLEN.append(R)
            ANS-=R-2
            C=num
        else:
            if len(CLEN)>0:
                ANS-=CLEN[N-num-1]-2
            else:
                ANS-=C-2

print(ANS)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(q)]
INF = 10 ** 9

ver = [-1] * (n + 1)
hor = [-1] * (n + 1)
ver[-1] = INF
hor[-1] = INF
ver_base = n - 1
hor_base = n - 1

white = 2 * n - 1
for num, x in query:
    if num == 1:
        if ver[x] == -1:
            white += ver_base
            i = x
            while ver[i] == -1:
                ver[i] = ver_base
                i += 1

        else:
            white += ver[x]

        hor_base = min(hor_base, x - 1)

    else:
        if hor[x] == -1:
            white += hor_base
            i = x
            while hor[i] == -1:
                hor[i] = hor_base
                i += 1

        else:
            white += hor[x]

        ver_base = min(ver_base, x - 1)

stone_sum = (n - 2) * (n - 2) + 2 * n - 1 + q
ans = stone_sum - white
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, q = LI()
    v = [n] * n
    h = [n] * n
    c = n
    r = n
    ans = 0
    for _ in range(q):
        q, x = LI()
        if q == 1:
            if c < x:
                ans += v[x] - 2
            else:
                ans += r - 2
                for i in range(x, c):
                    v[i] = r
                c = x
        else:
            if r < x:
                ans += h[x] - 2
            else:
                ans += c - 2
                for i in range(x, r):
                    h[i] = c
                r = x
    print((n - 2) ** 2 - ans)
    return


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

Submission status: Accepted

Solution code:
N, Q = map(int,input().split())
HW = [N, N]
ans = (N - 2) ** 2
L_HW = [[N - 2 for i in range(N)] for j in range(2)]
for _ in range(Q):
    vh, x = map(int,input().split())
    vh -= 1
    if x > HW[1 - vh]:
        ans -= L_HW[1 - vh][x]
    else:
        L_HW[1 - vh][x+1:HW[1 - vh]] = [HW[vh]-2] * (HW[1 - vh]-x-1)
        HW[1 - vh] = x
        ans -= HW[vh] - 2
print(ans)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
Min_x = [-1 for _ in range(N)] #一番遠い位置にある黒(0index)
#Min_x[N-1] = -1
Min_y = [-1 for _ in range(N)] #一番遠い位置にある黒(0index)
#Min_y[N-1] = -1
black = (N-2)**2
a = N-2; b = N-2 #左上の四角の部分
for query in range(Q):
  #print(black)
  temp = list(map(int,input().split()))#1index #x-=1 #0index
  if temp[0] == 1: #上に置く
    w = temp[1]-1 #0index
    if w <= b:
      #左上の更新する四角の中の場合、更新前の値が裏返りに使われる。
      black -= a #一番遠い黒-1 (0行目にはない）裏返る。0indexなのでそのまま引いてよい。
      for yoko in range(w,b+1): #w~bまで
        Min_y[yoko] = a
      b = w-1
    else:
      #既に更新する四角から外れている場合には既存の値を入れる。
      black -= Min_y[w] #一番遠い黒-1 (0行目にはない）裏返る。0indexなのでそのまま引いてよい。
  else: #横に置く
    h = temp[1]-1 #0index
    if h <= a:
      #左上の更新する四角の中の場合、更新前の値が裏返りに使われる。
      black -= b #一番遠い黒-1 (0行目にはない）裏返る。0indexなのでそのまま引いてよい。
      #print(h,a)
      for tate in range(h,a+1): #w~bまで
        Min_x[tate] = b
      a = h-1
    else:
      #既に更新する四角から外れている場合には既存の値を入れる。
      black -= Min_x[h] #一番遠い黒-1 (0行目にはない）裏返る。0indexなのでそのまま引いてよい。      
  #print("x",Min_x)
  #print("y",Min_y)
  #print("black", black)
print(black)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(SOLVE_PARAMS):
    pass


def main():
    from bisect import bisect_left
    N, Q = map(int, input().split())
    ret = (N - 2) ** 2
    xs = [-N]
    xvals = [N - 2]
    ys = [-N]
    yvals = [N - 2]
    for _q in range(Q):
        q, x = map(int, input().split())
        if q == 1:
            i = bisect_left(xs, -x)
            ret -= xvals[i - 1]
            if i == len(xs) and yvals[-1] > x - 2:
                ys.append(-xvals[i - 1] - 2)
                yvals.append(x - 2)
        else:
            y = x
            i = bisect_left(ys, -y)
            ret -= yvals[i - 1]
            if i == len(ys) and xvals[-1] > y - 2:
                xs.append(-yvals[i - 1] - 2)
                xvals.append(y - 2)

    print(ret)


# tests
T1 = """
5 5
1 3
2 3
1 4
2 2
1 2
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
200000 0
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
39999200004
"""

T3 = """
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
"""
_TEST_T3 = """
>>> as_input(T3)
>>> main()
31159505795
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
INF = 10**18

class BITmin():
    def __init__(self, max):
        self.max = max
        self.data = [self.max-1]*(self.max+1)
    
    # 上に登ってく
    def query_min(self, i):
        s = INF
        while i <= self.max:
            if s > self.data[i]:
                s = self.data[i]
            i += i & -i
        return s

    # iまで全ての要素をxで更新
    def update(self, i, x):
        while i > 0:
            if x < self.data[i]:
                self.data[i] = x
            # i += i & -i
            i -= i & -i

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
Query = [list(map(int, input().split())) for _ in range(Q)]

BitX = BITmin(N)
BitY = BITmin(N)

ans = (N-2)*(N-2)
for a, b in Query:
    b -= 1
    if a == 1:
        loc = BitX.query_min(b)
        ans -= loc-1
        BitY.update(loc, b)
    else:
        loc = BitY.query_min(b)
        ans -= loc-1
        BitX.update(loc, b)
    
print(ans)

Submission status: Accepted

Solution code:
def segfunc(x,y):return min(x,y)
ide_ele=10**18
class segtree():
  def __init__(self,init_val,segfunc=segfunc,ide_ele=ide_ele):
    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+=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):
    res=self.ide_ele
    l+=self.num
    r+=self.num+1
    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())
stx=segtree([ide_ele]*n)
sty=segtree([ide_ele]*n)
stx.update(n-1,n-2)
sty.update(n-1,n-2)
ans=(n-2)*(n-2)
for _ in range(q):
  x,y=map(int,input().split())
  if x==1:
    x=stx.query(y-1,n)
    ans-=x
    sty.update(x,min(y-2,sty.query(x,n)))
  else:
    x=sty.query(y-1,n)
    ans-=x
    stx.update(x,min(y-2,stx.query(x,n)))
print(ans)

Submission status: Accepted

Solution code:
def f(i, m, cnt):
    while True:
        if i > n or not cnt[i] == inf:
            return
        cnt[i] = m
        i += 1

n, q = map(int, input().split())
inf = n + 114514
ans = (n - 2) * (n - 2)
cnt1, cnt2 = [inf] * (n + 1), [inf] * (n + 1)
max1, max2 = n - 2, n - 2
for _ in range(q):
    t, x = map(int, input().split())
    if t == 1:
        if cnt1[x] == inf:
            ans -= max2
            max1 = x - 2
            f(x, max2, cnt1)
        else:
            ans -= cnt1[x]
    else:
        if cnt2[x] == inf:
            ans -= max1
            max2 = x - 2
            f(x, max1, cnt2)
        else:
            ans -= cnt2[x]
print(ans)

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
que=[list(map(int,input().split())) for i in range(q)]

ide_ele = 2000000000
def segfunc(x, y):
    return min(x,y)
class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        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):
        # param k: index(0-index)
        # param 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) 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
al = [n for i in range(n)]
seg1 = SegTree(al, segfunc, ide_ele)
seg2 = SegTree(al, segfunc, ide_ele)
sm = 0
for q in que:
    x=q[1]
    if q[0]==1:
        num = seg1.query(x,n+1)
        sm+=num-2
        if x < seg2.query(num, num+1):
            seg2.update(num,x)
    else:
        num = seg2.query(x,n+1)
        sm+=num-2
        if x < seg1.query(num, num+1):
            seg1.update(num,x)

print((n-2)*(n-2) - sm)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

class SegTree():
    """
    0-indexedの配列[a0, a1, a2, ..., a(N-1)]に対して以下のクエリをそれぞれO(logx)で行う：
        1. i番目の要素にxを代入
        2. 半開区間[i, j)内の最小値を返す
    self.id_elemとself.funcを変えることでRmQ以外にも例えばRMQに対応可能。
    参考：https://juppy.hatenablog.com/entry/2019/05/02/蟻本_python_セグメント木_競技プログラミング_Atcoder
    """
    def __init__(self, N):
        #####identity element######
        self.id_elem = 10**10
        self.func = min

        #num_max: the smallest power of two over N
        self.num_max = 2 ** ((N - 1).bit_length())
        self.x = [self.id_elem] * (2 * self.num_max - 1)

    def get_elem(self, i):
        """
        i番目の要素を返す
        """
        return self.x[self.num_max + i - 1]

    def update(self, i, x):
        """
        i番目の要素にxを代入
        """
        i += self.num_max - 1
        self.x[i] = x
        while (i > 0):
            i = (i - 1) // 2
            self.x[i] = self.func(self.x[i * 2 + 1], self.x[i * 2 + 2])

    def query(self, i=0, j=-1, k=0, l=0, r=-1):
        """
        半開区間[i, j)内の最小値を返す
        [l, r)はノードkに対応づく区間を与える
        query()で配列全体に対してクエリを実行する
        """
        if j == -1: j = self.num_max
        if r == -1: r = self.num_max

        # [i, j) and [l, r) are disjoint
        if (r <= i or j <= l): return self.id_elem
        # [l, r) is included in [i, j)
        if (i <= l and r <= j): return self.x[k]
        # [i, j] and [l, r) partially intersect
        vl = self.query(i, j, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(i, j, k * 2 + 2, (l + r) // 2, r)
        return self.func(vl, vr)

def main():
    N, Q = map(int, input().split())
    black = (N - 2) * (N - 2)
    """
    クエリの管理にセグ木をどう使うかわからず止まってしまった。。。
    （区間minをとるのにどこからどこまでの区間を取るか効率的に取得する方法がわからなかった）

    結論としては自分自身の位置から「末尾まで」のminを取れば良い。
    というのも白マスの取れる個数はjの位置に対して単調増加だから。
    """
    tree_width = SegTree(N)
    tree_height = SegTree(N)
    tree_width.update(N - 2, N - 2)
    tree_height.update(N - 2, N - 2)
    reversed = 0
    for _ in range(Q):
        q, x= map(int, input().split())
        x -= 1
        if q == 1:
            new_reversed = tree_width.query(x, N)
            if tree_height.query(new_reversed, N) > x - 1:
                tree_height.update(new_reversed, x - 1)
        else:
            new_reversed = tree_height.query(x, N)
            if tree_width.query(new_reversed, N) > x - 1:
                tree_width.update(new_reversed, x - 1)
        reversed += new_reversed
    print((N - 2) * (N - 2) - reversed)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

row = [N - 2] * (N + 2)
col = [N - 2] * (N + 2)
ans = (N - 2)**2

miRow = N
miCol = N

for _ in range(Q):
    q, x = map(int, input().split())

    if q == 1:
        for i in range(x, miRow + 1):
            row[i] = min(row[i], miCol - 2)
        miRow = min(x, miRow)
        ans -= row[x]

    if q == 2:
        for i in range(x, miCol + 1):
            col[i] = min(col[i], miRow - 2)
        miCol = min(x, miCol)
        ans -= col[x]

print(ans)

Submission status: Accepted

Solution code:
def search(L, x):
    low, high = 0, len(L)-1
    while low < high:
        mid = (low+high)//2
        if L[mid+1] < x < L[mid]:
            return mid
        elif x < L[mid+1]:
            low = mid+1
        else:
            high = mid
    return low

N, Q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(Q)]
B = [N-1]
Bv = [N-2]
R = [N-1]
Rv = [N-2]
ans = (N-2)**2
for f, x in query:
    x -= 1
    if f == 1:
        a = search(R, x)
        ans -= Rv[a]
        if R[-1] >= x:
            Bv[-1] = x-1
            R.append(x)
            Rv.append(Rv[-1])
    else:
        a = search(B, x)
        ans -= Bv[a]
        if B[-1] >= x:
            Rv[-1] = x-1
            B.append(x)
            Bv.append(Bv[-1])
    
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    
    left = top = N
    row, col = [N] * (N + 1), [N] * (N + 1)
    
    ans = (N - 2) ** 2
    for _ in range(Q):
        com, x = map(int, rl().split())
        if com == 1:
            if x < left:
                for i in range(x, left):
                    col[i] = top
                left = x
            ans -= col[x] - 2
        else:
            if x < top:
                for i in range(x, top):
                    row[i] = left
                top = x
            ans -= row[x] - 2
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.buffer.readline

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

    height, width = n, n
    mark1 = [0] * n
    mark2 = [0] * n
    ans = (n - 2) * (n - 2)

    for _ in range(q):
        typ, x = map(int, input().split())

        if typ == 1:
            if x < width:
                ans -= height - 2
                for i in range(x, width):
                    mark1[i] = height - 2
                width = x
            else:
                ans -= mark1[x]

        else:
            if x < height:
                ans -= width - 2
                for i in range(x, height):
                    mark2[i] = width - 2
                height = x
            else:
                ans -= mark2[x]

    print(ans)

main()

Submission status: Accepted

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

ans = (n-2)**2
rm = n
um = n
ruse = [-1]*(n+1)
uuse = [-1]*(n+1)

for _ in range(q):
    a,x = map(int,input().split())
    if a == 1:
        if uuse[x] >= 0:
            ans -= uuse[x]-2
        else:
            dif = um - 2
            ans -= dif
            for i in range(x,n+1):
                if uuse[i] >= 0:
                    break
                uuse[i] = um
            rm = min(rm,x)
    else:
        if ruse[x] >= 0:
            ans -= ruse[x]-2
        else:
            dif = rm - 2
            ans -= dif
            for i in range(x,n+1):
                if ruse[i] >= 0:
                    break
                ruse[i] = rm
            um = min(um,x)
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq



def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N, Q = LI()

    N0 = 2 ** (N-1).bit_length()

    stx = [N-1] * (N0*2)
    sty = [N-1] * (N0*2)

    def update(l,r,x,st):
        l += N0 - 1
        r += N0 - 1
        while l < r:
            st[l] = min(st[l],x)
            st[r] = min(st[r],x)

            l //= 2
            r = r // 2 - 1

        st[l] = min(st[l],x)

    def get_data(i,st):
        i += N0-1
        ret = N-1
        while i >= 0:
            ret = min(ret,st[i])
            i = (i-1) // 2
        return ret


    ans = (N-2) ** 2
    for _ in range(Q):
        c,p = LI()
        p -= 1
        if c == 1:
            s = get_data(p,sty)
            ans -= s - 1
            update(0,s-1,p,stx)
        else:
            s = get_data(p,stx)
            ans -= s - 1
            update(0,s-1,p,sty)

    print(ans)
if __name__ == '__main__':
    main()