P7286 「EZEC-5」人赢
可以想到对于每个数要找到比他大的数中下标最大的数，我们按照数的大小排序，我们维护原序列的一个指针，对于每个数如果比指针大那么就左移指针，可以思考下为什么：
指针上的数比现在这个数要小那比后面的数都小，于是我们左移指针直到大于这个数，可以发现我们也在一直维护下标最大值，复杂度为 \(O(n\log n)\)。
其实如果可以也可以用树状数组求，但是这题数据范围太大了。
#include <bits/stdc++.h>
#define int long long
#define re register
#define ll long long
const int N=1e6+10;
using namespace std;
int n;
int a[N];
int ans=0;
int k[N];
struct ss{
int val,id;
}b[N];
bool cmp(ss g,ss h){
return g.val<h.val;
}
signed main(){
// freopen("kingdom3.in","r",stdin);
// freopen("a.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i].id=i;
b[i].val=a[i];
ans=max(ans,a[i]*i);
}
sort(b+1,b+n+1,cmp);
int r=n;
for(int i=1;i<=n;i++){
while(a[r]<b[i].val||r==b[i].id){
r--;
}
ans=max(ans,(r+b[i].id)*b[i].val);
}
cout<<ans;
return 0;
}
P7291 「EZEC-5」人赢 加强版
加强版必须 \(O(n)\)，如果我们 \(i<j\) 并且 \(k_i<k_j\) 那么除了 \(x=j\) 我们选 \(j\) 总是最优的，有了这一点我们就从后向前枚举每一个数，同时维护最大值，更新时就找到离他最近的最大值。
为什么这样是对的，看图。
我们这时到了c本应该选a，他如果选b会怎么样。
已知 \(a>b>c\)，\((x+y)\times b\) 一定优于 \((z+y)\times c\)，因为此时第二个式子的数又不大同时下标和也不大，那如果 \(a>c>b\) 的话，\((z+y)\times b\)也不见得优到哪去，总结来说就是因为如果和后面的匹配更优，那后面的和这个相邻的匹配会比这个匹配更优。
#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define re register
#define ll long long
const int N=1e7+10;
const int mod=998244353;
using namespace std;
int n;
int a[N];
int ans=0;
inline int get(int x,int y){
return (x+y)*min(a[x],a[y]);
}
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
signed main(){
// freopen("kingdom3.in","r",stdin);
// freopen("a.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
n=read();
for(re int i=1;i<=n;i++){
a[i]=read();
ans=max(ans,a[i]*i);
}
int l=n;
for(re int i=n-1;i>=1;i--){
ans=max(ans,get(i,l));
if(a[i]>a[l]){
l=i;
}
}
cout<<ans;
return 0;
}