526互联

CF1817A Almost Increasing Subsequence

发布时间 2023-10-13 21:26:56作者: 悲伤鳄鱼吃面包

CF1817A

题面翻译

给定长度为 \(n\) 一个序列 \(a\) 以及 \(q\) 次询问，每次询问给出 \(l\) 和 \(r\)，找出序列 \(a\) 在 \([l,r]\) 内最长的几乎递增子序列。

对于几乎递增的定义：如果一个序列中不存在连续的三个数 \(x\)，\(y\)，\(z\)，使得 \(x \ge y \ge \ z\)，则这个序列是几乎递增的。

题目描述

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.

输入格式

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 $ .

输出格式

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 $ .

样例 #1

样例输入 #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 $ 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 $ .

分析

对于给定的序列a, 如果序列长度为2, 那肯定合法, 如果长度增加为3, 那我们就考虑新进来的那个数 a[3] 是否会与 a[2] 和 a[1] 构成不合法的序列, 如果是的话我们直接将 a[3] 删除即可

对此我们可以使用前缀和思想, s[i] 表示从1到i有几个数会使不合法部分出现, 我们称这些数为坏数, 在计算询问[l, r]的答案的时候, 我们只需要把区间长度减去这段区间内的坏数个数即可

注意:

  • s[l]是否 +1, 是由 a[l - 1] 和 a[l - 2] 决定的, 而 a[l - 1] 和 a[l - 2] 是区间外边的数, 我们不希望 [l, r] 的结果被区间外的数影响, 那我们就要减去被区间外边的数影响才变成坏数的数的个数, 所以区间[l, r]上实际的坏数个数 = s[r] - s[l + 1], 其中s[l + 1]既代表不在区间内的坏数, 也代表被区间外的数影响才变成坏数的数的个数

综上, ans = (r - l + 1) - (s[r] - s[l + 1]);

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N], s[N];
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		if (i < 3)
			continue;
		else
		{
			if (a[i] <= a[i - 1] && a[i - 1] <= a[i - 2])
				s[i] = s[i - 1] + 1;	//代表坏数, 最终要合法只需把坏数删掉即可
			else
				s[i] = s[i - 1];
		}
	}
	while (m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		if (r - l + 1 < 3)
			printf(" %d\n", r - l + 1);
		else
			printf(" %d\n", r - l + 1 - (s[r] - s[l + 1]));
	}
	return 0;
}