Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef always likes to play with arrays. He came up with a new term "magical subarray". A subarray is called magical if its starting index is 1 (1-based indexing). Now, Chef has an array of N elements and 2 types of queries:

type 1: Given two numbers i and x, the value at index i should be updated to x.
type 2: Given two numbers i and k, your program should output the total number of magical subarrays with the last index ≤ i in which the xor of all elements is equal to k.

------ Input ------ 

The first line of the input contains two integers N and Q denoting the number of elements in the array and the number of queries respectively.
The second line contains N space-separated integers A_{1}, A_{2} ... A_{N} denoting the initial values of the array.
Each of the following Q lines describes an operation. If the first integer is 1, it means that the operation is of type 1 and it will be followed by two integers i and x. If the first integer is 2, it means that the operations is of type 2 and it will be followed by two integers i and k.

------ Output ------ 

For each operation of type 2, print the number of magical subarrays on a separate line.

------ Constraints ------ 

$1 ≤ N, Q ≤ 100,000$
$1 ≤ A[i] ≤ 1,000,000$
$1 ≤ i ≤ N$
$1 ≤ x, k ≤ 1,000,000$

------ Subtasks ------ 

Subtask #1 (20 points): 1 ≤ N, Q ≤ 1,000

Subtask #2 (30 points): 1 ≤ N, Q ≤ 10,000

Subtask #3 (50 points): original constraints

----- Sample Input 1 ------ 
5 3
1 1 1 1 1
2 5 1
1 3 2
2 5 1
----- Sample Output 1 ------ 
3
1

Source: codechef | Difficulty: HARD
Tags: Bit manipulation

Square root algorithms

Mathematics


Solutions:
gstart = [0 for i in range(1000)]
gend = [0 for i in range(1000)]
gxor = [0 for i in range(1000)]
gid = [0 for i in range(10 ** 6 + 100)]
gcnt = [{} for j in range(1000)]
ps = [0 for i in range(10 ** 5 + 10)]

def buildSqrtDecomp(n):
	gsize = 1
	while gsize * gsize < n:
		gsize += 1
	ng = 0
	for i in range(0, n, gsize):
		gstart[ng] = i
		gend[ng] = i + gsize - 1
		ng += 1
	gend[ng - 1] = n - 1
	for g in range(ng):
		gxor[g] = 0
		for i in range(gstart[g], gend[g] + 1):
			if ps[i] in gcnt[g]:
				gcnt[g][ps[i]] += 1
			else:
				gcnt[g][ps[i]] = 1
			gid[i] = g
	return gsize
(n, q) = [int(c) for c in input().split()]
arr = [int(i) for i in input().split()]
currXor = 0
for i in range(len(arr)):
	currXor ^= arr[i]
	ps[i] = currXor
gsize = buildSqrtDecomp(n)
for _ in range(q):
	(op, i, x) = [int(c) for c in input().split()]
	if op == 1:
		i -= 1
		block_number = gid[i]
		c = arr[i] ^ x
		arr[i] = x
		for j in range(i, gend[block_number] + 1):
			gcnt[block_number][ps[j]] -= 1
			ps[j] ^= c
			if ps[j] in gcnt[block_number]:
				gcnt[block_number][ps[j]] += 1
			else:
				gcnt[block_number][ps[j]] = 1
		for j in range(gid[i] + 1, gsize + 1):
			gxor[j] ^= c
	else:
		i -= 1
		block_number = gid[i]
		ans = 0
		for j in range(gstart[block_number], i + 1):
			if ps[j] ^ gxor[block_number] == x:
				ans += 1
		for j in range(0, block_number):
			if x ^ gxor[j] in gcnt[j]:
				ans += gcnt[j][x ^ gxor[j]]
		print(ans)


import sys
data = sys.stdin.read().split()
data.reverse()

def read():
	return int(data.pop())

def readStr():
	return data.pop()
from collections import Counter
N = 2 * 10 ** 5 + 5
block = 317
nb = N // block
X = [0] * nb
D = [Counter() for i in range(nb)]

def init(n):
	for i in range(n):
		D[i // block][A[i]] += 1

def update(p, x):
	st = p // block
	en = (n - 1) // block
	toXor = A[p] ^ X[st] ^ x
	if p:
		toXor ^= A[p - 1] ^ X[(p - 1) // block]
	for i in range(p, min((st + 1) * block, n)):
		ele = A[i]
		D[st][ele] -= 1
		D[st][ele ^ toXor] += 1
		A[i] = ele ^ toXor
	for i in range(st + 1, en + 1):
		X[i] ^= toXor

def ansQuery(p, k):
	st = p // block
	ans = 0
	for i in range(st * block, p + 1):
		if A[i] ^ X[st] == k:
			ans += 1
	for i in range(st):
		ans += D[i][k ^ X[i]]
	return ans
(n, q) = (read(), read())
A = [read() for i in range(n)]
for i in range(1, n):
	A[i] ^= A[i - 1]
init(n)
ans = []
for query in range(q):
	(t, a, b) = (read(), read(), read())
	if t == 1:
		update(a - 1, b)
	else:
		ans.append(str(ansQuery(a - 1, b)))
print('\n'.join(ans))


import numpy
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
arr = [a[0]]
for i in range(1, n):
	arr.append(arr[-1] ^ a[i])
arr = numpy.array(arr)
for _ in range(q):
	(t, i, k) = map(int, input().split())
	if t == 1:
		b = a[i - 1] ^ k
		a[i - 1] = k
		arr[i - 1:] ^= b
	else:
		print(numpy.count_nonzero(arr[:i] == k))


import math

class decomp:

	def __init__(self, n, arr):
		self.size = math.ceil(n ** 0.5)
		self.block2 = []
		self.countarr = []
		bno = 1
		for i in range(n):
			if i // self.size != bno:
				pre = 0
				self.block2.append([])
				self.countarr.append({})
			bno = i // self.size
			pre = pre ^ arr[i]
			self.block2[bno].append(pre)
			try:
				self.countarr[bno][pre] += 1
			except:
				self.countarr[bno][pre] = 1

	def update(self, arr, index, value, n):
		bno = index // self.size
		if index % self.size == self.size - 1:
			self.countarr[bno][self.block2[bno][index % self.size]] -= 1
			self.block2[bno][index % self.size] = self.block2[bno][self.size - 2] ^ arr[self.size * bno + self.size - 1]
			try:
				self.countarr[bno][self.block2[bno][index % self.size]] += 1
			except:
				self.countarr[bno][self.block2[bno][index % self.size]] = 1
			return
		elif index % self.size == 0:
			pre = 0
		else:
			pre = self.block2[bno][index % self.size - 1]
		for i in range(index % self.size, self.size):
			if bno * self.size + i == n:
				break
			self.countarr[bno][self.block2[bno][i]] -= 1
			pre = pre ^ arr[self.size * bno + i]
			self.block2[bno][i] = pre
			try:
				self.countarr[bno][pre] += 1
			except:
				self.countarr[bno][pre] = 1

	def query(self, arr, index, k):
		bno = index // self.size
		pre = k
		count = 0
		for i in range(bno):
			try:
				count += self.countarr[i][pre]
				pre = pre ^ self.block2[i][-1]
			except:
				pre = pre ^ self.block2[i][-1]
		x = index % self.size + 1
		for i in range(x):
			if pre == self.block2[bno][i]:
				count += 1
		return count
(N, Q) = map(int, input().split())
arr = [int(x) for x in input().split()]
dem = decomp(N, arr)
for i in range(Q):
	op = [int(x) for x in input().split()]
	if op[0] == 1:
		arr[op[1] - 1] = op[2]
		dem.update(arr, op[1] - 1, op[2], N)
	else:
		print(dem.query(arr, op[1] - 1, op[2]))


import math
from collections import defaultdict
(n, q) = list(map(int, input().strip().split(' ')))
l = list(map(int, input().strip().split(' ')))
blocks_xor = []
prefix_xor = []
block_size = int(math.sqrt(n))
blocks = int(math.ceil(n / block_size))
for i in range(blocks):
	block_start = i * block_size
	block_end = min(block_start + block_size, n)
	xor_map = defaultdict(lambda : 0)
	prev = 0
	block_prefix_xor = []
	for j in range(block_start, block_end):
		prev ^= l[j]
		xor_map[prev] += 1
		block_prefix_xor.append(prev)
	blocks_xor.append(xor_map)
	prefix_xor.append(block_prefix_xor)
for i in range(q):
	(typ, index, k) = list(map(int, input().strip().split(' ')))
	index -= 1
	block = index // block_size
	block_start = block * block_size
	block_end = min(block_start + block_size, n)
	if typ == 1:
		xor_map = defaultdict(lambda : 0)
		prev = 0
		l[index] = k
		block_prefix_xor = []
		for j in range(block_start, block_end):
			prev ^= l[j]
			xor_map[prev] += 1
			block_prefix_xor.append(prev)
		blocks_xor[block] = xor_map
		prefix_xor[block] = block_prefix_xor
	else:
		prev = 0
		count = 0
		for j in range(block):
			xor_map = blocks_xor[j]
			if prev ^ k in xor_map:
				count += xor_map[prev ^ k]
			prev ^= prefix_xor[j][-1]
		block_prefix_xor = prefix_xor[block]
		for j in range(index - block_start + 1):
			if prev ^ block_prefix_xor[j] == k:
				count += 1
		print(count)


import numpy as np
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
xor = [A[0]]
for i in range(1, n):
	xor.append(xor[i - 1] ^ A[i])
xor = np.array(xor)
for i in range(q):
	(ii, index, x) = map(int, input().split())
	if ii == 1:
		y = A[index - 1] ^ x
		A[index - 1] = x
		xor[index - 1:] ^= y
	else:
		print(np.count_nonzero(xor[:index] == x))


import numpy
(n, q) = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
xor = [A[0]]
for i in range(1, n):
	xor.append(xor[-1] ^ A[i])
xor = numpy.array(xor)
for i in range(q):
	(t, ind, x) = map(int, input().strip().split())
	if t == 1:
		b = A[ind - 1] ^ x
		A[ind - 1] = x
		xor[ind - 1:] ^= b
	else:
		print(numpy.count_nonzero(xor[:ind] == x))


from math import sqrt, floor
(n, q) = (int(x) for x in input().strip().split())
A = [int(x) for x in input().strip().split()]
block_length = floor(sqrt(n))
block_count = (n + block_length - 1) // block_length
mapping = [dict() for _ in range(block_count)]
pending = [0 for _ in range(block_count)]
for i in range(n):
	A[i] ^= A[i - 1] if i else 0
	block_index = i // block_length
	mapping[block_index][A[i]] = mapping[block_index].get(A[i], 0) + 1
while q:
	(t, i, x) = (int(z) for z in input().strip().split())
	(block_index, ans) = ((i - 1) // block_length, 0)
	q -= 1
	if t == 1:
		x ^= A[i - 1] ^ pending[block_index]
		if i > 1:
			n_block_index = (i - 2) // block_length
			x ^= A[i - 2] ^ pending[n_block_index]
		for j in range(block_index + 1, block_count):
			pending[j] ^= x
		for j in range(i - 1, min((block_index + 1) * block_length, n)):
			mapping[block_index][A[j]] -= 1
			if mapping[block_index][A[j]] == 0:
				del mapping[block_index][A[j]]
			A[j] ^= x
			mapping[block_index][A[j]] = mapping[block_index].get(A[j], 0) + 1
	else:
		for j in range(block_index):
			ans += mapping[j].get(x ^ pending[j], 0)
		for j in range(block_index * block_length, i):
			ans += 1 if A[j] ^ pending[block_index] == x else 0
		print(ans)


import numpy
import sys
f = sys.stdin
(n, q) = map(int, f.readline().split())
a = list(map(int, f.readline().split()))
xor = [a[0]]
for i in range(1, n):
	xor.append(xor[-1] ^ a[i])
xor = numpy.array(xor)
for i in range(q):
	(t, ind, x) = map(int, f.readline().split())
	if t == 1:
		b = a[ind - 1] ^ x
		a[ind - 1] = x
		xor[ind - 1:] ^= b
	else:
		print(numpy.count_nonzero(xor[:ind] == x))


from collections import defaultdict as dd
import math
(n, nq) = [int(i) for i in input().split(' ')]
a = [int(i) for i in input().split(' ')]
e = math.sqrt(n)
w = math.sqrt(n)
if e != int(e):
	w += 1
w = int(w)
e = int(e)
d1 = []
b = []
c = []
d2 = []
t = 0
d = []
d3 = dd(int)
for i in range(n):
	d1.append(a[i])
	r = a[i] ^ t
	d3[r] += 1
	d2.append(r)
	t = r
	if i % e == e - 1 or i == n - 1:
		b.append(d1)
		d1 = []
		c.append(d2)
		t = 0
		d2 = []
		d.append(d3.copy())
		d3 = dd(int)
for _ in range(nq):
	(q, i, k) = [int(i) for i in input().split(' ')]
	if q == 2:
		w = len(b[0])
		i = i - 1
		nn = i // w + 1
		t = 0 ^ k
		s = 0
		for j in range(nn - 1):
			s += d[j][t]
			t = t ^ c[j][-1]
		s += c[nn - 1][:i - (nn - 1) * w + 1].count(t)
		print(s)
	else:
		w = len(b[0])
		i = i - 1
		nn = i // w
		b[nn][i - w * nn] = k
		t = 0
		d1 = dd(int)
		for i in range(len(b[nn])):
			t = t ^ b[nn][i]
			c[nn][i] = t
			d1[t] += 1
		d[nn] = d1.copy()