UVA1619 感觉不错 Feel Good（良好的感觉） 题解

0.题面：

给出正整数n和一个(1 <= n <= 100 000)长度的数列，要求找出一个子区间，使这个子区间的数字和乘上子区间中的最小值最大。输出这个最大值与区间的两个端点。

1.思路

一开始试图使用单调栈，然而在调试一上午无果后愤然打了个分治，然后就过了233

根据分治三步法，算法流程分为：

1.分解：定义 \(dfs(l,r)\) 为区间 \([l,r]\) 的最优解，\(mid = (l+r)/2\) ，可以把问题分为 \(dfs(l,mid)\) 和 \(dfs(mid+1,r)\) 两部分，分别对应最优解完全位于左子区间和右子区间的情况。

2.边界：当 \(l=r\) 时，\(dfs(l,r)={a_l}^2\)。（数列为\(a\)）

3.合并：在第一步处理了最优解完全位于左子区间和右子区间的情况，还有最优解跨越 \(mid\) 的情况没处理。注意到当最小值一定时，区间越大越好，所以可以从大到小地选择最大值，再从中点开始往左右两端“放宽”当前区间。

2.Code

#include 
using namespace std;
#define MAXN 1000000
typedef long long ll;
int n;
ll a[MAXN+5],sum[MAXN+5],ans;
struct answ{
	int l,r;ll v;
	answ(){
		l=r=v=0;
	}
	answ(int L,int R,ll V){
		l=L;r=R;v=V;
	}
};
bool operator < (answ l,answ r){
	return l.v tmp;
	for(int i=l;i<=r;i++){
		tmp.push_back(a[i]);
	}
	sort(tmp.begin(),tmp.end());reverse(tmp.begin(),tmp.end());//从大到小地取区间最小值
	int L=mid,R=mid+1;
	ans=max(ans,answ(L,R,query(L,R)));
	for(int i=0;ia[mid]||tmp[i]>a[mid]){
			continue;
		}
		while(a[L-1]>=tmp[i]&&L!=l){
			L--;
		}
		while(a[R+1]>=tmp[i]&&R!=r){
			R++;
		}//区间越大越好
		ans=max(ans,answ(L,R,query(L,R)));
	}
	return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	sum[i]=sum[i-1]+a[i];
    }
    qwq.build();
    answ ans=dfs(1,n);
    cout<