一道贪心的简单题，插入无非就是两种情况：

• 在开灯的区间内插入，应该让插入的元素尽可能地靠后
• 在关灯的区间内插入，应该让插入的元素尽可能地靠前

注意：

• g1 和 g2 的含义，g1 是指不落单（最后两次操作刚好完成一次开关）的后缀和，而 g2 则指的是会落单的后缀和
• i+1 和 i+2 的选择，应该在纸上画图而不是凭空乱想
• 因为 n 的奇偶性不知道，所以 ans 的初始值为末尾两个数的最大值

区间前缀和的经典问题，离散化后求前缀和（值即为覆盖的条数），用离散化之前的值直接计算即可。

注意：

• 离散化后的值有2𝑛个，sum 数组和 b 数组要开 n 的两倍
• 只需要对 L 和 R+1 进行离散化就可以了，但记住取 lower_bound 的时候也要取 R+1 的排名，所以算前缀和的时候是 --sum[y] 而不是 --sum[y+1]
• 相邻两个端点的值不相同，在最后计算 ans 的时候只能算一边！

DP 经典题目，枚举第一个正整数就得到了区间长度，再暴力枚举区间最后一个值，𝑂(𝑛2)的 DP 就搞定了。

在 DP 的时候，可以从 i 优化到 j 而不需要倒着循环来 DP， f[n+1] 就是答案。

注意：f[i] 的初值为 1！

无向图求割边的模板题，缩点后建立新图 DP 一下就可以了。

对于每条割边，答案都可以为 dp[x]+1+dp[y]，然后 dp[x]=dp[y]+1（合并节点 x 和 y）。

只需要注意 e1、e2 的区别和 h1、h2 的区别就行了。