JZOJ 5231. 序列问题 | Alpha1022's Blog

真是个码农题……

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

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

具体地说，我们按 $m i d \to l$ 顺序枚举 $i$ ，并同时维护满足 ${max}_{j = m i d + 1}^{j_{1}} a_{j} \leq {max}_{j = i}^{m i d} a_{j}$ 的最大的 $j_{1}$ 和满足 ${min}_{j = m i d + 1}^{j_{2}} a_{j} \geq {min}_{j = i}^{m i d} a_{j}$ 的最大的 $j_{2}$ 。
于是我们就可以把计算 $[m i d + 1, r]$ 对 $i$ 的贡献分成三个部分，这里我们假设 $j_{1} < j_{2}$ ，反过来类似： 1. $[m i d + 1, j_{1}]$ ，这一段的最值与 $[i, m i d]$ 相同。 2. $[j_{1} + 1, j_{2}]$ ，这一段仅最小值与 $[i, m i d]$ 相同。 3. $[j_{2} + 1, r]$ 这一段的最值与 $[i, m i d]$ 不同。

于是我们可以在递归进入时维护五个量： 1. $m a x_{i} = {max}_{j = m i d + 1}^{i} a_{j}$ 2. $m i n_{i} = {min}_{j = m i d + 1}^{i} a_{j}$ 3. $m a x s u m_{i} = \sum_{j = m i d + 1}^{i} m a x_{j}$ 4. $m i n s u m_{i} = \sum_{j = m i d + 1}^{i} m i n_{j}$ 5. $s u m_{i} = \sum_{j = m i d + 1}^{i} m a x_{i} \cdot m i n_{i}$

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

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

代码：

#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);
}

『My guiding star.』

JZOJ 5231 序列问题