CF1554A Cherry

A. Cherry

妙啊，CF div2的A我居然用了单调栈+RMQ。（无语）

先讲讲我的做法。

我是想用单调栈求出对于每一个 (i)，满足 (iin [l_i,r_i]) 且 (a_i=minlimits_{j=l_i}^{r_i} a_j) 的最大区间 ([l_i,r_i])。这个显然可以做到，正反扫一遍，时间复杂度 (O(n))。

这样，只要知道 ([l_i,r_i]) 中的最大值，我们就可以求出 (a_i) 作为区间最小值的答案了。

//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int MAXN=1e5+10;

int n;
int a[MAXN];
int l[MAXN],r[MAXN],g[MAXN][21];
stack<int> stk;

int query(int l,int r) {
	int j=log2(r-l+1);
	return max(g[l][j],g[r-(1<<j)+1][j]);
}

signed main() {
	int t=read();
	while(t--) {
		cin>>n; 
		for(int i=1;i<=n;i++) {
			a[i]=read();
			g[i][0]=a[i];
		}
		for(int j=1;j<=20;j++) {
			for(int i=1;i+(1<<j)-1<=n;i++) {
				g[i][j]=max(g[i][j-1],g[i+(1<<(j-1))][j-1]);
			}
		}
		
		for(int i=1;i<=n;i++) {
			while(!stk.empty()&&a[stk.top()]>a[i]) {
				r[stk.top()]=i-1;
				stk.pop();
			}
			stk.push(i);
		}
		while(!stk.empty()) {
			r[stk.top()]=n;
			stk.pop();
		}
		reverse(a+1,a+n+1);
		for(int i=1;i<=n;i++) {
			while(!stk.empty()&&a[stk.top()]>a[i]) {
				l[n-stk.top()+1]=(n-(i-1)+1);
				stk.pop();
			}
			stk.push(i);
		}
		while(!stk.empty()) {
			l[n-stk.top()+1]=1;
			stk.pop();
		}
		
		int ans=0;
		reverse(a+1,a+n+1);
		for(int i=1;i<=n;i++) {
			if(l[i]==r[i]) {
				continue;
                //若 li==ri，ai是数列最大值
			}
			ans=max(ans,query(l[i],r[i])*a[i]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

当然还有简单的方法。我们考虑对于 (i)，令 (f_{i,j}=minlimits_{k=i}^{j} a_k)，若固定 (i)，(f_{i,j}) 不严格单调递减。所以 (j=i+1) 是 (f_{i,j}) 最大。解法也就呼之欲出了。