It's hard to make up for it.

- If not necessary, do not use STL - patient red adzuki bean Online

Reference to: https://www.cnblogs.com/Dillonh/p/11240083.html (For the sake of two continue s, I was still pestering in the comments section. After many experiments, I seemed to understand a little, and deleted them without being noticed: P)

 

 

HDU-6592 Beauty of  unimodal sequence

After adjusting bug s such as subscribing another array in brackets, the biggest wa point is that the size of the dp array is less than 0.

Whether const xx maxn is all wrong, or whether each array is typed one wrong size, one wrong size, is a question (:)____________)._

Output format is very deadly ah ah wa and then sent PE

Text: Firstly, LIS is running in front of the sequence, then LIS is running in reverse. Then, ppo-positive (opo-over: P) is recorded and initialized to po.

The original blog has opened two vector s, so it's easy to imagine that an array (called v bar) can be reused by adding a subscript variable.

task1 Dictionary Order Minimum Subscript Sequence - Start looking for peaks, dictionary order is minimal, so once found, use this. Then I started to look for the number of LIS subscripts as far as possible from the peak, looked at the condition of the first continue of the original blog, and felt that there would be no such situation. Then I had to step in and (x) want to remove the second continue. However, the second one, which had a heavy effect ()checked the output file for a long time, suddenly noticed this problem. . After checking before and after, the latter part is taken as long as it meets the requirements, so that the subscription is the smallest. stack and v flip the output and it's done.

task 2 Dictionary Order Maximum Subscript Sequence - Start looking for the peak, find the peak as far back as possible, and re-initialize the po. Look ahead and take it as soon as you find it, so that the subscription is the largest. Look back. (A red bean who is too lazy to use reverse simulates a stack with v) Do something similar to the first half of task1. Output is done.

See the code for details.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
using namespace std;
typedef long long LL;
int n;
int num[300005], ppo[300005], opo[300005], v[300005], d[300005], po[300005];
stack<int>sa;

int main()
{
    while (~scanf("%d", &n)) {

        memset(d, 0x3f, sizeof d);
        d[0] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &num[i]);
            ppo[i] = lower_bound(d + 1, d + 1 + n, num[i]) - d;
            d[ppo[i]] = num[i];
            po[i] = 0x3f3f3f3f;
        }
        memset(d, 0x3f, sizeof d);
        d[0] = 0;
        for (int i = n; i >= 1; i--) {
            opo[i] = lower_bound(d + 1, d + 1 + n, num[i]) - d;
            d[opo[i]] = num[i];
        }


        int co = 0;
        int now = 1, m = ppo[1] + opo[1];
        for (int i = 2; i <= n; i++)
            if (ppo[i] + opo[i] > m) { now = i; m = opo[i] + ppo[i]; }
        po[ppo[now]] = num[now];
        for (int i = now - 1; i >= 1; i--) {
            if (po[ppo[i] + 1] <= num[i]) continue;
            while (!sa.empty() && ppo[i] >= ppo[sa.top()])po[ppo[sa.top()]] = 0x3f3f3f3f, sa.pop();
            sa.push(i);
            po[ppo[i]] = num[i];
        }
        while (!sa.empty()) v[co++] = sa.top(), sa.pop();
        v[co++] = now;
        for (int i = now + 1; i <= n; i++)
            if (opo[i] == opo[v[co - 1]] - 1 && num[i] < num[v[co - 1]])v[co++] = i;
        for (int i = 0; i < co; i++)printf("%d%c", v[i], " \n"[i == co - 1]);


        co = 0;
        now = 1; m = ppo[1] + opo[1]; po[1] = 0x3f3f3f3f;
        for (int i = 2; i <= n; i++) {
            if (ppo[i] + opo[i] >= m) { now = i; m = opo[i] + ppo[i]; }
            po[i] = 0x3f3f3f3f;
        }
        sa.push(now);
        for (int i = now - 1; i >= 1; i--)
            if (ppo[i] == ppo[sa.top()] - 1 && num[i] < num[sa.top()])sa.push(i);
        while (!sa.empty())v[co++] = sa.top(), sa.pop();
        po[opo[now]] = num[now];
        for (int i = now + 1; i <= n; i++) {
            if (num[i] >= po[opo[i] + 1]) continue;
            while (co && opo[i] >= opo[v[co - 1]])po[opo[v[co - 1]]] = 0x3f3f3f3f, co--;
            v[co++] = i;
            po[opo[i]] = num[i];
        }
        for (int i = 0; i < co; i++)printf("%d%c", v[i], " \n"[i == co - 1]);
    }

    return 0;
}

Beauty of unimodal sequence