题解：Feel Good

题目链接

依然枚举每个位置作为最小值的情况，记录“值/下标”二元组，按第一维从大到小排序后，每次将第二位的位置在序列中标成 \(1\)，那么选择的一定是序列里一个 \(1\) 的极长段。加入一个位置检查其左右是否加入过，如果加入过就用并查集合并掉，同时维护极长段的和/左右端点是简单的，复杂度 \(\mathcal O(n \log n + n \alpha (n))\)，瓶颈在于排序。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define power(x) ((x)*(x))
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define mp make_pair
#define fi first
#define se second
#define TT template<typename T>
#define TA template<typename T,typename ...Args>
#define dbg(x) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<'\n'
using namespace std;
using pii=pair<int,int>;
using pdi=pair<double,int>;
using piii=pair<pair<int,int>,int>;

bool Mbe;

namespace IO
{
    inline int read()
    {
        int s=0,w=0; char c=getchar();
        while(!isdigit(c)) w|=c=='-',c=getchar();
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        return s*(w?-1:1);
    }
    TT inline void read(T &s)
    {
        s=0; int w=0; char c=getchar();
        while(!isdigit(c)) w|=c=='-',c=getchar();
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        s*=w?-1:1;
    }
    TA inline void read(T &x,Args &...args) {read(x),read(args...);}
    TT inline void write(T x,char ch=' ')
    {
        if(x<0) x=-x,putchar('-');
        static char stk[30]; int top=0;
        do stk[top++]=x%10+'0',x/=10; while(x);
        while(top) putchar(stk[--top]);
        if(ch!='~') putchar(ch);
    }
}
using namespace IO;

namespace MTool
{
    static const int Mod=998244353;
    TT inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
    TT inline void cmax(T &a,T b) {a=max(a,b);}
    TA inline void cmax(T &a,T b,Args ...args) {a=max({a,b,args...});}
    TT inline void cmin(T &a,T b) {a=min(a,b);}
    TA inline void cmin(T &a,T b,Args ...args) {a=min({a,b,args...});}
}
using namespace MTool;

inline void file()
{
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

namespace LgxTpre
{
    constexpr int MAX=100010;
    constexpr int inf=2147483647;
    constexpr int INF=4557430888798830399;
    
    int n,vis[MAX],fl,ansl,ansr,ans;
	pii a[MAX];
    
    namespace DSU
    {
    	int fa[MAX],siz[MAX],sum[MAX],L[MAX],R[MAX];
    	inline void init() {for(int i=1;i<=n;++i) fa[i]=i,siz[i]=1,sum[i]=a[i].fi,L[i]=R[i]=i;}
    	int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
    	inline void merge(int x,int y)
		{
			x=find(x),y=find(y);
			if(x==y) return;
			siz[x]>siz[y]
			?(siz[x]+=siz[y],fa[y]=x,sum[x]+=sum[y],cmin(L[x],L[y]),cmax(R[x],R[y]))
			:(siz[y]+=siz[x],fa[x]=y,sum[y]+=sum[x],cmin(L[y],L[x]),cmax(R[y],R[x]));
		}
	}
	using namespace DSU;
    
    inline void mian()
    {
    	while(scanf("%lld",&n)!=EOF)
    	{
    		if(fl) puts(""); else fl=1;
    		for(int i=1;i<=n;++i) a[i]=mp(read(),i);
    		init(),sort(a+1,a+n+1,[](pii a,pii b){return a.fi>b.fi;}),ans=0,ansl=ansr=1;
    		for(int i=1;i<=n;++i)
    		{
    			auto [v,p]=a[i]; vis[p]=1;
    			if(vis[p-1]) merge(p,p-1);
    			if(vis[p+1]) merge(p,p+1);
    			int f=find(p);
    			if((ans<sum[f]*v)||(ans==sum[f]*v&&R[f]-L[f]<ansr-ansl)||(ans==sum[f]*v&&R[f]-L[f]==ansr-ansl&&L[f]<ansl)) ans=sum[f]*v,ansl=L[f],ansr=R[f];
			}
			for(int i=1;i<=n;++i) vis[i]=0;
			write(ans,'\n'),write(ansl),write(ansr,'\n');
		}
	}
}

bool Med;

signed main()
{
//  file();
    int Tbe=clock();
    LgxTpre::mian();
    int Ted=clock();
    fprintf(stderr,"\nMemory: %.3lf MB",abs(&Mbe-&Med)/1024.0/1024.0);
    fprintf(stderr,"\nTime: %.3lf ms",1e3*(Ted-Tbe)/CLOCKS_PER_SEC);
    return (0-0);
}