原题呈现

P11261 直方图 Histogram#

题目描述#

给定笛卡尔坐标系中的直方图，宽度为 $n$ ，第 $i$ 格的高度为 $h_i$ ．也就是说，对于 $\forall 1\le i\le n$ ，第 $i$ 格所占矩形的顶点坐标分别为 $(i-1,0),(i,0),(i-1,h_i),(i,h_i)$ ．

给定正整数 $p$ ，求出满足以下条件的矩形的数量：

矩形的四个顶点的坐标均为整数；
矩形有一条边在 $x$ 轴上；
矩形完全位于直方图内部（可以与边界相切）；
矩形的面积至少为 $p$ ．

输入格式#

第一行，两个正整数 $n,p$ ．

第二行， $n$ 个正整数 $h_1,h_2,\ldots,h_n$ ．

输出格式#

输出一行一个整数，表示答案．

输入输出样例 #1#

输入 #1#

1
6 9
2
1 4 4 5 2 3

输出 #1#

1
3

输入输出样例 #2#

输入 #2#

1
10 5
2
3 6 1 3 2 1 5 3 4 2

输出 #2#

1
31

说明/提示#

样例解释#

样例一解释：

数据范围#

对于 $100\%$ 的数据，保证：

$1\le n\le 10^5$ ；
$1\le p\le 10^{14}$ ；
$1\le h_i\le 10^{9}$ ．

子任务编号	$n\le$	$p$	$h_i\le$	得分
$1$	$3\, 000$	$\le 10^{12}$	$10^9$	$10$
$2$	$10^5$	$\le 10^8$	$1\, 000$	$15$
$3$	$10^5$	$=1$	$10^9$	$15$
$4$	$10^5$	$\le 10^5$	$10^9$	$25$
$5$	$10^5$	$\le 10^{14}$	$10^9$	$35$

思路#

由于高度最小的一项是瓶颈，考虑以高度最小的一项为中点，先计算出左端点在中点左边，右端点在中点右边的方案数，再分治，分左半边和右半边两个子问题分别考虑．

在处理子问题 $[l, r]$ 时，首先，使用 ST 表计算出 $[l,r]$ 中最小的一项 $lim$ ，其下表为 $m$ ．若 $m$ 左边的元素数量更小，考虑枚举起点 $i$ ，假定终点为 $j$ ，则有方案数为：

\sum^{m}_{i=l}\sum^{r}_{j=r}max\{lim - \lceil\frac{p}{j-i+1}\rceil + 1, 0\}

想想如何去掉 $max$ ．

当 $lim - \lceil\frac{p}{j-i+1}\rceil + 1 \geq 0$ 时，就有：

\begin{align*} lim - \lceil\frac{p}{j-i+1}\rceil &\geq 0\\ lim &\geq\lceil\frac{p}{j-i+1}\rceil\\ lim \times(j - i + 1) &\geq p\\ j - i + 1 &\geq \frac{p}{lim}\\ j&\geq\frac{p}{lim} - 1 + i\\ \end{align*}

由于 $j\in\mathbb{N}$ ，所以：

j\geq\lceil\frac{p}{lim}\rceil - 1 + i

令： $need = \lceil\frac{p}{lim}\rceil - 1 + i$

则原式化简为：

\begin{align*} \sum^{m}_{i=l}\sum^{r}_{j=need}(lim - \lceil\frac{p}{j-i+1}\rceil + 1)\\ \sum^{m}_{i=l}(\sum^{r}_{j=need}(lim + 1) - \sum^{r}_{j=need}(\lceil\frac{p}{j-i+1}\rceil)) \end{align*}

只需要使用前缀和记录 $\lceil\frac{p}{i}\rceil$ ，就可以在 $O(n)$ 的时间里算出上式．

若 $m$ 右边的元素数量更小，也是同理，考虑枚举终点为 $j$ ，假定起点为 $i$ ，则若令 $need = j + 1 - \lceil\frac{p}{lim}\rceil$

原式化简为：

\sum^{m}_{j=1}(\sum^{need}_{i=l}(lim + 1) - \sum^{need}_{i=l}(\lceil\frac{p}{j-i+1}\rceil))

1
#include <bits/stdc++.h>
2
#define int long long
3
using namespace std;
4
#define querySum(l, r) (sum[(r)] - sum[(l) - 1])
5

6
const int N = 1e5 + 100;
7

8
int n, p, h[N], sum[N], ans;
9

10
struct Node {
11
    int n;
12
    int id;
13
    friend bool operator<(const Node a, const Node b) { return a.n < b.n; }
14
} st[N][20];
15

16
Node query(int l, int r) {
17
    int len = log2(r - l + 1);
18
    return min(st[l][len], st[r - (1 << (len)) + 1][len]);
19
}
20

21
int ceilDivided(int a, int b) {
22
    double da = 1.0 * a / b;
23
    int ia = a / b;
24
    if (da != (double)ia) {
25
        da++;
26
    }
27
    return da;
28
}
29

30
void solve(int l, int r) {
31
    if (l > r) {
32
        // 不可能存在合法方案
33
        return;
34
    }
35
    if (l == r) {
36
        // 仅一竖条
37
        ans += max(0ll, h[l] - p + 1);
38
        return;
39
    }
40
    int m = query(l, r).id;
41
    int lim = h[m];
42
    // 处理跨过中间的
43
    if (m - l < r - m) {
44
        // 左边更少一点
45
        for (int i = l; i <= m; i++) {
46
            int j0 = max(m, ceilDivided(p, lim) + i - 1);
47
            if (j0 <= r)
48
                ans +=
49
                    (lim + 1) * (r - j0 + 1) - querySum(j0 - i + 1, r - i + 1);
50
        }
51
    } else {
52
        // 右边更少一点
53
        for (int j = m; j <= r; j++) {
54
            int i0 = min(m, j + 1 - ceilDivided(p, lim));
55
            if (l <= i0)
56
                ans +=
57
                    (lim + 1) * (i0 - l + 1) - querySum(j - i0 + 1, j - l + 1);
58
        }
59
    }
60
    // 处理只在两边的
61
    solve(l, m - 1);
62
    solve(m + 1, r);
63
}
64

65
signed main() {
66
    ios::sync_with_stdio(false);
67
    cin.tie(0);
68
    cout.tie(0);
69
    cin >> n >> p;
70
    // 预处理 ceil(p / i)
71
    for (int i = 1; i <= n; i++) {
72
        sum[i] = sum[i - 1] + ceilDivided(p, i);
73
    }
74
    for (int i = 1; i <= n; i++) {
75
        cin >> h[i];
76
    }
77
    for (int i = 0; i <= n; i++) {
78
        st[i][0] = {h[i], i};
79
    }
80
    for (int j = 1; j <= 17; j++) {
81
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
82
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
83
        }
84
    }
85
    solve(1, n);
86
    cout << ans << endl;
87
    return 0;
88
}

一般的，如果对于一道题，统计方案时有最大值或最小值作为阻碍/瓶颈，可以考虑分治。

音乐

音乐

P11261 直方图 Histogram#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

说明/提示#

样例解释#

数据范围#

思路#

文章分享

音乐

安吉D2-T2

P11261 直方图 Histogram#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

说明/提示#

样例解释#

数据范围#

思路#

文章分享