BZOJ4360 : achievement

对于$mode=0$的情况：

假设已经知道了最终要做哪些成就，那么这些成就一定是按$b$递减做的。

将成就按$b$从大到小排序，考虑往已选集合里新加一个成就。

假设该成就前面有$t$个已选成就，后面成就的$b$的和为$suf$，那么选该成就对答案的增量为$t\times b+a+suf$。

依次贪心取出增量最小的$k$个成就即可求出最优解。

注意到这就是一条条直线，所以需要维护一个数据结构，支持删除直线、修改直线的截距以及查询某个$x$对应的最小的$y$。

分块后每块维护凸壳即可，因为询问坐标递增，所以每块维护队列即可完成询问。

时间复杂度$O(n\sqrt{n})$。

对于$mode=1$的情况：

$1.$把已选的$k$个成就里某个成就的初始难度将为$0$，枚举每个成就更新答案即可。

$2.$从未选成就里选一个降为$0$，替换掉某个已选成就，需要根据两个成就的相对位置关系讨论。

时间复杂度$O(n)$。

一些常数优化：

$1.$合理调整块大小。

$2.$考虑对偶问题，即假设一开始所有成就都要做，然后贪心删掉$n-k$个成就，可以将$k$控制在$\lfloor\frac{n}{2}\rfloor$以内。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=100010,M=455,BUF=2500000;

const ll inf=1LL<<62;

char Buf[BUF],*buf=Buf;

int n,m,type,block,i,id,lim,pos[N],st[M],en[M],L[M],R[M],q[N],pre[M];ll tag[M];

bool v[N];int f[N];ll g[N],tmp,ans,old;

struct P{ll k,b,a;}a[N];

inline bool cmp(const P&a,const P&b){return a.k>b.k;}

inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}

inline double cross(const P&a,const P&b){return 1.0*(b.b-a.b)/(a.k-b.k);}

inline void build(int x){

  int l=st[x],r=en[x],t=l-1;

  for(int i=l;i<=r;i++)if(!v[i]){

    if(t>=l&&a[q[t]].k==a[i].k)if(a[q[t]].b<=a[i].b)continue;else t--;

    while(t>l&&cross(a[i],a[q[t]])<cross(a[q[t]],a[q[t-1]]))t--;

    q[++t]=i;

  }

  L[x]=l,R[x]=t;

}

inline void query(int x){

  int&i=L[x],j=R[x],X=pre[x];ll B=tag[x];

  if(i>j)return;

  for(;i<j;i++)if(a[q[i]].k*X+a[q[i]].b<a[q[i+1]].k*X+a[q[i+1]].b)break;

  ll t=a[q[i]].k*X+a[q[i]].b+B;

  if(t<tmp)tmp=t,id=i;

}

inline void choose(){

  int i;

  tmp=inf;

  for(i=0;i<=block;i++)query(i);

  ans+=tmp;

  int x=q[id],y=pos[x],l=st[y],r=en[y];ll k=a[x].k;

  v[x]=1;

  for(i=y+1;i<=block;i++)pre[i]++;

  for(i=y-1;~i;i--)tag[i]+=k;

  for(i=x-1;i>=l;i--)a[i].b+=k;

  for(i=x+1;i<=r;i++)a[i].b+=a[i].k;

  build(y);

}

inline void build2(int x){

  int l=st[x],r=en[x],t=l-1;

  for(int i=l;i<=r;i++)if(v[i]){

    if(t>=l&&a[q[t]].k==a[i].k)if(a[q[t]].b>=a[i].b)continue;else t--;

    while(t>l&&cross(a[i],a[q[t]])>cross(a[q[t]],a[q[t-1]]))t--;

    q[++t]=i;

  }

  L[x]=l,R[x]=t;

}

inline void query2(int x){

  int&i=L[x],j=R[x],X=pre[x];ll B=tag[x];

  if(i>j)return;

  for(;i<j;i++)if(a[q[i]].k*X+a[q[i]].b>a[q[i+1]].k*X+a[q[i+1]].b)break;

  ll t=a[q[i]].k*X+a[q[i]].b+B;

  if(t>tmp)tmp=t,id=i;

}

inline void choose2(){

  int i;

  tmp=-inf;

  for(i=0;i<=block;i++)query2(i);

  ans-=tmp;

  int x=q[id],y=pos[x],l=st[y],r=en[y];ll k=a[x].k;

  v[x]=0;

  for(i=y+1;i<=block;i++)pre[i]--;

  for(i=y-1;~i;i--)tag[i]-=k;

  for(i=x-1;i>=l;i--)a[i].b-=k;

  for(i=x+1;i<=r;i++)a[i].b-=a[i].k;

  build2(y);

}

int main(){

  fread(Buf,1,BUF,stdin);read(n),read(m),read(type);

  for(i=0;i<n;i++){

    int x,y;

    read(x),read(y);

    a[i].a=a[i].b=x,a[i].k=y;

  }

  sort(a,a+n,cmp);

  while(lim*lim*2<n)lim++;

  for(i=0;i<n;i++)pos[i]=i/lim;

  for(i=0;i<n;i++)en[pos[i]]=i;

  for(i=n-1;~i;i--)st[pos[i]]=i;

  block=pos[n-1];

  if(m+m<=n){

    for(i=0;i<=block;i++)build(i);

    for(i=0;i<m;i++)choose();

  }else{

    for(i=0;i<n;i++)v[i]=1;

    for(i=n-1;~i;i--)a[i].b+=tmp,tmp+=a[i].k,ans+=a[i].b;

    for(i=0;i<n;i++)a[i].b+=a[i].k*i;

    for(i=0;i<=block;i++)build2(i);

    for(i=0;i<n-m;i++)choose2();

  }

  if(!type)return printf("%lld",ans),0;

  old=ans;

  for(i=0;i<n;i++)if(v[i])ans=min(ans,old-a[i].a);

  for(i=0;i<n;i++){

    if(i)f[i]=f[i-1];

    if(v[i])f[i]++;

  }

  for(i=n-1;~i;i--){

    g[i]=g[i+1];

    if(v[i])g[i]+=a[i].k;

  }

  for(i=0;i<n;i++)if(v[i])f[i]--,g[i]-=a[i].k;

  tmp=inf;

  for(i=0;i<n;i++)if(v[i])tmp=min(tmp,-a[i].k*f[i]-a[i].a-g[i]);

  else if(tmp<inf)ans=min(ans,old+tmp+a[i].k*(f[i]-1)+g[i]);

  tmp=inf;

  for(i=n-1;~i;i--)if(v[i])tmp=min(tmp,-a[i].k*(f[i]+1)-a[i].a-g[i]);

  else if(tmp<inf)ans=min(ans,old+tmp+a[i].k*f[i]+g[i]);

  return printf("%lld",ans),0;

}