B. Psychos in a Line
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 ≤ 105). 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
2
input
6
1 2 3 4 5 6
output
0
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第幾個殺的
[cpp]
#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;
}
#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;
}
