\]

然后我们注意到如果我们想要让

inline">\(0\)，那么我们不需要太多多余的操作，因为假设

inline">\(0\)，那么也是同样道理的，把操作次数减的太小会让后面用更多的代价把操作次数加回去。

因此这种情况下，我们让

\]

第二个和第三个转移是简单的，一个是区间

inline">\(\max\)，一个是区间加法，都可以用一棵线段树来维护。

inline">\(\max\)，单点修改和区间加法。

那么这道题就做完了，复杂度

class="language-cpp">#include<bits/stdc++.h>

#define

T,n,m,bn,a[N],a_[N],a1_[N],b[N],c[N];

struct

tag[N<<2],tree[N<<2];void

addtag(int

p){addtag(p<<1,tag[p]),addtag(p<<1|1,tag[p]),tag[p]=0;}void

build(int

r){tag[p]=0,tree[p]=-1e15;if(l==r)return;int

mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);}void

assign(int

tree[p]=x,(void)0;push_down(p);int

mid=l+r>>1;k<=mid?assign(p<<1,l,mid,k,x):assign(p<<1|1,mid+1,r,k,x);tree[p]=max(tree[p<<1],tree[p<<1|1]);}void

update(int

x){if(L<=l&&r<=R)return

mid=l+r>>1;if(L<=mid)update(p<<1,l,mid,L,R,x);if(R>mid)update(p<<1|1,mid+1,r,L,R,x);tree[p]=max(tree[p<<1],tree[p<<1|1]);}int

query(int

R){if(L<=l&&r<=R)return

mid=l+r>>1,ret=-1e15;if(L<=mid)ret=max(ret,query(p<<1,l,mid,L,R));if(R>mid)ret=max(ret,query(p<<1|1,mid+1,r,L,R));return

ret;}

{scanf("%lld%lld",&n,&m),c[bn=1]=0;for(int

i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),c[++bn]=a[i],c[++bn]=a[i]-1;sort(c+1,c+1+bn),bn=unique(c+1,c+1+bn)-c-1;for(int

i=1;i<=n;i++)a_[i]=lower_bound(c+1,c+1+bn,a[i])-c;for(int

i=1;i<=n;i++)a1_[i]=lower_bound(c+1,c+1+bn,a[i]-1)-c;int

_0=lower_bound(c+1,c+1+bn,0)-c;T1.build(1,1,bn),T2.build(1,1,bn);T1.assign(1,1,bn,_0,0),T2.assign(1,1,bn,_0,0);for(int

i=1;i<=n;i++){int

fai_1=max(T1.query(1,1,bn,a1_[i],a1_[i]),T1.query(1,1,bn,a_[i],bn));int

fai=max(T1.query(1,1,bn,a_[i],a_[i]),T2.query(1,1,bn,1,a1_[i])-m*a[i]);T1.assign(1,1,bn,a_[i],fai),T2.assign(1,1,bn,a_[i],fai+m*c[a_[i]]);T1.assign(1,1,bn,a1_[i],fai_1),T2.assign(1,1,bn,a1_[i],fai_1+m*c[a1_[i]]);T1.update(1,1,bn,a_[i],bn,b[i]),T2.update(1,1,bn,a_[i],bn,b[i]);}printf("%lld\n",T1.tree[1]);

main()

{scanf("%lld",&T);while(T--)solve();return

---