不知道怎么放到 div1F 的，感觉没啥亮点。
首先对于一条 \(1\) 到 \(n+1\) 的路径而言，它经过的点的编号一定是递增的，也就是说，如果我们将关键点大小排个序，那么答案就是相邻两点间最短路的和。删 / 加点造成的变化是 \(O(1)\) 的，所以问题等价于，多次询问这张图中 \(x,y\) 之间最短路的值。
先假设 \(x\to y\) 全部走 \(a_i\) 的边，那么每一次走 \(i\to nxt_i\) 的边的变化相当于令答案扣除 \(\sum\limits_{j=i}^{nxt_i-1}a_j\) 再加上 \(b_i\)，由于我们走 \(i\to nxt_i\) 的边所对应的 \([i,nxt_i)\) 不能相交并且必须要满足 \(x\le i<nxt_i\le y\)，因此问题可以转化为，有 \(n\) 个形如 \([i,nxt_i-1]\) 的区间，带权，要求 \([x,y]\) 最大权不交区间集的权值。
朴素的做法是树状数组优化 DP，放在这里左端点不固定当然行不通。但是这个图的性质我们还没用。非常重要的一个性质是不存在 \(i<j<nxt_i<nxt_j\)，也就是任意两个区间如果有交，则它们是包含关系。考虑这样一个算法，从大到小枚举 \(l\)，然后考虑 \([l,nxt_l-1]\) 这个区间，如果它的权值 \(v\) 大于 \([l+1,nxt_l-1]\) 的最大权不交区间集的权值 \(v'\)，就令 \(\forall r\in[nxt_l-1,n]\)，\([l,r]\) 的答案加上 \(v-v'\)，这样查询相当于树状数组上一段前缀之和。\(O(n\log n)\) 维护即可。
const int MAXN=2e5;
int n,qu,p[MAXN+5],a[MAXN+5],b[MAXN+5],nxt[MAXN+5];
vector<tuple<int,int,int> >vec[MAXN+5];
void addqry(int l,int r,int id,int coef){vec[l].pb(mt(r,id,coef));}
ll res[MAXN+5],suma[MAXN+5],t[MAXN+5];
void add(int x,ll v){for(int i=x;i<=n;i+=(i&(-i)))t[i]+=v;}
ll query(int x){ll ret=0;for(int i=x;i;i&=(i-1))ret+=t[i];return ret;}
int main(){
scanf("%d%d",&n,&qu);
for(int i=1;i<=n;i++)scanf("%d",&p[i]);p[n+1]=n+1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),suma[i]=suma[i-1]+a[i];
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
addqry(1,n,0,1);set<int>st;st.insert(1);st.insert(n+1);
for(int i=1,x;i<=qu;i++){
scanf("%d",&x);
if(x!=1){
if(st.find(x)!=st.end()){
int pv=*(--st.lower_bound(x)),nt=*st.upper_bound(x);
addqry(pv,nt-1,i,1);addqry(pv,x-1,i,-1);addqry(x,nt-1,i,-1);
st.erase(st.find(x));
}else{
int pv=*(--st.lower_bound(x)),nt=*st.upper_bound(x);
addqry(pv,nt-1,i,-1);addqry(pv,x-1,i,1);addqry(x,nt-1,i,1);
st.insert(x);
}
}
}
static int stk[MAXN+5];int tp=0;
for(int i=n+1;i;i--){
while(tp&&p[stk[tp]]<p[i])--tp;
nxt[i]=stk[tp];stk[++tp]=i;
}
for(int i=n;i;i--){
ll v=suma[nxt[i]-1]-suma[i-1]-b[i],lst=query(nxt[i]-1);
if(v>lst)add(nxt[i]-1,v-lst);
for(auto t:vec[i])res[get<1>(t)]+=(suma[get<0>(t)]-suma[i-1]-query(get<0>(t)))*get<2>(t);
}
for(int i=1;i<=qu;i++)res[i]+=res[i-1];
for(int i=1;i<=qu;i++)printf("%lld\n",res[i]);
return 0;
}