M_sea

洛谷3246 [HNOI2016]序列
LuoguBZOJ分析莫队。重点是两个状态怎么 $O(1)$ 的转移。先来考虑从 $[l+1,r]$ 转移到 $[...
扫描右侧二维码阅读全文
22
2019/02

洛谷3246 [HNOI2016]序列

Luogu

BZOJ

分析

莫队。

重点是两个状态怎么 $O(1)$ 的转移。

先来考虑从 $[l+1,r]$ 转移到 $[l,r]$ 的情况。这样子会多出来 $[l,l],[l,l+1],...,[l,r]$ 这些区间,我们来考虑这些区间的答案。

先找到这段区间的最小值 $p$ ,那么右端点在 $[p,r]$ 之间的区间的贡献都是 $a[p]$ 。

还剩下右端点在 $[l,p-1]$ 的情况,把这一部分单独拿出来考虑。

设 $f[i]$ 表示左端点为 $i$ 时,到后面左右位置的贡献。

可以利用单调栈求出右边第一个比 $a[i]$ 小的数,记它的位置为 $R[i]$。

于是可以得到 $f[i]=f[R[i]]+(R[i]-i)\times a[i]$。

然后 $[l,p-1]$ 的贡献就是 $f[l]-f[p]$。

从 $[l,r-1]$ 转移到 $[l,r]$ 的情况同理。

然后就做完了。时间复杂度 $O(n\sqrt{n})$。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,block;
int a[N];
struct query { int l,r,id; } q[N];
int sta[N],top=0;
int L[N],R[N];
ll f[N],g[N],ans[N];
int st[20][N],lg[N];

inline int cmp(query a,query b) {
    return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}

inline void build() {
    for (re int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (re int i=1;i<=n;++i) st[0][i]=i;
    for (re int i=1;i<=lg[n];++i)
        for (re int j=1;j+(1<<(i-1))<=n;++j) {
            int x=st[i-1][j],y=st[i-1][j+(1<<(i-1))];
            st[i][j]=a[x]<=a[y]?x:y;
        }
}

inline int query(int l,int r) {
    int t=lg[r-l+1],x=st[t][l],y=st[t][r-(1<<t)+1];
    return a[x]<=a[y]?x:y;
}

inline ll calcL(int l,int r) {
    int p=query(l,r);
    return 1ll*(r-p+1)*a[p]+g[l]-g[p];
}

inline ll calcR(int l,int r) {
    int p=query(l,r);
    return 1ll*(p-l+1)*a[p]+f[r]-f[p];
}

int main() {
    n=read(),m=read(),block=sqrt(n);
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+m+1,cmp);
    //calc L R f g
    for (re int i=1;i<=n;++i) {
        while (top&&a[sta[top]]>a[i]) --top;
        L[i]=sta[top],sta[++top]=i;
    }
    sta[top=0]=n+1;
    for (re int i=n;i>=1;--i) {
        while (top&&a[sta[top]]>a[i]) --top;
        R[i]=sta[top],sta[++top]=i;
    }
    for (re int i=1;i<=n;++i) f[i]=f[L[i]]+1ll*(i-L[i])*a[i];
    for (re int i=n;i>=1;--i) g[i]=g[R[i]]+1ll*(R[i]-i)*a[i];
    //init RMQ
    build();
    //solve
    ll res=0;
    for (re int i=1,l=1,r=0;i<=m;++i) {
        while (r<q[i].r) res+=calcR(l,++r);
        while (l>q[i].l) res+=calcL(--l,r);
        while (r>q[i].r) res-=calcR(l,r--);
        while (l<q[i].l) res-=calcL(l++,r);
        ans[q[i].id]=res;
    }
    for (re int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 57 PM

发表评论