JZOJ 5231 序列问题

真是个码农题……

由于是乘，所以没法用单调栈来统计答案贡献。

考虑分治套路，于是问题变成了求区间左端点 ∈[l,mid]，区间右端点 ∈[mid+1,r] 的答案。
由于最值的单调性，我们可以多维护两个指针使得每层递归只需 O(n)。

具体地说，我们按 mid→l 顺序枚举 i，并同时维护满足 j1maxj=mid+1aj≤midmaxj=iaj 的最大的 j1 和满足 j2minj=mid+1aj≥midminj=iaj 的最大的 j2。
于是我们就可以把计算 [mid+1,r] 对 i 的贡献分成三个部分，这里我们假设 j1<j2，反过来类似： 1. [mid+1,j1]，这一段的最值与 [i,mid] 相同。 2. [j1+1,j2]，这一段仅最小值与 [i,mid] 相同。 3. [j2+1,r] 这一段的最值与 [i,mid] 不同。

于是我们可以在递归进入时维护五个量： 1. maxi=imaxj=mid+1aj 2. mini=iminj=mid+1aj 3. maxsumi=i∑j=mid+1maxj 4. minsumi=i∑j=mid+1minj 5. sumi=i∑j=mid+1maxi⋅mini

通过这五个量，三个部分的贡献就容易得出了。

此外，注意取模时，应该把较大的数先取模再乘。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e5;
const long long mod = 1e9 + 7;
int n;
long long a[N + 5],sum[N + 5],mx[N + 5],mn[N + 5],mxsum[N + 5],mnsum[N + 5];
long long ans;
void solve(int l,int r)
{
    if(l == r)
    {
        ans = (ans + a[l] * a[l] % mod) % mod;
        return ;
    }
    int mid = l + r >> 1;
    solve(l,mid),solve(mid + 1,r);
    mxsum[mid] = mnsum[mid] = sum[mid] = 0;
    mx[mid] = -0x3f3f3f3f3f3f3f3fLL,mn[mid] = 0x3f3f3f3f3f3f3f3fLL;
    for(register int i = mid + 1;i <= r;++i)
        mx[i] = max(mx[i - 1],a[i]),
        mn[i] = min(mn[i - 1],a[i]),
        mxsum[i] = mxsum[i - 1] + mx[i],
        mnsum[i] = mnsum[i - 1] + mn[i],
        sum[i] = (sum[i - 1] + mx[i] * mn[i] % mod) % mod;
    long long curmax = -0x3f3f3f3f3f3f3f3fLL,curmin = 0x3f3f3f3f3f3f3f3fLL;
    for(register int i = mid,j1 = mid,j2 = mid;i >= l;--i)
    {
        curmax = max(curmax,a[i]),curmin = min(curmin,a[i]);
        while(j1 < r && mx[j1 + 1] <= curmax)
            ++j1;
        while(j2 < r && mn[j2 + 1] >= curmin)
            ++j2;
        if(j1 <= j2)
            ans = (ans +
                curmax % mod * curmin % mod * (j1 - mid) % mod +
                (mxsum[j2] - mxsum[j1]) % mod * curmin % mod +
                (sum[r] - sum[j2]) % mod
            ) % mod;
        else
            ans = (ans +
                curmax % mod * curmin % mod * (j2 - mid) % mod +
                (mnsum[j1] - mnsum[j2]) % mod * curmax % mod +
                (sum[r] - sum[j1]) % mod
            ) % mod;
    }
}
int main()
{
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%lld",a + i);
    solve(1,n);
    printf("%lld\n",(ans + mod) % mod);
}