首先可以把时间区间离散化
然后求出 $cnt[l][r]$ 表示完全在时间 $[l,r]$ 之内的活动数量
设 $f[i][j]$ 表示当前考虑到时间 $i$，第一个会场活动数量为 $j$ 时，另一个会场的最大活动数量
这个转移直接枚举上一个时间分界线 $k$， $f[i][j]=max(f[k][j]+cnt[k][i])$ 表示 $[k,i]$ 时间的活动给第二个会场
$f[i][j]=max(f[k][j-cnt[k][i]])$ 表示 $[k,i]$ 时间的活动给第一个会场
这样第一问没有限制的最大数量就可以求出
考虑强制选某个的情况，那么我们可以把时间分成三部分，左右两边和中间强制选的一段时间
左边的贡献可以用 $f$ 求出，同理我们考虑设 $g[i][j]$ 表示当前从 $i$ 考虑到结束，第一个会场活动数量为 $j$ 时，另一个会场的最大活动数量
那么右边的贡献也可以求出，考虑设 $h[i][j]$ 表示 $[i,j]$ 的活动强制选时的最大答案
考虑枚举左右两边的 $j$ 分别为 $x,y$，即第一个会场活动数量
那么有 $h[L][R]=min(x+y+cnt[L][R],f[L][x]+g[R][y])$，这样总复杂度是 $n^4$ 的，考虑关于单调性的优化
发现转移时，对于某个 $x=a$，此时 $y=b$ 最优，那么对于 $x=a+1$，最优点 $y'<=b$
因为第一个会场活动多了第二个就少了，答案就会越来越小
所以枚举 $x$ 的时候动态维护 $y$ 指针即可，复杂度 $O(n^3)$
注意最后每一个的答案是枚举 $L<=a[i].l,R>=a[i].r$ 中的 $h[L][R]$ 取 $max$，而不是直接 $h[a[i].l][a[i].r]$
（$a[i].l,a[i].r$ 表示第 $i$ 个活动的时间区间）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=,INF=1e9+;
int n,d[N],m;
struct act{
int l,r;
}a[N];
int cnt[N][N],f[N][N],g[N][N],h[N][N];
inline int calc(int L,int R,int x,int y) { return min(x+y+cnt[L][R] , f[L][x]+g[R][y]); }
int main()
{
n=read();
for(int i=;i<=n;i++)
{
a[i].l=read(),a[i].r=a[i].l+read();
d[i]=a[i].l,d[n+i]=a[i].r;
}
sort(d+,d+*n+); m=unique(d+,d+*n+)-d-;
for(int i=;i<=n;i++)
{
a[i].l=lower_bound(d+,d+m+,a[i].l)-d;
a[i].r=lower_bound(d+,d+m+,a[i].r)-d;
}
for(int l=;l<=m;l++)
for(int r=l+;r<=m;r++)
for(int i=;i<=n;i++)
cnt[l][r]+=(a[i].l>=l&&a[i].r<=r);
for(int i=;i<=m;i++)
for(int j=;j<=n;j++) f[i][j]=g[i][j]=-INF;
for(int i=;i<=m;i++)
for(int j=;j<=cnt[][i];j++)
for(int k=;k<i;k++)
{
f[i][j]=max(f[i][j],f[k][j]+cnt[k][i]);
if(j>=cnt[k][i]) f[i][j]=max(f[i][j],f[k][j-cnt[k][i]]);
}
for(int i=m-;i>=;i--)
for(int j=;j<=cnt[i][m];j++)
for(int k=i+;k<=m;k++)
{
g[i][j]=max(g[i][j],g[k][j]+cnt[i][k]);
if(j>=cnt[i][k]) g[i][j]=max(g[i][j],g[k][j-cnt[i][k]]);
}
// min( x+y+cnt[L][R] , f[L][x]+f[R][y] )
for(int L=;L<=m;L++)
for(int R=L+;R<=m;R++)
for(int x=,y=n;x<=n;x++)
{
while(y&&calc(L,R,x,y)<=calc(L,R,x,y-)) y--;
h[L][R]=max(h[L][R],calc(L,R,x,y));
}
int ans=; for(int i=;i<=n;i++) ans=max(ans,min(f[m][i],i));
printf("%d\n",ans);
for(int i=;i<=n;i++)
{
ans=;
for(int L=;L<=a[i].l;L++)
for(int R=a[i].r;R<=m;R++) ans=max(ans,h[L][R]);
printf("%d\n",ans);
}
return ;
}