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.
I am stuck on this following problem for a pretty long time.
It will be really helpful if you can provide me with a solution.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Can we process queries offline? I think we can make Mo's algorithm work here.
YES, we can process queries offline.
Let's call the given permutation $$$A$$$. For every number from $$$1$$$ to $$$N$$$, write down its position in $$$A$$$ to get permutation $$$B$$$. Now we can solve the problem using Mo's algorithm and DSU: Consider a query like $$$[L_i,\,R_i]$$$. Let's call the $$$i$$$-th number in $$$B$$$ as $$$B_i$$$. Now consider an array of size $$$N$$$ such as $$$C$$$ and for each $$$B_j$$$ ($$$L_i \leq j \leq R_i$$$), mark the $$$B_j$$$-th cell in $$$C$$$. The answer of the query is the length of the longest contiguous subarray of $$$C$$$ that all of its cells are marked. You can keep track of the size of components (maximal contiguous subarrays of marked cells) using DSU.
Edit: By "DSU", I don't mean anything complicated. It's enough to keep the endpoints of the components as pairs in a proper data structure (for example:
std::set).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.
So we are getting a solution in $$$O(n sqrt(n) logn)$$$ which is still costly for us.
No. We don't need these complicated data structures. I edited my comment and explained it more.
But the set is taking extra $$$logn$$$. So what are you trying to come up with?
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.Provide the problem link. I will post my solution.
This is the problem but unfortunately, there is no dataset to judge the problem. So you will always get a runtime error.
TL;DR There exist variation of Mo's algorithm with only adds and rollbacks.
I assume that you understand
solution with Mo and DSUideas 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})$$$.
Thank you. This will work.