限制+修改单调队列（Ropeway）

2022ICPC 南京B.Ropeway

题意

n+2个点编号0到n+1，每个点有点权，要求选若干个点使得总点权最小，其中编号为0 和n + 1的点必须选且点权为0 ，同时满足任意两个被选的点之间的距离不超过k 。

此外还会给一个01串，表示1到n这些点是否为必选的点，1为必选，0为可选可不选

现在会给m个询问，每个询问为如果将编号为x的点权修改为v,答案是多少？每次询问互不影响

n<=5e5, m,k<=3e3

思路

1. 一眼单调队列，但是和普通单调队列不同，有些位置必须选，而且0，n+1都有一个点权为0的点，普通的单调队列是：0位置点权为0，而且每个点可选可不选
2. 位置0和n+1容易处理，只需要设pre[i]为从前往后扫描，而且选i的最小花费，suf[i]表示从后往前扫描，而且选i的最小花费
3. 有些位置必须选，可以这样思考，处理pre[i]的时候，枚举j的位置，j的区间为[i-m,i-1],表示上一个选的什么，但是如果i的前面有必须选的，那么j的范围就要改变，变成[k,i-1],k表示上一个必须选的位置，具体实现见代码
4. 现在考虑修改，如果将位置x的值修改，那么会影响到pre和suf数组，会影响多少呢？对于pre来说，x到n全部被影响到，suf同理。
5. 考虑答案是如何产生的，任选一个长度为k的区间，遍历这个区间所有的点，答案为min(pre[i]+suf[i]-a[i])
6. 所以修改一个位置，保证suf不动，那么答案可以在[i,i+k]中产生，此时需要修改pre数组
7. 但是6无法保证i+k<=n，但好像也没有关系，因为n+1这个点必选，那么从答案从n+1更新即可

第5点十分重要！！！

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=5e5+5;

int q[N],hh,tt;//单调队列，存数组下标 

int n,k;
ll a[N];//权值 
char s[N];//s数组是01串，1表示必须选

//pre和suf表示分别从前后遍历，结尾为i的最小花费
ll pre[N],suf[N],tem[N];


void init() { //初始化队头队尾
	hh=1,tt=0;
}
void get(ll f[]) {
	init();
	q[++tt]=0;
	f[0]=0;
	for(int i=1; i<=n+1; i++) {
		while(hh<=tt&&i-q[hh]>k) {
			hh++;
		}
		f[i]=f[q[hh]]+a[i];
		if(s[i]=='1') {
			init();
		}
		while(hh<=tt&&f[q[tt]]>=f[i]) {
			tt--;
		}
		q[++tt]=i;
	}
}
void get() { //处理presuf数组
	get(pre);
	reverse(a,a+n+2);
	reverse(s,s+n+2);
	get(suf);
	reverse(suf,suf+n+2);//反转suf数组
	//复原
	reverse(a,a+n+2);
	reverse(s,s+n+2);
}
ll ask(int pos) {
	//利用[pos+1,pos+k]更新答案
	init();
	ll ans=1e18;
	
	//对[pos-k,pos-1]做一遍单调队列
	for(int i=max(0,pos-k); i<pos; i++) {
		while(hh<=tt&&i-q[hh]>k)hh++;
		tem[i]=pre[i];
		if(s[i]=='1') {
			init();
		}
		while(hh<=tt&&pre[q[tt]]>=pre[i]) {
			tt--;
		}
		q[++tt]=i;
	}
	 
	//更新答案[pos,pos+k-1] 
    
    
    /*
    此时suf数组在pos位置是不准确的，但是为什么还可以用来更新答案呢？？
	因为suf数组表示以pos为结尾，选上pos但是不计算pos的答案，也就是说，pos位置的数无论是多少，都不影响suf
	那么此时suf值在pos位置就是准确的。
	此时，修改pos位置，影响到suf的区间[0,pos-1]	!!!!!
    */
    
    
	for(int i=pos; i<=min(n+1,pos+k-1); i++) {
		while(hh<=tt&&i-q[hh]>k)hh++;
		tem[i]=tem[q[hh]]+a[i];
		if(s[i]=='1') {
			init();
		}
		while(hh<=tt&&tem[q[tt]]>=tem[i]) {
			tt--;
		}
		q[++tt]=i;
		ans=min(ans,tem[i]+suf[i]);
	}
	return ans;
}
void solve() {
	init();
	cin>>n>>k;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	a[0]=a[n+1]=0;
	cin>>s+1;
	s[0]='1',s[n+1]='1';//必须选
	get();//处理pre，suf数组
	
	for(int i=0;i<=n+1;i++){
		suf[i]-=a[i];
        
        
		/*需要做这个处理
		suf数组表示选第i个，但是第i个权值并没有算进去
		这样ask询问好算，而且此处理后，pos修改只会影响[0,pos-1]的suf值，具体见ask处
		*/
        
        
	}

	int m;
	cin>>m;
	while(m--) {
		int pos,val;
		cin>>pos>>val;
		int back=a[pos];
		a[pos]=val;
		cout<<ask(pos)<<endl;//计算答案
		a[pos]=back;
	}
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}

思考

a. 对于本题目的答案ans

1. 对于任何一个必须选的点x，ans=pre[x]+suf[x]-a[x]
2. 特殊的，ans=suf[0]+pre[n+1]
3. 对于任何一个非必选的x，在一个长度为k的区间内，假设区间内的所有位置都非必选，则ans=min(pre[i]+suf[i]-a[i])
4. 第3条，假设区间内存在必须选的位置，ans=min(pre[i]+suf[i]-a[i])=pre[pos]+suf[pos]-a[pos]，(pos是必须要选的位置)

b. 代码中，如果x+k-1>n+1，也没事，因为答案会在n+1处取得

c. 注意本题目的suf数组的具体含义（见代码注释），因为这样处理，在ask询问中比较容易做，而且改变了a[pos]的修改对suf的影响！！！。