Problem:
Range Update Query (RUQ) Write a program which manipulates a sequence A = { a 0 , a 1 , . . .  , a n−1 } with the following operations:  update(s, t, x) : change a s , a s+1 , ..., a t to x .  find(i) : output the value of a i .  Note that the initial values of a i ( i = 0, 1, . . .  , n−1 ) are  2 31 -1. Input  n  q  query 1  query 2 : query q  In the first line, n (the number of elements in A ) and q (the number of queries) are given. Then, i th query query i 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 < 2 31 −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

Solution (Python):
class SegmentTree():
    """区間更新、一点取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: 区間[begin, end)をvalに変更する
    get_val: i番目の値を求める
    """
    def __init__(self, n):
        self.update_cnt = 0
        self.n = n
        self.size = 1
        INF = 2**31 - 1
        while self.size < n:
            self.size *= 2
        self.node = [[self.update_cnt, INF] for i in range(2*self.size - 1)]

    def update(self, begin, end, val):
        self.update_cnt += 1
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = [self.update_cnt, val]
            if (begin - 1) & 1:
                self.node[begin] = [self.update_cnt, val]
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = max(val, self.node[i])
        return val[1]


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(q)]

st = SegmentTree(n)
for i in range(q):
    if info[i][0] == 0:
        s, t, val = info[i][1], info[i][2], info[i][3]
        st.update(s, t + 1, val)
    else:
        s = info[i][1]
        print(st.get_val(info[i][1]))

Solution (Python):



INF = (-1, 2**31 - 1)
line = input()
n, q = list(map(int, line.split()))
N = 1
while N < n + 1:
    N *= 2
a = [INF for _ in range(0, 2 * N - 1)]

def find(i, k, l, r):
    z = a[0]
    while True:
        m = (l + r) // 2
        if i < m:
            k = k * 2 + 1
            r = m
        else:
            k = k * 2 + 2
            l = m
        z = max(z, a[k])
        if k >= N - 1:
            break
    return z[1]

def update(s, t, x, k, l, r):
    if r <= s or t <= l:
        return
    elif s <= l and r <= t:
        a[k] = x
        return
    m = (l + r) // 2
    update(s, t, x, k * 2 + 1, l, m)
    update(s, t, x, k * 2 + 2, m, r)
    return

for t in range(0, q):
    line = input()
    qu = list(map(int, line.split()))
    if qu[0] == 0:
        update(qu[1], qu[2]+1, (t, qu[3]), 0, 0, N)
    elif qu[0] == 1:
        ans = find(qu[1], 0, 0, N)
        print(ans)

Solution (Python):
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 R&1:
            R-=1
            tree[R]=v
        if L&1:
            tree[L]=v
            L+=1
        L>>=1;R>>=1

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

Solution (Python):
import sys



class RangeUpdateQuery:
    def __init__(self, n, initial=2 ** 31 - 1):
        self.n = 1 << (n - 1).bit_length()
        self.INT = (-1, initial)
        
        self.segtree = [self.INT] * (2 * self.n)

    
    def update(self, l, r, v):
        L, R = l + self.n, r + self.n
        while L < R:
            if L & 1:
                self.segtree[L] = v
                L += 1

            if R & 1:
                self.segtree[R - 1] = v
                R -= 1

            L >>= 1
            R >>= 1

    
    def query(self, i):
        i += self.n
        s = self.INT
        while i > 0:
            s = max(s, self.segtree[i])
            i = i // 2
        return s[1]


N, Q = map(int, input().split())
RUQ = RangeUpdateQuery(N)
for q in range(Q):
    query = list(map(int, sys.stdin.readline().split()))
    if query[0] == 0:
        s, t, x = query[1:]
        RUQ.update(s, t + 1, (q, x))

    if query[0] == 1:
        i = query[1]
        print(RUQ.query(i))

Solution (Python):
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 q 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, (q, x))
write("\n".join(ans))
write("\n")

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

Solution (Python):


















INF = 2**31 - 1
n, q = list(map(int, input().split()))
lazy = [None for i in range(4*n)]
for i in range(n):
  lazy[i] = INF

def updata(a, b, x, k, l, r):
  m = (l+r)//2
  if a >= r or b <= l:
    return 0
  elif a <= l and b >= r:
    lazy[k] = x
  else:
    if lazy[k] != None:
      lazy[k*2+1] = lazy[k]
      lazy[k*2+2] = lazy[k]
      lazy[k] = None
    updata(a, b, x, k*2+1, l, m)
    updata(a, b, x, k*2+2, m, r)

def find(x, k, l, r):
  m = (l+r)//2
  if lazy[k] != None:
    print(lazy[k])
  else:
    if x < (l+r)//2:
      find(x, k*2+1, l, m)
    else:
      find(x, k*2+2, m, r)
      
for i in range(q):
  data = list(map(int, input().split()))
  if len(data) == 4:
    f, a, b, x = data
    updata(a, b+1, x, 0, 0, n)
  else:
    f, i = data
    find(i, 0, 0, n)

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


for i in range(30):
    if n<=1<<i:
        seg_el=1<<i
        break

SEG=[None for i in range(2*seg_el-1)]

def lazy_update(k,x):
    if 0<=k<seg_el-1:
        lazy_item,SEG[k]=SEG[k],None
        SEG[k*2+1]=SEG[k*2+2]=lazy_item


def update(a,b,x,k,l,r):
    if SEG[k]!=None:
        lazy_update(k,x)
        
    if r<=a or b<=l:
        return 
    if a<=l and r<=b:
        SEG[k]=x
        return 
    update(a,b,x,k*2+1,l,(l+r)//2)
    update(a,b,x,k*2+2,(l+r)//2,r)

def getvalue(n):
    i=n+seg_el-1
    ANS=SEG[i]
    i=(i-1)//2

    while i>=0:
        if SEG[i]!=None:
            ANS=SEG[i]
        i=(i-1)//2
    return ANS

for i in range(n):
    SEG[i+seg_el-1]=(1<<31)-1

for query in Q:
    if query[0]==0:
        update(query[1],query[2]+1,query[3],0,0,seg_el)
    else:
        print(getvalue(query[1]))

Solution (Python):
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 q 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, (q, x))
write("\n".join(ans))
write("\n")