[Persistent Segment Trees] 351 - D Jeff and Removing Periods

351 - D - Jeff and Removing Periods

Problem statement:

Problem can be found here.The gist of the  problem is:

We're given an array $a$ of length $n$. With that we're given $q$ queries too, which are of the form $l r$. We have to answer the total number of unique numbers in that range plus if any number present with a constant gap (AP of indices) in the range then add 0, else if no such element is present then add 1.

Notice that if an element is present two or one times, then it automatically satisfied the condition mentioned

Approach:

There are two approaches to solve this question:

1. Mo's algorithm for sorting the queries and finding the answer. I have done this question and here is the solution. We will not discuss it here, since it is already discussed in the editorials.
2. Persistent segment trees. 

I followed rlac's submission to understand  this method.

Description:

You need to know about persistent segment trees, in order to understand this solution. If you don't then you can find material regarding them at these places:

• GKCS-MKTHNUM (SPOJ)
• This codechef tutorial

In my opinion, the idea isn't that much hard to understand. It's just like version control. Once you update some value, which is a leaf, you create new parents till the root, for each update.

Now to solve this problem we need two persistent segment trees:

1. To find the total number of  unique numbers for a range $l,r$
2. To find whether any element's indices follow any AP for a range $l,r$

For the first tree, the logic can be like:

We go from 0, to n-1 in this case.

You create an array pos, which saves the element's last occurrence. So, if the current element has been seen before, then we update that position with a zero (this creates a new root). Then for the current number, we update the for the current index with a 1. We can save this root as the ith root.

When queried, we can query the segment tree root r. The operation performed is the sum operation. That is, the parent's value is calculated by adding the values of the left child and the right child.

Initially, I thought why not just use a regular segment tree? But actually changing the one to zero, might affect some answers, so a regular segment tree might have not worked in that case.

Now, for the second tree, we can again use pos to save last occurrences, next_pos, to save the next position of an element in the array, and last to save the element after the last element of the AP.

Note that we go from n-1 to 0, in this case.

So, if the current element was present before, then it's index' value is set to zero for this segtree. Now if we have a next->next element, then we check if an AP is being formed. If not, then we know that two elements always form an AP, so the last value of the current element is the next->next value.

If next->next indeed follows an AP, then we have atleast three elements in AP, maybe more, maybe less. A check must have also been done for the next element which was saved in pos[a[i]]. We can save it's last value as last[i].

Now when queried, we go for the lth 2nd segment tree, and check for (l,r). Here the operator is the max. That is, the value for the parent node is calculated by taking the max of the left and right child.

If the queried result is less that r, then we know the AP got fucked up before the query r. So we know no AP is present in the range.

If the queries results is more than r, then we know that there is an AP in the given range, as the last element after the AP is more than r.

I hope this explanation helps

Here is my submission which I absolutely stole from rlac.