Problem:
 Score : 600 points    Problem Statement There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i -th row from the top and the j -th column from the left.  Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it.
Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.  Q queries are given. We ask you to process them in order.
There are two kinds of queries. Their input format and description are as follows:   1 x : Place a white stone on (1, x) . After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x) , replace it with a white stone.  2 x : Place a white stone on (x, 1) . After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1) , replace it with a white stone.   How many black stones are there on the grid after processing all Q queries?      Constraints  3 \leq N \leq 2\times 10^5  0 \leq Q \leq \min(2N-4,2\times 10^5)  2 \leq x \leq N-1  Queries are pairwise distinct.         Input Input is given from Standard Input in the following format:  N  Q  Query_1  \vdots  Query_Q       Output Print how many black stones there are on the grid after processing all Q queries.        Sample Input 1 5 5
1 3
2 3
1 4
2 2
1 2      Sample Output 1 1  After each query, the grid changes in the following way:        Sample Input 2 200000 0      Sample Output 2 39999200004       Sample Input 3 176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282      Sample Output 3 31159505795

Solution (Python):


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

        
        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

        
        self.data[index] = value
        self.lazy[index] = self.oe

        
        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

        
        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

        
        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

        
        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

        
        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

        
        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)


def yosupo():
    import sys
    input = sys.stdin.buffer.readline

    whitened = 0
    N, Q = map(int, input().split())
    xs = LazySegmentTree([N - 2] * (N - 2), N - 2, N - 2, min, min, min)
    ys = LazySegmentTree([N - 2] * (N - 2), N - 2, N - 2, min, min, min)
    for _ in range(Q):
        t, x = map(int, input().split())
        x -= 2
        
        if t == 1:
            tmp = xs.folded(x, x + 1)
            ys.effect(0, tmp, x)
            whitened += tmp
        else:
            tmp = ys.folded(x, x + 1)
            xs.effect(0, tmp, x)
            whitened += tmp

        
        

    print((N - 2) ** 2 - whitened)

if __name__ == "__main__":
    yosupo()

Solution (Python):
import sys

input = sys.stdin.readline

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

row = [-1 for i in range(N+1)]
column = [-1 for i in range(N+1)]

R = N
C = N

res = (N-2)**2

for _ in range(Q):
    t,x = map(int,input().split())
    if t==1:
        if column[x]==-1:
            for i in range(x,N+1):
                if column[i] ==-1:
                    column[i] = R
                else:
                    break
            res -= column[x] - 2
        else:
            res -= column[x] - 2

        if x<=C:
            C = x
    else:
        if row[x]==-1:
            for i in range(x,N+1):
                if row[i] == -1:
                    row[i] = C
                else:
                    break
            res -= row[x] - 2
        else:
            res -= row[x] - 2

        if x<=R:
            R = x

    
    
    

print(res)

Solution (Python):
import sys
input=lambda:sys.stdin.readline().rstrip()


class LazySegmentTree:
  
  
  
  __slots__ = ["n", "seg", "x_unit", "m_unit", "f", "g", "h", "lazy"]

  def __init__(self, n, p, x_unit, m_unit, f, g, h):
    self.n = n
    self.seg = p*2
    self.x_unit = x_unit
    self.m_unit = m_unit
    self.f = f
    self.g = g
    self.h = h
    for i in range(self.n-1, 0, -1):
      self.seg[i] = self.f(self.seg[i<<1], self.seg[(i<<1)+1])
    self.lazy = [m_unit] * (self.n * 2)

  def update(self, l, r, x):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    while l < r:
      if l & 1:
        self.lazy[l] = self.h(self.lazy[l], x)
        l += 1
      if r & 1:
        r -= 1
        self.lazy[r] = self.h(self.lazy[r], x)
      l >>= 1
      r >>= 1
    while ll > 1:
      ll >>= 1
      self.seg[ll] = self.f(self.g(self.seg[ll << 1], self.lazy[ll << 1]), self.g(self.seg[(ll << 1)+1], self.lazy[(ll << 1)+1]))
      self.lazy[ll] = self.m_unit
    while rr > 1:
      rr >>= 1
      self.seg[rr] = self.f(self.g(self.seg[rr << 1], self.lazy[rr << 1]), self.g(self.seg[(rr << 1)+1], self.lazy[(rr << 1)+1]))
      self.lazy[rr] = self.m_unit

  def query(self, l, r):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    ans_l = ans_r = self.x_unit
    while l < r:
      if l & 1:
        ans_l = self.f(ans_l, self.g(self.seg[l], self.lazy[l]))
        l += 1
      if r & 1:
        r -= 1
        ans_r = self.f(self.g(self.seg[r], self.lazy[r]), ans_r)
      l >>= 1
      r >>= 1
    return self.f(ans_l, ans_r)

n,q=map(int,input().split())
def f(x,y):
  return min(x,y)
def g(x,y):
  return min(x,y)
def h(x,y):
  return min(x,y)
up_seg=LazySegmentTree(n-2,[n-2]*(n-2),n-2,n-2,f,g,h)
left_seg=LazySegmentTree(n-2,[n-2]*(n-2),n-2,n-2,f,g,h)
ans=(n-2)**2
for _ in range(q):
  i,x=map(int,input().split())
  x-=2
  if i==1:
    m=up_seg.query(x,x+1)
    ans-=m
    left_seg.update(0,m,x)
  else:
    m=left_seg.query(x,x+1)
    ans-=m
    up_seg.update(0,m,x)
print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
class SegmentTreeDual():
    def __init__(self, init, initX, unitA, g, h):
        self.g = g 
        self.h = h 
        self.unitA = unitA
        if type(init) == int:
            self.n = init
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [initX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [initX] * self.n + init + [initX] * (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.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    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 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
    
    def check(self, randX, randA, maxs, rep):
        from random import randrange
        for _ in range(rep):
            x = randX()
            a = randA()
            b = randA()
            c = randA()
            s = randrange(1, maxs + 1)
            err = 0
            if not h(a, unitA) == h(unitA, a) == a:
                err = 1
                print("!!!!! unitA Error !!!!!")
                print("unitA =", unitA)
                print("a =", a)
                print("f(a, unitA) =", f(a, unitA))
                print("f(unitA, a) =", f(unitA, a))
                
            if not h(h(a, b), c) == h(a, h(b, c)):
                err = 1
                print("!!!!! Associativity Error A !!!!!")
                print("a, b, c, h(a, b), h(b, c) =", a, b, c, h(a, b), h(b, c))
                print("h(h(a, b), c) =", h(h(a, b), c))
                print("h(a, h(b, c)) =", h(a, h(b, c)))
            
            if not g(x, unitA, s) == x:
                err = 1
                print("!!!!! Identity Error !!!!!")
                print("unitA, x, s =", unitA, x, s)
                print("g(x, unitA, s) =", g(x, unitA, s))
            
            if not g(g(x, a, s), b, s) == g(x, h(a, b), s):
                err = 1
                print("!!!!! Act Error !!!!!")
                print("x, a, b, s, g(x, a, s), h(a, b) =", x, a, b, s, g(x, a, s), h(a, b))
                print("g(g(x, a, s), b, s) =", g(g(x, a, s), b, s))
                print("g(x, h(a, b), s)    =", g(x, h(a, b), s))
            
            if err:
                break
                assert h(a, unitA) == h(unitA, a) == a
                assert h(h(a, b), c) == h(a, h(b, c))
                assert g(x, unitA, s) == x
                assert g(g(x, a, s), b, s) == g(x, h(a, b), s)
        else:
            pass
            print("Monoid Check OK!")
    
    def debug(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")

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

g = lambda x, a, s: min(x, a)
h = lambda a, b: min(a, b)
unitA = 1 << 30
initX = N
st1 = SegmentTreeDual(N, initX, unitA, g, h)
st2 = SegmentTreeDual(N, initX, unitA, g, h)

if False:
    from random import randrange
    randX = lambda: randrange(-10, 11)
    randA = lambda: [-1, randrange(21)][randrange(2)]
    maxs = 10
    rep = 1000
    st1.check(randX, randA, maxs, rep)
    st2.check(randX, randA, maxs, rep)

    print("END")

ans = (N - 2) ** 2
for _ in range(Q):
    t, x = map(int, input().split())
    if t == 1:
        a = st2.getvalue(x)
        ans -= a - 2
        st1.operate_range(1, a, x)
    else:
        a = st1.getvalue(x)
        ans -= a - 2
        st2.operate_range(1, a, x)
    

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

class SegmentTreeOverwriteRMQ:
    M: int
    H: int
    N: int
    st: [int]
    cover: [int]
    I: int = 99999999999999

    def __init__(self, n):
        self.N = n
        self.H = 1
        while self.H < self.N:
            self.H *= 2
        self.M = self.H * 2
        self.cover = [self.I] * self.H
        self.st = [self.I] * self.M
        for i in range(self.H-1, 0, -1):
            self.propagate(i)

    def propagate(self, i):
        if self.cover[i] == self.I:
            self.st[i] = min(self.st[2*i], self.st[2*i+1])
        else:
            self.st[i] = self.cover[i]

    def update(self, l, r, v):
        self._update(l, r, v, 0, self.H, 1)

    def _update(self, l, r, v, cl, cr, cur):
        if l <= cl and cr <= r:
            if cr == cl + 1:
                self.st[cur] = v
            else:
                self.cover[cur] = v
                self.propagate(cur)
        else:
            mid = (cl+cr)//2
            bp = False
            if self.cover[cur] != self.I:
                if 2*cur >= self.H:
                    self.st[2*cur] = self.cover[cur]
                    self.st[2*cur+1] = self.cover[cur]
                else:
                    self.cover[2*cur] = self.cover[cur]
                    self.cover[2 * cur + 1] = self.cover[cur]
                    bp = True
                self.cover[cur] = self.I
            if cl < r and l < mid:
                self._update(l, r, v, cl, mid, 2*cur)
            elif bp:
                self.propagate(2*cur)
            if mid < r and l < cr:
                self._update(l, r, v, mid, cr, 2*cur+1)
            elif bp:
                self.propagate(2*cur+1)
            self.propagate(cur)

    def min(self, l, r):
        return self._min(l, r, 0, self.H, 1)

    def _min(self, l, r, cl, cr, cur):
        if l <= cl and cr <= r:
            return self.st[cur]
        else:
            if self.cover[cur] != self.I:
                return self.cover[cur]
            L, R = self.I, self.I
            mid = cl+cr>>1
            if cl < r and l < mid:
                L = self._min(l, r, cl, mid, 2*cur)
            if mid < r and l < cr:
                R = self._min(l, r, mid, cr, 2*cur+1)
            return min(L, R)

n, q = na()

row = SegmentTreeOverwriteRMQ(n+2)
row.update(2, n, n)

col = SegmentTreeOverwriteRMQ(n+2)
col.update(2, n, n)

rmin = n
cmin = n

black = (n-2)*(n-2)
for z in range(q):
    t, x = na()
    if t == 1:
        black -= row.min(x, x + 1) - 2
        if x < rmin:
            rmin = x
            col.update(0, cmin, rmin)
    else:
        black -= col.min(x, x + 1) - 2
        if x < cmin:
            cmin = x
            row.update(0, rmin, cmin)
print(black)