「Bzoj 1651」「Usaco2006 Feb」Stall Reservations 专用牛棚(差分序列)

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)$单点查询(这里可以用数据结构维护，但是本题不需要)

#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;
}