Problem:


Range Update Query (RUQ)

Write a program which manipulates a sequence A = {a0, a1, . . .  , an&minus;1} with the following operations:

  
update(s, t, x): change as, as+1, ..., at to x.

  
find(i): output the value of ai.

Note that the initial values of ai (i = 0, 1, . . .  , n&minus;1) are  231-1.

Input

n q
query1
query2
:
queryq

  In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:

0 s t x 

  or

1 i

  The first digit represents the type of the query. '0' denotes update(s, t, x) and '1' denotes find(i).

Output

For each find operation, print the value.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

  0 ≤ s ≤ t < n

  0 ≤ i < n

  0 ≤ x < 231&minus;1
  

Sample Input 1

3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0
1 1

Sample Output 1

1
3

Sample Input 2

1 3
1 0
0 0 0 5
1 0

Sample Output 2

2147483647
5



Sample input:
3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0
1 1


Sample output:
1
3

Submission status: Accepted

Solution code:
class TemplateTree:
  def __init__(self, iterable):
    self.iter_size = self.get_size(iterable)
    self.size = self.iter_size * 2 - 1
    self.value = [None] * self.size
    for i, v in enumerate(iterable):
      self.value[self.iter_size + i - 1] = (-1, v)
    self.set_value(0)
    self.range = [None] * self.size
    self.set_range(0, 0, self.iter_size - 1)
  
  def get_size(self, iterable):
    ret = 1
    x = len(iterable)
    while ret < x:
      ret *= 2
    return ret
  
  def set_range(self, x, left, right):
    self.range[x] = (left, right)
    if left != right:
      self.set_range(x * 2 + 1, left, (right + left) // 2)
      self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

  def set_value(self, x):
    if x >= self.iter_size - 1:return self.value[x]
    a = self.set_value(x * 2 + 1)
    b = self.set_value(x * 2 + 2)
    if a == None and b == None:
      self.value[x] = None
    elif a == None:
      self.value[x] = b
    elif b == None:
      self.value[x] = a
    else:
      self.value[x] = a
    return self.value[x]

  def update(self, x, val, order, left, right):
    #print(x)
    x_left, x_right = self.range[x]
    if left <= x_left and x_right <= right:
      self.value[x] = (order, val)
    elif right < x_left or x_right < left:
      pass
    else:
      self.update(x * 2 + 1, val, order, left, right)
      self.update(x * 2 + 2, val, order, left, right)
      
  def query(self, x, order, value):
    if x < 0:
      return value
    x_order, x_val = self.value[x]
    if order < x_order:
      return self.query((x - 1) // 2, x_order, x_val)
    else:
      return self.query((x - 1) // 2, order, value)

  def print_tree(self):
    print(self.value)
    print(self.range)

n, q = map(int, input().split())
INF = 2 ** 31 - 1
tree = TemplateTree([INF] * n)

for j in range(q):
  lst = list(map(int, input().split()))
  if lst[0] == 0:
    s, t, x = lst[1:]
    tree.update(0, x, j, s, t)
  else:
    i = lst[1]
    print(tree.query(tree.iter_size - 1 + i, -2, 0))

Submission status: Accepted

Solution code:
import sys
import math
import time
sys.setrecursionlimit(20000)
INT_MAX = 2**31 - 1

def update(tree,x,y,z,N):
    left = x + N #- 1
    right = y + N#- 1

    while True:
        if(left >= right):
            break
        if(right % 2 == 1):
            right -= 1
            tree[right - 1] = z
        if(left % 2 == 1):
            tree[left - 1] = z
            left += 1

        #left += 1#math.floor((left + 1)/2)
        #right -= 1#math.floor((right - 1)/2)
        left >>= 1
        right >>= 1

def find(tree,x,N):
    x += N - 1
    s = (INT_MAX, -1)
    while True:
        if(x < 0):
            break
        if(tree[x][0] is not None and (tree[x][1] > s[1])):
            s = tree[x]
        x = math.floor((x - 1)/2)
    return s[0]

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    N = 1
    while True:
        if(N >= _N):
            break
        N *= 2
    A = [(None,-1)]*(2*N - 1)

    #start = time.time()
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            update(A,query[1],query[2]+1,(query[3],i),N)
            #print(A)
        # find
        if(query[0]==1):
            #z = find(A,lazy_A,query[1],query[1]+1,0,0,N,N)
            z = find(A,query[1],N)
            print(z)
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
n, q = map(int, readline().split())
 
N0 = 2**(n-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v
 
        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
        
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]
 
 
ans = []
for i in range(q):
    t, *cmd = map(int, readline().split())
    if t:
        ans.append(str(query(cmd[0])))
    else:
        s, t, x = cmd
        update(s, t+1, (i, x))
        
write("\n".join(ans))
write("\n")

Submission status: Accepted

Solution code:
from math import log2, ceil


class SegmentTree:
    def __init__(self, n):
        tn = 2 ** ceil(log2(n))
        self.a = [2 ** 31 - 1] * (tn * 2)

    def find(self, c, l, r, i):
        if self.a[c] != -1:
            return self.a[c]
        mid = (l + r) // 2
        if i <= mid:
            return self.find(c * 2, l, mid, i)
        else:
            return self.find(c * 2 + 1, mid + 1, r, i)

    def update(self, c, l, r, s, t, x):
        if l == s and r == t:
            self.a[c] = x
            return
        cv = self.a[c]
        if cv != -1:
            self.a[c * 2] = self.a[c * 2 + 1] = cv
            self.a[c] = -1
        mid = (l + r) // 2
        if t <= mid:
            self.update(c * 2, l, mid, s, t, x)
        elif s > mid:
            self.update(c * 2 + 1, mid + 1, r, s, t, x)
        else:
            self.update(c * 2, l, mid, s, mid, x)
            self.update(c * 2 + 1, mid + 1, r, mid + 1, t, x)


n, q = map(int, input().split())
st = SegmentTree(n)
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        s, t, x = map(int, query[1:])
        st.update(1, 0, n - 1, s, t, x)
    else:
        print(st.find(1, 0, n - 1, int(query[1])))

Submission status: Accepted

Solution code:
import math
def lazy_update(s, e, value):
    a = [(1, l+s, l+e, 1)]
    while a:
        k, s, e, depth = a.pop()
        l_end, r_end = k << (rank-depth), (k+1) << (rank-depth)
        mid = (l_end + r_end) // 2
        if s == l_end and e == r_end:
            lazy[k] = value
        else:
            if lazy[k] is not None:
                lazy[k<<1] = lazy[k]
                lazy[(k<<1)+1] = lazy[k]
                lazy[k] = None
            if s < mid:
                a.append((k<<1, s, min(mid, e), depth+1))
            if e > mid:
                a.append(((k<<1)+1, max(mid, s), e, depth+1))

def get_value(i):
    i += l
    for j in range(rank, -1, -1):
        n = lazy[i>>j]
        if n is not None:
            return n
    return tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [2**31-1]*(2*l)
lazy = [None]*(2*l)
rank = int(math.log2(len(tree)))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        lazy_update(query[1], query[2]+1, query[3])
    else:
        ap(get_value(query[1]))

print("\n".join((str(n) for n in ans)))

Submission status: Accepted

Solution code:
import math
def lazy_update(s, e, value):
    a = [(1, l+s, l+e, 1)]
    ap = a.append
    while a:
        k, s, e, depth = a.pop()
        l_end, r_end = k << (rank-depth), (k+1) << (rank-depth)
        mid = (l_end + r_end) // 2

        if s == l_end and e == r_end:
            lazy[k] = value
        else:
            child = k<<1
            if lazy[k] is not None:
                lazy[child] = lazy[k]
                lazy[child+1] = lazy[k]
                lazy[k] = None
            if s < mid:
                ap((child, s, (mid, e)[e<mid], depth+1))
            if e > mid:
                ap((child+1, (mid, s)[s>mid], e, depth+1))

def get_value(i):
    i += l
    for j in range(rank, -1, -1):
        n = lazy[i>>j]
        if n is not None:
            return n
    return tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [2**31-1]*(2*l)
lazy = [None]*(2*l)
rank = int(math.log2(len(tree)))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        lazy_update(query[1], query[2]+1, query[3])
    else:
        ap(get_value(query[1]))

print("\n".join((str(n) for n in ans)))

Submission status: Accepted

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

#from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 2 ** 31 - 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def set_depth(depth):
    global N, SEGTREE_SIZE, NONLEAF_SIZE
    N = depth
    SEGTREE_SIZE = 1 << N
    NONLEAF_SIZE = 1 << (N - 1)


def range_update(table, left, right, action):
    left += SEGTREE_SIZE // 2
    right += SEGTREE_SIZE // 2
    while left < right:
        if left & 1:
            table[left] = action(table[left])
            left += 1
        if right & 1:
            right -= 1
            table[right] = action(table[right])
        left //= 2
        right //= 2


def down_propagate_to_leaf(table, pos, binop, unity):
    pos += NONLEAF_SIZE
    down_propagate(table, pos, binop, unity)
    return table[pos]


def down_propagate(table, pos, binop, unity):
    for max_level in range(N):
        if 2 ** max_level > pos:
            max_level -= 1
            break
    for level in range(max_level):
        i = pos >> (max_level - level)

        table[i * 2] = binop(table[i], table[i * 2])
        table[i * 2 + 1] = binop(table[i], table[i * 2 + 1])
        table[i] = unity


def set_items(table, xs):
    for i, x in enumerate(xs, NONLEAF_SIZE):
        table[i] = x


def debugprint(xs, minsize=0, maxsize=None):
    strs = [str(x) for x in xs]
    if maxsize != None:
        for i in range(NONLEAF_SIZE, SEGTREE_SIZE):
            strs[i] = strs[i][:maxsize]
    s = max(len(s) for s in strs[NONLEAF_SIZE:])
    if s > minsize:
        minsize = s

    result = ["|"] * N
    level = 0
    next_level = 2
    for i in range(1, SEGTREE_SIZE):
        if i == next_level:
            level += 1
            next_level *= 2
        width = ((minsize + 1) << (N - 1 - level)) - 1
        result[level] += strs[i].center(width) + "|"
    print(*result, sep="\n")


def main():
    from operator import add
    N, Q = map(int, input().split())
    depth = N.bit_length() + 1
    set_depth(depth)
    action_unity = (-1, INF)
    table = [action_unity] * SEGTREE_SIZE

    for time in range(Q):
        q, *args = map(int, input().split())
        if q == 0:
            # update
            s, t, new_value = args
            range_update(table, s, t + 1, lambda x: (time, new_value))

        else:
            # find
            print(down_propagate_to_leaf(
                table, args[0], max, action_unity)[1])


# tests
T1 = """
3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0
1 1
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    1
    3
    """
# add tests above


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


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
class SegmentTree:
    n=0
    node=[]

    def __init__(self, sz):
        self.n=1
        while self.n<sz: self.n *= 2
        self.node = [INF] * (2*self.n-1)

    def update(self, a, b, x=-1, k=0, l=0, r=-1):
        if r<0: r = self.n
        if r<=a or  b<=l: return
        if a<=l and r<=b: 
            if x>=0: self.node[k] = x
            return
        if self.node[k]!=INF:
            self.node[k*2+1] = self.node[k*2+2] = self.node[k]
        self.node[k] = INF
        self.update(a, b, x, 2*k+1, l, (l+r)//2)
        self.update(a, b, x, 2*k+2, (l+r)//2, r)

    
INF = 2**31-1
sz, q = map(int, input().split())
ruq = SegmentTree(sz)
for _ in range(q):
    c, *l = map(int, input().split())
    if c:
        ruq.update(l[0], l[0]+1)
        print(ruq.node[l[0]+ruq.n-1])
    else:
        s, t, x = l
        ruq.update(s, t+1, x)

Submission status: Accepted

Solution code:
import sys

INF = 2**31 - 1


class RUQ:

    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp *= 2
        self.n = tmp * 2
        self.A = [INF] * (2 * self.n - 1)

    def update(self, a, b, x=-1, k=0, l=0, r=0):
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            if x >= 0:
                self.A[k] = x
            return
        if self.A[k] != INF:
            self.A[k*2+1] = self.A[k*2+2] = self.A[k]
        self.A[k] = INF
        self.update(a, b, x, k*2+1, l, (l+r)/2)
        self.update(a, b, x, k*2+2, (l+r)/2, r)


line = sys.stdin.readline()
n, q = map(int, line.split())
ruq = RUQ(n)
for i in range(q):
    line = sys.stdin.readline()
    if line[0] == "0":
        com, s, t, x = map(int, line.split())
        ruq.update(s, t+1, x, 0, 0, ruq.n)
    else:
        com, i = map(int, line.split())
        ruq.update(i, i+1, -1, 0, 0, ruq.n)
        print(ruq.A[i+ruq.n-1])

Submission status: Accepted

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

size = 2**((n-1).bit_length())
tree = [None]*(size*2)
INF = (-1, 2**31-1)

def _find(i):
    ind = size+i
    s = INF
    while ind:
        if tree[ind]:
            s = max(s, tree[ind])
        ind = ind//2
    return s
def find(i):
    return _find(i)[1]

def update(s, t, v):
    L = s+size;R = t+size
    while L<R:
        if L&1:
            tree[L]=v
            L+=1
        if R&1:
            R-=1
            tree[R]=v

        L>>=1;R>>=1

res = []
for i in range(q):
    a, *b = map(int, input().split())
    if a:res.append(find(b[0]))
    else:update(b[0],b[1]+1,(i,b[2]))
print('\n'.join(map(str,res)))

Submission status: Accepted

Solution code:
"""
Segment-Tree
    maxval:入力されるデータ以上の値
    offset:根と枝の数(n=1のときは根1つ葉2つの木)
    init_array(array):配列で初期化
    update(k,x):k番目をxに変更
    sum_query(p,q):[p,q)の範囲の合計
"""
class SegmentTree():
    maxval=(1<<31)-1

    def __init__(self,n):
        self.offset=self.setOffset(n)
        self.segTree=[(0,self.maxval) for i in range(2*self.offset+1)]
        self.time=0

    def setOffset(self,n):
        if n==1:
            return 1
        else:
            return 2**(n-1).bit_length()-1

    def find(self,k):
        k+=self.offset
        data=self.segTree[k]
        while k:
            k=(k-1)//2
            data=max(data,self.segTree[k])
        return data

    def update_query(self,p,q,x):
        if p>=q:
            return

        self.time+=1
        p+=self.offset
        q+=self.offset-1
        v=(self.time,x)

        while q-p>1:
            #p%2==0
            if not p&1:
                self.segTree[p]=v
            #q%2==1
            if q&1:
                self.segTree[q]=v
                q-=1
            p=p//2
            q=(q-1)//2

        if p==q:
            self.segTree[p]=v
        else:
            self.segTree[p]=v
            self.segTree[q]=v

    def show(self):
        print(self.segTree)

n,q=map(int,input().split())
ST=SegmentTree(n)
for i in range(q):
    qry=list(map(int,input().split()))
    if qry[0]==0:
        ST.update_query(qry[1],qry[2]+1,qry[3])
    else:
        print(ST.find(qry[1])[1])

Submission status: Accepted

Solution code:

class LazySegTree:
    inf = 2147483647
    INF = [-1,2147483647]
    def __init__(self,n_):
        self.n_ = n_
        self.n = 1
        while self.n < n_: self.n*=2
        self.st = [self.INF]*(2*self.n-1)
        self.lazy = [self.INF]*(2*self.n-1)

    def propagate(self,k):
        if self.lazy[k]==self.INF:return
        self.st[k] = self.lazy[k][1]
        if k<self.n_-1:
            self.lazy[k*2+1] = self.lazy[k]
            self.lazy[k*2+2] = self.lazy[k]
        self.lazy[k] = self.INF
    
    def update(self,a,b,k,x,l,r):
        #self.propagate(k)
        if r<=a or b<=l :return
        if a<=l and r<=b:
            self.st[k] = x
            self.lazy[k] = x
            return
        self.update(a,b,k*2+1,x,l,(l+r)//2)
        self.update(a,b,k*2+2,x,(l+r)//2,r)

    def Update(self,a,b,x):
        return self.update(a,b,0,x,0,self.n)

    def search(self,k,l,r):
        #self.propagate(k)
        k += self.n-1
        res = self.INF
        while 0<=k:
            res = max(res,self.lazy[k])
            k = (k-1)//2
        return res[1]

    def Search(self,k):
        return self.search(k,0,self.n)

def main():
    n,m = map(int,input().split())
    lst = LazySegTree(n)
    for i in range(m):
        q = list(map(int,input().split()))
        if q[0] == 0:
            lst.Update(q[1],q[2]+1,[i,q[3]])
        else        :print(lst.Search(q[1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

class LazyPropSegmentTree:
    def __init__(self, lst, op, apply, comp, e, identity):
        self.n = len(lst)
        self.depth = (self.n - 1).bit_length()
        self.N = 1 << self.depth
        self.op = op # binary operation of elements
        self.apply = apply # function to apply to an element
        self.comp = comp # composition of functions
        self.e = e # identity element w.r.t. op
        self.identity = identity # identity element w.r.t. comp
        self.v = self._build(lst) # self.v is set to be 1-indexed for simplicity
        self.lazy = [self.identity] * (2 * self.N)
    
    def __getitem__(self, i):
        return self.fold(i, i+1)
    
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N elements (tree[0] is not used)
        tree = [self.e] * (self.N) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 1, 0, -1): tree[i] = self.op(tree[i << 1], tree[(i << 1)|1])
        return tree
    
    def _indices(self, l, r):
        left = l + self.N; right = r + self.N
        left //= (left & (-left)); right //= (right & (-right))
        left >>= 1; right >>= 1
        while left != right:
            if left > right: yield left; left >>= 1
            else: yield right; right >>= 1
        while left > 0: yield left; left >>= 1
    
    # propagate self.lazy and self.v in a top-down manner
    def _propagate_topdown(self, *indices):
        identity, v, lazy, apply, comp = self.identity, self.v, self.lazy, self.apply, self.comp
        for k in reversed(indices):
            x = lazy[k]
            if x == identity: continue
            lazy[k << 1] = comp(lazy[k << 1], x)
            lazy[(k << 1)|1] = comp(lazy[(k << 1)|1], x)
            v[k << 1] = apply(v[k << 1], x)
            v[(k << 1)|1] = apply(v[(k << 1)|1], x)
            lazy[k] = identity # propagated

    # propagate self.v in a bottom-up manner
    def _propagate_bottomup(self, indices):
        v, op = self.v, self.op
        for k in indices: v[k] = op(v[k << 1], v[(k << 1)|1])

    # update for the query interval [l, r) with function x
    def update(self, l, r, x):
        *indices, = self._indices(l, r)
        self._propagate_topdown(*indices)
        
        N, v, lazy, apply, comp = self.N, self.v, self.lazy, self.apply, self.comp
        
        # update self.v and self.lazy for the query interval [l, r)
        left = l + N; right = r + N
        if left & 1: v[left] = apply(v[left], x); left += 1
        if right & 1: right -= 1; v[right] = apply(v[right], x)
        left >>= 1; right >>= 1
        while left < right:
            if left & 1:
                lazy[left] = comp(lazy[left], x)
                v[left] = apply(v[left], x)
                left += 1
            if right & 1:
                right -= 1
                lazy[right] = comp(lazy[right], x)
                v[right] = apply(v[right], x)
            left >>= 1; right >>= 1
        self._propagate_bottomup(indices)
    
    # returns answer for the query interval [l, r)
    def fold(self, l, r):
        self._propagate_topdown(*self._indices(l, r))
        
        e, N, v, op = self.e, self.N, self.v, self.op
        
        # calculate the answer for the query interval [l, r)
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: # self.v[left] is the right child
                L = op(L, v[left])
                left += 1
            if right & 1: # self.v[right-1] is the left child
                right -= 1
                R = op(v[right], R)
            left >>= 1; right >>= 1
        return op(L, R)
    
N, Q = map(int, input().split())
op = min
apply = lambda x, f: f
comp = lambda f, g: g
e = 2**31 - 1
identity = None
A = [e] * N
lpsg = LazyPropSegmentTree(A, op, apply, comp, e, identity)
ans = []
for _ in range(Q):
    t, *arg, = map(int, input().split())
    if t == 0:
        s, t, x = arg
        lpsg.update(s, t+1, x)
    else:
        ans.append(lpsg[arg[0]])
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
class SegmentTreeDual():
    def __init__(self,arr,op=lambda x,y:y if y != -1 else x,ie=-1):
        self.h = (len(arr)-1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(len(arr))]
        self.laz = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]
    def propagate(self,k):
        if self.laz[k] == self.ie:
            return
        if self.n <= k:
            self.val[k-self.n] = self.op(self.val[k-self.n],self.laz[k])
            self.laz[k] = self.ie
        else:
            self.laz[(k<<1)] = self.op(self.laz[(k<<1)],self.laz[k])
            self.laz[(k<<1)+1] = self.op(self.laz[(k<<1)+1],self.laz[k])
            self.laz[k] = self.ie
    def update(self,left,right,f):
        left += self.n
        right += self.n
        for i in reversed(range(self.h+1)):
            self.propagate(left>>i)
        for i in reversed(range(self.h+1)):
            self.propagate((right-1)>>i)
        while right - left > 0:
            if right & 1:
                right -= 1
                self.laz[right] = self.op(self.laz[right],f)
            if left & 1:
                self.laz[left] = self.op(self.laz[left],f)
                left += 1
            left >>= 1
            right >>= 1
    def get(self,index):
        res = self.val[index]
        index += self.n
        while index:
            res = self.op(res,self.laz[index])
            index //= 2
        return res

INF = 2**31-1
N,Q = map(int,input().split())
A = [INF for _ in range(N)]
sg = SegmentTreeDual(A)
ans = []

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0] == 0:
        s,t,x = q[1:]
        sg.update(s,t+1,x)
    else:
        i = q[1]
        ans.append(sg.get(i))

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:

def func(x,y):
    return x if x < y else y

class LazySegmentTree():
    def __init__(self, n):
        n_ = 1
        c_ = 0
        while n_ < n:
            n_ *= 2
            c_ +=1

        self.lv = c_
        self.n = n_
        self.arr = [2**31-1] * (2*self.n-1)
        self.lazy = [None] * (2*self.n-1)

    #伝播区間
    def getidx(self, l, r):
        L = (l + self.n) >> 1
        R = (r + self.n) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.lv):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>=1

    #伝播
    def propagate(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.arr[2*i-1] = self.lazy[2*i] = self.arr[2*i] = v
            self.lazy[i-1] = None

    #[l, r] をxで更新
    def update(self,l,r,x):
        #[l, r)に変更
        r+=1
        *ids, = self.getidx(l,r)
        self.propagate(*ids)

        L = self.n + l; R = self.n + r
        while L < R:
            if R & 1:
                R -=1
                self.lazy[R-1] = self.arr[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.arr[L-1] = x
                L += 1
            L >>= 1; R >>= 1

        for i in ids:
            self.arr[i-1] = func(self.arr[2*i-1], self.arr[2*i])

    #[l, r]のクエリに答える
    def query(self,l,r):
        #[l, r)に変更
        r+=1
        self.propagate(*self.getidx(l,r))
        L = self.n + l; R = self.n + r

        s = 2**31-1
        while L < R:
            if R & 1:
                R -=1
                s = func(s, self.arr[R-1])
            if L & 1:
                s = func(s, self.arr[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

#0-indexed なので1-からのときは−１する
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
sg=LazySegmentTree(n)
for _ in range(q):
    l=list(map(int,input().split()))
    if l[0]==0:
        c,s,t,x=l
        sg.update(s,t,x)
    else:
        c,i=l
        print(sg.query(i,i))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 2 ** 31 - 1
MOD = 10 ** 9 + 7

class SegTreeLazy:
    """ 遅延評価セグメント木(区間更新・区間最小値取得) """

    def __init__(self, N, func, intv):
        self.intv = intv
        self.func = func
        LV = (N-1).bit_length()
        self.N0 = 2**LV
        self.data = [intv]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    # 遅延評価の伝搬処理
    def propagates(self, *ids):
        # 1-indexedで単調増加のインデックスリスト
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None

    def update(self, l, r, x):
        """ 区間[l,r)の値をxに更新 """

        *ids, = self.gindex(l, r)
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*ids)
        # 2. 区間[l,r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i])

    def query(self, l, r):
        """ 区間[l,r)の最小値を取得 """

        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小値を求める
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

N, Q = MAP()
stl = SegTreeLazy(N+1, min, INF)

ans = []
for i in range(Q):
    cmd, *arg = MAP()
    if cmd == 0:
        s, t, x = arg
        stl.update(s, t+1, x)
    else:
        i, = arg
        ans.append(str(stl.query(i, i+1)))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
#3158554 By JAKENU0X5E　参照
n,q = map(int,input().split( ))
s = 1
while s < n:
    s*=2

A = [(-1,2**31-1)]*(2*s-1)
#print(A)
def update(l,r,i,v):#A[l,r)および対応する親ノードをiターン目にvに書き換える
    while l<r:
        if r&1:
            r -= 1###-1
            A[r-1] = (i,v)###-1
        if l&1:
            A[l-1]=(i,v)###-1
            l+=1###+1
        l//=2
        r//=2


for i in range(q):
    c = list(map(int, input().split( )))
    if not c[0]:
        x = c[1]
        y = c[2]
        u = c[3]
        x += s ###
        y += s
        #x -=1###
        update(x,y+1,i,u)
        #print(A)
            
    else:
        res = (-1,0)
        x = c[1] + s-1
        while x>=0:
            #print(res,A[x])
            if A[x] > res:
                res = A[x]
            x -=1
            x//=2
        print(res[1])