A HUGE TOWER

· · 题解

这题只要排序加二分就行，思路很简单，先划重点：

如果按照从小到大的顺序向塔中插入砖。假设当前插入的砖（也就是最长的砖）在最下面，一定满足。

假若不在最下面，设它上面的长为 a，下面的长为 b，a + d \le x 把最长砖抽去，因为 x + d \le b，且 x \ge b，所以 a + d \le b，原来一定也是合法方案。

所以找到 a_i - d \le x 的砖的个数，加上 1，也就是这块砖能放的方案数。累乘起来就是答案了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 700010
#define GET (ch>='0'&&ch<='9')
#define P 1000000009
#define LL long long
using namespace std;
int n,d;
int a[MAXN];
LL ans=1;
void in(int &x)
{
    char ch=getchar();x=0;
    while (!GET)    ch=getchar();
    while (GET) x=x*10+ch-'0',ch=getchar();
}
int main()
{
    in(n);in(d);int id;
    for (int i=1;i<=n;i++)  in(a[i]);
    sort(a+1,a+n+1);//快排
    for (int i=1;i<=n;i++)  id=lower_bound(a+1,a+i,a[i]-d)-a,ans=ans*(i-id+1)%P;//累乘
    printf("%lld\n",ans);
    return 0;
}