here is the [Problem][1].we are given an array. we have to find number of ways to partition array such that mex in each subset is not more than k .

i tried to solve it by first calculating all the ways to partition and then removing the ways which are not valid.

Sample input 1

n=10, k=3;

0 1 2 3 4 0 1 2 5 3

Output

379

total number of ways to partition are 2^(n-1)=2^9=512;

now i am having difficulty in removing the ways which are not valid.

can anyone help me to explain me this sample input.

[1]: CodeChef: Practical coding for everyone

Let dp[i] represents no.of ways to partition arr[1:i]

Now lets consider last partition cases which ends at i,lets say we last partition is [j:i] ,

Obviously if MEX of [j:i] is >k,then MEX of [j-1:i] is also >k.so we got a monotonous function ,we can apply binary search to find first p such that[p:i] MEX<=k,so now dp[i]=sum(dp[j]) where p-1<j<i

Do this using segment

How to find mex of arr[j:i] in logn complexity ? I mean what to store on each node of segment tree ?

please explain a little bit more ?

all i can think now is persistent segment tree,where each node [i:j] contains number of distinct element values in range[i:j]

So for [j:i] take ith segment tree,and (j-1)th segment tree

and then lets say u are node [a:b],see if mex lies in [a:(a+b)/2] or [(a+b)/2:b]