multiset 合并的写法

类似大根堆，这题是小根堆，且允许相等

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 200'000;
int n;
vector<int> e[MAXN + 5];
int val[MAXN + 5];
// se[u]["i"] 表示子树 u 留下 i+1 个点的最大值最小是几
multiset<int> se[MAXN + 5];
void dfs(int u)
{
    for (int v : e[u])
    {
        dfs(v);
        // 把 se[v] 融入 se[u]
        for (auto x : se[v])
            se[u].insert(x);
    }
    auto it = se[u].upper_bound(-val[u]);
    if (it != se[u].end())
        se[u].erase(it);
    se[u].insert(-val[u]);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    for (int i = 2; i <= n; i++)
    {
        int p;
        cin >> p;
        e[p].push_back(i);
    }
    dfs(1);
    cout << se[1].size();
    return 0;
}

线段树合并的写法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
//基础数据
int n;
int w[MAXN];
vector<int> e[MAXN];
//离散化
int tempTot;
int temp[MAXN];
//线段树
struct Node
{
    int l, r, val;
} poi[MAXN * 20];
int pTot;       //线段树节点个数
int root[MAXN]; //每个线段树的根节点
//区间修改
void update(int &now, int l, int r, int x, int y, int z)
{
    if (!now)
        now = ++pTot;
    if (x <= l && r <= y)
    {
        poi[now].val += z;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
        update(poi[now].l, l, mid, x, y, z);
    if (y >= mid + 1)
        update(poi[now].r, mid + 1, r, x, y, z);
    poi[now].val = poi[poi[now].l].val + poi[poi[now].r].val;
}
//区间查询
int query(int now, int l, int r, int x, int y)
{
    if (!now)
        return 0;
    if (x <= l && r <= y)
        return poi[now].val;
    int res = 0;
    int mid = (l + r) / 2;
    if (x <= mid)
        res += query(poi[now].l, l, mid, x, y);
    if (y >= mid + 1)
        res += query(poi[now].r, mid + 1, r, x, y);
    return res;
}
//合并
void Merge(int &a, int b, int l, int r)
{
    if (!a || !b)
    {
        a = a + b;
        return;
    }
    if (l == r)
    {
        poi[a].val += poi[b].val;
        return;
    }
    int mid = (l + r) / 2;
    Merge(poi[a].l, poi[b].l, l, mid);
    Merge(poi[a].r, poi[b].r, mid + 1, r);
    poi[a].val = poi[poi[a].l].val + poi[poi[a].r].val;
}
//找左边第一个前缀和位x的位置
int findP(int now, int l, int r, int x)
{
    if (l == r)
    {
        if (poi[now].val == 0)
            return 0;
        return l;
    }
    int mid = (l + r) / 2;
    if (poi[poi[now].l].val >= x)
        return findP(poi[now].l, l, mid, x);
    return findP(poi[now].r, mid + 1, r, x - poi[poi[now].l].val);
}
void dfs(int u)
{
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        dfs(v);
        Merge(root[u], root[v], 1, tempTot);
    }
    int pos = findP(root[u], 1, tempTot,
                    query(root[u], 1, tempTot, 1, w[u]));
    update(root[u], 1, tempTot, w[u], w[u], 1);
    if (pos)
        update(root[u], 1, tempTot, pos, pos, -1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //输入
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 2; i <= n; i++)
    {
        int fa;
        cin >> fa;
        e[fa].push_back(i);
    }
    //对 w 离散化
    for (int i = 1; i <= n; i++)
        temp[i] = w[i];
    sort(temp + 1, temp + n + 1);
    tempTot = unique(temp + 1, temp + n + 1) - temp - 1;
    for (int i = 1; i <= n; i++)
        w[i] = lower_bound(temp + 1, temp + tempTot + 1, w[i]) - temp;
    //遍历树，线段树合并
    dfs(1);
    //输出
    cout << poi[root[1]].val << endl;
    return 0;
}