BZOJ5326 : [Jsoi2017]博弈

将所有物品按照$b$的选择顺序排序，则先手在任意前$i$个物品中最多只能拿走$\lceil\frac{i}{2}\rceil$个物品。

将每个物品的价值设为$a+b$，那么答案为先手拿走的价值和减去所有物品的$b$之和，目标是最大化先手拿走的价值和。

如果不考虑修改，则满足拟阵，可以贪心选取，修改时最优解最多发生一处变动。

每个修改可以看作是先删除一个物品，再插入一个物品。

设$f[i]$表示$[1,i]$里选择的物品数减去$\lceil\frac{i}{2}\rceil$，则方案合法的条件为$\max(f[1,n])\leq 0$。

对于插入物品$x$：

如果$x$可以直接加入最优解，那么直接加入。
否则加入$x$会导致$f$中出现$1$，那么需要找到一个最优解中的价值最小的物品$y$，满足$y$在$f$从左往右第一个$1$之前，要么不选$x$，要么将$y$替换成$x$。

对于删除物品$x$：

如果$x$不在最优解中，那么直接删除。
否则删除$x$后可以继续多加入一个物品，那么需要找到一个不在最优解中的价值最大的物品$y$，满足$y$到$n$的所有$f$都是负数。

以上所有操作都可以用线段树维护，时间复杂度$O((n+m)\log n)$。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef pair<int,int>P;

const int N=100010,M=262150,inf=~0U>>1,BUF=10000000;

char Buf[BUF],*buf=Buf;long long ans;

int n,m,i,x,y,pos[N];bool used[N];

P ma[M],mi[M];int f[M],tag[M];

struct E{int a,b,p;}e[N];

inline bool cmp(const E&a,const E&b){

  if(a.b!=b.b)return a.b>b.b;

  return a.p<b.p;

}

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

inline void up(int x){

  ma[x]=max(ma[x<<1],ma[x<<1|1]);

  mi[x]=min(mi[x<<1],mi[x<<1|1]);

}

void build(int x,int a,int b){

  if(a==b){

    ma[x]=P(-inf,a);

    mi[x]=P(inf,a);

    f[x]=-(a+1)/2;

    return;

  }

  int mid=(a+b)>>1;

  build(x<<1,a,mid),build(x<<1|1,mid+1,b),up(x);

  f[x]=max(f[x<<1],f[x<<1|1]);

}

inline void tag1(int x,int p){f[x]+=p;tag[x]+=p;}

inline void pb(int x){if(tag[x])tag1(x<<1,tag[x]),tag1(x<<1|1,tag[x]),tag[x]=0;}

void maketag(int x,int a,int b,int c,int d,int p){

  if(c<=a&&b<=d){tag1(x,p);return;}

  pb(x);

  int mid=(a+b)>>1;

  if(c<=mid)maketag(x<<1,a,mid,c,d,p);

  if(d>mid)maketag(x<<1|1,mid+1,b,c,d,p);

  f[x]=max(f[x<<1],f[x<<1|1]);

}

void setused(int x,int a,int b,int c,int p){

  if(a==b){

    used[a]=1;

    ma[x]=P(-inf,a);

    mi[x]=P(p,a);

    return;

  }

  int mid=(a+b)>>1;

  if(c<=mid)setused(x<<1,a,mid,c,p);else setused(x<<1|1,mid+1,b,c,p);

  up(x);

}

void setunused(int x,int a,int b,int c,int p){

  if(a==b){

    used[a]=0;

    ma[x]=P(p,a);

    mi[x]=P(inf,a);

    return;

  }

  int mid=(a+b)>>1;

  if(c<=mid)setunused(x<<1,a,mid,c,p);else setunused(x<<1|1,mid+1,b,c,p);

  up(x);

}

int askf(int x,int a,int b,int c,int d){

  if(c<=a&&b<=d)return f[x];

  pb(x);

  int mid=(a+b)>>1,t=-inf;

  if(c<=mid)t=askf(x<<1,a,mid,c,d);

  if(d>mid)t=max(t,askf(x<<1|1,mid+1,b,c,d));

  return t;

}

P askmi(int x,int a,int b,int c,int d){

  if(c<=a&&b<=d)return mi[x];

  int mid=(a+b)>>1;P t(inf,0);

  if(c<=mid)t=askmi(x<<1,a,mid,c,d);

  if(d>mid)t=min(t,askmi(x<<1|1,mid+1,b,c,d));

  return t;

}

P askma(int x,int a,int b,int c,int d){

  if(c<=a&&b<=d)return ma[x];

  int mid=(a+b)>>1;P t(-inf,0);

  if(c<=mid)t=askma(x<<1,a,mid,c,d);

  if(d>mid)t=max(t,askma(x<<1|1,mid+1,b,c,d));

  return t;

}

inline int findfirstpos(){

  int x=1,a=1,b=n,mid;

  while(a<b){

    pb(x);

    mid=(a+b)>>1;

    if(f[x<<1]>0)x=x<<1,b=mid;else x=x<<1|1,a=mid+1;

  }

  return a;

}

inline int findlastneg(){

  int x=1,a=1,b=n,mid,ret=n+1;

  while(a<b){

    pb(x);

    mid=(a+b)>>1;

    if(f[x<<1|1]<0){

      x=x<<1;

      b=mid;

      ret=mid+1;

    }else{

      x=x<<1|1;

      a=mid+1;

    }

  }

  if(f[x]<0)ret=a;

  return ret;

}

inline void additem(int x){

  int val=e[x].a+e[x].b,tmp=askf(1,1,n,x,n);

  maketag(1,1,n,x,n,1);

  if(tmp<0){

    setused(1,1,n,x,val);

    ans+=val;

    return;

  }

  int o=findfirstpos();

  maketag(1,1,n,x,n,-1);

  P y=askmi(1,1,n,1,o);

  if(y.first>=val){

    setunused(1,1,n,x,val);

    return;

  }

  ans+=val-y.first;

  setunused(1,1,n,y.second,y.first);

  maketag(1,1,n,y.second,n,-1);

  setused(1,1,n,x,val);

  maketag(1,1,n,x,n,1);

}

inline void delitem(int x){

  if(!used[x])return;

  ans-=e[x].a+e[x].b;

  setunused(1,1,n,x,-inf);

  maketag(1,1,n,x,n,-1);

  int o=findlastneg();

  if(o>n)return;

  P y=askma(1,1,n,o,n);

  if(y.first<=0)return;

  ans+=y.first;

  setused(1,1,n,y.second,y.first);

  maketag(1,1,n,y.second,n,1);

}

int main(){

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

  for(i=1;i<=n;i++)read(e[i].a);

  for(i=1;i<=n;i++)read(e[i].b),e[i].p=i,ans-=e[i].b;

  sort(e+1,e+n+1,cmp);

  for(i=1;i<=n;i++)pos[e[i].p]=i;

  build(1,1,n);

  for(i=1;i<=n;i++)additem(i);

  printf("%lld\n",ans);

  read(m);

  while(m--){

    read(x),read(y);

    x=pos[x];

    delitem(x);

    e[x].a=y;

    additem(x);

    printf("%lld\n",ans);

  }

  return 0;

}

巴特西

BZOJ5326 : [Jsoi2017]博弈

最新文章

热门文章