Educational Codeforces Round 111 (Rated for Div. 2) C. Manhattan Subarrays

题意：给定一个长度为n的序列，问有多少子串符合以下要求
不存在任意三点满足d(p,r)=d(p,q)+d(q,r)出现在子串当中
子串种的一点的曼哈顿坐标为(ai,i)
d(x,y)为x与y的曼哈顿距离

思路：

1.首先子串是连续的，我一开始还以为是子序列不连续，后面发现样例对不上理解……

2.首先随便挑出一个样例会发现，只有当xa<=xb<=xc,ya<=yb<=yc这种格式出现时，才能有效得到答案，我也是使用了类似于画图的方式得到，还有例举样例得证
出自CF1550C 题解 - 洛谷专栏   网上看到比较好的解释

3.既然已知只有这种情况，那么原题目其实就在求最长非递减递增子序列，本人利用了栈求得，然后算贡献即可
这里使用栈模仿了类似LIS贪心优化，由于长度超过3就结束了，而且第一个元素不能去掉，所以不需要二分，贪心的求最长就行

4.看似时间复杂度有问题，但是你可以模拟或者怎样，因为是非递减非递增，如果你想让一个元素的非递减非递增尽可能长，你会发现最后弄出来的序列，它的子序列长度根本就不会很长，因此看似时间复杂度O(n*n)，实际上就是常数O(n)

所以枚举每个l，算出它的最长选取的地方算贡献，注意下标问题，前面已经选取的区间自己就不要在用了，因为会含括
样例：
1
5
9 3 5 6 3
9 3 5 6种3 5 6已经是错误的了，但是9 3 5 6的栈判断不出来

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS                       \
	std::ios::sync_with_stdio(0); \
	std::cin.tie(0);              \
	std::cout.tie(0)

const int N = 3e5 + 5;
const int INF = 1e18;
// const int MOD = 998244353;
// const int MOD=1e9+7;
// const int MOD=100003;
const int maxn=5e5+10;



void solve(){
    int n;
    std::cin >> n;
    std::vector<int> ve(n);
    for(int i=0;i<n;i++){
        std::cin >> ve[i];
    }

    int ans=2*n-1;
    // std::cout << ans << '\n';
    int last=n;
    for(int i=n-3;i>=0;i--){
        stack<int> up;
        stack<int> down;
        up.push(ve[i]);
        down.push(ve[i]);
        int f=0;
        for(int j=i+1;j<=last;j++){
            // std::cout << i << " " << j << " " << up.size() << " " << up.top() << '\n';
            // std::cout << i << " " << j << " " << down.size() << " " << down.top() << '\n';
            if(up.size()>=3){
                int len=j-i-3;
                ans+=std::max(0ll,len);
                // std::cout << i << " " << len << " YES\n";
                last=j-1;
                f=1;
                break;
            }
            if(j==last) goto p;
            if(ve[j]>=up.top()){
                up.push(ve[j]);
            }
            else if(up.size()>1 && ve[j]>=ve[i] && ve[j]<up.top()){
                up.pop();
                up.push(ve[j]);
            }

            p:
            if(down.size()>=3){
                int len=j-i-3;
                ans+=std::max(0ll,len);
                // std::cout << i << " " << len  << " NO\n";
                f=1;
                last=j-1;
                break;
            }
            if(j==last) break;
            if(ve[j]<=down.top()){
                down.push(ve[j]);
            }
            else if(down.size()>1 && ve[j]<=ve[i] && ve[j]>down.top()){
                down.pop();
                down.push(ve[j]);
            }
        }
        if(f==0){
            // std::cout << i << " " << last-i-2 << " fuck\n"; 
            ans+=std::max(0ll,last-i-2);
        }
    }

    std::cout << ans << '\n';
}

signed main(){
    IOS;

    int t=1;
    std::cin >> t;
    while(t--){
        solve();
    }
}