Problem Statement
Takahashi loves sorting.
He has a permutation (p1,p2,…,pN) of the integers from 1 through N. Now, he will repeat the following operation until the permutation becomes (1,2,…,N):
First, we will define high and low elements in the permutation, as follows. The
i-th element in the permutation is high if the maximum element between the
1-st and
i-th elements, inclusive, is the
i-th element itself, and otherwise the
i-th element is low.Then, let
a1,a2,…,ak be the values of the high elements, and
b1,b2,…,bN−k be the values of the low elements in the current permutation, in the order they appear in it.Lastly, rearrange the permutation into
(b1,b2,…,bN−k,a1,a2,…,ak).
How many operations are necessary until the permutation is sorted?
Constraints
1≤N≤2×105(p1,p2,…,pN) is a permutation of the integers from
1 through
N.
Input
Input is given from Standard Input in the following format:
N
p1 p2 ...
pN
Output
Print the number of operations that are necessary until the permutation is sorted.
Sample Input 1
Copy
5
3 5 1 2 4
Sample Output 1
Copy
3
The initial permutation is (3,5,1,2,4), and each operation changes it as follows:
In the first operation, the
1-st and
2-nd elements are high, and the
3-rd,
4-th and
5-th are low. The permutation becomes:
(1,2,4,3,5).In the second operation, the
1-st,
2-nd,
3-rd and
5-th elements are high, and the
4-th is low. The permutation becomes:
(3,1,2,4,5).In the third operation, the
1-st,
4-th and
5-th elements are high, and the
2-nd and
3-rd and
5-th are low. The permutation becomes:
(1,2,3,4,5).
Sample Input 2
Copy
5
5 4 3 2 1
Sample Output 2
Copy
4
Sample Input 3
Copy
10
2 10 5 7 3 6 4 9 8 1
Sample Output 3
Copy
6
题意：给一个排列，
每次把max(a[1] to a[i]) = a[i]的放进vector A（记为high）里，其他放进vector B（记为low）里 然后把序列改成B + A 问升序排序需要搞多少次
题解：
我基本就是在翻译题解...
考虑去掉1剩下2到n的序列，剩下的答案是T，1并不影响其他数的操作 那么最后的答案一定是T或者T + 1 如果T = 0，直接判 如果T > 0， 考虑T - 1次操作之后的情况 记f为这个序列的第一项，显然f > 2 (如果f = 2，那么要么这个序列已经被排好序或者下一次f会被移到后面) 如果最后是(f, 1, 2)答案是T否则是T + 1 结论1： (考虑序列2到n) 在前T - 1次， f不会出现它在不第一个位置且它又是high的情况 证明1： 考虑某个时刻x是high但是不在第一个位置， 显然第一个位置是high， 故vectorA中x前面还有一个数，记为y， y < x 如果x, y都是high或者都是low，它们的相对位置不变 如果x, y是high而y变成low了，这时y仍然在x左边，如果x不在第一个位置，和之前一样了 结论2： 定义循环序列(a, b, c) = (b, c, a) = (c, a, b) 则1, 2, f在前T - 1次组成的(关于它们位置的)循环序列不会变 证明2： 如果1是第一个元素 { 如果2是第二个元素，那么1, 2是high， f是low 如果f是第二个元素，那么1, f是high， 2是low 否则2, f都是low } 如果2是第一个元素，那么2是high，1和f是low 如果f是第一个元素，那么f是high，1和2是low 否则1, 2, f都是low 然后就证明完了
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define fill( x, y ) memset( x, y, sizeof x )
#define copy( x, y ) memcpy( x, y, sizeof x )
using namespace std;
typedef long long LL;
typedef pair < int, int > pa;
inline int read()
{
int sc = 0, f = 1; char ch = getchar();
while( ch < '0' || ch > '9' ) { if( ch == '-' ) f = -1; ch = getchar(); }
while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0', ch = getchar();
return sc * f;
}
const int MAXN = 200020;
int q[MAXN], p[MAXN], n, T[MAXN], f[MAXN];
int main()
{
#ifdef wxh010910
freopen( "data.in", "r", stdin );
#endif
n = read();
for( int i = 1 ; i <= n ; i++ ) q[ p[ i ] = read() ] = i;
for( int i = n - 1 ; i ; i-- )
{
if( !T[ i + 1 ] )
{
if( q[ i ] > q[ i + 1 ] ) T[ i ] = 1, f[ i ] = i + 1;
else T[ i ] = 0;
}
else
{
int cnt = 0;
cnt += q[ f[ i + 1 ] ] < q[ i ];
cnt += q[ i ] < q[ i + 1 ];
cnt += q[ i + 1 ] < q[ f[ i + 1 ] ];
if( cnt == 2 ) T[ i ] = T[ i + 1 ], f[ i ] = f[ i + 1 ];
else T[ i ] = T[ i + 1 ] + 1, f[ i ] = i + 1;
}
}
return printf( "%d\n", T[ 1 ] ), 0;
}
