[toc]

题目链接：QuestOJ 2067。

题目

题意简述

一个长度为 $n−1$ 的、仅由 < 与 > 组成的字符串。你现在要求出两个排列，要求如下：

• 排列中元素的大小关系与字符串中描述的一致。
• 在保证第一个要求的情况下，求出最长上升子序列最长的排列和最长上升子序列最短的排列。

数据范围

$$1\leq n\leq 2\times 10^5$$

时空限制

$$1\text{s}/256\text{MiB}$$

题解

思路

考虑序列，发现只要把连续的小于号连起来则有最长上升子序列。

最短上升子序列的情况处理一下即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=200000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n;
char str[MAXN];

inline void Read(void){
    scanf("%d\n%s",&n,str+1);
    return;
}

bool l[MAXN],r[MAXN];
int a[MAXN];

inline void Work(void){
    for(reg int T=0;T<=1;++T){
        memset(l,false,sizeof(l));
        memset(r,false,sizeof(r));
        reg int last=0;
        for(reg int i=1;i<=n;++i)
            if(str[i]=='<'&&!last)
                last=i;
            else if((str[i]=='>'||i==n)&&last){
                l[last]=r[i]=true;
                last=0;
            }
        stack<int> ID,temp;
        reg bool flag=false;
        for(int i=n;i>=1;--i){
            if(l[i]){
                ID.push(i);
                while(!temp.empty())
                    ID.push(temp.top()),temp.pop();
                flag=false;
            }
            else if(r[i])
                flag=true,temp.push(i);
            else if(flag)
                temp.push(i);
            else
                ID.push(i);
        }
        for(reg int i=n;i>=1;--i){
            a[ID.top()]=i;
            ID.pop();
        }
        if(T==1)
            reverse(a+1,a+1+n);
        for(reg int i=1;i<=n;++i)
            printf("%d%c",a[i],i==n?'\n':' ');
        reverse(str+1,str+n);
        for(reg int i=1;i<=n-1;++i)
            str[i]^=2;
    }
    return;
}