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

[Trees][Binary Lifting] 501 - D Misha And Permutations

Misha and Permutations

Problem statement:

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

You're given two permutations of $n$. Their order might be $a$, and $b$. By "order" I mean, the index of the permutation. That is, for $n=3$, $0,1,2$ is the first permutation, whereas, $2,1,0$ is the last (=6th). 

So, we have to find $(a+b)%(n!)$th permutation. 

This is it. Simple. Isn't is? 

No. Nope. Nada. Wtf is this question man?

Okay, rants apart.

Ideas:

The major point here is the conversion of order, and the permutation. We convert the initial permutations into the order. Add them. Mod by n!, and then find the resulting permutation.

There are many problems with this approach. You'll have to find ways to interconvert order and permutation, plus the mod by n!. Since $1 \leq n \leq 200000$, thus $n!$ can be a very large number. You don't want to solve, this way.

Enter the [Factorial Number System](https://en.wikipedia.org/wiki/Factorial_number_system).

As the name suggests, it's the factorial number system. Instead of bases, you have factorials! An example would be:

$$ 4\times 4! + 3\times 3!+2\times 2!+1\times 1!+0\times 0!$$.

This number in factorial representation (or factoradic) can be written as $43210_{!}$, which in decimal representation can be written as $119_{10}$. 

A good property is that, we can represent permutations using factoradics. This way, we can ignore the decimal representation altogether. But you'll say what about the n! mod? We'll come back to that later. I promise.

Pemutation to factoradic conversions:

Given a permuation $3,0,2,1$. It's factoradic representation is not simply $4132_{!}$. We have to put some mind to it. 

We have $n=4$. So we have $A\times 3! + B\times 2! + C\times 1! + D\times 0!$. We have to find the values of $A,B,C$ and $D$. 

A = We can simply do that by finding number of elements smaller than 3. That is 3. 

Now we remove 3 from consideration, and have $\{0,1,2\}$. 

B = Number of elements smaller than 0? None. So 0. Remove 0. We're left with $\{1,2\}$.

C = Number of elements smaller than 2? 1. So 1. We have $\{1\}$ left.

D = 0

So, we have $3010_{!}$, representing $3,0,2,1$. To double check, you can find the decimal value, which comes out to be: $3\times 3!+0\times 2!+1\times 1!+ 0 \times 0! = 18+0+1+0 = 19$

As you can see here, 3021, is indeed the 19th permutation for n=4. 

The basic inference you can get from here is that factoradic representation gives the rank of the number, for the remaining numbers. 

This can be done by fenwick trees / Binary indexed trees, easily.

Modulus n!: 

Thanks to Ecenerwala's solution.

So, until now, we have converted the permutations into their factoradic representations, and added them. How do we do the mod n!?

A factoradic representation is of the form (for n):

$$X_{(n-1)!}\times (n-1)!+X_{(n-2)!}\times(n-2)!+...+X_{2!}\times 2!+X_{1!}\times 1!$$.

Thus if $X_{(i-1)!}>=i$, then it can be written in the form: $X_{(i-1)!} = i+(X_{(i-1)!}-i)$. Thus, the term $$X_{(i-1)!}\times (i-1)! = i \times (i-1)! + (X_{(i-1)!}-i\times (i-1)!) \\= i!+(X_{(i-1)!}-i\times (i-1)!$$

This extra $i!$ can be added to the next greater element. So, if we percolate up to $(n-1)$, then we might get an extra $n!$ element. That's it!

Isn't that what we want? We know that there can be at most one n! extra. You can check that. (Kuchh to krlo khud se)

Code for that:

Good. Beautiful.

Factoradic to permutation conversion:

So, as I mentioned earlier, factoradic-> Rank (well actually, number of elements smaller). So you have ranks, and  you want the permutation now. Consider $3010_{!}$ again. You want the (3+1)th element, amongst $0,1,2,3$ = 3. Remove 3. $\{0,1,2\}$ left. You want the (0+1)st element. You get 0. Remaining $\{1,2\}$. You want the (1+1)nd element. You get 2. Remaining $\{1\}$. You want the (0+1)st element. You get 1. So $3,0,2,1$ formed.

This can be done by binary searching on he fenwick tree, or doing binary lifting on it. 

My submission can be found here.