P10845 [EGOI 2024] Bouquet / 花束制作

Day 1 Problem B. 题面译自 [EGOI2024 bouquet](https://wiki.egoi2024.nl/tasks/bouquet/statement-isc.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。

参观了世界上最大的花园之一库肯霍夫后，Lieke 非常喜欢花，因此她决定收集一些路边生长的郁金香来制作一个漂亮的花束。然而，在收集花朵时，她必须遵守荷兰严格的郁金香保护法的一些规定。 沿着道路从左到右有 $N$ 株郁金香，编号从 $0$ 到 $N - 1$。郁金香保护法为郁金香 $i$ 分配了两个整数，$l_i$ 和 $r_i$。如果郁金香 $i$ 被包含在花束中，则郁金香 $i$ 左边紧邻的 $l_i$ 株郁金香和右边紧邻的 $r_i$ 株郁金香不能包含在花束中。注意，如果郁金香 $i$ 左边的郁金香少于 $l_i$ 株，或者右边的郁金香少于 $r_i$ 株，那么该侧所有的郁金香仍然不能包含在花束中（允许溢出）。 Lieke 想知道如果她最佳地选择花朵，最多能摘取多少株郁金香。帮她找到这个问题的答案，制作一个漂亮的花束吧！

输入的第一行包含一个整数 $N$，表示沿路生长的郁金香数量。 接下来的 $N$ 行描述了郁金香保护法的信息：第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，表示郁金香 $i$ 的保护限制。

输出一个整数，表示 Lieke 在遵守保护法的情况下可以摘取的最大郁金香数量。

**样例解释** 在第一个样例中，如果 Lieke 摘取郁金香 $0$，她不能摘取右边的两朵郁金香。摘取郁金香 $1$ 并不禁止她摘取郁金香 $2$，但郁金香 $2$ 禁止她摘取郁金香 $1$，因此她不能同时摘取它们。所以，Lieke 可以摘取的最大花朵数量是 $1$。 在第二个样例中，Lieke 可以摘取的郁金香数量最多是 $3$，获得此结果的方式如图所示。其他摘取郁金香的方式会导致更小的答案。  在第三个样例中，通过摘取郁金香 $0, 1, 3$ 和 $6$ 可以获得最多的 $4$ 朵郁金香。 --- **数据范围** 对于全部数据，$1\le N\le 2\times 10^5$，$0\le l_i,r_i\le N$。 - 子任务一（$8$ 分）：对于任意 $(i,j)$，$l_i=r_i=l_j=r_j$。 - 子任务二（$16$ 分）：$r_i=0$。 - 子任务三（$28$ 分）：$N\le 1000$。 - 子任务四（$18$ 分）：$l_i,r_i\le 2$。 - 子任务五（$30$ 分）：无特殊限制。 注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。