线段树 + 树状数组(什么鬼, 我选择单调栈)

Table of Contents

  1. Description
  2. Solution

Description

给定一个序列，初始为空。现在我们将$1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

Solution

我们可以发现一个性质, 由于数字是递增插入的, 所以不会影响插入位置后面的答案. 那么我们直接构造出最终的序列, 求出每个位置对应数值的答案$f_{a[i]}$, 那么到每个数值为止的答案就是$f$的前缀最大值了.

怎么构造最终序列呢? 平衡树?算了早就不会写了可以用线段树倒着占坑, 因为后插入的不会影响先插入的相对位置, 也就是我们倒着插入时找到第$x_i + 1$个空位就可以了, 在线段树上二分即可.

然后就是求LIS了, 随便哪种$O(nlogn)$的算法都可以.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn = 1e+5 + 5;

int n, a[maxn];

int stk[maxn], mx, top, ans[maxn];

int s[maxn << 2];
inline void pushup(int cur) {
  s[cur] = s[cur << 1] + s[cur << 1|1];
}
void build(int cur, int l, int r) {
  if (l == r) {
    s[cur] = 1; return;
  }
  int mid = (l + r) >> 1;
  build(cur << 1, l, mid);
  build(cur << 1|1, mid + 1, r);
  pushup(cur);
}
void update(int cur, int l, int r, int p, int v) {
  if (l == r) {
    s[cur] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid) update(cur << 1, l, mid, p, v);
  else update(cur << 1|1, mid + 1, r, p, v);
  pushup(cur);
}
int query(int cur, int l, int r, int k) {
  if (l == r) {
    return l;
  }
  int mid = (l + r) >> 1, tmp = s[cur << 1];
  if (k <= tmp) return query(cur << 1, l, mid, k);
  else return query(cur << 1|1, mid + 1, r, k - tmp); 
}

int main()
{
  scanf("%d", &n); int *x = new int[n + 1];
  build(1, 1, n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", x + i);
  for (int i = n; i; --i) {
    //scanf("%d", x);
    int pos = query(1, 1, n, *(x+i) + 1);
    a[pos] = i;
    update(1, 1, n, pos, 0);
  }
  for (int i = 1; i <= n; ++i) {
    if (stk[top] < a[i]) stk[++top] = a[i], ans[a[i]] = top;
    else {
      int pos = lower_bound(stk + 1, stk + 1 + top, a[i]) - stk;
      stk[pos] = a[i];
      ans[a[i]] = pos;
    }
  }
  for (int i = 1; i <= n; ++i) {
    ans[i] = max(ans[i], ans[i - 1]);
    printf("%d\n", ans[i]);
  }
  return 0;
}