Buy Tickets hoj 单调队列优化DP的简单应用

/*题意是问能相互看见的人有多少对。只需要建一个单调递减的队列。枚举每一个i时，对前i-1个元素形成的单调队列里找>=a[i]的元素的个数即可。简单、*/#include <iostream>#include <stdio.h>#define maxn 500001using namespace std;int q[maxn];int a[maxn];int main(){    int n;    while(scanf("%d",&n)==1)    {        int head=0,rear=0;        int step=0;        for(int i=1;i<=n;i++)        scanf("%d",&a[i]);        for(int i=1; i<n; i++)        {            while(head<rear&&q[rear-1]<a[i]) rear--;            q[rear++]=a[i];            int t=rear;            while(head<t)            {                t--;                if(head==t) step++;                else if(a[i+1]>=q[t]) step++;            }        }        printf("%d\n",step);    }    return 0;}