Chef And Easy Xor Queries
All submissions for this problem are available.
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.
- 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 A1, A2 ... AN 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.
For each operation of type 2, print the number of magical subarrays on a separate line.
- 1 ≤ N, Q ≤ 100,000
- 1 ≤ A[i] ≤ 1,000,000
- 1 ≤ i ≤ N
- 1 ≤ x, k ≤ 1,000,000
Subtask #1 (20 points): 1 ≤ N, Q ≤ 1,000
Subtask #2 (30 points): 1 ≤ N, Q ≤ 10,000
Subtask #3 (50 points): original constraints
Input: 5 3 1 1 1 1 1 2 5 1 1 3 2 2 5 1 Output: 3 1
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions