# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3673 |

3 | Um_nik | 3493 |

4 | apiadu | 3397 |

5 | 300iq | 3317 |

6 | maroonrk | 3250 |

7 | Benq | 3230 |

8 | LHiC | 3229 |

9 | TLE | 3223 |

10 | ecnerwala | 3216 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 192 |

2 | Errichto | 186 |

3 | tourist | 182 |

4 | vovuh | 170 |

5 | pikmike | 169 |

6 | ko_osaga | 165 |

7 | Radewoosh | 164 |

8 | Um_nik | 162 |

9 | 300iq | 155 |

10 | Petr | 154 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/05/2020 19:16:43 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

EDIT: misunderstood the problem

This is interesting. You just solved the longest increasing subsequence problem in

O(n) ? Care to explain how?My mistake, I thought subsequence meant consecutive, thanks for correcting me.

No problem.

On a sidenote, my solution to OP's problem has complexity

O(t*n*log10000) using segment tree.so what is the solution for the problem ?

Ok, well I reduced the problem to the following one:

You are given an array of integers and a number of queries. Each query is of the form

a,b.The query means — Find out the maximum element in the range [

a,b]. Also find out the number of occurences of the maximum element in that range.sorry but it is not clear to me :( can you please describe it a little more ?

Thank you very much , good answers ....

so no one ??

this problem almost the same as find longest increasing sub-sequence.

in longest increasing sub-sequence problem the dp states is dp[i] which represent the length of longest increasing sub-sequence from using only numbers from 1 to i and i'th element must be included , and it's calculated like this dp[i]= max ( dp[j] + 1) for all j<i and Array[j]<Array[i]

this is O(N^2) and it is easy to reduce it to O(N log N) using data structures, however this only calculates the length of longest increasing sub-sequence , how to count how many sub-sequences are there?

it is very simple let cnt[i] represent the number of sub-sequences which satisfy the conditions of dp[i] then to calculate cnt[i] do the following while you iterate over j to calculate dp[i]:

if you find j such that dp[j]+1>dp[i] then make the value of cnt[i] equal to cnt[j]

if you find j such that dp[j]+1==dp[i] then add to cnt[i] the value of cnt[j]

if you find j such that dp[j]+1<dp[i] ignore it.

now let's back to your problem , to solve it you need little bit change to dp states so it will become dp[i][0] represent longest mountain-sequence while it's in increasing part of it

and dp[i][1] represent longest mountain-sequence while it's in decreasing part of it

now it's your exercise to continue solving the problem based on my explanation of longest increasing sub-sequence problem