差分是一种算法。
先看AcWing上的一道题目↓
贝茜对她最近在农场周围造成的一切恶作剧感到抱歉，她同意帮助农夫约翰把一批新到的干草捆堆起来。
开始时，共有 N 个空干草堆，编号 1?N。
约翰给贝茜下达了 K 个指令，每条指令的格式为 A B，这意味着贝茜要在 A..B范围内的每个干草堆的顶部添加一个新的干草捆。
例如，如果贝茜收到指令 10 13，则她应在干草堆 10,11,12,13中各添加一个干草捆。
在贝茜完成了所有指令后，约翰想知道 N个干草堆的中值高度——也就是说，如果干草堆按照高度从小到大排列，位于中间的干草堆的高度。
方便起见，N 一定是奇数，所以中间堆是唯一的。
请帮助贝茜确定约翰问题的答案。
输入格式：
第一行包含 N 和 K。
接下来 K 行，每行包含两个整数 A,B用来描述一个指令。
输出格式：
输出完成所有指令后，N 个干草堆的中值高度。
数据范围：
1≤N≤1e6,
1≤K≤25000，
1≤A≤B≤N，
输入样例：
7 4
5 5
2 4
4 6
3 5输出样例：
1错误/超时代码-------复杂度O(n*m)
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stack>
#define N 1000010
using namespace std;
int main()
{int n,k,j,i,a,b;int num[N]={0};cin >> n >> k;while (k--){cin >> a >> b;for (i = a; i <= b; i++){num[i]++;}}sort(num, num + n + 1);cout << num[n / 2 + 1];return 0;
}差分做法
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N],b[N];
int n,k;
void insert(int l,int r)//建立差分数组
{b[l] ++;b[r + 1] --;
}
int main()
{cin >> n >> k;while(k --){int l,r;cin >> l >> r;insert(l,r);}for(int i = 1; i <= n; i ++)a[i] = a[i - 1] + b[i];sort(a + 1, a + 1 + n);cout << a[(n + 1) / 2] << endl;return 0;
}