` Given an array of N integers. Count the number of subarrays so that every value that appears in the subarray appears an odd number of times. I think this can be solved using XOR hashing but do not know how. Can someone help? Thanks! `

` N, Ai <= 1e5 `

# | User | Rating |
---|---|---|

1 | tourist | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 154 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 148 |

6 | SecondThread | 148 |

8 | Petr | 147 |

9 | nor | 145 |

10 | cry | 144 |

` Given an array of N integers. Count the number of subarrays so that every value that appears in the subarray appears an odd number of times. I think this can be solved using XOR hashing but do not know how. Can someone help? Thanks! `

` N, Ai <= 1e5 `

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2024 04:48:12 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

l

I think there's a O(n * sqrt(n) * log(n)) solution. Let p[i] be xor hash on prefix ending at i. Then the condition for [l, r] can be rewritten as p[r] ^ p[l — 1] = (xor of hashes of numbers that appear at least once in [l, r]) or in other words p[r] = p[l — 1] ^ (xor of ... in [l, r]). Create another array t of length n. Initially t[i] = p[i — 1]. We will move r and support this array. Let last[i] be the right most position of i (it will change as we move r). Then i will appear in [l, r] iff l <= last[i]. In transition (r — 1) -> r : last[a[r]] will change to r, so we have to xor t[i] with hash(a[r]) for 1 <= i <= last[a[r]], change last[a[r]] to r and xor t[i] with hash(a[r]) for 1 <= i <= r. After this we need to know the number of 1 <= i <= r such that t[i] = p[r]. So we need a DS that supports 2 operations: 1) Xor of Prefix. 2) Count on Prefix. This can be done with sqrt-decomposition by supporting how much we've xored each block with (lazily) and how many times each number appears in a block.

Why are people downvoting this? Its a valid (if not the best) solution given a hashmap with O(1) update/query

In fact, there is a problem the same as this one: link.

In fact, there is a problem the same as this one: link

In fact, I don't know a problem the same as this one: No Link

I really feel like Persistent segtree would be able to count suitable L for fixed R. But can't put my finger on how.