HILO - High and Low
A student is always bored during his math classes. As the teacher won't let him sleep, he finds something else to do: try to find patterns in the numbers written on the board! Currently, he's spending his time trying to find Hi&Lo subsequences.
Intuitively, a Hi&Lo sequence is any sequence that has consecutive differences with opposite signs, that is, if the first number is greater than the second, then the second is smaller than the third, the third is greater than the fourth, and so on.
Formally, let x, x, ..., x[n] be the numbers written on the board. A Hi&Lo subsequence of length k that only uses elements from A to B is a sequence of indices a1, a2, ..., ak such that:
- B ≥ ak > ... > a2 > a1 ≥ A
- x[ai]- x[ai-1] != 0, for 1 < i <= k
- ( x[ai] - x[ai-1] )( x[ai+1] - x[ai] ) < 0, for 1 < i < k
Note that every sequence with only one element is a Hi&Lo sequence.
However, as the amount of numbers increases, finding a big subsequence is getting harder and harder, so he asked you to create a program to help him and quickly find the largest Hi&Lo subsequence in a given interval.
The input contains several test cases. A test case begins with a line containing integers N (1 ≤ N ≤ 100000) and M (1 ≤ M ≤ 10000), separated by spaces. On the second line there are N positive integers, the initial state of the board. M lines follow, each with an instruction. Instructions can be of two kinds:
1) q A B: Print the length of the longest high & low subsequence only using elements in positions from A to B, inclusive. You may assume that 1 ≤ A ≤ B ≤ N.
2) m A B: Modify the Ath element of the sequence to the positive integer B. You may assume that 1 ≤ A ≤ N.
No number on the board will ever exceed 109. There is a blank line after each test case. The last test case is followed by a line containing two zeros.
For each instruction of type 1, print a line containing an integer, the answer to the query. After each test, print a blank line.
Input:5 7 1 2 3 4 5 q 2 4 m 3 1 q 2 4 m 3 2 q 2 4 m 4 2 q 2 4
Output: 2 3 2 1
1 Fenwick tree (getting the next turnpoint to the left or right in log(n)^2 instead log(n)) seems to be a tiny little faster...
If you have the stupid idea to solve this with 3 Fenwick trees, be prepared to suffer from 11 assertion failures, 1 wrong answer and 1 TLE during 4 different days while figuring out why your assumptions where wrong :/
does the elements of the subsequence should be consecutive?
Hussain Kara Fallah:
really hard problem !!
Strong, really strong test cases!!!
Buda IM (retired):
Yes indeed, cool problem
This one was A LOT of fun. Well done!