社区讨论

关于 abc E

2024/06/23 10:01学术版参与者 5已保存回复 8

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

rt，赛时做法是先求出每个隔板左边离他最近且比他高的隔板编号，然后瞎搞即可。

即用

pre

数组表示当前隔板左边最后一个比他高的隔板编号，该部分代码：

CPP

for(int i=1;i<=n;i++)
	{
		pre[i]=i-1;
		while(a[pre[i]]<a[i]&&pre[i]!=0)pre[i]=pre[pre[i]];
	}

这么写赛时通过了，但是如何证明复杂度？

共 8 条回复，欢迎继续交流。

正在加载回复...