one_autum_leaf's blog

By one_autum_leaf, history, 4 weeks ago, In English

Problem Statement:

You are given an array arr of size $$$N$$$. Initially, all $$$arr[i]$$$ are set to 0. Now consider $$$Q$$$ queries, where each query is of one of the following two types:

  1. [1, l, r]: In this case, calculate the sum of values of $$$arr[i]$$$ for $$$l \le i \le r$$$.
  2. [2, l, r, x]: In this case, for each $$$arr[i]$$$, $$$l \le i \le r$$$, update the value to $$$arr[i] = arr[i] \oplus x$$$ (where $$$\oplus$$$ is the XOR operation).

Constraints:

  1. $$$ 1 \le N \le 10^5 $$$
  2. $$$ 1 \le Q \le 10^5 $$$
  3. $$$ 1 \le l \le r \le N $$$
  4. $$$ 1 \le x \le 2^{30} - 1 $$$

Problem Link — 242E - XOR на отрезке


Approach:

This problem can be solved easily with a Segment Tree with Lazy Propagation, had there been no XOR updates. Lazy Propagation requires that for an update on range $$$[l, r]$$$, we should be able to calculate the value of $$$[l, r]$$$ after the update in $$$O(1)$$$ time (or at least sub-linear time like $$$O(\log n)$$$).

For other updates, say multiply by $$$x$$$, this would be simple. The value of $$$[l, r]$$$ after the update would be:

new_sum = x * prev_sum

For XOR updates, though, this is not so straightforward.


Simplifying the XOR Update

Generalizing for the Full Problem:

Code
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by one_autum_leaf (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by one_autum_leaf (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$O(nlognloga_i)$$$

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

I'm pretty sure that if you build one seg tree with a node that has information for those 30 bits instead of building 30 seg trees the solution would run way faster due to cache reasons.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yeah I think keeping the lazy as an integer which was 1 in bits that are inverted and 0 in not inverted bits works

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by one_autum_leaf (previous revision, new revision, compare).