CF1817A.Almost Increasing Subsequence
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
A sequence is almost-increasing if it does not contain three consecutive elements x,y,z such that x≥y≥z .
You are given an array a1,a2,…,an and q queries.
Each query consists of two integers 1≤l≤r≤n . For each query, find the length of the longest almost-increasing subsequence of the subarray al,al+1,…,ar .
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.
输入格式
The first line of input contains two integers, n and q ( 1≤n,q≤200000 ) — the length of the array a and the number of queries.
The second line contains n integers a1,a2,…,an ( 1≤ai≤109 ) — 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≤l≤r≤n ) — the query is about the subarray al,al+1,…,ar .
输出格式
For each of the q queries, print a line containing the length of the longest almost-increasing subsequence of the subarray al,al+1,…,ar .
输入输出样例
输入#1
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
输出#1
3 4 3 1 4 2 7 1
说明/提示
In the first query, the subarray is a1,a2,a3=[1,2,4] . The whole subarray is almost-increasing, so the answer is 3 .
In the second query, the subarray is a1,a2,a3,a4=[1,2,4,3] . The whole subarray is a almost-increasing, because there are no three consecutive elements such that x≥y≥z . So the answer is 4 .
In the third query, the subarray is a2,a3,a4,a5=[2,4,3,3] . The whole subarray is not almost-increasing, because the last three elements satisfy 4≥3≥3 . An almost-increasing subsequence of length 3 can be found (for example taking a2,a3,a5=[2,4,3] ). So the answer is 3 .