难度：省选/NOI-

题目描述

        农夫约翰决定给站在一条线上的N(1 ≤ N ≤ 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。
        于是约翰拍摄了M(1 ≤ M ≤ 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号ai 到 bi的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。
        在拍完照片后，约翰发现了一个有趣的事情：每张照片中都有且仅有一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

输入输出格式

输入格式：

        第一行两个整数：N和M。
        第2到M+1行，两个整数，ai和bi。

输出格式：

        共一行，牛群中斑点奶牛的最大数目。如果无解输出-1。

输入输出样例

Sample input

5 3
1 4
2 5
3 4

Sample output

1

题解

        这其实是差分约束的题目，也可以用DP做。
        规定r(i)为包含i这个点的所有区间的左端点最小值-1，l(i)表示在i左侧的所有区间左端点的最大值。这两个量是后面DP的基础，可以用两遍for循环解决。初始化l(i)=0，r(i)=i-1，并在读入数据时预处理。有方程：

        这个思路很重要，可以用于一些区间DP的预处理。
        令dp(i)为1~i的奶牛最大数量并且i处必须有奶牛，仅有i=n+1时为i处没有奶牛的值。有状态转移方程：

        如果l(i)>r(i)则dp(i)=-inf。最终答案即为dp(n+1)，如果为负输出-1。
        注意到l和r都是单调递增的，可以用单调队列优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstdio>

#define N 200000+1
#define inf 0x7ffffff
using namespace std;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '0' || e > '9')e = getchar();
    while (e >= '0' && e <= '9')s = s * 10 + e - '0', e = getchar();
    return s;
}

int deq[N + 100], fr = 0, ba = -1;
int n, m, l[N] = {0}, r[N], dp[N];
int x, y;

inline void Push(int x) {//单调队列
    while (ba >= fr && dp[deq[ba]] < dp[x])ba--;
    deq[++ba] = x;
}

inline int Front(int x) {
    while (deq[fr] < x)fr++;
    return deq[fr];
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n + 1; i++)r[i] = i - 1;
    for (int i = 1; i <= m; i++) {
        x = read(), y = read();
        l[y + 1] = max(l[y + 1], x), r[y] = min(r[y], x - 1);
    }
    for (int i = 2; i <= n + 1; i++)l[i] = max(l[i], l[i - 1]);
    for (int i = n; i >= 1; i--)r[i] = min(r[i], r[i + 1]);
    dp[0] = 0;
    int key = 0;
    for (int i = 1; i <= n + 1; i++) {
        for (int k = key; k <= r[i]; k++)Push(k);
        key = r[i] + 1;
        if (l[i] > r[i])dp[i] = -inf;
        else if (i <= n)dp[i] = dp[Front(l[i])] + 1;
        else dp[i] = dp[Front(l[i])];
    }
    if (dp[n + 1] < 0)cout << -1;
    else cout << dp[n + 1];
    return 0;
}

        LYH注：这法真是妙，深深感受到自己的渺小