BZOJ 2459:[BeiJing 2011]謎の善人

#include<cstdio>

#define N 100010

struct P{int d[4][4];}T[N<<2],tmp;

int n,m,op,x,y,u,v,i,j,k,a[N],b[N],c[N],f[8][8],g[8][8],inf=~0U>>2,flag,ans,d1,d2;

inline void up(int&x,int y){if(x>y)x=y;}

inline void floyed(int n){for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)up(f[i][j],f[i][k]+f[k][j]);}

inline void cal(P&x,int p){

  for(i=0;i<4;i++)for(j=0;j<4;j++)if(i==j)f[i][j]=0;else f[i][j]=inf;

  f[0][1]=f[1][0]=b[p];

  f[2][3]=f[3][2]=b[p+1];

  f[0][2]=f[2][0]=a[p];

  f[1][3]=f[3][1]=c[p];

  floyed(4);

  for(i=0;i<4;i++)for(j=0;j<4;j++)x.d[i][j]=f[i][j];

}

inline void up(P&x,P l,P r){

  for(i=0;i<6;i++)for(j=0;j<6;j++)if(i==j)f[i][j]=0;else f[i][j]=inf;

  for(i=0;i<4;i++)for(j=0;j<4;j++)up(f[i][j],l.d[i][j]),up(f[i+2][j+2],r.d[i][j]);

  floyed(6);

  for(i=0;i<4;i++)for(j=0;j<4;j++)x.d[i][j]=f[i>1?i+2:i][j>1?j+2:j];

}

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

  if(a+1==b){cal(T[x],a);return;}

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

  build(x<<1,a,mid),build(x<<1|1,mid,b),up(T[x],T[x<<1],T[x<<1|1]);

}

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

  if(a+1==b){cal(T[x],a);return;}

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

  if(c<mid)change(x<<1,a,mid,c);else change(x<<1|1,mid,b,c);

  up(T[x],T[x<<1],T[x<<1|1]);

}

void ask(int x,int a,int b,int c,int d){

  if(c<=a&&b<=d){

    if(!flag)flag=1,tmp=T[x];else up(tmp,tmp,T[x]);

    return;

  }

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

  if(c<mid)ask(x<<1,a,mid,c,d);

  if(d>mid)ask(x<<1|1,mid,b,c,d);

}

int main(){

  scanf("%d",&n);

  for(i=1;i<n;i++)scanf("%d",&a[i]);

  for(i=1;i<=n;i++)scanf("%d",&b[i]);

  for(i=1;i<n;i++)scanf("%d",&c[i]);

  build(1,1,n);

  scanf("%d",&m);

  while(m--){

    scanf("%d%d%d",&op,&x,&y);

    if(!op){

      if(x==0)scanf("%d",&a[y]);

      if(x==1)scanf("%d",&b[y]);

      if(x==2)scanf("%d",&c[y]);

      if(y<n)change(1,1,n,y);

      if(y>1)change(1,1,n,y-1);

    }else{

      if(x==y){puts("0");continue;}

      if(x>y)i=x,x=y,y=i;

      u=(x+1)/2,v=(y+1)/2,d1=x&1^1,d2=y&1^1;

      if(u==v){

        ans=b[u];

        if(u>1)flag=0,ask(1,1,n,1,u),up(ans,tmp.d[2][3]);

        if(u<n)flag=0,ask(1,1,n,u,n),up(ans,tmp.d[0][1]);

      }else{

        for(i=0;i<8;i++)for(j=0;j<8;j++)if(i==j)g[i][j]=0;else g[i][j]=inf;

        flag=0,ask(1,1,n,u,v);

        for(i=0;i<4;i++)for(j=0;j<4;j++)up(g[i+2][j+2],tmp.d[i][j]);

        if(u>1)for(flag=0,ask(1,1,n,1,u),i=0;i<4;i++)for(j=0;j<4;j++)up(g[i][j],tmp.d[i][j]);

        if(v<n)for(flag=0,ask(1,1,n,v,n),i=0;i<4;i++)for(j=0;j<4;j++)up(g[i+4][j+4],tmp.d[i][j]);

        for(i=0;i<8;i++)for(j=0;j<8;j++)f[i][j]=g[i][j];

        floyed(8);

        ans=f[2+d1][4+d2];

      }

      printf("%d
",ans);

    }

  }

  return 0;

}