[bzoj4540][Hnoi2016][序列] (莫队算法+单调栈+st表)

时间：2021-11-03 11:59:08

Description

　　给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：al,al+1,…,ar-
1,ar。若1≤l≤s≤t≤r≤n，则称a[s:t]是a[l:r]的子序列。现在有q个询问，每个询问给定两个数l和r，1≤l≤r
≤n，求a[l:r]的不同子序列的最小值之和。例如，给定序列5,2,4,1,3，询问给定的两个数为1和3，那么a[1:3]有
6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这6个子序列的最小值之和为5+2+4+2+2+2=17。

Input

　　输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开
,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。

Output

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

Sample Input







Sample Output












HINT




1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9


Solution


litc学长在暑假就讲过的题，现在临近寒假才过掉。。。


观察题目要求，容易得出若要优化暴力枚举，就要有技巧地统计每个元素产生的贡献


我们知道，任意元素x的贡献都可以表示为一个区间(l,r)，其中a[l]<a[x] 且 a[r]<a[x]


询问时，我们用莫队离线做，分块一下


先按块编号和右端点下标分别为第一、第二关键字排序询问


区间最小值可以用st表预处理出来


对每个询问，我们用O(n^(1/2))时间进行转移，每次移除或加入一个元素时，统计此元素对当前区间[l,r]的贡献，算一下就行


最后输出就好了，我的程序有点慢，估计是变量名太长、函数太多




#include <math.h>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define MaxN 100010

#define MaxBuf 1<<22

#define L long long

#define RG register

#define inline __inline__ __attribute__((always_inline))

#define Blue() (S == T&&(T=(S=B)+fread(B,1,MaxBuf,stdin),S == T) ? 0 : *S++)

#define dmin(x,y) ((x) < (y)?(x):(y))

char B[MaxBuf],*S=B,*T=B;

inline void Rin(RG int &x) {

    x=;RG int c=Blue(),f=;

    for(; c < ||c > ; c=Blue())

        if(c == )f=-;

    for(; c > &&c < ; c=Blue())

        x=(x<<)+(x<<)+c-;

    x*=f; }

L sl[MaxN],sr[MaxN],ans[MaxN];

int n,m,a[MaxN],block_size,log_pre[MaxN],pl[MaxN],pr[MaxN],_pb[MaxN];

struct Pr{

    int fir,sec;

    Pr() {}

    Pr(RG int _,RG int __) : fir(_),sec(__) {}

    bool operator < (const Pr &other) const {

        return fir < other.fir; } }f[MaxN][];

struct Request{

    int l,r,id,belong;

    bool operator < (const Request &other) const {

        if(belong == other.belong)

            return r < other.r;

        return belong < other.belong; } }Q[MaxN];

inline void Rmq_Init() {

    for(RG int i=; i<; i++)

        log_pre[<<i]=;

    for(RG int i=; i<=n; i++)

        log_pre[i]+=log_pre[i-];

    for(RG int i=; i<=n; i++)

        f[i][]=Pr(a[i],i);

    for(RG int k=; k<; k++)

        for(RG int i=; i<=n-(<<k)+; i++)

            f[i][k]=dmin(f[i][k-],f[i+(<<k-)][k-]); }

inline int Rmq_Query(RG int l,RG int r) {

    RG int tim=log_pre[r-l+];

    return dmin(f[l][tim],f[r-(<<tim)+][tim]).sec; }

inline void Mono_Stack() {

    RG int top=,i;

    for(i=; i<=n; i++) {

        while(top && a[_pb[top]] > a[i])

            pr[_pb[top]]=i,top--;

        _pb[++top]=i; }

    while(top)pr[_pb[top]]=n+,top--;

    for(i=n; i; i--) {

        while(top && a[_pb[top]] > a[i])

            pl[_pb[top]]=i,top--;

        _pb[++top]=i; }

    while(top)pl[_pb[top]]=,top--;

    for(i=; i<=n; i++)

        sl[i]=sl[pl[i]]+(L)a[i]*(i-pl[i]);

    for(i=n; i; i--)

        sr[i]=sr[pr[i]]+(L)a[i]*(pr[i]-i);

}

inline L extend(RG int l,RG int r,RG bool c) {

    RG int x=Rmq_Query(l,r);

    return c ? (L)a[x]*(x-l+)+sl[r]-sl[x] :

                (L)a[x]*(r-x+)+sr[l]-sr[x];

}

inline void block_solve() {

    RG L ans;

    RG int l,r,i;

    for(i=; i<=m; i++) {

        if(i == ||Q[i].belong != Q[i-].belong)

            r=(Q[i].belong-)*block_size,l=r+,ans=;

        while(r < Q[i].r)

            ans+=extend(l,++r,);

        while(l < Q[i].l)

            ans-=extend(l++,r,);

        while(l > Q[i].l)

            ans+=extend(--l,r,);

        :: ans[Q[i].id]=ans; } }

int main() {

    Rin(n),Rin(m);

    block_size=static_cast<int>(sqrt(n));

    for(RG int i=; i<=n; i++)

        Rin(a[i]);

    for(RG int i=; i<=m; i++)

        Rin(Q[i].l),Rin(Q[i].r),Q[i].id=i,Q[i].belong=(Q[i].l-)/block_size+;

    std::sort(Q+,Q++m);

    Rmq_Init();

    Mono_Stack();

    block_solve();

    for(RG int i=; i<=m; i++)

        printf("%lld\n",ans[i]);

    return ; }




相关文章