题目链接：https://ac.nowcoder.com/acm/contest/1106/A
题目大意：
1.一条长1e9的线段，每个节点都可以上色。给出n次操作，每次操作将【l, r】区间内的节点染一次色。问最后染色次数的最大值是多少。
题解思路：
1.首先想到暴力，即遍历每个区间+1，对最终结果遍历一遍找最大值，但是1e9的长度一定超时。
2.解决超时就得缩小遍历长度，由于每个区间都是连续的，那么我们可以通过记录端点来达到记录区间同样的效果。即利用差分数组。A的差分数组B：第i位的值表示A的第i位与A的第i-1位的差值。当A数组【l,r】区间都增加k（k可为负）时，对于B，只需要改变B【l】+= k,B【r + 1】-= k。接下来讨论一下如何记录端点：对于每次给定的区间【l,r】，【l,r】区间内每一个数+1，即为B【l】+= 1,B【r + 1】-= 1。最后n次操作结束后，对B差分数组进行前缀和，即可得到染色最大次数。
3.由于1e9的区间长度，我们还需要进行离散化，我的思路是将出现的点升序排序并去重。对于每个点都映射为其排序后的下标。（用map实现）
代码如下：
1 #include<stdio.h> 2 #include<map> 3 #include<string.h> 4 #include<algorithm> 5 const int MAXN = 1e5 + 100; 6 using namespace std; 7 8 int a[MAXN], sum[MAXN], b[MAXN]; 9 map<int, int>mp; 10 11 struct Query 12 { 13 int l, r; 14 }q[MAXN / 2]; 15 16 int main() 17 { 18 int n, cnt = 0; 19 scanf("%d", &n); 20 for(int i = 1; i <= n; i ++) 21 { 22 int l, r; 23 scanf("%d%d", &l, &r); 24 q[i].l = l, q[i].r = r; 25 a[++ cnt] = l, a[++ cnt] = r; 26 } 27 sort(a + 1, a + 1 + cnt); 28 int len = (unique(a + 1, a + 1 + cnt) - (a + 1)); 29 for(int i = 1; i <= len; i ++) 30 mp[a[i]] = i; 31 for(int i = 1; i <= n; i ++) 32 { 33 b[mp[q[i].l]] ++; 34 b[mp[q[i].r] + 1] --; 35 } 36 int ans = 0; 37 for(int i = 1; i <= len; i ++) 38 { 39 sum[i] = sum[i - 1] + b[i]; 40 ans = max(ans, sum[i]); 41 } 42 printf("%d ", ans); 43 return 0; 44 }