问题描述

给定长度为 $n$ 的序列:$a_1,a_2,…,a_n$,记为 $a[1:n]$。有 $q$ 个询问,每个询问给定两个数 $l,r$,求 $a[l:r]$ 中所有子序列的最小值之和。

输入

第一行包含两个整数 $n$ 和 $q$,分别代表序列长度和询问数。

接下来一行,包含 $n$ 个整数,第 $i$ 个整数为 $a_i$。

接下来 $q$ 行,每行包含两个整数 $l$ 和 $r$,代表一次询问。

输出

对于每次询问,输出一行,代表询问的答案。

思路

有一种比较直观的方法就是使用莫队,队中维护一个单调栈,并且记录栈中元素到前一个元素这段区间的答案。当插入元素时,更新单调栈,通过记录的信息可以比较容易的求出答案。

这题还有一个很妙的 Idea。考虑类似于上面莫队的方法,先处理出右端点为 $i$ 的所有 $a[l,i]$ 的最小值的和,记为 $pre_i$,再处理一个 $pre_i$ 的前缀和 $spre_i$,这样 $spre_i$ 即是 $a[1,i]$ 的答案。类似的再处理出 $suf_i$,表示所有左端点为 $i$ 的序列的最小值之和,以及 $ssuf_i$ 表示 $suf_i$ 的后缀和。

预处理完这些东西后,考虑如何回答区间 $a[l,r]$ 的答案,我们设 $a[l,r]$ 中最小值位于 $pos$,这个可以利用 ST 表求出。经过 $pos$ 这一点的所有区间对答案的贡献可以直接计算出来,考虑剩下 $a[l,pos-1]$ 及 $a[pos+1,r]$ 这两段的贡献如何计算。我们发现 $spre[r]-spre[pos]$ 就包含了 $a[pos+1,r]$ 这一段的答案和右端点在 $[pos+1,r]$ 左端点在 $[1,pos-1]$ 的区间最小值之和。而后面一部分由于跨过了 $pos$,它的贡献可以等价为 $(r-pos)*pre[pos]$,将它们相减就可以计算出 $a[pos+1,r]$ 的贡献,类似的可以同样计算出 $a[l,pos-1]$ 的贡献。

这样我们可以在 $O(1)$ 的时间内回答每一个询问,而算法复杂度的瓶颈在 $O(n \log n)$ 的 ST 表预处理上,而如果使用笛卡尔树或者用一些 $O(n)$ RMQ 的高级姿势,就可以在线性复杂度内完成这个操作。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, q, top, a[MAXN], f[MAXN][20], sta[MAXN], Log[MAXN];
LL pre[MAXN], spre[MAXN], suf[MAXN], ssuf[MAXN];

int query(int x, int y)
{
    int k=Log[y-x+1];
    if(a[f[x][k]]<a[f[y-(1<<k)+1][k]]) return f[x][k];
    else return f[y-(1<<k)+1][k];
}

int main()
{
    scanf("%d%d", &n, &q);
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &a[i]);
        f[i][0]=i;
    }
    for(rint i=1; i<20; ++i)
        for(rint j=1; j+(1<<i)-1<=n; ++j)
        {
            if(a[f[j][i-1]]<a[f[j+(1<<i-1)][i-1]]) f[j][i]=f[j][i-1];
            else f[j][i]=f[j+(1<<i-1)][i-1];
        }
    for(rint i=2; i<=n; ++i) Log[i]=Log[i/2]+1;
    sta[top=0]=0;
    for(rint i=1; i<=n; ++i)
    {
        while(top && a[sta[top]]>=a[i]) top--;
        pre[i]=pre[sta[top]]+1LL*a[i]*(i-sta[top]);
        sta[++top]=i;
        spre[i]=spre[i-1]+pre[i];
    }
    sta[top=0]=n+1;
    for(rint i=n; i>=1; --i)
    {
        while(top && a[sta[top]]>=a[i]) top--;
        suf[i]=suf[sta[top]]+1LL*(sta[top]-i)*a[i];
        sta[++top]=i;
        ssuf[i]=ssuf[i+1]+suf[i];
    }
    for(rint i=1, l, r; i<=q; ++i)
    {
        LL ans=0;
        scanf("%d%d", &l, &r);
        int pos=query(l, r);
        ans+=1LL*(pos-l+1)*(r-pos+1)*a[pos];
        ans+=ssuf[l]-ssuf[pos]-1LL*(pos-l)*suf[pos];
        ans+=spre[r]-spre[pos]-1LL*(r-pos)*pre[pos];
        printf("%lld\n", ans);
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注