前言经过不少差分题的拷打也是渐入佳境理解不少以前以为差分只是简单的让每个数能够更轻松的一起加上某个数然后做题没什么接触到这类题型没想到一做起来差分类题目居然如此有意思。温馨提示若前缀和不知为何物可先去了解。那我直接从题开说题目值周链接https://ac.nowcoder.com/acm/problem/24636来源牛客网JC内长度为L的马路上有一些值周同学每两个相邻的同学之间的间隔都是1米。我们可以把马路看成一个数轴马路的一端在数轴0的位置另一端在L的位置数轴上的每个整数点即0,1,2,…L都有一个值周同学。 由于水宝宝有用一些区间来和ssy搞事情所以为了避免这种事走漏风声水宝宝要踹走一些区域的人。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数区域之间可能有重合的部分。现在要把这些区域中的人包括区域端点处的两个人赶走。你的任务是计算将这些人都赶走后马路上还有多少个人。输入描述:第一行有2个整数L和ML代表马路的长度M代表区域的数目L和M之间用一个空格隔开。 接下来的M行每行包含2个不同的整数用一个空格隔开表示一个区域的起始点和终止点的坐标输出描述:1个整数表示马路上剩余的人的数目。示例1输入复制500 3 150 300 100 200 470 471500 3 150 300 100 200 470 471输出复制298298说明对于所有的数据1≤L≤100000000 对于10%的数据1M100 对于20%的数据1M1000 对于50%的数据1M100000 对于100%的数据1M1000000其实相比这题大家更熟悉的应该是校门外的树这题就是它的加强版可能很多人像我以前一样做校门外的树时咱直接暴力但这里数据加大了范围明显不能暴力那这里就不得不提到我们的差分了。首先我们可以这样想象把这题的当做一个超大数轴然后我们需要在里边把需要将人赶走的区域给记录下来然后整个数轴减去这些区域就是我们所求马路上还留有多少人的解。但是这些区域还有重叠这让我咋整让我们想想差分的作用让一个区域更好的同时加上某个数那我们不妨让给定区域做上标记a[L]到a[R]都加上某个数如何加上当然用到我们的前缀和了在a[R1]-去标记数即可结束标记任务而区域内如果有重叠的话可以那么重叠区域的每个标记会大于未重叠区域的每个标记我们可以视为大于等于标记数的区域为题目所说要赶走的人最后将总人数减去符合标记条件的人答案则为我们所要求的马路上还留下的人。附上咱的AC代码#includebits/stdc.h using namespace std; #define int long long int a[100005000]; signed main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int l,m; int sum10,sum20; cin l m; a[0]1; for(int i1;im;i) { int l1,l2; cin l1 l2; a[l1]1; a[l21]-1; } for(int i0;il;i) { sum1a[i]; if(sum1) { sum2; } } cout sum2; return 0; }这边用sum1当作前缀和因为你要是再开个数组的话没啥区别然后我们将所有的数标记为1也就是a[0]1然后前缀和在部分区域的头到尾做1记号使得前缀和时这部分区域大于1而等于1的部分则为我们需要的个数我们可以想象一下我们将一个大的数轴上的每一位都变为1了然后输入的区域让我们的数轴上的这片区域再加上1如果有重叠那就是再加上1那么始终保持为1的区域就是我们需要的答案。总结还有几题核心也是打标记多重叠有的是找标记后前缀和为某一值的个数有的是找重叠次数最多的地方具体如何我还未掌握那么清楚但我觉得这题对于我这样的新手来说理解好真能受益匪浅。