Codeforces contest[user:uditgupta][submission:27884973][problem:http://mirror.codeforces.com/problemset/problem/597/C]-Consider for index ith

-Now at each index we want to find number of subsequences ending at index i

of length 1 , 2 , 3 ... k+1 ;

How we can compute this ?

say arr[i] == 5

if know number of subsequences which end at value either 1 or 2 or 3 or 4

from index 1 to index i+1

pls read above lines again if not clear.

so now wat the equation becomes

no of subsequences of length k+1 which end at index i=

    number of subsequences of length k which end at [value 1] from index range 1  to (i-1) of given array

    +   number of subsequences of length k which end at [value 2] from index range 1  to (i-1) of given array 

    +   number of subsequences of length k which end at [value 3] from index range 1  to (i-1) of given array 

    +   number of subsequences of length k which end at [value 4] from index range 1  to (i-1) of given array   

For this part we can use Segemnt Tree to compute sum of subsequences ...

Segment tree : we use tree[1] to store number of subsequences which end at value 1

             : we use tree[2] to store number of subsequences which end at value 2


But we want number of subsequences of length 1 , 2 ,3 .. (k+1)

 So we will use 2-d Segment Tree

My submission : http://mirror.codeforces.com/contest/597/submission/27884973