YouKn0wWho's blog

How To Solve This Magical Problem?
By YouKn0wWho, 5 years ago, In English

I am stuck on this following problem for a pretty long time.

statement
input
output
sample
time limit

It will be really helpful if you can provide me with a solution.

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

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

Can we process queries offline? I think we can make Mo's algorithm work here.

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

    So we need a persistent DSU for this. AFAIK, Persistent DSU works in $$$O(log N)$$$ as we need a stack to take snapshots and do rollbacks and merging from small to large components.

    Bottleneck Explained

    So we are getting a solution in $$$O(n sqrt(n) logn)$$$ which is still costly for us.

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

      No. We don't need these complicated data structures. I edited my comment and explained it more.

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

        But the set is taking extra $$$logn$$$. So what are you trying to come up with?

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

          I didn't mean that we can reduce the order of complexity using a std::set. :D I just meant that there's an easier way to implement the solution.

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

Provide the problem link. I will post my solution.

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

    This is the problem but unfortunately, there is no dataset to judge the problem. So you will always get a runtime error.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +45 Vote: I do not like it

TL;DR There exist variation of Mo's algorithm with only adds and rollbacks.

I assume that you understand solution with Mo and DSU ideas of how to use Mo and how to use DSU to solve one query in $$$O(N \alpha(N))$$$.

This is not Mo, but similar: Queries with length less then $$$\sqrt{N}$$$ we can answer in $$$O(len)$$$ time similar to what I will do next, let's leave it as an exercise. All longer queries we will group by the bucket (of size $$$\sqrt{N}$$$) in which its left border is. For one bucket we will sort all queries by right border. Let's say that borders of bucket are $$$L$$$ and $$$R$$$ (which means left borders of all queries are in $$$[L, R]$$$). We will start with segment $$$[R, R]$$$ and then will move right border to the right (adding the right element). When we encounter right border for some query, we will move left border to the left so that it coincides with left border of query. Then we will answer the query and rollback all the left border movements. The complexity is like in Mo's algorithm, the difference is that we do only adds and rollbacks.

Underlying DS is not DSU, but just remembering left border of segment for right border and vice versa. All the changes are in strict $$$O(1)$$$ time, so total complexity is $$$O(Q\sqrt{N})$$$.

→ Reply