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