题意
给定一个长度为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; }