现在能写了。
考虑 dp 做法。
在读入数据之后，我们下意识地对每条线段 \((l_i,r_i)\) 进行排序。随后经过尝试，我们可以排除以猫的编号为阶段进行 dp 的方案。因此我们选择以位置为阶段进行 dp。
设 \(dp(i,0/1)\) 表示位置 \(i\) 是否投喂能获得的最大价值。有转移方程（注意 \(dp(i,1)\) 进行了一步推导）：
\[\begin{cases} dp(i,0)=\max(dp(i-1,0),dp(i-1,1))\\ dp(i,1)=\max(dp(lp_i-1,0),dp(lp_i-1,1))+cnt=dp(lp_i,0)+cnt \end{cases}\]其中，\(lp_i\) 表示所有覆盖位置 \(i\) 的线段中，左端点编号 \(l\) 的最小值；如果没有线段覆盖，\(lp_i=i\)。\(cnt\) 表示覆盖位置 \(i\) 的线段条数。
\(lp\) 可用双指针进行处理，\(cnt\) 可用差分进行处理。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=1e6+10;
int t,n,m,dp[MAXN][2],diff[MAXN],lp[MAXN];
pair<int,int>cat[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=0;i<=n+5;i++)dp[i][0]=dp[i][1]=diff[i]=0;
for(int i=1;i<=m;i++)cin>>cat[i].first>>cat[i].second;
sort(cat+1,cat+m+1);
for(int i=1;i<=m;i++)
{
diff[cat[i].first]++;
diff[cat[i].second+1]--;
}
int j=1;
for(int i=1;i<=n;i++)
{
if(i<cat[j].first)lp[i]=i;
if(cat[j].first<=i&&i<=cat[j].second)lp[i]=cat[j].first;
while(cat[j].second<i&&j<=m)j++;
if(j>m)lp[i]=i;
else lp[i]=cat[j].first;
}
int cnt=0;
for(int i=1;i<=n;i++)
{
cnt+=diff[i];
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=dp[lp[i]][0]+cnt;
}
cout<<max(dp[n][0],dp[n][1])<<'\n';
}
return 0;
}