题解【P2422 良好的感觉】

· · 题解

传送门

用链表做的，本来以为题解区都是链表，结果没想到都是单调栈，好像没有链表。。。。。 不过单调栈是 $O(n)$ 的，链表要加一个排序的复杂度，是 $O(n\log n+n)$。 $\large{\text{Soltion}}

其实思路都差不多。都是枚举区间最小值，然后向两边拓展。

但是我们发现一个重要性质：若枚举到比它小的值就停下，这就让我想到了链表。

我们考虑每次找到当前最大值，我们记完它的值，就把它删除（先不管怎么记录），然后我们会发现，在这样的操作后，每一次访问访问，链表中就没有数比它大。

然后我们就可以轻松发现，当前值的左指针所指的值即为左侧第一个比它小的值，当前值的右指针所指的值即为右侧第一个比它小的值，而它所能更新到的区间即为它的左指针 +1\sim 右指针 -1。

计算的话就是当前值 \times 区间和，你可以用各种数据结构、前缀和等维护区间和。

因为每次要找最大值，所以排序是本程序的复杂度瓶颈（当然你可以用各种数据结构），总复杂度为 O(n\log n+n)，轻松通过。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#define int long long
using namespace std;
//char cc[1<<21],*uu=cc,*vv=cc;
//#define getchar() (uu==vv&&(vv=(uu=cc)+fread(cc,1,1<<21,stdin),uu==vv)?EOF:*uu++)
inline int read(){
    char ch=getchar();int X=0;bool fl=0;
    while(ch<'0'||ch>'9'){if(ch=='-')fl=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){X=(X<<1)+(X<<3)+ch-'0';ch=getchar();}
    if(fl)return ~(X-1);
    return X;
}
int n,l[100005],r[100005],s[100005],ans;
struct N{
    int s,id;
    bool operator<(const N&U)const{//为了排序重载一下，你也可以写cmp
        return s>U.s;
    }
}a[100005];
signed main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=(N){read(),i},s[i]=s[i-1]+a[i].s;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)l[i]=i-1,r[i]=i+1;//链表的初始化
    for(int i=1;i<=n;i++){//倒序排序后取出的就是最大值
        int t=s[r[a[i].id]-1]-s[l[a[i].id]];//前缀和当前区间和
        ans=max(ans,t*a[i].s);//取max
        l[r[a[i].id]]=l[a[i].id];//删点
        r[l[a[i].id]]=r[a[i].id];
    }
    cout<<ans<<'\n';
}

如果您有什么链表优化到 O(n) 的方法，也可以跟我说哦，谢谢！

然后昨天晚上做梦的时候想到了，你说神不神奇。。。

但是这也足以体现我的 sb。

其实方法比较简单，既然排序是复杂度瓶颈，那么就把快排改成桶排或者各种玄学排序。。。但是为了记录编号，所以要开个 vector。

结果由于 vector 慢的一批，所以还没 sort 快。。复杂度 O(K+n)（K 为常数）。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#define int long long
using namespace std;
//char cc[1<<21],*uu=cc,*vv=cc;
//#define getchar() (uu==vv&&(vv=(uu=cc)+fread(cc,1,1<<21,stdin),uu==vv)?EOF:*uu++)
inline int read(){
    char ch=getchar();int X=0;bool fl=0;
    while(ch<'0'||ch>'9'){if(ch=='-')fl=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){X=(X<<1)+(X<<3)+ch-'0';ch=getchar();}
    if(fl)return ~(X-1);
    return X;
}
int n,l[100005],r[100005],s[100005],a[100005],ans;
vector<int>v[1000005];//桶
signed main(){
    n=read();
    int ms=0;
    for(int i=1;i<=n;i++){
        a[i]=read(),s[i]=s[i-1]+a[i];
        v[a[i]].push_back(i);
        ms=max(ms,a[i]);
    }
    for(int i=1;i<=n;i++)l[i]=i-1,r[i]=i+1;
    for(int i=ms;i;i--){
        if(v[i].empty())continue;
        for(int j=0;j<v[i].size();j++){
            int t=s[r[v[i][j]]-1]-s[l[v[i][j]]];
            ans=max(ans,t*i);
            l[r[v[i][j]]]=l[v[i][j]];
            r[l[v[i][j]]]=r[v[i][j]];
        }
    }
    cout<<ans<<'\n';
}