悬线法

稍微介绍一下悬线法，其适用范围是单调栈的真子集（即任何悬线法可以解决的问题单调栈都可以解决)，虽然可能用处不大，但是相比于单调栈在一部分扫描序列时维护单调信息时较为简单和方便。

悬线，就是一条竖线，这条竖线有初始位置和高度两个性质，可以在其上端点不超过当前位置的矩形高度的情况下左右移动。

对于本题，我们可以考虑枚举每个位置$i$，然后钦定$a_i$为最小值，我们需要找到的就是最大的两端$\texttt{L,R}$满足$\min\limits_{j=L}^Ra_j=a_i$。

定义$l_i$为当前$i$位置的悬线所能扩展到的最左边的位置，初始时令$l_i=i$，然后每一次暴力判断能否继续向左扩展。

• 如果$l_i=1$，即已经扩展到了边界，已经不能再继续扩展。
• 如果当前$a_i>a_{l_i-1}$，则在$l_i-1$位置存在比$\texttt i$更小的值，说明当前悬线已经不能再次往左扩展了。
• 如果当前$a_i\leq a_{l_i-1}$，说明直到$l_i-1$位置$a_i$都是最小值，说明当前悬线仍然可以向左扩展，并且$l_i-1$位置的悬线也能向左扩展，将$l_i$更新为$l_{l_i-1}$，并继续暴力向左扩展。

定义$r_i$为当前$i$位置的悬线所能扩展到的最右边的位置，扩展时同理。

这么做可能直观上感觉是$O(n^2)$的，但实际上可以发现每个$l_i$最多被遍历一次，所以时间复杂度仍然是$O(n)$的。（但由于缓存等玄学原因，悬线法一般都会比单调栈慢）。

代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int n,a[111111],l[111111],r[111111];
int g[111111],res,L,R;
int qwq=1;
signed main()
{
	while(scanf("%lld",&n)==1)
	{
		memset(a,-1,sizeof(a));
		if(!qwq) puts("");else qwq=0;
		res=0,L=R=1;R(i,1,n) l[i]=r[i]=i;
		R(i,1,n) a[i]=read(),g[i]=g[i-1]+a[i];
		R(i,1,n) while(a[l[i]-1]>=a[i]) l[i]=l[l[i]-1];
		L(i,1,n) while(a[r[i]+1]>=a[i]) r[i]=r[r[i]+1];
		R(i,1,n) 
		{
			int tmp=a[i]*(g[r[i]]-g[l[i]-1]);
			if(res<tmp||(res==tmp&&R-L>r[i]-l[i])) res=tmp,L=l[i],R=r[i];
		}
		printf("%lld\n%lld %lld\n",res,L,R);
	}
}