题面：[COTS 2018] 直方图 Histogram

题目背景

译自 Izborne Pripreme 2018 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{1s,1G}$。

题目描述

给定笛卡尔坐标系中的直方图，宽度为 $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
2
6 9
1 4 4 5 2 3

样例输出 #1

1
3

样例 #2

样例输入 #2

1
2
10 5
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]$ 的长度，我们就可以知道答案应该是：

但是显而易见我们不可以枚举每一个区间，于是就想到了启发式合并，一层一层的合并，但是所谓层为何物？想到笛卡尔树，既可以快速求得最小值，也可以知道合并顺序。

那么我们现在假设知道了，当前点是 $u$ ，左子树选了 $L$ 个元素，右子树选了 $R$ 个元素，那么答案其实就是：

那么其实就是启发式合并区间 $L$ 和 $R$ 了。这就说明我们要快速计算 $\sum\limits_{i=l}^r \max\left\{h-\left\lceil\cfrac P i\right\rceil+1,0\right\}$

那么 $h-\left\lceil\cfrac P i\right\rceil\ge0$ 的最小值其实就是当 $i=h$ 的时候，所以直接处理出前缀和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 1e5 + 10;

int n; ll p;
int a[N];

inline void Input() {
    read(n, p);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
}

int stk[N], top;
int ls[N], rs[N], rt;

ll sum[N];
ll ans;

inline ll Calc(int l, int r, int h) {
    h++; l = max(l, (int)((p + h - 1) / h));
    if(l <= r) return 1LL * h * (r - l + 1) - sum[r] + sum[l - 1];
    else return 0;
}

void Dfs(int u, int l, int r) {
    if(u == 0) return ;
    // cout << u << ' ' << ls[u] << endl << u << ' ' << rs[u] << endl;
    Dfs(ls[u], l, u - 1), Dfs(rs[u], u + 1, r);
    int szL = u - l + 1, szR = r - u + 1;
    if(szL > szR) swap(szL, szR);
    for(int i = 1; i <= szL; i++) 
        ans += Calc(i, i + szR - 1, a[u]);
}

inline void Work() {
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (p + i - 1) / i;
    for(int i = 1; i <= n; i++) {
        int k = top;
        while(k > 0 && a[i] < a[stk[k]]) k--;
        if(k) rs[stk[k]] = i;
        else rt = i;
        if(k < top) ls[i] = stk[k + 1];
        stk[++k] = i;
        top = k;
    }
    Dfs(rt, 1, n);
    printf("%lld\n", ans);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}