Bzoj 1651(差分序列)

BZOJ 1651
Luogu 2859
from: USACO 2006 Feb Sliver(USACO刷题第4题)

首先需要发现的是,覆盖次数最多的点就是答案
然后可以用线段树求解了
但是这里要介绍一个很有用的东西,差分序列
差分序列$f$记录$a[i]-a[i-1]$的值,$a$为原序列
那么根据定义可以发现差分序列的前缀和就是原序列的数
那么输入$a,b$, 我们让$f[a]+1, f[b+1]-1$就可以构造出差分序列
这样可以实现$O(1)$区间修改,$O(n)$单点查询(这里可以用数据结构维护,但是本题不需要)

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXV = 1000000 + 5;
int n, f[MAXV];
void clear() {
ms(f, 0);
}
void init() {
clear();
for (int i=1;i<=n;i++) {
int a, b;
scanf("%d%d", &a, &b);
f[a]++, f[b+1]--;
}
}
void solve() {
int sum = 0, ans = 0;
for (int i=1;i<=1000001;i++) {
sum += f[i];
ans = max(ans, sum);
}
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d", &n)==1&&n) init(), solve();
return 0;
}

------ 本文结束 ------