牛客多校赛第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;
}