HDU 3410【单调栈】

思路：

单调栈。

鄙人的记忆：按当前为最大值的两边延伸就是维护单调递减栈。

//#include <bits/stdc++.h>

#include <iostream>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <vector>

#include <map>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=50000+10;

struct asd{

    int id;

    int left,right,w;

};

int n,a[N];

int ans[N][2];

stack<asd>q;

int main()

{

    while(!q.empty())

        q.pop();

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        asd now,nex;

        scanf("%d",&n);

        for(int i=1;i<=n;i++)

            scanf("%d",&a[i]);

        now.id=1;

        now.left=now.right=1;

        now.w=a[1];

        q.push(now);

        for(int i=2;i<=n;i++)

        {

            nex.id=i;

            nex.left=nex.right=i;

            nex.w=a[i];

            while(!q.empty()&&q.top().w<a[i])

            {

                now=q.top();q.pop();

                ans[now.id][0]=now.left!=now.id?now.left:0;

                ans[now.id][1]=now.right!=now.id?now.right:0;

                if(!q.empty())

                    q.top().right=now.id;

                nex.left=now.id;

            }

            q.push(nex);

        }

        while(!q.empty())

        {

            now=q.top();q.pop();

            ans[now.id][0]=now.left!=now.id?now.left:0;

            ans[now.id][1]=now.right!=now.id?now.right:0;

            if(!q.empty())

                q.top().right=now.id;

        }

        printf("Case %d:\n",cas++);

        for(int i=1;i<=n;i++)

            printf("%d %d\n",ans[i][0],ans[i][1]);

    }

    return 0;

}

巴特西

HDU 3410【单调栈】

最新文章

热门文章