CF 196B(Psychos in a Line-单调队列贪心)

There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who has an id greater than the psycho to his right (if exists) kills his right neighbor in the line. Note that a psycho might kill and get killed at the same step.

You're given the initial arrangement of the psychos in the line. Calculate how many steps are needed to the moment of time such, that nobody kills his neighbor after that moment. Look notes to understand the statement more precise.

Input

The first line of input contains integer n denoting the number of psychos, (1 ≤ n ≤ 10⁵). In the second line there will be a list of n space separated distinct integers each in range 1 to n, inclusive — ids of the psychos in the line from left to right.

Output

Print the number of steps, so that the line remains the same afterward.

Sample test(s)input

10
10 9 7 8 6 5 3 4 2 1

output

input

6
1 2 3 4 5 6

output

Note

In the first sample line of the psychos transforms as follows: [10 9 7 8 6 5 3 4 2 1] → [10 8 4] → [10]. So, there are two steps.

考试的时候一直想这题是单调队列优化DP的LIS??结果试了半天没试出来。

......

听CCR说这题没错是单调队列，一个人杀人的次数可以NlogN求出来。。。=调换的次数（没听懂。。。）

讲一下辛苦YY的O(n)做法：

令f[i]表示[i,n]中i杀人的次数

从后向前推

若i杀得到j(不会被其它人杀) 则

（1）i把j杀时j未杀完,j未杀的归i

（2）j杀完，i杀j

可以用单调队列判断j是i第几个杀的

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define MAXN (100000+10)
int n,st[MAXN],size=0,a[MAXN],kill[MAXN]={0},f[MAXN]={0};
int main()
{
freopen("CF319B.in","r",stdin);
int ans=0;
scanf("%d",&n);
For(i,n) cin>>a[i];
ForD(i,n)
{
int t=0;
while (size&&a[st[size]]<a[i]) {t++,f[i]=t=max(t,f[st[size]]),size--;}
st[++size]=i;
ans=max(ans,t);
}
cout<<ans<<endl;
return 0;
}

秒客网

CF 196B(Psychos in a Line-单调队列贪心)

相关文章