题意
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("%dn", sum[root[1]]);
return 0;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
