长颈鹿烩面
solution
直接考虑原问题是个 dp，可以用数据结构优化 dp 来 \(O(tn)\) 求出 \([1,t]\) 中每个 \(k\) 的答案。也可以 wqs 二分 \(O(n\log n)\) 得到单点的答案。（实际上 dp 的时候还带并查集的复杂度）
注意到 wqs 二分的斜率超过 \(T\) 时原序列会分成不超过 \(O(\dfrac{n}{T})\) 段，否则答案小于 0，不优。
这样就可以根号分治，\(O(n\sqrt n)\) 解决这个问题。
但是数据是 \(10^6\) 的，上面的做法很难进一步推进。
这时候把原问题写成线性规划的形式。
设每个人被交了 \(a_i\) 次朋友，\(a_i\in \{0,1\}\)。每天举办了 \(bi\) 次宴会，\(b_i\in \{0,1\}\)。
则要最大化 \(\sum\limits_{i=1}^m a_i\)，同时满足 \(a_i\leq \sum\limits_{j=l_i}^{r_i} b_j,\sum\limits_{i=1}^n b_i\leq k\) 以及上面 \(a,b\) 取值的限制（这时把 \(a\) 的限制写成 \(0\leq a_i\leq 1\)，把 \(b\) 的限制写成 \(0\leq b_i\)，没有上界是因为 \(b\) 大于 1 不优）。
注意此时 \(a,b\) 都是离散的，但是根据一些线性代数理论（全幺模矩阵），\(a,b\) 取非负实数不改变答案。
于是就可以写成标准的线性规划形式。
再对偶一下就得到：要最小化 \(kt+\sum y_i\)，同时满足 \(x_i+y_i\ge 1\) 和 \(\forall i\in [1,n],t-\sum\limits_{p\in [l_i,r_i]}x_p \ge 0\)。其中 \(x_i,y_i,t\) 是非负变量。
理解一下这堆东西，就是：选出来一些区间覆盖对应位置，要求每个位置被覆盖不超过 \(t\) 次，最小化 \(kt\) 加上没有选的区间数量。
可以发现，对于每个 \([1,m]\) 中的 \(t\)，都求出最多能选出多少个区间，就可以很容易地得到对每个 \(k\) 的答案。
这个东西比原问题好做的地方在于，对于 \(t\) 选出的区间，\(t+1\) 一定也会选。
线段树维护每个位置被覆盖的次数，以及被覆盖次数最大值最靠右的位置，每个位置为左端点还没有选的区间的最小右端点。
这样从小到大枚举 \(t\) 就可以 \(O(n\log n)\) 求出每个 \(t\) 的答案。
code
#include<bits/stdc++.h>
using namespace std;
constexpr int inf=0x3f3f3f3f;
struct segment{
vector<int> maxx,tag,minx,wh,pos;
void build(int u,int l,int r){
minx[u]=inf;
maxx[u]=0,pos[u]=r;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
segment(int sz){
minx=wh=maxx=pos=tag=vector<int>(sz*4+10);
build(1,1,sz);
}
void spread(int u,int val){
maxx[u]+=val;
tag[u]+=val;
}
void dn(int u){
if(!tag[u]) return ;
spread(u<<1,tag[u]);
spread(u<<1|1,tag[u]);
tag[u]=0;
}
void modify(int u,int l,int r,int pos,int val){
if(l==r){
minx[u]=val;
wh[u]=l;
return ;
}
dn(u);
int mid=(l+r)>>1;
if(pos<=mid) modify(u<<1,l,mid,pos,val);
else modify(u<<1|1,mid+1,r,pos,val);
minx[u]=minx[u<<1],wh[u]=wh[u<<1];
if(minx[u<<1|1]<minx[u]) minx[u]=minx[u<<1|1],wh[u]=wh[u<<1|1];
}
void add(int u,int l,int r,int L,int R,int val){
if(L<=l&&r<=R){
spread(u,val);
return ;
}
dn(u);
int mid=(l+r)>>1;
if(L<=mid) add(u<<1,l,mid,L,R,val);
if(mid<R) add(u<<1|1,mid+1,r,L,R,val);
maxx[u]=maxx[u<<1],pos[u]=pos[u<<1];
if(maxx[u<<1|1]>=maxx[u]){
maxx[u]=maxx[u<<1|1];
pos[u]=pos[u<<1|1];
}
}
pair<int,int> query(int u,int l,int r,int L,int R){
if(L<=l&&r<=R){
return make_pair(minx[u],wh[u]);
}
dn(u);
int mid=(l+r)>>1;
if(L<=mid&&mid<R) return min(query(u<<1,l,mid,L,R),query(u<<1|1,mid+1,r,L,R));
if(L<=mid) return query(u<<1,l,mid,L,R);
return query(u<<1|1,mid+1,r,L,R);
}
};
int main(){
cin.tie(nullptr),cout.tie(nullptr)->sync_with_stdio(false);
int n,m;
cin>>n>>m;
vector<multiset<int>> rpos(n+1);
mt19937 gen(time(0));
for(int i=1; i<=m; i++){
int l,r;
cin>>l>>r;
//l=gen()%n+1,r=gen()%n+1;
if(l>r) swap(l,r);
rpos[l].insert(r);
}
vector<int> ans(m+1);
segment S(n);
for(int l=1; l<=n; l++){
if(rpos[l].size()){
S.modify(1,1,n,l,*rpos[l].begin());
}
}
ans[0]=0;
for(int i=1; i<=m; i++){
ans[i]=ans[i-1];
auto T=S.query(1,1,n,1,n);
while(T.first!=inf){
ans[i]++;
int l=T.second;
int r=*rpos[l].begin();
//cerr<<"use "<<l<<' '<<r<<endl;
S.add(1,1,n,l,r,1);
rpos[l].erase(rpos[l].begin());
if(rpos[l].size()){
S.modify(1,1,n,l,*rpos[l].begin());
}else{
S.modify(1,1,n,l,inf);
}
assert(S.maxx[1]==i);
int p=S.pos[1];
if(p==n) break;
T=S.query(1,1,n,p+1,n);
}
}
int pt=m;
for(int k=1; k<=n; k++){
long long res=inf;
while(pt&&(pt-1)*1ll*k-ans[pt-1]<pt*1ll*k-ans[pt]){
pt--;
}
res=pt*1ll*k+m-ans[pt];
cout<<res<<'\n';
}
return 0;
}