Codeforces 1495F - Squares

不知道怎么放到 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;
}