洛谷P4577 [FJOI2018]领导集团问题(dp 线段树合并)

// luogu-judger-enable-o2
#include<bits/stdc++.h>
template<typename A, typename B> inline bool chmax(A &x, B y) {return x < y ? x = y, 1 : 0;}
template<typename A, typename B> inline bool chmin(A &x, B y) {return x > y ? x = y, 1 : 0;}
#define LL long long 
using namespace std;
const int MAXN = 2e5 + 1, SS = 1e7 + 5e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], ans, date[MAXN], num;
vector<int> v[MAXN];
#define lson ls[k], l, mid
#define rson rs[k], mid + 1, r
int root[SS], ls[SS], rs[SS], sum[SS], tot;
int Merge(int x, int y) {
    if(!x || !y) return x | y;
    int nw = ++tot; sum[nw] = sum[x] + sum[y];
    ls[nw] = Merge(ls[x], ls[y]);
    rs[nw] = Merge(rs[x], rs[y]);
    return nw;
}
void update(int k) {
    sum[k] = sum[ls[k]] + sum[rs[k]];
}
void Add(int &k, int l, int r, int p, int v) {
    if(!k) k = ++tot;
    if(l == r) {sum[k] += v; return ;}
    int mid = l + r >> 1;
    if(p <= mid) Add(lson, p, v);
    else Add(rson, p, v);
    update(k);
}
int find(int k, int l, int r, int pos) {
    if(!k) return 0;
    if(l == r) return sum[k] ? l : 0;
    int mid = l + r >> 1;
    if(pos <= mid) return find(lson, pos);
    else {
        int t = find(rson, pos); 
        if(t) return t;
        else return find(lson, pos);
    }
}
void dfs(int x, int fa) {   
    for(auto &to : v[x]) {
        dfs(to, x);
        root[x] = Merge(root[x], root[to]);
    }
    Add(root[x], 0, N, a[x], +1);
    int pos = find(root[x], 0, N, a[x] - 1);
    if(pos) 
        Add(root[x], 0, N, pos, -1);
}
void Des() {
    sort(date + 1, date + num + 1);
    num = unique(date + 1, date + num + 1) - date - 1;
    for(int i = 1; i <= N; i++) a[i] = lower_bound(date + 1, date + num + 1, a[i]) - date;
}
signed main() {
    N = read();
    for(int i = 1; i <= N; i++) a[i] = read(), date[++num] = a[i];
    Des();
    for(int i = 2; i <= N; i++) {
        int x = read();
        v[x].push_back(i);
    }
    dfs(1, 0);
    //for(int i = 1; i <= N; i++) cout << sum[root[i]] << '\n';
    printf("%d\n", sum[root[1]]);
    return 0;
}