题解 杂题 数据结构

成外集训考试题 洗

---

题目背景

二叉排序树：

一棵二叉树为一颗二叉排序树，当且仅当所有的节点(叶子结点除外)的左子树上的所有点的值都小于此节点的值，且所有右节点的值都大于此节点的值。

题目大意

有一棵二叉树，每个节点有一个权值。问最少要修改多少个点的权值(只能修改为整数)，才能使这棵树变为一颗二叉排序树。输出最小修改次数。

第一行一个整数$N$，第二行$N$个整数表示$N$个点的权值。接下来$N-1$行输入两个数，第$i$行第一个数$x$表示节点$i+1$的父亲为$x$，第二个数$y$表示左右关系。若$y=0$，则$i+1$为$x$的左儿子。若$y=1$ ，则为右儿子。

样例输入

3
2 2 2
1 0
1 1

样例输出

2

样例解释

将节点$1$的值修改为$1$，将节点$3$的值修改为$3$。

数据范围

• 对于$20$%的数据，满足$N \leq 10,a_i \leq 100$
• 对于$40$%的数据，满足$N \leq 100,a_i \leq 200$
• 对于$60$%的数据，满足$N \leq 2000$
• 对于$100$%的数据，满足$N \leq 10^5,a_i < 2^{31}$

---

解析

对于二叉排序树的定义，我们不难想到如果对于一颗二叉排序树进行中序遍历，那么得到的序列一定是一个严格递增的序列。

因此，我们要做的就是对于输入的一棵树，将其进行中序遍历，再用最小的操作次数将其修改为严格递增的即可。

所以不难想到，只需要找到遍历出的数组的最长上升子序列的长度，再用总长减去即可。

但是这样做会有一个问题，例如遍历出来的权值为：$2,3,5,1,1,6,7$，那么按上述做法，找到了最长上升子序列$2,3,5,6,7$，即要修改$1,1$的值。但题中有规定，权值只能修改为整数，因此只修改$1,1$是无法达到要求的。

因此，我们来做进一步考虑。

不难发现，如果要将$i$与$j(i<j)$之间的所有数改为递增，那么必须满足一个条件：

$$a[j]-a[i]-1 \geq j-i-1$$ 表示$i$与$j$之间的数的个数应不大于两权值之差，这样才能满足条件。如上述要修改$3$和$6$之间的数，但$6-5-1<6-3-1$,因此不能修改。

我们再将此式化简，得到:

$$a[j]-j \geq a[i]-i$$ 即要修改$i$与$j$之间的值必须满足以上条件。

我们定义$b[i]=a[i]-i$，那么这个问题就很好办了：我们只需要求出$b$数组，再找到$b$的最长不下降子序列($LIS$)的长度，再用总长减去即可。

$Code：$

#include<iostream>
using namespace std;
const int N=2e5+5;
int n;
int a[N],f[N],b[N],tot;
int tree[N][2];
inline void dfs(int u){
    if(tree[u][0]) dfs(tree[u][0]);
    b[++tot]=a[u]-tot; //同时求出b数组
    if(tree[u][1]) dfs(tree[u][1]);
}
inline int lis(){
    int res=0;
    f[1]=1;
    for(int i=2;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++)
            if(b[i]>=b[j]) f[i]=max(f[i],f[j]+1);
        res=max(res,f[i]);
    }
    return res; //LIS模板，没什么好说的
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2;i<=n;i++){
        int x,f;
        cin>>x>>f;
        tree[x][f]=i;
    }
    dfs(1); //中序遍历
    cout<<n-lis();
}

不过普通$LIS$的时间复杂度趋近于$O(N^2)$，但此题$N \leq 10^5$ ，因此，这份代码只能过$60$%的数据。

接下来，我们考虑优化。

谈到优化$DP$，那就是令人脑袋疼的数据结构优化$DP$了。线段树、树状数组、$RMQ$都可以来解决此问题(玄学卡常就免了)。这里，我们来介绍树状数组的做法。

观察上述代码第$18$行，我们发现，对于以$b[i]$结尾的$f$是由$i$之前的最大的$f$转移而来。因此我们可以用树状数组维护最大值。具体理论可以参考其他大佬讲解。

对于每一个数，先查出小于这个数结尾的的$LIS$的最大值，那么$f[i]=query(b[i])+1;$
然后再把以$b[i]$结尾的$LIS$的最大值$f[i]$插入到树状数组中。利用树状数组维护这一过程。

由于$b[i]$非常大，普通的数组下标存不下。因此，要将$b[i]$离散化。

---

代码实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define inv(x) (lower_bound(v.begin(),v.end(),x)-v.begin()+1) //求离散化后的映射值
const int N=1e5+5;
int n,a[N];
int tree[N][2];
int b[N],tot,c[N];
int f[N];
vector<int> v; //离散数组
inline int lowbit(int x){
    return x& (-x);
}
inline void dfs(int u){
    if(tree[u][0]) dfs(tree[u][0]);
    b[++tot]=a[u]-tot;
    if(tree[u][1]) dfs(tree[u][1]);
}
inline void lisan(){//离散化
    for(int i=1;i<=n;i++)
        v.push_back(b[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
inline int query(int x){ //找到小于b[x]结尾的LIS的最大值
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res=max(res,c[i]);
    return res;
}
inline void updata(int x,int y){//更新最大值
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]=max(c[i],y);
}
inline int lis(){
    int res=0;
    for(int i=1;i<=n;i++){
        b[i]=inv(b[i]);
        f[i]=query(b[i])+1;
        updata(b[i],f[i]);
        res=max(res,f[i]);
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2;i<=n;i++){
        int u,x;
        cin>>u>>x;
        tree[u][x]=i;
    }
    dfs(1);
    lisan();
    cout<<n-lis();
}

完结撒花~