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

## 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;
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);
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]);
}
int pos = find(root[x], 0, N, a[x] - 1);
if(pos)
}
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() {
for(int i = 1; i <= N; i++) a[i] = read(), date[++num] = a[i];
Des();
for(int i = 2; i <= N; i++) {