HNOI2016 序列 题解

HNOI2016 序列题解

$\text{Description}$

给定一个序列 $\{a_n\}$，每次询问求一个区间内所有子序列的最小值之和。

$\text{Solution}$

考虑当前待求的询问是 $[l,r]$。

我们求出它的最小值位置 $p$，那么所有包含 $p$ 的子序列的最小值答案都是 $p$，这部分的答案是 $a_p\times(p-l+1)\times(r-p+1)$。

现在考虑 $(p,r]$ 部分的答案。我们记 $f_i$ 表示以 $i$ 结尾的子序列的答案，$L_i$ 表示满足 $j<i,a_j<a_i$ 的最大的 $j$，若不存在则为 $0$，那么容易有：

$f_i=a_i\times(i-L_i)+f_{L_i}$

如果不理解上式可以将 $f_{L_i}$ 展开。

可以证明，对于任意的 $i\in(p,r]$，都可以通过 $i\leftarrow L_i$ 得到 $p$。故对于任意的 $i\in(p,r]$，展开 $f_i$ 后都会有 $f_p$ 这一项。我们将其减去后，发现这里的答案不再包含区间左端点 $\le p$ 的答案了。也就是说这部分的答案其实是：

$(\sum_{i=p+1}^rf_i)-f_p\times(r-p)$

对 $f$ 作前缀和即可。

对于 $[l,p)$ 的部分，我们记 $g_i$ 表示以 $i$ 开头的子序列的答案，$N_i$ 表示满足 $j>i,a_j<a_i$ 的最小的 $j$，若不存在则为 $0$，那么类似地有：

$g_i=a_i\times(N_i-i)+g_{N_i}$

然后跟上面差不多，得到答案：

$(\sum_{i=l}^{p-1}g_i)-g_p\times(p-l)$

对于 $N,L$ 可以用单调栈 $O(n)$ 求。区间最小值用 ST 表 $O(n\log n+q)$ 求。那么总时间复杂度就是 $O(n\log n)$。

$\text{Code}$

#include<bits/stdc++.h>
#define REG register
#define MAXN 100005
#define LL long long
using namespace std;
inline int read(){
    REG int x(0),sign(0);
    REG char c=getchar();
    while(!isdigit(c)) sign=(c^45)?sign:1,c=getchar();
    while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
    return sign?-x:x;
}

int n,q;

int a[MAXN];
int Rmq[MAXN][25],Log[MAXN];
LL f[MAXN],sf[MAXN];
LL g[MAXN],sg[MAXN];
int N[MAXN],L[MAXN];
int Sta[MAXN],top;

inline int Min(int lhs,int rhs){return a[lhs]<a[rhs]?lhs:rhs;}

inline void Init(){
    for(REG int i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
    for(REG int i=1;i<=n;++i) Rmq[i][0]=i;
    for(REG int j=1;j<=Log[n];++j)
        for(REG int i=1;i<=n-(1<<(j-1))+1;++i)
            Rmq[i][j]=Min(Rmq[i][j-1],Rmq[i+(1<<(j-1))][j-1]);
}

inline int Ask(int l,int r){
    int k=r-l+1;
    return Min(Rmq[l][Log[k]],Rmq[r-(1<<Log[k])+1][Log[k]]);
}

inline void getLN(){
    for(REG int i=1;i<=n;++i){
        while(top&&a[i]<a[Sta[top]]) N[Sta[top--]]=i;
        L[i]=Sta[top],Sta[++top]=i;
    }
    while(top) N[Sta[top--]]=n+1;
}


inline void PreWork(){
    for(REG int i=1;i<=n;++i)
        f[i]=1ll*a[i]*(i-L[i])+f[L[i]];
    for(REG int i=1;i<=n;++i)
        sf[i]=sf[i-1]+f[i];
    for(REG int i=n;i;--i)
        g[i]=1ll*a[i]*(N[i]-i)+g[N[i]];
    for(REG int i=n;i;--i)
        sg[i]=sg[i+1]+g[i];
}

void Work(){
    n=read(),q=read();
    a[0]=a[n+1]=2e9;
    for(REG int i=1;i<=n;++i) a[i]=read();
    Init(),getLN(),PreWork();
    while(q--){
        int l=read(),r=read();
        int p=Ask(l,r);
        LL res=1ll*a[p]*(p-l+1)*(r-p+1);
        res+=sf[r]-sf[p]-f[p]*(r-p);
        res+=sg[l]-sg[p]-g[p]*(p-l);
        printf("%lld\n",res);
    }
}

int main(){Work();}

2021-03-20

CF Chapter2 简要题解

CodeForces

HNOI2016 序列题解