令
ansi
表示当
p
等于i时的答案。对
bi
排序，枚举
c
，更新ansi。 考虑分块，维护每一块的最大值和取得最大值的位置。更新
ai
时，会将
ans1，ans2⋯ansai
加
1
。如果一整块加1，显然如果最大值会变化，取得最大值的位置一定是增大的。那么在要改变最大值时暴力重构整个块就可以了。如果是一块中的一段加
1
，直接暴力重构这个块。这样一个块只会重构O(n)次，时间复杂度是
O(nn√)
的。 接下来考虑怎么判断最大值位置会发生变化。假设当前取得最大值的位置是
i
，增加k后最大值变为
j
，fi表示当前
i
的值。可得：fi−fj<k(j−i)，即
k>fi−fjj−i
。重构时求出
k
<script type="math/tex" id="MathJax-Element-3413">k</script>的最小值就可以了。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 100010
#define SN 320
#define ll long long
struct Node{
int x,y;
}a[N];
ll mx[SN],Ans,T,r[SN];
int i,j,k,n,m,p[SN],S,t[SN],w,b[N],f[N],Cnt,M,x;
inline bool Cmp(Node a,Node b){
return a.y<b.y;
}
inline ll Max(ll x,ll y){
return x<y?y:x;
}
inline int Max(
int x,
int y){
return x<y?y:x;
}
inline ll Min(ll x,ll y){
return x<y?x:y;
}
inline void Update(
int x){
for(
int i=
1;i<b[x];i++){
p[i]++;mx[i]+=t[i];
if(--r[i]<=
0){
r[i]=n;
for(
int j=t[i]+
1;b[j]==i;j++){
T=
1ll*j*(f[j]+p[i]);
if(T>mx[i])mx[i]=T,t[i]=j;
}
for(
int j=t[i]+
1;b[j]==i;j++)
r[i]=Min(r[i],(
1ll*(f[t[i]]+p[i])*t[i]-
1ll*(f[j]+p[i])*j)/(j-t[i]));
}
}
for(
int i=x;i&&b[i]==b[x];i--){
f[i]++;
T=
1ll*i*(f[i]+p[b[x]]);
if(T>mx[b[x]])mx[b[x]]=T,t[b[x]]=i;
}
r[b[x]]=n;
for(
int i=t[b[x]]+
1;b[i]==b[x];i++)
r[b[x]]=Min(r[b[x]],(
1ll*(f[t[b[x]]]+p[b[x]])*t[b[x]]-
1ll*(f[i]+p[b[x]])*i)/(i-t[b[x]]));
}
int main(){
scanf(
"%d%d",&n,&w);
for(i=
1;i<=n;i++)
scanf(
"%d%d",&a[i].x,&a[i].y),M=Max(a[i].x,M);
for(S=
sqrt(M),i=
1;i<=M;i++)b[i]=i/S+
1;
for(i=
1;i<=b[M];i++)t[i]=(i-
1)*S;
sort(a+
1,a+n+
1,Cmp);
for(i=
0;i<=a[n].y+
1;i++){
for(;j<n&&a[j+
1].y<i;)Update(a[++j].x);
for(k=
1,Ans=x=
0;k<=b[M];k++)
if(mx[k]>Ans)Ans=mx[k],x=t[k];
printf(
"%I64d %d\n",Ans+
1ll*i*w*(n-j),x);
}
return 0;
}
