题解：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 lmy_forever()
    {
        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::lmy_forever();
    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);
}