hdu3410 Passing the Message 单调栈

// hdu3410 Passing the Message 单调栈
// 题目意思：给你n个数，询问第i个数直到左边比它本身大的第一个数的这段
// 区间内求一个最大的值 和 直到右边比它本身大的数的第一个数的这段区间内
// 再求一个最大值。// 解题方法：
// 单调栈，维护一个栈，使得站内元素单调递减即离栈顶越近，值越小
// 从左往右扫一遍，最后一个比当前元素小的数组下标(出栈的元素)就是我们要求
// 的值。然后从右往左再扫一次，就可以了。// 高大上一点，用了单调队列，只是队列的头不出而已，就是单调栈#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 50008;
int deq[MAX_N];
int a[MAX_N];
int L[MAX_N];
int R[MAX_N];
int n;
void input(){scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);
}void solve(){int head=0,tail=0;for (int i=1;i<=n;i++){int flag = 0;while(head < tail && a[deq[tail-1]]<=a[i]){tail--;flag = 1;}L[i] = flag ? deq[tail] : 0;deq[tail++] = i;}head = tail = 0;for (int i=n;i>=1;i--){int flag = 0;while(head < tail && a[deq[tail-1]] <= a[i]){flag = 1;tail--;}R[i] = flag ? deq[tail] : 0;deq[tail++] = i;}for (int i=1;i<=n;i++){printf("%d %d\n",L[i],R[i]);}
}int main(){//freopen("1.txt","r",stdin);int t;scanf("%d",&t);int kase = 0;while(t--){printf("Case %d:\n",++kase);input();solve();}
}