Submission #21422232

---

Source Code Expand

size, q = map(int, input().split())
a = list(map(int, input().split()))

#葉の数がlistのサイズ以上になるように完全2分木を作る。
n = 1
while n < size:
    n *= 2
node = [0]*(2*n-1)

#n-1, ..., n+size-2にaを入れる。n+size-1, ..., 2n-2は0(xorでの単位元)で、影響を与えない。
for i in range(size):
    node[i+n-1] = a[i]
#node[i] = node[2i+1]^node[2i+2]で、葉以外のノードであるnode[n-2], ..., node[0]を更新して行く
for i in range(n-2, -1, -1):
    node[i] = node[2*i+1] ^ node[2*i+2]


def update(i, x): #a[i]をxで更新する
    i += n-1
    node[i] = x
    while i > 0:
        i = (i-1)//2 #2i+1, 2i+2(子ノード)からi(親ノード)に行くには、1引いて2で切り捨て割り算すればok
        node[i] = node[2*i+1] ^ node[2*i+2]

def fold(L, R): #a[L]^a[L+1]^...^a[R-1]を出力する
    L += n-1
    R += n-1
    vL = 0
    vR = 0
    while R > L:
        if L % 2 == 0:
            vL ^= node[L]
            L += 1
        if R % 2 == 0:
            vR ^= node[R-1]
        L = (L-1)//2
        R = (R-1)//2
    return (vL^vR)

ret = []
for i in range(q):
    t, x, y = map(int, input().split())
    x -= 1    
    if t == 1:
        update(x, node[x+n-1]^y)
    else:
        ret.append(fold(x, y))
    
for v in ret:
    print(v)

Submission Info

Judge Result