发布于 

AT2300 Snuke Line

树状数组 题解 OI

题意

有一趟列车有 个车站, 从 0 到 M 编号. 有 N 种商品, 第 i 种只在编号 的车站出售. 一辆列车有一个预设好的系数 d, 从 0 出发, 只会在 d 的倍数车站停车. 对于 d 从 1 到 M 的列车, 求最多能买到多少种商品.

分析

对于每一种商品, 假设他的覆盖的区间长度为 , 那么如果 , 则这种商品一定能买到; 否则最多只能在一个点被买到. 那么对于每一个 , 的情况直接将区间按长度排序后计数; 将所有 的区间的答案加一, 总答案就是 这些位置上的答案之和 (由于需要用树状数组统计的区间最多只会被一个点查询, 所以能做到不重不漏).

复杂度分析: 由于 , 树状数组的复杂度是 , 所以总复杂度是

代码

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 3e5 + 10;
const int MAXM = 3e5 + 10;

template <typename value_t>
class fenwick {
public:
fenwick(int n) {
memset(c, 0, sizeof c);
this->n = n;
}

void add(int i, value_t x) {
while (i <= n) {
c[i] += x;
i += Lowbit(i);
}
}

value_t sum(int x) {
value_t sum = 0;
while (x > 0) {
sum += c[x];
x -= Lowbit(x);
}
return sum;
}

value_t sum(int x1, int x2) { return sum(x2) - sum(x1 - 1); }

private:
value_t c[MAXN];
int n;

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

struct interval {
int l, r;
} a[MAXM];
struct comp {
bool operator()(const interval& a, const interval& b) {
return a.r - a.l < b.r - b.l;
}
};

#include <cctype>
#include <cstdio>

inline int read() {
int X = 0, w = 0;
char ch = 0;
while (!isdigit(ch))
{
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch)) {
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}

int main() {
int n = read();
int m = read();
for (int i = 1; i <= n; i++) {
a[i].l = read();
a[i].r = read();
}
sort(a + 1, a + n + 1, comp());
fenwick<int>* tree = new fenwick<int>(m);
int cur = 1;
for (int d = 1; d <= m; d++) {
while (cur <= n && a[cur].r - a[cur].l + 1 < d) {
tree->add(a[cur].l, 1);
tree->add(a[cur].r + 1, -1);
cur++;
}
int ans = n - cur + 1;
for (int i = d; i <= m; i += d) {
ans += tree->sum(i);
}
cout << ans << endl;
}
}