Submission #7949869

---

Source Code Expand

import sys
input = sys.stdin.readline
class balancing_tree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)
    
    def append(self, v):
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                self.delete(v-1)
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break
    
    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd
    
    def find_r(self, v):
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                if nd.value > v: prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1
    
    def delete(self, v, nd = None, prev = None):
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return 0
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return 0
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)
    
    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

NN = 30
bt = balancing_tree(NN)
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]
for a in A:
    bt.append(a)

X = []
for _ in range(Q):
    l, r, x = map(int, input().split())
    a = bt.find_r(l-1)
    c = 0
    k = 0
    while a <= r:
        bt.delete(a)
        k ^= a
        a = bt.find_r(a)
        c ^= 1
    print(k)
    if c:
        bt.append(x)

Submission Info

Judge Result