bzoj4540

莫队+st表

据说这是经典问题，但是我不会。。。

问题在于莫队怎么算贡献，每次移动一个位置，现在为[l,r],那么就增加了[l-1,r),r的贡献，怎么算呢？我们预处理fl,fr,fl[i]表示以i为开头的前缀和，fr表示以i为结尾的后缀和，这个东西能够相减，但也不是完全满足

每次我们计算贡献的时候，设最小值的位置为p，那么对于右端点来说，贡献就是fr[r]-fr[p]+(p - l + 1) * a[p],这也是因为不完全满足可减性，因为求前缀和是fr[i]=(i - l[i] + 1) * a[i] + fr[l[i]-1],那么满足可减性是在每个l[i]的时候可以减，又因为p作为最小值肯定是处于一个l的位置，那么就能减了，而到l的贡献就是p作为最小值。

理解得还不是很透彻我一直以为我的单调栈是左闭右闭的，竟然是左开右闭的

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + ;

int n, m, block, l = , r, top;

ll sum;

int st[N], Log[N], f[N][], L[N], R[N];

ll fl[N], fr[N], a[N], ans[N];

struct query {

    int l, r, id;

    bool friend operator < (const query &a, const query &b) {

        return (a.l - ) / block == (b.l - ) / block ? a.r < b.r : (a.l - ) / block < (b.l - ) / block;

    }

} q[N];

inline int rd()

{

    int x = , f = ; char c = getchar();

    while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

    while(c >= '' && c <= '') { x = x *  + c - ''; c = getchar(); }

    return x * f;

}

int Min(int x, int y)

{

    return a[x] < a[y] ? x : y;

}

int rmq(int l, int r)

{

    int x = Log[r - l + ];

    return Min(f[l][x], f[r - ( << x) + ][x]);

}

void addl(int l, int r, ll f)

{

    int p = rmq(l, r);

    sum += f * (fl[l] - fl[p] + a[p] * (ll)(r - p + ));

}

void addr(int l, int r, ll f)

{

    int p = rmq(l, r);

    sum += f * (fr[r] - fr[p] + a[p] * (ll)(p - l + ));

}

int main()

{

    n = rd();

    m = rd();

    block = sqrt(n);

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

    {

        a[i] = rd();

        f[i][] = i;

    }

    for(int i = ; i <= n; ++i) Log[i] = Log[i >> ] + ;

    for(int j = ; j <= ; ++j)

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

            f[i][j] = Min(f[i][j - ], f[i + ( << (j - ))][j - ]);

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

    {

        q[i].l = rd();

        q[i].r = rd();

        q[i].id = i;

    }

    sort(q + , q + m + );

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

    {

        L[i] = R[i] = i;

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

        {

            R[st[top - ]] = R[st[top]];

            L[i] = L[st[top]];

            --top;

        }

        st[++top] = i;

    }

    while(top)

    {

        R[st[top - ]] = R[st[top]];

        --top;

    }

    for(int i = ; i <= n; ++i) fr[i] = fr[L[i] - ] + (ll)(i - L[i] + ) * a[i];

    for(int i = n; i; --i) fl[i] = fl[R[i] + ] + (ll)(R[i] - i + ) * a[i];

    l = ;

    r = ;

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

    {

        while(r < q[i].r) addr(l, ++r, );

        while(r > q[i].r) addr(l, r--, -);

        while(l < q[i].l) addl(l++, r, -);

        while(l > q[i].l) addl(--l, r, );

        ans[q[i].id] = sum;

    }

    for(int i = ; i <= m; ++i) printf("%lld\n", ans[i]);

    return ;

}

莫队一定要先动r

巴特西

bzoj4540

最新文章

热门文章