ALORA6 - Editorial(ALOHOMORA)

Problem Link: ALORA6

Author: Rishup_nitdgp

Tester: Shivansh7

Editorialist: Aman0312

Pre-Requisite:Segment Trees or BIT.

Problem:Find the number of possible strictly increasing subsequences in the given sequence
such that the maximum element of this subsequence is at max k.

Explanation:

We will use the following notation:

S[i]:Number of strictly increasing subsequences in which maximum element is i.

Query_Operation(l,r): Sum of values from l to r in S array.

Update_operation(pos,val): Add val to S[pos].

n:Size of array.

When array size is x-1,S[i] denotes Number of strictly increasing subsequences in array of size
x-1 in which maximum element is i.
So when we add an element(array size becomes x) no. of strictly increasing subsequences in
which maximum element is a[x] is equal to (1+sum of all strictly increasing subsequences in
which maximum element is less than a[x]) which is nothing but Query_ Operation(1,a[x]-1);
Now we will update the values of S[a[x]] by Update_ Operation.

Initially all S[i] were zeroes.
After adding all elements S[i] denotes Number of strictly increasing subsequences in array of size
n in which maximum element is i.

We can perform update and query operations efficiently in O(log N) by segment trees
or BIT(Fenwick Tree) easily.

Queries:

Answer will be Query_operation(1,k) because we have to find the no. of
strictly increasing subsequences in which max element is ATMOST k.

But there is a problem,if array elements are equal to 1e9 we cannot make S array of size
1e9.We can use coordinate compression and make sure that array size will not
be greater than 1e5.

Time Complexity:T*(N logN +Q logN).

Solution: Link

Setters Solution:Link

//