题目链接：传送门

Description

给你一个长度为N的排好序的数列S和两个数A、B，你需要将这个数列分成两组，第一组中任意两个数的差要大于等于A，第二组中任意两个数的差要大于等于B，求方案数(Mod 1e9 + 7)

Hint

1 <= N <= 1e5 1 <= A, B, Si <= 1e18

Sample Input

5 3 7 1 3 6 9 12

Sample Output

5

Solution

很容易想到一个Dp，设Dp1[i][j]表示第i个数被分到第1组中，另外一组最后一个数的位置为j时的方案数,Dp2[i][j]的定义类似。 那么有

TeX parse error: Couldn't find closing ']' for argument to \\

，

TeX parse error: Undefined control sequence \[

但是这是N^2的Dp。 我们可以用树状数组优化，只是要注意清空的时候不能用memset，会超时。 由于每次加入树状数组中的元素不多，直接把修改过的元素记录下来直接赋0即可

Summary

这道题调了一下午，最后是写了个暴力写到一半才发现的错误。代码能力要提高，然后memset不能乱用

Code

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
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int Maxn = 100000 + 100, Mod = 1e9 + 7;
int N;
LL A, B;
LL S[Maxn];
int Sum1[Maxn], Sum2[Maxn];
int Cnt1, Cnt2, Vis1[Maxn * 10], Vis2[Maxn * 10];

inline int lowbit (int x) {return x & (-x);}

inline void Update1 (int x, LL d)
{
    ++x;
    while (x <= (N + 1))
    {
        (Sum1[x] += d) %= Mod;
        Vis1[++Cnt1] = x;
        x += lowbit(x);
    }
}

inline void Update2 (int x, int d)
{
    ++x;
    while (x <= (N + 1))
    {
        (Sum2[x] += d) %= Mod;
        Vis2[++Cnt2] = x;
        x += lowbit(x);
    }
}

inline int Query1 (int x)
{
    int Ans = 0;
    ++x;
    while (x)
    {
        (Ans += Sum1[x]) %= Mod;
        x -= lowbit(x);
    }
    return Ans;
}

inline int Query2 (int x)
{
    int Ans = 0;
    ++x;
    while (x)
    {
        (Ans += Sum2[x]) %= Mod;
        x -= lowbit(x);
    }
    return Ans;
}

int main()
{
#ifdef hk_cnyali
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
#endif
    scanf("%d%lld%lld", &N, &A, &B);
    for (int i = 1; i <= N; ++i) scanf("%lld", &S[i]);
    S[0] = -0x3f3f3f3f3f3f3f3f;
    Update1(0, 1);
    Update2(0, 1);
    for (int i = 1; i < N; ++i)
    {
        int l = 0, r = i, Ans1 = 0, Ans2 = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (S[mid] <= S[i + 1] - B) l = mid + 1, Ans1 = mid;
            else r = mid - 1;
        }
        l = 0, r = i;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (S[mid] <= S[i + 1] - A) l = mid + 1, Ans2 = mid;
            else r = mid - 1;
        }
        //cout<<i + 1<<" "<<Ans1<<" "<<Ans2<<endl;
        int SUM1 = Query1(Ans1);
        int SUM2 = Query2(Ans2);
        if (S[i + 1] - S[i] < A)
            while (Cnt1)
                Sum1[Vis1[Cnt1--]] = 0;
            //memset(Sum1, 0, sizeof(Sum1));
        if (S[i + 1] - S[i] < B)
            while (Cnt2)
                Sum2[Vis2[Cnt2--]] = 0;
            //memset(Sum2, 0, sizeof(Sum2));
        Update2(i, SUM1);
        Update1(i, SUM2);
        //Ans += Query1(i + 1) + Query2(i + 1);
    }
    printf("%d\n", (Query1(N) + Query2(N)) % Mod);
    return 0;
}