自动搬运

查看原文

来自洛谷，原作者为

	kkxacj Full of Hope.

搬运于2025-08-24 22:20:33，当前版本为作者最后更新于2023-01-07 16:54:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

upd: 增加文章可读性。

题目传送门

题意

现在有一个 $1\sim n$ 的排列 $a$，将序列中的元素依次放进一个 BST 里，求 BST 中插入函数的执行次数。

注意：第一个数已经作为 BST 的根。

思路

暴力模拟肯定会超时，根据二叉搜索树的性质，思考一下可以发现我们每次只需要找到小于第 $i$ 个数的最大值和大于第 $i$ 个数的最小值。

所以可以考虑用单调栈解决这道题，又由于 $1\le a_i\le n$，$a_i$ 互不相同，所以数字可以从 $1$ 开始模拟到 $n$,找到第 $i$ 个数左边比它小的数的最大值,再从 $n$ 开始模拟到 $1$,找到第 $i$ 个数右边比它大的最小值。

注意：由于找第 $i$ 个数右边比它大的最小值不能是还没有输入的，所以我们应该找第 $i$ 个数左边比它大的最小值。

干完这一切之后，只需计算它的深度即可。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 300005;
int n,k,dep[maxn],l[maxn],r[maxn],a[maxn],x[maxn],d[maxn],cnt = 1;
long long ans;
int main()
{
//   freopen(".in","r",stdin);
//   freopen(".out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;i++) 
	{
		scanf("%d",&x[i]);
		a[x[i]] = i; 
	} 
	for(int i = 1;i <= n;i++)
	{
		while(a[i] < d[cnt] && cnt > 1) cnt--;
		l[i] = x[d[cnt]];
		d[++cnt] = a[i];
	}
	int cnt = 1;
	for(int i = n;i >= 1;i--)
	{
		while(a[i] < d[cnt] && cnt > 1) cnt--;
		r[i] = x[d[cnt]];
		d[++cnt] = a[i];
	}
	cout << 0 << endl;
	for(int i = 2;i <= n;i++) 
	{
		dep[x[i]] = 1 + max(dep[l[x[i]]],dep[r[x[i]]]);
		ans += dep[x[i]];
		printf("%lld\n",ans);
	}
    return 0;
}