更好的阅读体验

题目翻译

我们定义“几乎递增”序列表示这个序列没有 $3$ 个连续的元素 $x,y,z$ 使得 $x\ge y\ge z$。

现在有一个长度为 $n$ 的序列，有 $q$ 次询问，每次问一个区间 $[l,r]$，你回答 $[l,r]$ 中最长的“几乎递增”子序列长度。

一行 $2$ 个正整数 $n,q$ 表示长度和查询个数。

$q$ 行每行 $1$ 个整数，表示最长的“几乎递增”子序列长度。

$1\leq n,q\leq 2\times 10^5,a_i\leq 10^9$。

题目思路

这里讲一下莫队算法。

因为莫队算法是基于分块的，也就是说每个询问，莫队算法的时间复杂度为 $\mathcal O(\sqrt n)$，总时间复杂度 $\mathcal O(q\sqrt n)$，可以接受。

很显然，这题在进行莫队的时候，我们只需对于新进的数字判断一下三个数关系即可实现莫队精华部分。

接着我们按照莫队常规操作记录编号输出即可。

完整代码

#include<bits/stdc++.h>
usingnamespacestd;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
char buf[1000000],*p1=buf,*p2=buf;
inline int read()
{
    registerchar c=getchar();registerint x=0;
    while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}
int len,n,q;
int a[200020];
int ans[200020];
struct node
{
	int l,r,id;
}b[2000020];
bool cmp(node x,node y)
{
    int fx=(x.l-1)/len,fy=(y.l-1)/len;
    if(fx^fy)return fx<fy;
    if(fx&1)return x.r>y.r;
    return x.r<y.r;
}
int main()
{
    n=read();q=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    len=sqrt(n);
    for(int i=1;i<=q;i++)
    {
        int l,r;
        l=read();r=read();
        b[i]={l,r,i};
    }
    sort(b+1,b+q+1,cmp);
    int l=1,r=0,ANS=0;
    for(int i=1;i<=q;i++)
	{
		while(r<b[i].r)
		{
			r++;ANS++;
			if(r-l+1<3)continue;
			if(a[r-2]>=a[r-1]&&a[r-1]>=a[r])ANS--;
		}
		while(r>b[i].r)
		{
			if(r-l+1<3)
			{
				r--;ANS--;
				continue;
			}
			if(a[r-2]<a[r-1]||a[r-1]<a[r])ANS--;
			r--;
		}
		while(l<b[i].l)
		{
			if(r-l+1<3)
			{
				l++;ANS--;
				continue;
			}
			if(a[l]<a[l+1]||a[l+1]<a[l+2])ANS--;
			l++;
		}
		while(l>b[i].l)
		{
			l--;ANS++;
			if(r-l+1<3)continue;
			if(a[l]>=a[l+1]&&a[l+1]>=a[l+2])ANS--;
		}
		ans[b[i].id]=ANS;
	}
	for(int i=1;i<=q;i++)
    {
        printf("%d\n",ans[i]);
    }
    return0;
}