可以转化成区间加，询问 ai×i 的最大值 这个不好维护，分块，零散的加，直接重构整块，否则在块上打标记 同时我们在块上还要维护当前最大值所在的 i <script type="math/tex" id="MathJax-Element-121">i</script> 和 接下来至少要整块加多少次才能使得最大值变化 每次在块上打标记，当达到临近就重构更新最大值，注意这个最大值随着全局加肯定是单调右移的，那么重构复杂度也是对的
#include<cstdio> #include<cstdlib> #include<cassert> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=100005; int n,W; int a[N],b[N]; int maxa=0; int idx[N]; inline bool cmp(int x,int y){ return b[x]<b[y]; } const int BB=505; int B,cnt; int pos[N]; int lp[BB],rp[BB]; ll c[N]; int tag[BB]; ll clk[BB]; int K[BB]; inline void Build(){ B=(int)sqrt(maxa); for (int i=0;i<=maxa;i++) pos[i]=i/B+1; cnt=pos[maxa]; for (int i=1;i<=cnt;i++) lp[i]=(i-1)*B,rp[i]=i*B-1; rp[cnt]=maxa; for (int i=1;i<=cnt;i++){ K[i]=lp[i]; if (K[i]==rp[i]) clk[i]=1<<30; else clk[i]=1; } } inline void rebuild(int x,int l,int r){ ll maxv=-1,k=0,t=0; for (int i=lp[x];i<=rp[x];i++){ c[i]+=tag[x]; c[i]+=(l<=i && i<=r); if (c[i]*i>maxv) maxv=c[i]*i,k=i; } K[x]=k; tag[x]=0; clk[x]=1<<30; for (int i=k+1;i<=rp[x];i++) clk[x]=min(clk[x],(c[k]*k-c[i]*i)/(i-k)+1); } inline void Add(int r){ int rb=pos[r]; rebuild(rb,lp[rb],r); for (int i=1;i<rb;i++){ tag[i]++; clk[i]--; if (!clk[i]) rebuild(i,0,-1); } } ll ans=0,p; inline void Query(){ ans=0; p=0; for (int i=1;i<=cnt;i++) if ((c[K[i]]+tag[i])*K[i]>ans) ans=(c[K[i]]+tag[i])*K[i],p=K[i]; } int main(){ freopen("deep.in","r",stdin); freopen("deep.out","w",stdout); read(n); read(W); for (int i=1;i<=n;i++) read(a[i]),read(b[i]),idx[i]=i,maxa=max(maxa,a[i]); Build(); sort(idx+1,idx+n+1,cmp); int lim=b[idx[n]]+1,pnt=1; for (int c=0;c<=lim;c++){ while (pnt<=n && c>b[idx[pnt]]) Add(a[idx[pnt]]),pnt++; Query(); printf("%lld %d\n",(ll)c*W*(n-pnt+1)+ans,p); } return 0; }