首先有简单的 \(O(n^3)\) \(dp\)，可以决策单调性优化到 \(O(n^2)\)，还可以进一步利用不同差分数 \(O(\sqrt n)\) 优化到 \(O(n\sqrt n\log n)\)，不过这个方向已经没什么前途了
考虑线性规划形式，设 \(a_{1\sim n}\) 表示第 \(i\) 天是否开宴，\(b_{1\sim m}\) 表示是否交到第 \(i\) 个朋友，这里要求整数线性规划：
由于系数矩阵是幺模矩阵 \((\text{unimodular matrix})\)，因此可以放宽成实数的线性规划，这样就可以对偶了，去掉无用的变量之后，剩下的设变量 \(x_{1\sim n},y_{1\sim m},z_{1\sim m},T\)：
可以发现对偶问题的系数矩阵依然是幺模矩阵，所以一定存在最优的整数解，考虑其组合意义，由于 \(y_i+z_i\) 一定取 \(1\) 最优，因此可以看作对于每个宴会，可以选择将区间 \([l_i,r_i]\) 中的 \(x_i+T\) 的限制增大 \(1\)，或者将目标函数增大 \(1\)
发现 \(T\) 这个变量能放宽所有 \(x\) 的限制，因此每个宴会产生的限制都一定是让 \(T\) 变化，也就是说最优情况下 \(x_i=0\)，那么问题变成从 \(m\) 个区间中选出一个子集 \(S\)，最小化 \(|S|+k\max\)，其中 \(\max\) 是所有 \(i\notin S\) 的区间覆盖之后所有位置的最大值
这是一个斜率优化的形式，考虑对每个 \(\max\) 算一个选择的区间数的最大值，即要求每个位置被覆盖的次数不超过 \(\max\) 次最多能选出多少个区间，可以发现这个问题有决策单调性，因为 \(i\) 的答案可以视作 \(i-1\) 的答案加上使最大值取到 \(i\) 的区间，所以直接贪心，用线段树维护，每次跑一个最大不交区间即可
点击查看代码
#include<bits/stdc++.h>
#define inf (int)1e9
#define N 1000005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
int n,m,dp[N];vector<int>vec[N];
namespace SGT{
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
pair<int,int>Max[N<<2],Min[N<<2];int Tag[N<<2];
void Pushup(int k){
Max[k]=max(Max[ls],Max[rs]);
Min[k]=min(Min[ls],Min[rs]);
}
void Update(int k,int v){Max[k].first+=v;Tag[k]+=v;}
void Pushdown(int k){Update(ls,Tag[k]);Update(rs,Tag[k]);Tag[k]=0;}
void Build(int k,int l,int r){
if(l==r){
sort(vec[l].begin(),vec[l].end(),[](int x,int y){return x>y;});
Max[k].first=0;Min[k].first=vec[l].empty()?inf:vec[l].back();
Max[k].second=Min[k].second=l;
return;
}
Build(ls,l,mid);Build(rs,mid+1,r);Pushup(k);
}
void Modify(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return Update(k,1);
if(Tag[k])Pushdown(k);
if(x<=mid)Modify(ls,l,mid,x,y);
if(mid<y)Modify(rs,mid+1,r,x,y);
Pushup(k);
}
void Pop(int k,int l,int r,int x){
if(l==r){
vec[l].pop_back();
Min[k].first=(vec[l].empty()?inf:vec[l].back());
return;
}
if(Tag[k])Pushdown(k);
x<=mid?Pop(ls,l,mid,x):Pop(rs,mid+1,r,x);Pushup(k);
}
pair<int,int>Query(int k,int l,int r,int x,int y){
if(l>y||r<x||x>y)return make_pair(inf,0);
if(l>=x&&r<=y)return Min[k];
if(Tag[k])Pushdown(k);
if(y<=mid)return Query(ls,l,mid,x,y);
if(mid<x)return Query(rs,mid+1,r,x,y);
return min(Query(ls,l,mid,x,y),Query(rs,mid+1,r,x,y));
}
}
using namespace SGT;
signed main(){
n=read();m=read();dp[0]=m;
for(int i=1,l,r;i<=m;i++)l=read(),r=read(),vec[l].emplace_back(r);
Build(1,1,n);
for(int i=1,sum=0;i<=m;i++){
int cur=1;
while(true){
pair<int,int>nxt=Query(1,1,n,cur,n);
if(nxt.first==inf)break;
Modify(1,1,n,nxt.second,nxt.first);
Pop(1,1,n,nxt.second);
sum++;cur=Max[1].second+1;
}
dp[i]=m-sum;
}
for(int i=1,j=m;i<=n;i++){
while(j>=1&&dp[j-1]<=dp[j]+i)j--;
printf("%d\n",dp[j]+i*j);
}
return 0;
}