I saw a problem somewhere and I want to know the most efficient for this problem.
You're given t testcases an array aof n elements and q queries. Each query gives you a range l and r. You want to get a subsegment in [l,r] so that the subsegment is sorted in increasing order.
For example
Input
3
5 2
1 2 3 5 4
1 5
3 5
5 2
1 2 3 4 5
1 5
3 5
6 5
1 4 2 3 9 1
1 3
1 2
1 6
3 6
6 6
Output
4
2
5
3
2
2
3
3
1
I heard that problem can bo solved with segment trees but I don't know how
What do you mean by "You want to get a subsegment in [l,r] so that the subsegment is sorted in increasing order."? Is it to get any pair $$$(tl;tr)$$$ s.t. $$$a[tl..tr]$$$ is sorted, or get number of such pairs or what?
Based on "reverse-engineering" the provided input-output, I think the OP probably means to find the length of a longest such sorted subarray a[tl..tr] with l <= tl <= tr <= r.
A "hint" to the OP could be:
Use the array generated by the STL function adjacent_difference as your new input and see what you need in terms of that array
Segment trees seem like the way to go. Using them, for each testcase, the time complexity will be
O(n)for preprocessing andO(q * logn)for the queries (in total). We can round the total complexity for the problem toO(t * n * logn), so around 20 * 100000 * 17 = 34000000 = 34M "steps" at most, which is really reasonable.Start from the bottom. Keep 3 variables for each node: pref, suf, ans. pref = max. length of a subsegment that is in increasing order, starts at the left end of the segment marked by the node and end inside the segment; suf = ..... ends at the right end of the segment ......; ans = best increasing order subsegment in the segment.
For each node, if the data for both children is correct, you can create its pref, suf and ans in O(1).
Create pref using the prefs, create suf using the sufs, create ans using the ans for both children AND a combination of left child suf and right child pref. There are a few cases to consider, and you might have to compare the last element of the left child's segment with the first element of the right child's segment.