题解 SP3544 【BST - Binary Search Tree】
___new2zy___ · · 题解
题解 SP3544 【BST - Binary Search Tree】
题目传送门：
https://www.luogu.org/problemnew/show/SP3544
这题。。。题目迷惑性很大
不得不说是一道够毒的题。。。但是脑洞还是很大的
================================================================
先扯一些没用的东西。。。
这题是我们同学没事闲的跳到的。。。然后就开始尝试切掉
可能是我太
本来以为是个
（我不会告诉你我把我同学的做法卡下去了嘿嘿嘿）
那就来讲一下如何做吧
这题上来就丢给我们一个
之后就问我们（其实也是题目大意）：
向一个最初为空的
而且
况且对于
那么我们就不必建立一颗
而是可以每次二分
找到
对答案的贡献其实就是这个深度，累加起来即可
可以直接建立
之后在
又由于
那么最终插入完整个序列则是
写完之后发现好像有点不太好。。。可能数据稍微大一些就死了
但是总感觉这个过程可以用别的方法来写
或许还有
也许等我想出了
到这里大概也就讲完了。。。
如果不会
（我也没有什么好的链接233）
下面放两个代码，第一个是最开始做的时候的代码（比较慢），第二个是（丧心病狂）卡完常之后的代码
本人代码丑，各位
code1:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
inline int read()
{
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;}
//const int maxn=3e5+3;
int n;
ll ans;
map <int,int> dep;
map <int,int>::iterator it;
int main()
{
/*（以下是我写题的时候的心路历程）
分析：
可以发现这题直接模拟是肯定会挂的
因为n<=300000,而数据又是不一定的
可能出现一个有序序列使得每次插入元素都是O(n)的
那么累加起来就是个O(n^2)的模拟算法
显然复杂度不可接受
那么不妨换位思考一下
我们何必维护一颗二叉搜索树呢
由于这是一颗BST
可以证明的是,对于一个序列中的要插入的数x
它只会最终接在x的前驱或后继的下一层,这是十分显然的
而且x最终一定是这两者中深度较大的那一个的儿子节点上
况且对于x的前驱和后继,一定有x的前驱是x的后继的祖先
那么我们其实就不必建立一颗BST去模拟过程
而是每次在map中O(logn)的寻找x的前驱和后继
找到一个二者深度最大的位置+1即为x的深度
对答案的贡献其实就是这个深度,累加起来即可
那么直接建立map,之后在map内lower_bound查找就行了
lower_bound单次复杂度是O(logn)的
那么最终插入完整个序列则是O(nlogn)的
可能还有O(n)做法吧。。。可是我太菜了想不出。。。
*/
n=read();
for(int i=1;i<=n;i++)
{
int x=read(),pos=0,new_dep1,new_dep2;
it=dep.lower_bound(x);//找到第一个>=x的数
if(it!=dep.end())//存在一个第一个>=x且已经插入了的数
{
new_dep1=it->second+1;
pos=max(pos,new_dep1);
// printf("\nQAQ %d\n",it->first);
}
if(it!=dep.begin())//找不到一个>=x的数,则找第一个<x的数的位置
{
new_dep2=(--it)->second+1;
pos=max(pos,new_dep2);
// printf("\nQWQ %d\n",it->first);
}
dep[x]=pos,ans+=pos;
//在较深的位置插入节点,并累加新的深度贡献
printf("%lld\n",ans);
}
return 0;
}code2:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#define re register
using namespace std;
typedef long long ll;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()
{
int now=0,f=1;re char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;}
int n;
ll ans;
map <int,int> dep;
map <int,int>::iterator it;
int main()
{
n=read();
for(re int i=1;i<=n;i++)
{
int x=read(),pos=0;
it=dep.lower_bound(x);
if(it!=dep.end())pos=max(pos,it->second+1);
if(it!=dep.begin())pos=max(pos,(--it)->second+1);
dep[x]=pos,ans+=pos;
printf("%lld\n",ans);
}
return 0;
}大概。。。这题就到这里了吧。。。
=================================================================
前方高能预警！
所以滚回来再想一想优化方法。。。
仔细想了一想（大概又过了1个半小时吧）发现好像可以
我上面也说可能有一种
但是现在，
先公布一下好结果：
（我的
其实自己都没想到能
行了，不说没用的了，直接开讲
上面的思路很清晰了，对于每一个要插入的数找到前驱和后继就行了
但是发现
而对于找前驱和后继的问题，貌似也就只能想到平衡树了233
可能我是因为我不会平衡树的原因（我还是太菜了），我想到了另外一种东西：链表
因为链表是一个链状结构，每一个节点都有一个前驱节点和后继节点
发现正好符合上面的要求：对于一个数要找前驱和后继
那么我们不妨换个思路，倒着来
（我用了数组模拟链表）
对于一个初始有
删除一个数（所在节点）后，它原位置的前驱和后继的指针会随之更新
那么在删除前它的前驱和后继肯定也是固定的
我们只需要倒序删掉所有数,同时记下每个数前驱后继就行了
最后正着还是按
也是累加贡献，即为每一次的答案
考虑一下这个算法的时间复杂度：
由于每个元素在链表中只被删除一次，所以复杂度是
那么。。。这就是改进之后的算法了
这样就再也不用效率低的
可能自己又口胡了一个神奇做法？结果神奇的过掉了233
下面还是放两个代码，一个是我写的第一个优化（带注释版），另一个是过掉之后的卡常版
还是那句话，本人代码丑，各位dalao不喜勿喷
code3:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline int read()
{
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;}
const int maxn=300003;
int n,opt[maxn],L[maxn],R[maxn],dep[maxn],pre[maxn],nex[maxn];
ll ans;
int main()
{
/*
分析：上一次写的用了map
效率比较低(主要是SPOJ不给开O2所以很慢233)
这次又想到一个貌似是O(n)的算法,再来改造一下。。。
思考发现,对于一个数肯定要找前驱和后继
那么我们不妨换个思路,倒着来
对于一个初始的链表,我们在其中删除数
它原位置的前后指针会随之更新
那么在删除前它的前驱和后继肯定也是固定的
我们只需要倒序删掉所有数,同时记下前驱后继就行了
最后正着还是按depth[i]=max(depth[pre],depth[nex])+1算就行了
最终也是累加贡献
由于每个元素在链表中只被删除一次,所以复杂度是O(n)的
*/
n=read();
for(int i=1;i<=n;i++)//初始化链表
{
opt[i]=read();
L[i]=i-1,R[i]=i+1;
}
L[1]=0,R[n]=0,dep[0]=-1;
for(int i=n;i>=1;i--)//逆序删除数字
{
pre[opt[i]]=L[opt[i]];
nex[opt[i]]=R[opt[i]];
//记下每个删除的数的前驱和后继
R[L[opt[i]]]=R[opt[i]];
L[R[opt[i]]]=L[opt[i]];
//在链表中删除这个数
}
for(int i=1;i<=n;i++)
{
dep[opt[i]]=max(dep[pre[opt[i]]],dep[nex[opt[i]]])+1;
ans+=dep[opt[i]];//更新深度,累加贡献
printf("%lld\n",ans);
}
return 0;
}code4:
#include<iostream>
#include<cstdio>
#include<cmath>
#define re register
using namespace std;//register吼啊
typedef long long ll;
const int inf=1e9+7;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂
{
int now=0,f=1;re char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;}
const int maxn=300003;
int n,opt[maxn],L[maxn],R[maxn],dep[maxn],pre[maxn],nex[maxn];
ll ans;
int main()
{
n=read();
for(re int i=1;i<=n;i++)
{
opt[i]=read();
L[i]=i-1,R[i]=i+1;
}
L[1]=0,R[n]=0,dep[0]=-1;
for(re int i=n;i>=1;i--)
{
pre[opt[i]]=L[opt[i]];
nex[opt[i]]=R[opt[i]];
R[L[opt[i]]]=R[opt[i]];
L[R[opt[i]]]=L[opt[i]];
}
for(re int i=1;i<=n;i++)
{
dep[opt[i]]=max(dep[pre[opt[i]]],dep[nex[opt[i]]])+1;
ans+=dep[opt[i]];
printf("%lld\n",ans);
}
return 0;
}或许到这里这题就真的没什么了吧。。。我是真的想不出其他做法了233
最后来对比一下两种做法卡完常前后：
果然。。。
希望有人把我的
最后，做完发现，这题的脑洞其实还是挺大的。。。希望大家能好好做
还有就是。。。不要让题目迷惑了双眼QAQ
还要注意算法效率的改进和提升！
最后，感谢你的阅读！
最后的最后。。。无耻的推一波我的blog：
https://www.luogu.org/blog/new2zy/
拜拜~~~