题解 | #AsubB#_牛客博客

我们容易发现一个事实，假设 $[l,r]$ 能够成为一个答案，那么 $[l,r-1]$ 一定也是一个答案，也就是说，当我们固定 $l$ 时，一定存在一个分界点 $p$ ，使得 $[l,l]$ 到 $[l,p]$ 都是答案，而 $[l,p+1]$ 到 $[l,n-1]$ 都不是答案。所以对每个 $l$ ，考虑二分这个分界点 $p$ ，每次只需要判断 $[l,p]$ 是不是答案，然后缩小范围即可。

而判断 $[l,p]$ 是不是答案是容易的，我们可以暴力处理出来 $a_l \sim a_r$ 和 $a_1 \sim a_{l-1} + a_{r+1} \sim a_n$ ，然后判断 $a_l \sim a_r$ 是不是 $a_1 \sim a_{l-1} + a_{r+1} \sim a_n$ 的子序列即可，显然这是容易做到的。

时间复杂度 $O(n^2 \log n)$ ，通过绰绰有余了。代码：

#include<bits/stdc++.h>
#define ll long long
#define vec vector
#define pb push_back
using namespace std;
ll n,a[2005],b[2005],c[2005],ans=0;
bool ck(ll l,ll r){
    ll tot=0,cnt=0,pos=1;
    for(ll i=1;i<l;i++) b[++tot]=a[i];
    for(ll i=r+1;i<=n;i++) b[++tot]=a[i];
    for(ll i=l;i<=r;i++) c[++cnt]=a[i];
    for(ll i=1;i<=cnt;i++){
        while(pos<=tot&&b[pos]!=c[i]) pos++;  
        if(pos>tot) return false;
        pos++;
    }
    return true;
}
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>a[i];
    for(ll i=2;i<n;i++){
        ll l=i,r=n-1,res=0;
        while(l<=r){
            ll md=(l+r)>>1;
            if(ck(i,md)){
                l=md+1;
                res=md;
            }else{
                r=md-1;
            }
        }
        ans+=(!res?0:res-i+1);
    }
    cout<<ans<<endl;
}