题目来源：Codeforces 1932F(Div.3)

题目大意

您需要从 $1$ 到 $n$ 中选择几个整数点，使得在给定的区间中，没有一个区间覆盖两个或两个以上的所选点，而有尽可能多的区间覆盖一个所选点。

I/O 限制与约定

第一行包含两个整数 $n$ 和 $m$ $(1≤n≤10^6，1≤m≤2⋅10^5)$.

接下来的$m$行中，第 $i$ 行包含一对整数 $l_i$ 和 $r_i$ $(1≤l_i≤r_i≤n)$表示一个区间.

样例

输入

15 6
2 10
3 5
2 4
7 7
8 12
11 11

输出

5

题目解析

不水了，要的是干货。

这道题看一眼数据范围可知为$O(n)$做法。

即想到线性DP做法：

记$dp_i$为考虑了前$i$个位置，最大能选多少区间

$tp_i$为覆盖$i$的所有区间中左端点最靠左的位置

$w_i$为位置$i$被多少个区间同时覆盖

有：

$$ dp_i = max\left\{\begin{matrix} dp_{i-1} \\ dp_{tp_i-1} + w_i \end{matrix}\right. $$

经典线性dp式：

  • 要么这个不选，直接从上一个位置转移
  • 要么这个选，从能覆盖自己的所有区间中左端点最靠左的上一个位置转移（因为这是最靠右的合法状态，显然也是最优的）

显然右端点是不用考虑的，因为如果后面的点选进了自己右边的区间，则一定存在至少一个区间同时包含两个点，而dp的第二种转移可以保证最后一个点选的时候一定是合法的。

考虑预处理$tp$和$w$：

  1. $w$显然可以用差分求，也可以排序扫描一边维护，这里选前者；
  2. tp考虑单调性，当$i$增大的时候，$tp_i$单调不降，反证法可易证。那么就可以用双指针来维护。也可以直接取min（参考第二份代码）

核心代码部分：

cin>>n>>m;
for(int i=0;i<=n;i++){
    dp[i]=a[i]=0;
    tp[i]=i;
}
for(int i=0;i<m;i++){
    cin>>sect[i].first>>sect[i].second;
    a[sect[i].first]++;
    a[sect[i].second+1]--;
}
for(int i=1;i<=n;i++)a[i] += a[i-1];
sort(sect,sect+m);
int l=0,r=1;
while(l<m && r<=n){
    while(sect[l].first>r && r<=n)r++;
    while(sect[l].second<r && l<m)l++;
    if(sect[l].second<r)break;
    tp[r] = sect[l].first;
    r++;
}
for(int i=1;i<=n;i++){
    dp[i] = max(dp[i-1],dp[tp[i]-1]+a[i]);
}
cout<<dp[n]<<endl;

但是这份代码挂了，还有一份过了的：

cin>>n>>m;
for(int i=0;i<=n+2;i++){
    dp[i]=a[i]=0;
    tp[i]=i;
}
for(int i=0;i<m;i++){
    int l,r;
    cin>>l>>r;
    tp[r] = min(tp[r],l);
    a[l]++,a[r+1]--;
}
for(int i=1;i<=n;i++)a[i] += a[i-1];
for(int i=n;i>=1;i--){
    tp[i] = min(tp[i],tp[i+1]);
}
for(int i=1;i<=n;i++){
    dp[i] = max(dp[i-1],dp[tp[i]-1]+a[i]);
}
cout<<dp[n]<<endl;