2023牛客多校第九场 D Non-Puzzle: Error Permutation

题意

给定一个长度为n的序列，计算有多少个子区间满足子区间第K小的数不在子区间第K位。

找出所有不满足条件的区间。枚举所有的ai和左端点al，找出满足ai是区间[l,r]中第r-l+1小的右端点r，则右端点r一定是一段区间。

例如      3 4 2 1 6 5

                 l  i     

则r=[3,6]

当l向左移动时，如果al<ai，则r不变，否则r就向右移动。

使用双指针维护找到所有不满足条件的区间。将不合法区间合并，最终答案就是剩余的区间个数。

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

int sum[5001][5001];
signed main()
{
    IO;
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin >> n;
        vector<int> vec(n + 1);
        for (int i = 0; i <= n + 1;i++)
            for (int j = 0; j <= n + 1;j++)
                sum[i][j] = 0;
        for (int i = 1; i <= n;i++)
            cin >> vec[i];
        for (int i = 1; i <= n;i++)
        {
            int l = i, r = i;
            while(r<n&&vec[r+1]>vec[i])
                r++;
            sum[i][l]++, sum[i][r + 1]--;
            for (int j = i - 1; j >= 1;j--)
            {
                if(vec[j]>vec[i])
                {
                    l = r + 1;
                    r = l;
                    while(r<n&&vec[r+1]>vec[i])
                        r++;
                }
                if(l<=n)
                    sum[j][l]++, sum[j][r + 1]--;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n;i++)
        {
            int f = 0;
            sum[i][i - 1] = 0;
            for (int j = i; j <= n;j++)
            {
                f += sum[i][j];
                if(!f)
                    ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}