hdu 3410 Passing the Message(单调队列)

题目链接：hdu 3410 Passing the Message

题意：

说那么多，其实就是对于每个a[i]，让你找他的从左边（右边）开始找a[j]<a[i]并且a[j]=max(a[j])(k+1<j<i),a[k]>a[i]。

题解：

从左往右维护一个递减的单调队列，每次都从尾巴开始把比a[i]的踢掉，最后踢的那个就是答案。

右边同理。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int N=5e4+7;
int t,n,a[N],Q[N],ans1[N],ans2[N],head,tail,ic;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        F(i,1,n)scanf("%d",a+i);
        head=1,tail=0;
        F(i,1,n)
        {
            int flag=0;
            while(head<=tail&&a[Q[tail]]<a[i])tail--,flag=1;
            if(flag)ans1[i]=Q[tail+1];else ans1[i]=0;
            Q[++tail]=i;
        }
        head=1,tail=0;
        for(int i=n;i>0;i--)
        {
            int flag=0;
            while(head<=tail&&a[Q[tail]]<a[i])tail--,flag=1;
            if(flag)ans2[i]=Q[tail+1];else ans2[i]=0;
            Q[++tail]=i;
        }
        printf("Case %d:
",++ic);
        F(i,1,n)printf("%d %d
",ans1[i],ans2[i]);
    }
    return 0;
}