Almost Increasing Subsequence (Codeforces 1817A)
Tags: Greedy, binary search

A sequence is almost-increasing if it does not contain three consecutive elements $$$x, y, z$$$ such that $$$x\ge y\ge z$$$.You are given an array $$$a_1, a_2, \dots, a_n$$$ and $$$q$$$ queries.Each query consists of two integers $$$1\le l\le r\le n$$$. For each query, find the length of the longest almost-increasing subsequence of the subarray $$$a_l, a_{l+1}, \dots, a_r$$$. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input: The first line of input contains two integers, $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$)  — the length of the array $$$a$$$ and the number of queries.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)  — the values of the array $$$a$$$.Each of the next $$$q$$$ lines contains the description of a query. Each line contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$)  — the query is about the subarray $$$a_l, a_{l+1}, \dots, a_r$$$.

Output: For each of the $$$q$$$ queries, print a line containing the length of the longest almost-increasing subsequence of the subarray $$$a_l, a_{l+1}, \dots, a_r$$$.

Note: In the first query, the subarray is $$$a_1, a_2, a_3 = [1,2,4]$$$. The whole subarray is almost-increasing, so the answer is $$$3$$$.In the second query, the subarray is $$$a_1, a_2, a_3,a_4 = [1,2,4,3]$$$. The whole subarray is a almost-increasing, because there are no three consecutive elements such that $$$x \geq y \geq z$$$. So the answer is $$$4$$$.In the third query, the subarray is $$$a_2, a_3, a_4, a_5 = [2, 4, 3, 3]$$$. The whole subarray is not almost-increasing, because the last three elements satisfy $$$4 \geq 3 \geq 3$$$. An almost-increasing subsequence of length $$$3$$$ can be found (for example taking $$$a_2,a_3,a_5 = [2,4,3]$$$ ). So the answer is $$$3$$$.

Sample Inputs:
9 8
1 2 4 3 3 5 6 2 1
1 3
1 4
2 5
6 6
3 7
7 8
1 8
8 8

Sample Outputs:
3
4
3
1
4
2
7
1

Solution (Python):
import sys
input = sys.stdin.readline

def read_list():
    return list(map(int, input().split()))

def calculate_results(n, q, a):
    res = [0] * n
    for i in range(2, n):
        if a[i - 2] >= a[i - 1] >= a[i]:
            res[i] = res[i - 1] + 1
        else:
            res[i] = res[i - 1]
    results = []
    for i in range(q):
        (l, r) = read_list()
        result = r - l + 1
        if result >= 3:
            result -= res[r - 1] - res[l]
        results.append(result)
    return results
(n, q) = read_list()
a = read_list()
results = calculate_results(n, q, a)
for result in results:
    print(result)

Solution (Python):
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
valid = []
out = []
for i in range(2, n):
    if a[i - 2] >= a[i - 1] >= a[i]:
        valid.append(0)
    else:
        valid.append(1)
pref_sum = [0, 0, 0]
for v in valid:
    pref_sum.append(pref_sum[-1] + v)
for _ in range(q):
    (l, r) = map(int, input().split())
    l -= 1
    if r - l <= 2:
        out.append(r - l)
    else:
        out.append(2 + pref_sum[r] - pref_sum[l + 2])
print('\n'.join(map(str, out)))

Solution (Python):
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
x = list(map(int, input().split()))
freq = [0] * (1 + n)
for i in range(n - 2):
    if i == 0:
        (a, b, c) = (x[i], x[i + 1], x[i + 2])
    else:
        (a, b, c) = (b, c, x[i + 2])
    if a >= b >= c:
        freq[i + 3] = freq[i + 2] + 1
    else:
        freq[i + 3] = freq[i + 2]
for i in range(q):
    (l, r) = map(int, input().split())
    ans = r - l + 1
    if ans >= 3:
        ans -= freq[r] - freq[l + 1]
    print(ans)