Cristiano07's blog

Array range queries — change all occurances of number x to y in range [l,r] of an array
By Cristiano07, history, 3 years ago, In English

Hi, I was doing this problem https://codeforces.net/contest/1620/problem/E and have some questions about the more general version of this problem: Given an array of n elements, we are given q numebr of queries: l r x y — change all occurances of number 'x' to 'y' in the [l,r] segment of the array. Lastly, we want to print all elements of the array after these queries. Constraints: n,q <= 200000. TL 1 second, ML 256 MB. I know there is a solution using DSU-on-tree, but is there a segment trees/lazy propagation approach to this problem that is efficient enough to fit in the time limit? This was my first intuitive approach (since the problem involves range updates) but I couldn't seem to find a way with it.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the lazy tag is $$$O(n)$$$, so (I think), no

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you mean O(n) per update query? So it would be O(n*q) in total at best?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      the tag can't be merging, so it will increase when pushdown. I'will solve this problem by segment tree split/merge.(or FHQ-treap)

      → Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Actually you can, although the solution is not what you might've expected. Check 911G - Mass Change Queries and its editorial, there is comment which explains the other solution which works for bigger $$$a[i]$$$.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I would try using segment tree with lazy propagation. In each Node I would store hash table, where key is $$$x$$$, value is $$$y$$$. Let's say you want to push down value from node $$$x$$$, then you simply assign table from a parent to children and assign hash table to null in parent, seems legit to me. Final time complixity is $$$n \cdot \log n$$$.

→ Reply