# CF 319B Psychos in a Line 【单调队列】

oh it is

```#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int NN=111111;
int f[NN];
struct Q{
int x,pos;
}q[NN*10];
int main(){
#ifndef ONLINE_JUDGE
freopen("G:/in.txt","r",stdin);
//freopen("G:/myout.txt","w",stdout);
#endif
int n,pos=0;cin>>n;
for(int i=1;i<=n;i++)
cin>>f[i];
for(int i=2;i<=n;i++){//找到一开始递增的数串中最后一个数
if(f[i]<f[i-1]){
pos=i;
break;
}
}
if(pos==0){//全递增
cout<<0<<endl;
return 0;
}
int maxn=0;
q[tail++]=(Q){f[1],1};
for(int i=pos;i<=n;i++){
if(f[i]<q[tail-1].x){//没有弹出数的是第一场就被吃掉的
q[tail++]=(Q){f[i],1};
maxn=max(q[tail-1].pos,maxn);
}else if(f[i]>q[tail-1].x){//弹出数中最大场次+1是该数被吃掉的场次
int maxpos=0;
while(f[i]>q[tail-1].x && tail>0){
maxpos=max(maxpos,q[tail-1].pos);
tail--;
}
if(tail==0){
q[tail++]=(Q){f[i],1};
}else{
q[tail++]=(Q){f[i],maxpos+1};
}
maxn=max(q[tail-1].pos,maxn);
}
}
cout<<maxn<<endl;
return 0;
}
```
` `

## Codeforces Round #189 (Div. 1) B. Psychos in a Line 单调队列

B. Psychos in a Line Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/problemset/problem/319/B Description 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 h

## codeforces 251A Points on Line(二分or单调队列)

Description Little Petya likes points a lot. Recently his mom has presented him n points lying on the line OX. Now Petya is wondering in how many ways he can choose three distinct points so that the distance between the two farthest of them doesn't e

## HDU 4122 Alice&#39;s mooncake shop 单调队列优化dp

Alice's mooncake shop Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4122 Description The Mid-Autumn Festival, also known as the Moon Festival or Zhongqiu Festival is a popular harvest festival celebrated by Ch

## hdu 1506 Largest Rectangle in a Histogram 单调队列

Largest Rectangle in a Histogram Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 12554    Accepted Submission(s): 3509 Problem Description A histogram is a polygon composed of a sequence of rec

## [ACM] poj 2823 Sliding Window（单调队列）

Sliding Window Time Limit: 12000MS   Memory Limit: 65536K Total Submissions: 36212   Accepted: 10723 Case Time Limit: 5000MS Description An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left