P9275 题解

Purslane · 2023-05-01 21:40:59 · 题解

Solution

一道简单题，提供一种不需要脑子的做法。

首先题目问的是 \max_{l\le u<v \le r \& a_u>a_v} a_u \times a_v。后文称这是 u 和 v 的配对。

然后考虑如果 l \le u < v \le r 时，如果出现了 a_u<a_v，那么最终答案肯定不是 u 和 v 之后的配对，不然换 v 根他们配对更优。

所以对于每个数 i，它只会和第一个不比它小的数之前的一部分进行配。也就是说，用单调栈找到后面的第一个不比它小的数 nxt_i，最终 u 只能和 (u,nxt_u) 中的数配对。最优情况肯定是选中间的最大值。

那么考虑询问的时候，从 l 出发，每次找到下一个 k=nxt_l。由定义，(l,k) 中的数肯定比 a_l 都小，也都比 a_k 小，他们一定不会作为答案配对的前者，不然换 l 会更优。

所以要么用 l 和 (l,k) 之间的数配对，这个可以预处理。要么看 k 和后面的情况，令 l=k。

这个过程可以看做每个 l 向 nxt_l 连边然后找树链的最大值。可以倍增解决。

复杂度 O(n \log n)。

代码：

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,nxt[MAXN][30],mx[MAXN][30],st[MAXN][30],a[MAXN],q;
stack<int> sts; int calc(int l,int r) {if(l>r) return 0;int k=log2(r-l+1);return max(st[l][k],st[r-(1<<k)+1][k]);}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n; ffor(i,1,n) cin>>a[i],st[i][0]=a[i];
    ffor(k,1,20) for(int l=1,r=(1<<k);r<=n;l++,r++) st[l][k]=max(st[l][k-1],st[l+(1<<k-1)][k-1]);
    a[n+1]=INT_MAX; sts.push(n+1);
    ffor(i,0,21) nxt[n+1][i]=n+1;
    roff(i,n,1) {
        while(a[sts.top()]<a[i]) sts.pop();
        nxt[i][0]=sts.top(),mx[i][0]=a[i]*calc(i+1,nxt[i][0]-1);    
        ffor(j,1,20) nxt[i][j]=nxt[nxt[i][j-1]][j-1],mx[i][j]=max(mx[i][j-1],mx[nxt[i][j-1]][j-1]);
        sts.push(i);
    }
    cin>>q;
    ffor(i,1,q) {
        int l,r; cin>>l>>r;
        int ans=0;
        roff(j,20,0) if(nxt[l][j]<=r) ans=max(ans,mx[l][j]),l=nxt[l][j];
        ans=max(ans,a[l]*calc(l+1,r));
        cout<<ans<<'\n';    
    }
    return 0;
}