SP6950 CTOI10D3 - A HUGE TOWER 题解

题目链接：CTOI10D3 - A HUGE TOWER

题意：

题目描述 有 \(N(2\le N\le620000)\) 块砖，要搭一个 \(N\) 层的塔，要求：

如果砖 \(A\) 在砖 \(B\) 上面，那么 \(A\) 不能比 \(B\) 的长度 \(+D\) 要长。

问有几种方法，输出 答案模 \(10^9+9\) 的值。

输入格式：

第一行： \(N,D\) 。

第二行： \(N\) 个数，表示每块砖的长度。

输出格式：

方案数。

思路挺有趣的题目。我们会发现，以 \(i\) 为结尾的一些方案可能会从后面得到贡献。

并且我们实际上并不知道也不关心某种方案的结尾是什么构成的，这意味着我们无法从结尾上考虑

因此不妨考虑每个 \(i\) 会在什么时候插入答案序列。

首先先把所有的 \(a_i\) 从小到大排序，然后依次考虑每个 \(i\) 。

容易发现，如果存在一个已经插入的砖块满足 \(a_i \le a_j+d\) ，则 \(i\) 可以插到 \(j\) 的前面

因为我们已经做了排序，记 \(j\) 原来上面的是 \(k\) ，所以 \(a_i\) 一定大于等于 \(a_k\) 从而可以插入。

于是每个 \(i\) 的方案数即为 \(1 + \sum_{j < i} [a_i \le a_j+d]\) ，前面的 \(1\) 表示直接添加到最后。

最后的方案数就是每个 \(i\)​ 的方案数乘起来。

可以发现，\(j\) 的个数随着 \(i\) 增长而增长，并且可以直接继承原有的答案，即我们可以线性维护这个 \(j\)

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(7e5 + 15))

int n, d, res = 1, l = 1, a[N];
const int mod = 1e9 + 9;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> d;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++)
    {
        while(l <= n && a[i] > a[l] + d) ++l;
        res = res * (i - l + 1) % mod;
    }
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/wm3agnr5