Problem

给定一个排列，对于每个位置$i$，求出除这个位置之外有多少个位置$j$，如果删去$j$位置上的数会使得包含位置$i$的$LIS$变短

Solution

我们对排列求一遍$LIS$，在过程中对每个长度的$LIS$保存结束位置，则其位置上数字的大小单调递减

对于位置$i$来说，若其$LIS$长度为$len$，一定是从$LIS$长度为$len-1$且数值小于$a_i$的位置转移过来的

我们将$LIS$转移对应的两端点连边，构成一张拓扑图，那么求$i$位置前面有哪些数字删除会导致包含位置$i$的$LIS$变短，就等价于求这张拓扑图的支配树上$i$节点的深度

我们正反做两遍$LIS$，将对应支配树深度相加就是答案

支配树的构造可以在$LIS$的同时完成，所有长度为$len-1$的小于$a_i$的点$LCA$向$i$点连边即可

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
#include <bits/stdc++.h>
using namespace std;
const int N = 250000 + 10;
int n, a[N], c[N], ans[N];
void upd(int x, int y) {
    while (x < N) c[x] = max(c[x], y), x += x & -x;
}
int qry(int x) {
    int s = 0;
    while (x) s = max(s, c[x]), x -= x & -x;
    return s;
}
vector<int> v[N];
int f[N][18], d[N];
int find(int x, int y) {
    int l = 0, r = v[x].size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[v[x][mid]] > y)
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}
int lca(int x, int y) {
    if (d[x] < d[y]) swap(x, y);
    for (int i = 17; ~i; --i)
        if (d[f[x][i]] >= d[y]) x = f[x][i];
    if (x ^ y) {
        for (int i = 17; ~i; --i)
            if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
        x = f[x][0], y = f[y][0];
    }
    return x;
}
void LIS() {
    for (int i = 1; i <= n; i++) {
        int prv = qry(a[i]);
        v[prv + 1].push_back(i);
        upd(a[i], prv + 1);
        int pos = find(prv, a[i]);
        int fx = lca(v[prv][pos], v[prv].back());
        f[i][0] = fx;
        d[i] = d[fx] + 1;
        for (int j = 1; j < 18; j++) f[i][j] = f[f[i][j - 1]][j - 1];
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    v[0].push_back(0);
    LIS(); 
    for (int i = 1; i <= n; ++i) ans[i] += d[i] - 1;
    memset(f, 0, sizeof(f));
    memset(c, 0, sizeof(c));
    memset(d, 0, sizeof(d));
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) a[i] = n + 1 - a[i];
    for (int i = 1; i <= n; ++i) v[i].clear(); 
	LIS();
    for (int i = 1; i <= n; ++i)
        printf("%d%c", ans[i] + d[n + 1 - i] - 1, " \n"[i == n]);
    return 0;
}