BZOJ 4540 - [Hnoi2016]序列

#莫队 #RMQ

Published on 2016-04-21

描述

给定长度为 $n(n\le 100000)$ 的序列。现在有 $q(q\le 100000)$ 个询问，每个询问给定两个数 $l$ 和 $r$ ，求 $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。

样例输入

样例输出

分析

题目地址

区间问题，又不强制在线，我们可以考虑莫队算法。
关于莫队算法，如果初学的话，可以先看 HNOI 2016 Day2 T3，几乎是一个裸的莫队。
如果已知区间 $[l, r]$ 的答案，如果可以在 $O(1)$ 的时间内得出 $[l, r + 1]$ ， $[l, r - 1]$ , $[l + 1, r]$ , $[l - 1, r]$ 的答案的话，那么使用莫队算法可以在 $O(n\sqrt n)$ 的时间内求解所有询问。那么处理本题的关键就是如何实现 $O(1)$ 转移。

我们考虑从 $[l, r]$ 转移到 $[l, r + 1]$ 的增量，这样就可以从 $[l, r] \rightarrow [l, r + 1]$ ，也可以减去 $[l, r - 1] \rightarrow [l, r]$ 的增量到 $[l, r - 1]$ 。而左边是类似的，只需反过来做，所以只考虑：从 $[l, r]$ 转移到 $[l, r + 1]$ 的增量。
从 $[l, r]$ 到 $[l, r + 1]$ ，唯一的变化是多了一个 $a_{r + 1}$ ，也就多了以 $a_{r + 1}$ 结尾的 $r - l + 2$ 个子串，暴力扫一边可以 $O(1)$ 转移，但这无法承受！
我们定义 $\mathrm{left}(i)$ 为 $a_i$ 左边第一个小于等于它的元素位置，利用单调栈（单调队列无队首操作），我们可以在 $O(n)$ 的时间内求出所有元素的 $\mathrm{left}$ ，步骤如下：

向栈中添加位置 -1，表示无穷小的边界。
对于每个 $i$ ，弹出栈顶所有大于它的元素，则 $\mathrm{left}(i)$ 等于栈顶元素。
将位置 $i$ 推入栈。
跳到 2，直到结束。

为什么可以弹出栈顶所有大于 $a_i$ 的元素呢？考虑后面所有的元素，如果 $a_i$ 小于 $a_j (j < i)$ ，那么 $a_i$ 既比 $a_j$ 小，又比 $a_j$ 后，后面的元素肯定不会选到它。由于每个元素最多出入栈一次，所以复杂度为 $O(n)$ 。

接着考虑转移，可以用 RMQ 在 $O(1)$ 的时间里面找到 $[l, r + 1]$ 的最小元素 $a_{\mathrm{pos}}$ ，则新增的以 $[l, \mathrm{pos}]$ 开头， $r + 1$ 结尾的字串都以 $a_{\mathrm{pos}}$ 为最小值，贡献为 $(\mathrm{pos} - l + 1) * a_{\mathrm{pos}}$ 。剩下的部分就是考虑以 $[\mathrm{pos} + 1, r + 1]$ 开头部分的贡献了。
我们定义 $f_{[l, r]}$ 为 $[l, r]$ 部分的贡献，则我们要 $f_{[\mathrm{pos} + 1, r + 1]}$ 。刚刚求了 $\mathrm{left}$ ，所以我们不难得到

f_{[\mathrm{pos} + 1, r + 1]} = (r + 1 - \mathrm{left}(r + 1)) * a_{r + 1} + f_{[\mathrm{pos} + 1,\mathrm{left}(r + 1)]}

而又由于 $a_{\mathrm{left}(\mathrm{left}(r + 1))}$ 是左边第一个比 $a_{\mathrm{left}(r + 1)}$ 小的元素，所以 $a_{\mathrm{left}(r + 1)}$ 在 $[\mathrm{left}(\mathrm{left}(r + 1)) + 1, r + 1]$ 中最小，贡献为 $(\mathrm{left}(\mathrm{left}(r + 1)) - \mathrm{left}(r + 1)) * a_{\mathrm{left}(r + 1)}$ 。而如果 $a_{\mathrm{left}(\mathrm{left}(r + 1))}$ 就是 $\mathrm{pos}$ 的话，我们应该停止迭代，答案已经统计完毕，否则继续迭代直到碰到 $\mathrm{pos}$ 。因为 $\mathrm{pos}$ 是 $[l, r + 1]$ 的最小元素，所以一定会碰到 $\mathrm{pos}$ 。

那么就有递推：

f_{[l, r]} = \begin{cases}(r - \mathrm{left}(r)) * a_r + f_{[l, \mathrm{left}(r)] } & \mathrm{left}(r) \neq \mathrm{pos}\\ (r - \mathrm{left}(r)) * a_r & \mathrm{left}(r) = \mathrm{pos} \end{cases}

注意到这个每次转移仅仅只有终止位置 $\mathrm{pos}$ 不同，所以我们可以换种方法定义，维护一个类似前缀和的东西：

f_i = \begin{cases}(i - \mathrm{left}(i)) * a_i + f_{\mathrm{left}(i)} & i \ge 0 \\0 & i < 0 \end{cases}

则终止位置是 $\mathrm{pos}$ 的话，从 $[l, r]$ 转移到 $[l, r + 1]$ 的增量就是：

(\mathrm{pos} - l + 1) * a_{\mathrm{pos}} + f_{r + 1} - f_{\mathrm{pos}}

可以愉快的 $O(1)$ 转移了。整个算法的复杂度是： $O(n\sqrt n)$ ，带上 RMQ 的若干常数，注意预处理 $\lfloor \log_2n\rfloor$ 来减小常数。

代码

//  Created by Sengxian on 4/20/16.
//  Copyright (c) 2016年 Sen0gxian. All rights reserved.
//  BZOJ 4540 序列 sequence
#include <algorithm>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    static bool flag;
    n = 0, ch = getchar(), flag = false;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int maxn = 100000 + 3, maxm = maxn;
int block_size = 316;
int a[maxn], logs[maxn], n, q;
typedef long long ll;
ll ans[maxn], leftSum[maxn], rightSum[maxn], nowAns = 0;

struct query {
    int l, r, idx, bel;
    query(int l = 0, int r = 0, int idx = 0): l(l), r(r), idx(idx), bel(l / block_size) {}
    inline bool operator < (const query &q) const {
        return bel < q.bel || (bel == q.bel && r < q.r);
    }
}qs[maxm];

namespace RMQ {
    int minv[maxn][20];
    inline int cmp(const int &i, const int &j) {
        return a[i] < a[j] ? i : j;
    }
    inline void process() {
        for (int i = 0; i < n; ++i) minv[i][0] = i;
        for (int i = 1; i <= n; ++i) {
            static int q;
            logs[i] = 0, q = 1;
            while (q << 1 <= i) logs[i]++, q <<= 1;
        }
        for (int w = 1; (1 << w) <= n; ++w)
            for (int i = 0; i + (1 << w) <= n; ++i)
                minv[i][w] = cmp(minv[i][w - 1], minv[i + (1 << (w - 1))][w - 1]);
    }
    inline int get_min(int l, int r) {
        int bit = logs[r - l], q = 1 << bit;
        return cmp(minv[l][bit], minv[r - q][bit]);
    }
}

int stk[maxn];
void getLeft(int *a, ll *leftSum) {
    int sz = 0;
    stk[sz++] = -1;
    for (int i = 0; i < n; ++i) {
        while (sz != 1 && a[stk[sz - 1]] > a[i]) sz--;
        leftSum[i] = sz == 1 ? 0 : leftSum[stk[sz - 1]] + (i - stk[sz - 1]) * (ll)a[i];
        stk[sz++] = i;
    }
}

ll cnt = 0;

inline ll goRight(int l, int r) {
    int pos = RMQ::get_min(l, r + 1);
    return (pos - l + 1) * (ll)a[pos] + leftSum[r] - leftSum[pos];
}

inline ll goLeft(int l, int r) {
    int pos = RMQ::get_min(l - 1, r);
    return (r - pos) * (ll)a[pos] + rightSum[l - 1] - rightSum[pos];
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("test.in", "r", stdin);
    #endif
    n = ReadInt(), q = ReadInt(), block_size = sqrt(n);
    for (int i = 0; i < n; ++i) a[i] = ReadInt();
    for (int i = 0; i < q; ++i) {
        int l = ReadInt() - 1, r = ReadInt();
        qs[i] = query(l, r, i);
    }
    sort(qs, qs + q);
    RMQ::process();
    getLeft(a, leftSum);
    reverse(a, a + n);
    getLeft(a, rightSum);
    reverse(a, a + n);
    reverse(rightSum, rightSum + n);
    int l = 0, r = 0;
    for (int i = 0; i < q; ++i) {
        const query &q = qs[i];
        while (r < q.r) nowAns += goRight(l, r), r++;
        while (r > q.r) nowAns -= goRight(l, r - 1), r--;
        while (l > q.l) nowAns += goLeft(l, r), l--;
        while (l < q.l) nowAns -= goLeft(l + 1, r), l++;
        ans[q.idx] = nowAns;
    }
    for (int i = 0; i < q; ++i) printf("%lld\n", ans[i]);
    return 0;
}

k-d树学习笔记 HNOI 2016 Day1 简略题解

Sengxian's Blog