莫队、前缀和

看上去很强的性质可能满足传递性，总之就是注意察觉问题的性质。

如果对于长度为 $k$ 的序列 $x$ 不存在满足 $x_i \geq x_{i+1} \geq x_{i+2}$ 的正整数 $i (1 \leq i \leq k-2)$，就称序列 $x$ 为几乎上升序列。

给定长度为 $n$ 的序列 $a$ 和 $m$ 个询问，每次询问给定正整数 $l,r$，求 $a_l \sim a_r$ 中最长的几乎上升子序列长度，$1 \leq n,m \leq 2 \times 10^5$。

考虑满足 $a_i \geq a_{i+1} \geq a_{i+2}$ 的正整数 $i$，如果出现了满足这个条件的子序列，那么必定要删除 $a_i,a_{i+1},a_{i+2}$ 中的一个数，显然删掉哪个数是无所谓的。

因此获得做法，找到所有满足 $a_l \geq a_{l+1} \geq a_{l+2} \geq \cdots \geq a_r$ 的极长连续子序列，把 $a_l \sim a_r$ 删到剩余两个元素为止。由于找的是极长连续子序列，这些被找到的序列不会重合。

Solution 1：莫队，每次扩展到 $i$ 时，如果是从 $l$ 扩展到 $i$ 则判断 $a_i \geq a_{i+1} \geq a_{i+2}$ 是否不成立（注意区间长度小于等于 $2$ 的情况，这样也算不成立），如果不成立则增加贡献。同理如果是从 $r$ 扩展到 $i$ 则判断 $a_{i-2} \geq a_{i-1} \geq a_i$ 是否不成立。

由于 $n,m$ 同阶，时间复杂度 $O(n \sqrt{n})$。

#include<bits/stdc++.h>
using namespace std;
constexpr int B=500;
struct Question{int i,l,r;}q[200'005];
int n,m,a[200'005],ans[200'005];
inline int fl(int l,int r){
    if(r-l+1<=2) return 1;
    if(a[l]>=a[l+1]&&a[l+1]>=a[l+2]) return 0;
    return 1;
}
inline int fr(int l,int r){
    if(r-l+1<=2) return 1;
    if(a[r-2]>=a[r-1]&&a[r-1]>=a[r]) return 0;
    return 1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].i=i;
    sort(q+1,q+m+1,[](auto x,auto y){
        if(x.l/B!=y.l/B) return x.l/B<y.l/B;
        return (x.l/B)&1 ? x.r>y.r:x.r<y.r;
    });
    int l=1,r=1,sum=1;
    for(int i=1;i<=m;i++){
        while(q[i].l<l) --l,sum+=fl(l,r);
        while(q[i].r>r) ++r,sum+=fr(l,r);
        while(q[i].l>l) sum-=fl(l,r),++l;
        while(q[i].r<r) sum-=fr(l,r),--r;
        ans[q[i].i]=sum;
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

Solution 2：标记所有满足 $a_i \geq a_{i+1} \geq a_{i+2}$ 的正整数 $i$，求出 $[l,r-2]$ 中被标记的正整数的数量 $cnt$，答案为 $r-l+1-cnt$。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[200'005],sum[200'005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n-2;i++) if(a[i]>=a[i+1]&&a[i+1]>=a[i+2]) sum[i]=1;
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    for(int i=1;i<=m;i++){
        static int l,r,ans;
        scanf("%d%d",&l,&r);
        ans=r-l+1;
        if(ans>=3) ans-=sum[r-2]-sum[l-1];
        printf("%d\n",ans);
    }
    return 0;
}