题干：
小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[i](1≤L[i]≤R[i]≤n)。 输出描述:
输出一行，包括两个整数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没被线段覆盖到。 题目大意：
给你1..n长度的总区间，外加m条线段(可能没有覆盖所有1~n的点)。问去掉哪一条线段 使得总区间未被覆盖的点最少。
输出那一条线段的编号，并且输出未被覆盖的点的个数。
解题报告：
因为是最后查询，求个差分，，，就行了。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
int l[MAX],r[MAX];
int d[MAX];
int a[MAX];
int sum[MAX];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1; i<=m; i++) {
scanf("%d %d",l+i,r+i);
d[l[i]]++;d[r[i]+1]--;
}
int zeros=0;
for(int i = 1; i<=n; i++) {
a[i] = a[i-1] + d[i];
if(a[i]==0) zeros++;
}
for(int i = 1; i<=n; i++) {
sum[i] = sum[i-1] + (a[i]==1);
}
int minn = 0x3f3f3f3f,id;
for(int i = m; i>=1; i--) {
if(sum[r[i]]-sum[l[i]-1] < minn) {
id = i;minn = sum[r[i]]-sum[l[i]-1];
}
}
printf("%d %d\n",id,minn+zeros);
return 0 ;
}
京公网安备 11010502036488号