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

题意

题目链接

sol

首先不难想到一个dp，设\(f[i][j]\)表示\(i\)的子树内选择的最小值至少为\(j\)的最大个数

转移的时候维护一个后缀\(mx\)然后直接加

因为后缀max是单调不升的，那么我们可以维护他的差分数组(两个差分数组相加再求和 与 对两个原数组直接求和是一样的)

向上合并的过程中对\(a[x]\)处\(+1\)，再找到\(a[x]\)之前为\(1\)的位置\(-1\)即可

(怎么感觉暴力区间加也可以qwq)

复杂度\(o(nlogn)\)

// 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;
}