Блог пользователя Cristiano07

Array range queries — change all occurances of number x to y in range [l,r] of an array
Автор Cristiano07, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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]$$$.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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$$$.

→ Ответить