牛客多校赛第9场D Error Permutaition
给定一个长度为n的排列，计算满足条件的子区间的个数。
对于子区间\([l , r]\)要求任意区间第k小，不在区间的第k个位置上。
\(n <= 5000\)
从每个值入手，设这个值为先，寻找对于x来讲是不合法的区间，也就是x在这个区间中是第k小，并且在区间的第k个位置上。
1. 如果固定区间左端点l，那么右端点r的应该是一段区间。
固定的左端点l，那么x在区间中的位置就可以确定了，假设是t。
向右移动右端点时，区间中小于x的数的数目就会逐渐增加，当增加到和t相等时对应的一段r就是对x来讲不合法的区间。
2. 而如果将左端点向左侧移动时，右端点对应的区间不会向左侧移动。
因为l左移，则x在区间中的位置是一定增加1的，也就是t变成了t+1。
但是比x小的数不一定增加1,（因为l-1上的数不一定是比x小的）。
所以r只有可能向右移动来补足比x小的数的数量。
3. 对于各个数字不合法的区间取并集，剩余的就是合法的区间
用\(Not[i][j]\)表示区间\([l ,r]\)是否合法。
因为l固定时，不合法的区间的r是连续的一段。所以可以利用差分的思想，给这一段整体标记。
#include<iostream>
using namespace std;
const int N = 5010;
int A[N] , Not[N][N];
void Solve()
{
int n , Answer = 0;
cin >> n;
for(int i = 1 ; i <= n ; ++i)
cin >> A[i];
for(int i = 1 ; i <= n ; ++i)
{
int r1 = i , r2 = i , cnt = 0;
for(int l = i ; l >= 1 ; --l)
{
if(A[l] <= A[i]) cnt++;
while(r2 + 1 <= n && cnt < i - l + 1)
{
r2++; r1 = r2;
if(A[r2] <= A[i]) cnt++;
}
if(cnt == i - l + 1)
{
while(r2 + 1 <= n && A[r2 + 1] > A[i]) r2++;
Not[l][r1]++; Not[l][r2 + 1]--;
// cout << l << ' ' << r1 << ' ' << r2 << '\n';
}
}
}
for(int i = 1 ; i <= n ; ++i)
{
for(int j = i ; j <= n ; ++j)
{
Not[i][j] = Not[i][j] + Not[i][j-1];
if(Not[i][j] == 0) Answer++;
}
}
cout << Answer << '\n';
for(int i = 1 ; i <= n + 1 ; ++i)
for(int j = i ; j <= n + 1 ; ++j)
Not[i][j] = 0;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T;
cin >> T;
while(T--) Solve();
return 0;
}