BZOJ2130 : 魔塔

考虑从$0$到$n$枚举$A$的通关楼层。

设$f[i]$表示$B$通关$i$层时$C$最多能得到多少金币，因为金币数非负，所以也可以看作最多通关多少层。

当$A$的通关楼层往上多$1$的时候，这把钥匙必须给$A$。

如果这把钥匙还剩$0$把，那么说明：

$1.B$某些楼层$j$以上都不能到达，对应$f[\geq j]$变为$-inf$。

$2.C$某些楼层$j$以上都不能到达，对应$f$的某个后缀与$sumc[j-1]$取$min$。

如果这把钥匙还剩$1$把，那么说明：

当$B$的楼层在$j$以上时，$C$不能到达$k$以上的楼层，对应$f$的某个$\geq j$的后缀中与$sumc[k-1]$取$min$。

任意时刻，随着$i$的增加，$f[i]$不会增加，所以用线段树维护即可。

线段树上每个节点维护区间内最左边、最右边的$f$以及区间内某个$f$加上$sumb$的最大值。

当修改时，可以通过上下界判断是否可以打标记，否则暴力递归左右儿子。

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

#include<cstdio>

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

int T,n,i,w[N],a[N],b[N],c[N],pb[N],pc[N],sa[N],sb[N],sc[N],f[N],vl[M],vr[M],v[M],tag[M],ans;

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

inline void umin(int&a,int b){if(a>b)a=b;}

inline void umax(int&a,int b){if(a<b)a=b;}

inline void up(int x){

  vl[x]=vl[x<<1],vr[x]=vr[x<<1|1];

  v[x]=v[x<<1]>v[x<<1|1]?v[x<<1]:v[x<<1|1];

}

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

  tag[x]=-1;

  if(a==b){

    vl[x]=vr[x]=f[a];

    v[x]=f[a]+sb[a];

    return;

  }

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

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

  up(x);

}

inline void tag1(int x,int r,int p){tag[x]=vl[x]=vr[x]=p,v[x]=sb[r]+p;}

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

  if(c<=a){

    if(p>=vl[x])return;

    if(p<vr[x]){tag1(x,b,p);return;}

  }

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

  if(tag[x]!=-1)tag1(x<<1,mid,tag[x]),tag1(x<<1|1,b,tag[x]),tag[x]=-1;

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

  change(x<<1|1,mid+1,b,c,p);

  up(x);

}

int solve(){

  read(n);

  for(i=1;i<=n;i++)read(w[i]);

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

  for(i=1;i<=n;i++)read(b[i]),pb[b[i]]=i;

  for(i=1;i<=n;i++)read(c[i]),pc[c[i]]=i;

  for(i=1;i<=n;i++)read(sa[i]),sa[i]+=sa[i-1];

  for(i=1;i<=n;i++)read(sb[i]),sb[i]+=sb[i-1];

  for(i=1;i<=n;i++)read(sc[i]),sc[i]+=sc[i-1];

  for(f[0]=sc[n],i=1;i<=n;i++){

    f[i]=f[i-1];

    if(w[b[i]]==1)umin(f[i],sc[pc[b[i]]-1]);

  }

  build(1,0,n);

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

    if(w[a[i]]==1)change(1,0,n,pb[a[i]],-inf),change(1,0,n,0,sc[pc[a[i]]-1]);

    else change(1,0,n,pb[a[i]],sc[pc[a[i]]-1]);

    umax(ans,sa[i]+v[1]);

  }

  return ans;

}

int main(){

  char _[9];

  scanf("%s",_);

  for(read(T);T--;printf("%d\n",solve()));

  return 0;

}