专栏文章

题解：P12263 『STA - R9』回听

EELECTRODE_kaf
P12263题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipitm75
此快照首次捕获于
2025/12/03 12:42
3 个月前
此快照最后确认于
2025/12/03 12:42
3 个月前
查看原文
考虑对于一个 bib_i，它右侧的数与它交换会减少，所以它由它左侧的 aja_j 贡献 aja_j，右侧的 aja_j 最多贡献 aj−(j−i)=aj−j+ia_j-(j-i)=a_j-j+i。即 bi=max⁡(0,min⁡k=1iak,min⁡k=i+1nak−k+i)b_i=\max(0,\min_{k=1}^ia_k,\min_{k=i+1}^na_k-k+i)。所以 bib_i 单调不减。若继续观察 bib_i 的增速可以发现，bi+1b_{i+1} 若选择与 bib_i 相同的 aka_k 则 bi+1=bi+1b_{i+1}=b_i+1，所以相邻的 bib_i 最多相差 11。所以所求不同 bib_i 的种数即为 bn−b1+1b_n-b_1+1。代入上式得到 b1=max⁡(0,min⁡k=1nak−k+1),bn=min⁡akb_1=\max(0,\min_{k=1}^na_k-k+1),b_n=\min a_k，用两个线段树分别维护这两个值即可。
CPP
const ll N=5e5+10;
ll n,q,a[N],sgtr1[N*4],sgtr2[N*4],tg1[N*4],tg2[N*4];

ll ls(ll p){
	return p*2; 
} 

ll rs(ll p){
	return p*2+1; 
}

void pushup(ll p){
	sgtr1[p]=min(sgtr1[ls(p)],sgtr1[rs(p)]);
	sgtr2[p]=min(sgtr2[ls(p)],sgtr2[rs(p)]);
}

void pushdown(ll p){
	if(tg1[p]){
		sgtr1[ls(p)]+=tg1[p];
		sgtr1[rs(p)]+=tg1[p];
		tg1[ls(p)]+=tg1[p];
		tg1[rs(p)]+=tg1[p];
		tg1[p]=0;
	}
	
	if(tg2[p]){
		sgtr2[ls(p)]+=tg2[p];
		sgtr2[rs(p)]+=tg2[p];
		tg2[ls(p)]+=tg2[p];
		tg2[rs(p)]+=tg2[p];
		tg2[p]=0;
	}
}

void build(ll p,ll l,ll r){
	if(l==r){
		sgtr1[p]=a[l]-l+1;
		sgtr2[p]=a[l];
		return;
	}
	
	ll mid=(l+r)/2;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
}

void upd(ll p,ll l,ll r,ll ql,ll qr,ll v){
	if(l>qr or r<ql) return;
	
	if(ql<=l and r<=qr) {
		sgtr1[p]+=v;
		sgtr2[p]+=v;
		tg1[p]+=v;
		tg2[p]+=v;
		return;
	}
	
	pushdown(p);
	ll mid=(l+r)/2;
	upd(ls(p),l,mid,ql,qr,v);
	upd(rs(p),mid+1,r,ql,qr,v);
	pushup(p);
}

int main(){
	sync_off;
	cin>>n>>q;
	
	rep(i,1,n) cin>>a[i];
	
	build(1,1,n);
	
	count(q){
		ll l,r,v;
		cin>>l>>r>>v;
		upd(1,1,n,l,r,v);
		cout<<max(0ll,sgtr2[1])-max(0ll,sgtr1[1])+1<<'\n';
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...