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:

    __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
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> 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
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> 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

        # 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
        i = l0
        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
        i = r0
        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 folded(self, l, r):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> 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
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> 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

        # 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)

import sys
input = sys.stdin.readline
def fmo(m1, o1):
    if o1 == -1:
        return m1
    return o1
def foo(o1, o2):
    if o2 == -1:
        return o1
    return o2
        

n, q = map(int, input().split())
ans = (n-2)*(n-2)
h = n-2
w = n-2
LR = LazySegmentTree([-2]*n, h, -1, min, fmo, foo)
DU = LazySegmentTree([-2]*n, w, -1, min, fmo, foo)
for _ in range(q):
    t, x = map(int, input().split())
    x -= 1
    if t == 1:
        temp = LR.folded(x, x+1)
        if temp == -2:
            ans -= h
            LR.effect(x+1, w+1, h)
            w = x-1
        else:
            ans -= temp
    else:
        temp = DU.folded(x, x+1)
        if temp == -2:
            ans -= w
            DU.effect(x+1, h+1, w)
            h = x-1
        else:
            ans -= temp
print(ans)

Submission status: Accepted

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

area_W = N - 2
area_H = N - 2

walls_H = []
walls_V = []

count = (N - 2) * (N - 2)

# search smallest i ( s <= i < e ) such that f(i) == True
def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

for _ in range(Q):
	q, i = input().split()
	i = int(i) - 2
	if q == "1":
		if i < area_W:
			area_W = i
			count -= area_H
			walls_H.append((i, area_H))
		else:
			j = bisearch_smallest(lambda j: walls_H[j][0] < i, 0, len(walls_H))
			count -= walls_H[j][1]
	else:
		if i < area_H:
			area_H = i
			count -= area_W
			walls_V.append((i, area_W))
		else:
			j = bisearch_smallest(lambda j: walls_V[j][0] < i, 0, len(walls_V))
			count -= walls_V[j][1]

#print(area_W, area_H)
print(count)

Submission status: Accepted

Solution code:
class F:
    def __init__(self, x):
        self.bit = x
        for i in range(len(x)):
            j = i | (i + 1)
            if j < len(x):
                x[j] += x[i]
    def update(self, idx, x):
        while idx < len(self.bit):
            self.bit[idx] += x
            idx |= idx + 1
    def query(self, end):
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x
    def findkth(self, k):
        idx = -1
        for d in reversed(range(len(self.bit).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(self.bit) and k >= self.bit[right_idx]:
                idx = right_idx
                k -= self.bit[idx]
        return idx + 1
import sys
z=sys.stdin.readline
y=lambda:map(int,z().split())
n,q=y()
v=F([0]*(n-2))
h=F([0]*(n-2))
w=j=n-2
s=0
for _ in range(q):
    a,b=y()
    if a<2:
        if b-2<w:h.update(n-2-j,w-b+2);w=b-2
        s+=n-2-v.query(n-b)
    else:
        if b-2<j:v.update(n-2-w,j-b+2);j=b-2
        s+=n-2-h.query(n-b)
print((n-2)*(n-2)-s)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

class SegTree:
  def segfunc(self, x, y):
    return min(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      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 + 1:
      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

lseg = SegTree(N, N, [N] * N)
useg = SegTree(N, N, [N] * N)
res = (N - 2) * (N - 2)
for _ in range(Q):
  q, x = map(int, input().split())
  x -= 1
  if q == 1:
    u = useg.query(x, N)
    res -= u - 2
    l = lseg.query(u - 1, u)
    lseg.update(u - 1, min(l, x + 1))
    #print(res, u, "u", x)
  else:
    l = lseg.query(x, N)
    res -= l - 2
    u = useg.query(l - 1, l)
    useg.update(l - 1, min(u, x + 1))
    #print(res, l, "l", x)
print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
N, Q = map(int, input().split())

ans = 0
tate = [[-N, N-2]]
tateL = 1
yoko = [[-N, N-2]]
yokoL = 1
ans = (N-2) * (N-2)
for _ in range(Q):
    s, x = input().split()
    x = int(x)
    if s == '1':
        idx = bisect_left(tate, [-x, 0])
        ans -= tate[idx-1][1]
        if idx == tateL:
            tate.append([-x, tate[idx-1][1]])
            tateL += 1
            yoko[-1][1] = x - 2
    else:
        idx = bisect_left(yoko, [-x, 0])
        ans -= yoko[idx-1][1]
        if idx == yokoL:
            yoko.append([-x, yoko[idx-1][1]])
            yokoL += 1
            tate[-1][1] = x - 2
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

class segtree():#seg=segtree(A),単位元とsegfuncを指定すること
    def __init__(self,A,ide=1000000000):#単位元とsegfuncを指定すること
        n=len(A)
        num=2**(n-1).bit_length()#n以上の最小の2のべき乗
        seg=[ide]*(2*num-1)
        segfunc=self.segfunc
        self.ide,self.n,self.num,self.seg = ide, n, num, seg
        for i in range(n): seg[i+num-1]=A[i]#setvalue
        for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])#build
    
    def segfunc(self,x,y):return min(x,y) #seg木の基本関数
    
    def update(self,k,x):#Aのk番目の要素をxに置き換える,計算量log(N)
        k += self.num-1
        seg,segfunc=self.seg,self.segfunc
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
    def query(self,p,q):#区間[p,q)の累積segfuncを求める,計算量log(N)
        if q<=p: return self.ide
        num,segfunc,seg=self.num,self.segfunc,self.seg
        p += num-1; q += num-2
        res=self.ide
        while q-p>1:
            if p&1 == 0: res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p,q = p//2, (q-1)//2
        if p == q: res = segfunc(res,seg[p])
        else: res = segfunc(segfunc(res,seg[p]),seg[q])
        return res 
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, Q = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(Q)) #改行行列

    tot=(N-2)*(N-2)
    seg1=segtree([N]*(N+1))
    seg2=segtree([N]*(N+1))
    l1=[N]*(N+1)
    l2=[N]*(N+1)
    for t,x in S:
        if t==1:
            place=seg2.query(x,N+1)
            tot-=place-2
            l1[place]=min(l1[place],x)
            seg1.update(place,l1[place])
        else:
            place=seg1.query(x,N+1)
            tot-=place-2
            l2[place]=min(l2[place],x)
            seg2.update(place,l2[place])
        #printe(place,l1)
    print(tot)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]


class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = self.op(x,self.node[k])
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res
    
def smin(a,b):
    if a>b:
        return b
    else:
        return a

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

    ST1 = SegmentTree([N-2]*(N-2),smin,N-2)
    ST2 = SegmentTree([N-2]*(N-2),smin,N-2)

    ans = 0
    for i in range(Q):
        a,b = list(map(int,input().split()))
        b-=2
        if a==1:
            c = ST1.get(b,N-3)
            ans+=c
            ST2.substitute(c-1,b)
        else:
            c = ST2.get(b,N-3)
            ans+=c
            ST1.substitute(c-1,b)
        #print(ans)
        #print(*[ST1.get_one((i)) for i in range(N-2)])
        #print(*[ST2.get_one((i)) for i in range(N-2)])


    print((N-2)**2 - ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from itertools import accumulate
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def solve(N,queries):
    N -= 2
    X = [0]*(N+1)
    Y = [0]*(N+1)

    for a,b in queries:
        if b == 0:
            continue
        if a == 0:
            X[b] += 1
        else:
            Y[b] += 1
    X = tuple(accumulate(X))
    Y = tuple(accumulate(Y))
    w = N
    h = N

    res = 0
    for a,b in queries:
        # print('i',a,b)
        b -= 1
        if a == 0:
            if w > b:
                # print(X[w]-X[b],h)
                res += (X[w]-X[b])*h
                w = b
        else:
            if h > b:
                # print((Y[h]-Y[b]),w)
                res += (Y[h]-Y[b])*w
                h = b
    return N*N - res



if __name__ == '__main__':
    N,Q = map(int, readline().split())
    m = map(lambda x: int(x)-1, read().split())

    queries = tuple(zip(m,m))

    print(solve(N,queries))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
ans = (N - 2) * (N - 2)

n = N - 2
fixed1 = [-1] * (N + 1)
fixed2 = [-1] * (N + 1)

cand1 = n
cand2 = n

ans = 0
for _ in range(Q):
    x, y = map(int, input().split())
    y -= 1
    if x == 1:
        if fixed1[y] != -1:
            ans += fixed1[y]
        else:
            ans += cand1
            for i in range(y + 1, n + 1):
                if fixed1[i] != -1:
                    break
                fixed1[i] = cand1
            cand2 = min(cand2, y - 1)
    else:
        if fixed2[y] != -1:
            ans += fixed2[y]
        else:
            ans += cand2
            for i in range(y + 1, n + 1):
                if fixed2[i] != -1:
                    break
                fixed2[i] = cand2
            cand1 = min(cand1, y - 1)

print(n * n - ans)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
query=[list(input().split()) for _ in range(q)]
from bisect import bisect_right as bl
ax=[-n]
vx=[n-2]
ay=[-n]
vy=[n-2]
ans=(n-2)**2
for t,i in query:
  i=int(i)
  if t=='1':
    idx=bl(ax,-i)
    if idx==len(ax):
      ax.append(-i)
      vx.append(vx[-1])
      vy[-1]=i-2
    ans-=vx[idx-1]
  else:
    idx=bl(ay,-i)
    if idx==len(ay):
      ay.append(-i)
      vy.append(vy[-1])
      vx[-1]=i-2
    ans-=vy[idx-1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    examF()

def examA():
    S = SI()
    if S[-1]=="s":
        ans = S+"es"
    else:
        ans = S+"s"
    print(ans)
    return

def examB():
    N = I()
    D = [LI()for _ in range(N)]
    current = 0
    for d1,d2 in D:
        if d1==d2:
            current += 1
        else:
            current = 0
        if current==3:
            print("Yes")
            return
    print("No")
    return

def examC():
    N = I()
    cnt = 0
    for i in range(1,N):
        for j in range(1,1+N//i-(N%i==0)):
            cnt += 1
    ans = cnt
    print(ans)
    return

def examD():
    N, K = LI()
    LR = [LI()for _ in range(K)]
    dp = [0]*N
    S = [0]*N
    dp[0] = 1
    S[0] = 1
    for i in range(1,N):
        cur = 0
        for l,r in LR:
            if i<l:
                continue
            cur += S[i-l]
            if i<r+1:
                continue
            cur -= S[i-r-1]
            cur += mod2
            cur %= mod2

        dp[i] = cur
        S[i] = S[i-1] + cur
        S[i] %= mod2

    ans = dp[-1]
    print(ans)
    return

def examE():
    N, X, M = LI()
    cnt = 0
    L = []
    used = [-1]*(M+1)

    for i in range(N):
        used[X] = i
        L.append(X)
        cnt += X
        X = pow(X,2,M)
        if X==1 or X==0:
            cnt += (N-i-1)*X
            break
        if used[X]>=0:
            loop = i - used[X] + 1
            S = sum(L[used[X]:i+1])
            rest = N-i-1
            cnt += (rest//loop) * S + sum(L[used[X]:used[X]+rest%loop])
            break
    #print(L)
    #print(used)
    ans = cnt
    print(ans)
    return
def examF():
    # 区間加算、上書き、一点取得
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            #####単位元######要設定0or1orinf
            self.ide_ele = ele
            self.segfun = segfun
            ####################
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2

        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret
    N, Q = LI()
    SH = SegmentTree(N,N-2,lambda a, b: min(a,b))
    SW = SegmentTree(N,N-2,lambda a, b: min(a,b))
    cnt = 0
    for q in range(Q):
        t, x = LI()
        if t==1:
            up_w_0 = SH.query(x - 2)
            cnt += up_w_0
            SW.update(0, up_w_0, x - 2)
            #print(q,up_w_0)
        elif t==2:
            left_h_0 = SW.query(x-2)
            cnt += left_h_0
            SH.update(0,left_h_0,x-2)
            #print(q,left_h_0,x-2)
        #print(cnt)
    #print(cnt)
    ans = (N-2)**2 - cnt
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
10 4 6 
"""

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
Query = [list(map(int, input().split())) for _ in range(Q)]
ans = 0

for T in range(1, 3):
    Depth = [N-2]*N
    left = N
    up = N-2
    for t, x in Query:
        if t == T:  # |
            if left < x:
                ans += Depth[x]
            else:
                for i in range(x, left):
                    Depth[i] = up
                left = x
                ans += up
        else:  # -
            up = min(up, x-2)
        #print(f"ans={ans}, up={up}")
    #print("---")

print((N-2)**2-ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    def f(self,i):
        return self.sum(i,i+1)
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

ly,lx=N-1,N-1
by,bx=RangeBIT(N),RangeBIT(N)
ans=0
for _ in range(Q):
    a,x=map(int1,input().split())
    if a==0:
        if x>lx:
            res=bx.f(x)
            ans+=res
        else:
            ans+=ly-1
            bx.add(x,lx,ly-1)
            lx=x
    else:
        if x>ly:
            res=by.f(x)
            ans+=res
        else:
            ans+=lx-1
            by.add(x,ly,lx-1)
            ly=x
print((N-2)**2-ans)

Submission status: Accepted

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

class Dualsegtree:
    def __init__(self, A, intv, initialize = True):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
    
    def segf(self, a, b):
        return min(a, b)
    
    def query(self, k):
        k += self.N0
        s = self.data[k]
        while k > 0:
            k >>= 1
            s = self.segf(s, self.data[k])
        return s
    
    def update(self, l, r, x):
        L, R = l+self.N0, r+self.N0
        while L < R:
            if R & 1:
                R -= 1
                self.data[R] = x
            if L & 1:
                self.data[L] = x
                L += 1
            L >>= 1
            R >>= 1

N, Q = map(int, readline().split())
INF = 10**9+7
H, W = Dualsegtree([N-1]*(N-1), INF, initialize = True), Dualsegtree([N-1]*(N-1), INF, initialize = True)

ans = 0


mw = N
mb = N

for _ in range(Q):
    t, x = map(int, readline().split())
    x -= 1
    if t == 1:
        st = H.query(x)
        ans += st-1
        if mw > x:
            mw = x
            W.update(0, st, x)
    else:
        st = W.query(x)
        ans += st-1
        if mb > x:
            mb = x
            H.update(0, st, x)
print((N-2)*(N-2)-ans)

Submission status: Accepted

Solution code:
n, Q = [int(i) for i in input().split(" ")]
deepx = [-1] * (n-2)
deepy = [-1] * (n-2)
queries = [[0, 0] for i in range(Q)]
for i in range(Q):
  queries[i] = [int(j) for j in input().split(" ")]

curx = n-2
cury = n-2
ans = 0

for q in queries:
  d = q[0]
  pos = q[1]-2
  if d == 1:
    if curx < pos:
      ans += deepx[pos]
    else:
      ans += cury
      for i in range(pos+1, curx):
        deepx[i] = cury
      curx = pos
  else:
    if cury < pos:
      ans += deepy[pos]
    else:
      ans += curx
      for i in range(pos+1, cury):
        deepy[i] = curx
      cury = pos
  # print("curx", curx)
  # print("cury", cury)
  # print("ans", ans)
print((n-2)**2-ans)