D. Shortest and Longest LIS

Codeforces Round 620 (Div. 2) D. Shortest and Longest LIS

Description

Gildong recently learned how to find the longest increasing subsequence (LIS) in $O(n\log{n})$ time for a sequence of length n. He wants to test himself if he can implement it correctly, but he couldn't find any online judges that would do it (even though there are actually many of them). So instead he's going to make a quiz for you about making permutations of n distinct integers between 1 and n, inclusive, to test his code with your output.

The quiz is as follows.

Gildong provides a string of length n−1, consisting of characters '<' and '>' only. The i-th (1-indexed) character is the comparison result between the i-th element and the i+1-st element of the sequence. If the i-th character of the string is '<', then the i-th element of the sequence is less than the i+1-st element. If the i-th character of the string is '>', then the i-th element of the sequence is greater than the i+1-st element.

He wants you to find two possible sequences (not necessarily distinct) consisting of n distinct integers between 1 and n, inclusive, each satisfying the comparison results, where the length of the LIS of the first sequence is minimum possible, and the length of the LIS of the second sequence is maximum possible.

Input
Each test contains one or more test cases. The first line contains the number of test cases t ($1 \le t \le 10^4$).

Each test case contains exactly one line, consisting of an integer and a string consisting of characters '<' and '>' only. The integer is n ($2 \le n \le 2 \cdot 10^5$), the length of the permutation you need to find. The string is the comparison results explained in the description. The length of the string is n−1.

It is guaranteed that the sum of all n in all test cases doesn't exceed $2 \cdot 10^5$.

Output
For each test case, print two lines with n integers each. The first line is the sequence with the minimum length of the LIS, and the second line is the sequence with the maximum length of the LIS. If there are multiple answers, print any one of them. Each sequence should contain all integers between 1 and n, inclusive, and should satisfy the comparison results.

It can be shown that at least one answer always exists.

Example

input
3
3 <<
7 >><>><
5 >>><
output
1 2 3
1 2 3
5 4 3 7 2 1 6
4 3 1 7 5 2 6
4 3 2 1 5
5 4 2 1 3
Note
In the first case, 1 2 3 is the only possible answer.

In the second case, the shortest length of the LIS is 2, and the longest length of the LIS is 3. In the example of the maximum LIS sequence, 4 '3' 1 7 '5' 2 '6' can be one of the possible LIS.

Problem solving

这道题的意思就是给你一个数n代表序列长度，然后给你一个字符串，字符串的长度为n-1，字符串由大于号和小于号组成，字符串的第i位代表着序列中第i个数和第i+1个数的大小关系。现在让你找到两个序列，满足其中的最长公共子序列最长（最短）。
我们首先考虑最短的情况，上升子序列，也就是说字符串中出现一个">"就意味着一个上升子序列的终点，换句话说，我们可以通过">"将字符串分成若干个部分，例如第一个部分，我们把这一部分的最后一个数置为n，每往前移动一位，n减一。直到这一部分服指完毕。就接着寻找下一部分。这里说这还是很简单的。不懂得话可以等下看代码注释。
然后我们考虑最长的情况。这次我们从出现"<"的地方进行划分，出现"<"之前肯定都是">"(因为我们就是这样统计的)，所以这一部分一定不满足是一个上升的子序列，所以我们需要把每个划分中的最后一位做出贡献组成上升子序列即可。换句话说，每一部分开始赋值的时候都选择最小的开始。跟上部分代码很相似，不理解的话可以看代码注释。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], b[maxn];//用a记录最短,b记录最长
int main()
{
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n; string s;
        cin >> n >> s;
        int num, last;
        /*我们首先处理最短的，把num的初始值赋为n（即当前能达到的最大值），last记录的是新的划分开始的位置，用当前位置i减去last即为这一个划分的元素个数*/
        num = n, last = 0;
        for (int i = 0; i < n; i++) {
            if (i == n - 1 || s[i] == '>') {//根据s[i]='>'进行划分，同时因为可能出现最后一位是<的情况，我们也需要考虑遍历到最后一位时直接进行赋值
                for (int j = i; j >= last; j--)//从当前能达到的最大值进行赋值，i到last（即当前的一个划分）
                    a[j] = num--;//因为根据">"划分，所以每一个划分里面的元素都是递增的，所以我们需要倒着赋值，每次取当前能取到的最大值(即num--)
                last = i + 1;//每次last更新新划分的开始
            }
        }
        /*然后我们处理最长的，代码，变量含义作用跟上面基本一样，不同的是，num我们要从当前能达到的最小的开始赋值*/
        num = 1, last = 0;
        for (int i = 0; i < n; i++) {
            if (i == n - 1 || s[i] == '<') {
                for (int j = i; j >= last; j--)
                    b[j] = num++;//因为根据"<"划分，所以每一个划分里面的元素都是递减的，所以我们需要倒着赋值，每次取当前能取到的最小值(即num++)
                last = i + 1;
            }
        }
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
        for (int i = 0; i < n; i++)
            cout << b[i] << " ";
        cout << endl;
    }
}