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;
}

  

上一篇:splay训练


下一篇:两种方式:mysql查看正在执行的sql语句