本文共 1743 字，大约阅读时间需要 5 分钟。

链接：

来源：牛客网

题目描述

小w有m条线段，编号为1到m。

用这些线段覆盖数轴上的n个点，编号为1到n。

第i条线段覆盖数轴上的区间是L[i]，R[i]。

覆盖的区间可能会有重叠，而且不保证m条线段一定能覆盖所有n个点。

现在小w不小心丢失了一条线段，请问丢失哪条线段，使数轴上没被覆盖到的点的个数尽可能少，请输出丢失的线段的编号和没被覆盖到的点的个数。如果有多条线段符合要求，请输出编号最大线段的编号（编号为1到m）。

输入描述:

第一行包括两个正整数n，m(1≤n，m≤10^5)。 接下来m行，每行包括两个正整数L[i]，R。 输出描述: 输出一行，包括两个整数a b。 a表示丢失的线段的编号。 b表示丢失了第a条线段后，没被覆盖到的点的个数。 示例1 输入 复制 5 3 1 3 4 5 3 4 输出 复制 3 0 说明 若丢失第1条线段，1和2没被线段覆盖到。 若丢失第2条线段，5没被线段覆盖到。 若丢失第3条线段，所有点都被线段覆盖到了。 示例2 输入 复制 6 2 1 2 4 5 输出 复制 2 4 说明 若丢失第1条线段，1，2，3，6没被线段覆盖到。 若丢失第2条线段，3，4，5，6没被线段覆盖到。

牛客竞赛上的一道题目。。没有接触过差分的概念。。本来想用暴力，一秒的时间，1e5的数据，肯定不行。看了看题解，有的用线段树，nlogn的时间复杂度，可能也可以。但是用差分，只有O（n）的时间复杂度。在处理区间加减或者求和操作的时候，真的很方便

1.定义： 对于已知有n个元素的离线数列d，我们可以建立记录它每项与前一项差值的差分数组f：显然，f[1]=d[1]-0=d[1];对于整数i∈[2,n]，我们让f[i]=d[i]-d[i-1]。

2.简单性质：

(1)计算数列各项的值：观察d[2]=f[1]+f[2]=d[1]+d[2]-d[1]=d[2]可知，数列第i项的值是可以用差分数组的前i项的和计算的，即d[i]=f[i]的前缀和。 (2)计算数列每一项的前缀和：第i项的前缀和即为数列前i项的和，那么推导可知 即可用差分数组求出数列前缀和； 3.用途： (1)快速处理区间加减操作： 假如现在对数列中区间[L,R]上的数加上x，我们通过性质(1)知道，第一个受影响的差分数组中的元素为f[L],即令f[L]+=x，那么后面数列元素在计算过程中都会加上x；最后一个受影响的差分数组中的元素为f[R],所以令f[R+1]-=x，即可保证不会影响到R以后数列元素的计算。这样我们不必对区间内每一个数进行处理，只需处理两个差分后的数即可；

(2)询问区间和问题：

由性质(2)我们可以计算出数列各项的前缀和数组sum各项的值；那么显然，区间[L,R]的和即为ans=sum[R]-sum[L-1];

这是差分的定义以及原理。。

这道题目除了差分，还有另一个，就是book数组，这个数组就是记录这个点之前有多少个点被覆盖了，到时候只要区间两端点的book值相减就是这个区间的覆盖点的个数。 代码如下：

#include
   
    using namespace std;const int maxx=1e5+10;int vis[maxx];int book[maxx];int n,m;struct node{	int l;	int r;}p[maxx];int main(){	cin>>n>>m;	for(int i=0;i
    
     >p[i].l>>p[i].r;		int l=p[i].l;		int r=p[i].r;		vis[l]++;		vis[r+1]--;	}//差分	for(int i=1;i<=n;i++)	{		vis[i]+=vis[i-1];//还原	}	int ans=0;	for(int i=1;i<=n;i++)	{		book[i]+=book[i-1];		if(vis[i]==0) ans++;//没有覆盖的点 		if(vis[i]==1) book[i]++;//只被一条线段覆盖的点 	}	int x=n,id=1;	for(int i=0;i
    
   

努力加油a啊，(^o)/~

转载地址：http://tuxvi.baihongyu.com/