题目链接:https://ac.nowcoder.com/acm/contest/297/C
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小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条线段后，没被覆盖到的点的个数。

输入

5 3
1 3
4 5
3 4
6 2
1 2
4 5

输出

3 0
2 4

说明

样例1:
若丢失第1条线段，1和2没被线段覆盖到。
若丢失第2条线段，5没被线段覆盖到。
若丢失第3条线段，所有点都被线段覆盖到了。
样例2:
若丢失第1条线段，1，2，3，6没被线段覆盖到。
若丢失第2条线段，3，4，5，6没被线段覆盖到。

解题思路

我们可以先求出那些没有被覆盖的长度，然后再求出那些覆盖长度为1的最长的那一段。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct edge {
    int l, r, t;
}e[100010];
int main()
{
    int n, k, m, sum, ans[100010];
    while (~scanf("%d%d", &n, &m))
    {
        k = sum = 0;
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d", &e[i].l, &e[i].r);
            ans[e[i].l]++;
            ans[e[i].r + 1]--;
        }
        for (int i = 1; i <= n; i++)
            ans[i] += ans[i - 1];
        for (int i = 1; i <= n; i++)
        {
            if (!ans[i])
                sum++;
            ans[i] = !(ans[i] - 1);
            ans[i] += ans[i - 1];
        }
        for (int i = 1; i < m; i++)
            if (ans[e[i].r] - ans[e[i].l - 1] <= ans[e[k].r] - ans[e[k].l - 1])
                k = i;
        printf("%d %d\n", k + 1, ans[e[k].r] - ans[e[k].l - 1] + sum);
    }
    return 0;
}