### YouKn0wWho's blog

By YouKn0wWho, 5 years ago,

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.

• +36

| Write comment?
 » 5 years ago, # |   +4 Can we process queries offline? I think we can make Mo's algorithm work here.
•  » » 5 years ago, # ^ |   +9 YES, we can process queries offline.
 » 5 years ago, # | ← Rev. 3 →   +8 SpoilerLet'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).
•  » » 5 years ago, # ^ |   0 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 ExplainedNormal DSU that works in O(1) on averageint find(int u) { if(par[u]==u) return u; return par[u]=find(par[u]); }  Persistent DSU that works in $O(log N)$int find(int u) { if(par[u]==u) return u; return find(par[u]);//we can't use par[u]=find(par[u]) as we are using a stack to take snapshots } So we are getting a solution in $O(n sqrt(n) logn)$ which is still costly for us.
•  » » » 5 years ago, # ^ |   0 No. We don't need these complicated data structures. I edited my comment and explained it more.
•  » » » » 5 years ago, # ^ |   0 But the set is taking extra $logn$. So what are you trying to come up with?
•  » » » » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   0 Provide the problem link. I will post my solution.
•  » » 5 years ago, # ^ |   0 This is the problem but unfortunately, there is no dataset to judge the problem. So you will always get a runtime error.
 » 5 years ago, # | ← Rev. 2 →   +45 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})$.
•  » » 5 years ago, # ^ |   +3 Thank you. This will work.