CF1817A Almost Increasing Subsequence

题意

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

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

思路

注意到，当有连续的\(x\geq y\geq z\)时，只需要拿走一个\(y\)，即可破坏这个三元组，将序列变为“几乎递增”的

所以，可以用一个前缀和\(f_i\)表示\(a_3\)到\(a_i\)之间满足\(a_{i-2}\geq a_{i-1}\geq a_i\)，那么最终的答案就是\(r-l+1-(f_r-f_{l+1})\)

简单解释一下，因为在\([l,r]\)这段区间里，我们每遇到一个三元组不满足题目要求都可以通过删除一个元素使其满足题目要求，所以最少删除的元素就是\(f_r-f_{l+1}\)个

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=2e5+10;
int a[Maxn],f[Maxn];
int n,q,l,r;
void run()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=3;i<=n;i++)
	{
		if(a[i-2]>=a[i-1] && a[i-1]>=a[i]) f[i]=1;
		else f[i]=0;
		f[i]+=f[i-1];
	}
	while(q--)
	{
		cin>>l>>r;
		cout<<r-l+1-(r-l+1<=2?0:(f[r]-f[l+1]))<<endl;
	}
}
signed main()
{
	run(); 
	return 0;
}