Logue P4577 [FJOI2018] leading group problem (dp line tree merging)

meaning of the title

Title Link

Sol

First of all, it's not hard to think of a dp. Set \ (f[i][j] \) to represent the minimum number of \ (j \) in the subtree of \ (I \)

When transferring, maintain a suffix \ (mx \) and add it directly

Because the suffix max is monotonous, then we can maintain its difference array (the sum of two difference arrays is the same as the sum of two original arrays)

In the process of upward merging, you can find the location \ (- 1 \) at \ (a[x] \), which was \ (1 \) before \ (a[x] \)

(how do you feel the violence interval can also be qwq)

Complexity \ (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;
}

Tags: C++

Posted on Wed, 04 Dec 2019 09:33:35 -0800 by Ben Cleary