前缀和 差分
值周
https://ac.nowcoder.com/acm/problem/24636
和校门口的树是一样的。只不过校门口的树数据太水了。
对于，前缀和 + 差分可以满足需求，再大就需要离散化，这个离散化还是稍有难度的（暂时先不写了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e8 + 7;
const ll mod = 1e9 + 7;
inline ll read() {
ll s = 0, f = 1;
char ch;
do {
ch = getchar();
if (ch == '-') f = -1;
} while (ch < 48 || ch > 57);
while (ch >= 48 && ch <= 57)
s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
ll vis[N];
int main() {
ll n = read(), m = read(), a, b, ans=0;
while (m--) {
a = read(), b = read();
--vis[a], ++vis[b + 1];
}
for (int i = 1; i <= n; ++i) vis[i] += vis[i - 1];
for (int i = 0; i <= n; ++i) ans += !vis[i];
printf("%lld\n", ans);
return 0;
} 这道题的收获其实是：1e8的规模可以a，但是巨量的数据吞吐导致cin即使关闭了与C的关联性，依然会TLE
这题也可以使用贪心的思维，对线段进行排序，可以到一样的结果
对离散化的概括
算法竞赛之路 文章被收录于专栏
整理、记录算法竞赛的好题
查看30道真题和解析