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

若想有三点满足这条公式 ,假设 已知两点的坐标,若想使 点坐标 满足上述公式这一点 需要落在 以 为对角线的矩形上 图片说明
因为题目的限制,所以一个序列是否是好序列,相当于取寻找这个序列的最长(不降 / 不升)子序列是否大于等于3,如果大于等于3,那么就是坏序列,还存在这样一个性质这个好序列的长度最长只有4.
证明:我们构造一个组长度为4的好序列,首先这个数不能比(最大的大 比 最小的小 ) 这点显而易见,对于在除最大最小的两个数,剩下的数的其中 一个数 ,我们所构造的这个数那么比他大要么比他小 比他大 它和最小值就组成不降序列,同样比他小 它和最大值就组成 不升序列, 那么题目的答案就是 以序列中每个元素开头,看他先后能形成最长的连续序列有多长,那么加上它的贡献,就是最后的答案

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define NUM 200010
#define LL long long 
using namespace std;
int n,arr[NUM];
LL ans =0;
bool check(int *p ,int l,int r){
    int le = r-l+1;
    if (le <=2) return true;
    for (int i =l;i<=r;i++){
        for (int j =i+1;j<=r;j++){
            for (int k=j+1;k<=r;k++){
                if ((p[i]<=p[j] && p[j] <= p[k]) || (p[i]>=p[j] && p[j]>=p[k]) )
                    return false;
            }
        }
    }
    return true;
}
void sovle () {
    ans = 0;
    scanf("%d",&n);
    for (int i =0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    for (int i=0;i<n;i++){
        int tq =1;
        for (int q=0,j =i-1;j>=max(0,i-3);j--){
            if (check(arr,j,i))
                tq++;
            else break;
        }
        // int tp = 1;
        // for (int p=0, j =i-1;j>=0;j--){
        //     if (arr[j]<=arr[j+1]) p++;
        //     //else break;
        //     if (p>=2) break;
        //     tp++;
        // }
        ans += tq;
    }
    printf("%lld\n",ans);
    return ;
}
int main () {
    int t;
    scanf("%d",&t);
    while (t--){
        sovle();
    }
    return 0;
}