洛谷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;

}