Submission #793127

#	Time	Username	Problem	Language	Result	Execution time	Memory
793127		poustouflan	XORanges (eJOI19_xoranges)	Pypy 3	100 / 100	860 ms	46976 KiB

xoranges

n, q = map(int, input().split())

A = list(map(int, input().split())) # scan results
A_pair = A[0::2]
A_impair = A[1::2]

prefixe = [0]
for x in A_pair:
    prefixe.append(x ^ prefixe[-1])
arbre_pair = []
for k in range(1, len(A_pair)+1):
    arbre_pair.append(
        prefixe[k] ^ prefixe[k-(k & (-k))]
    )

prefixe = [0]
for x in A_impair:
    prefixe.append(x ^ prefixe[-1])
arbre_impair = []
for k in range(1, len(A_impair)+1):
    arbre_impair.append(
        prefixe[k] ^ prefixe[k-(k & (-k))]
    )

def somme(k, arbre):
    # Somme k premiers elts
    s = 0
    while k >= 1:
        s ^= arbre[k-1]
        k -= k & (-k)
    return s

def ajouter(k, x, arbre):
    # Ajoute x en position k
    k += 1
    while k <= len(arbre):
        arbre[k-1] ^= x
        k += k & (-k)

def xorsum(l, r):
    assert l % 2 == r % 2

    if l % 2 == 0:
        # A_pair
        l = l // 2
        r = r // 2
        return somme(r+1, arbre_pair) ^ somme(l, arbre_pair)

    else:
        # A_impair
        l = l // 2
        r = r // 2
        return somme(r+1, arbre_impair) ^ somme(l, arbre_impair)

def set(i, j):
    if i % 2 == 0:
        # A_pair
        i = i // 2
        diff = A_pair[i] ^ j
        A_pair[i] = j
        ajouter(i, diff, arbre_pair)
    else:
        # A_impair
        i = i // 2
        diff = A_impair[i] ^ j
        A_impair[i] = j
        ajouter(i, diff, arbre_impair)




for _ in range(q):
    q, i, j = map(int, input().split())
    if q == 1:
        # rescan
        set(i-1, j)
    else:
        # query
        if (j - i) % 2 == 1:
            print(0)
        else:
            print(xorsum(i-1, j-1))

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25