题解：P14598 [COCI 2025/2026 #2] 搭塔 / Tornjevi

考虑一次操作怎么做，显然从大到小（从小到大等效）贪心，记录当前分别以蓝色、红色为顶的塔的数量，不够就增加。考虑换种方式刻画，只记录蓝色塔的数量，初始值为零，若来了一块蓝积木，则蓝色塔数量加一，否则减一，那么其历史最大值与历史最小值之差即为塔的数量。过程中可能会出现负数，但不难理解，假设当前值小于历史最小值了，说明多加了一个红色塔，此时下基准改变，塔的总数量加一；大于历史最大值时，说明多加了一个蓝色塔，此时上基准改变，塔的总数量加一。于是题意转化为前缀和的 RMQ 问题，用自己喜欢的数据结构维护即可，ST 表应该是最快的，笔者用了线段树，代码非常好写。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=1e8;
char a[N];
int s[N],tmax[N<<2],tmin[N<<2];
void build(int u,int l,int r){
	if(l==r){
		tmax[u]=tmin[u]=s[l];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	tmax[u]=max(tmax[u<<1],tmax[u<<1|1]);
	tmin[u]=min(tmin[u<<1],tmin[u<<1|1]);
	return;
}
pair<int,int> ask(int u,int l,int r,int x,int y){
	if(x<=l && r<=y) return {tmax[u],tmin[u]};
	int mid=l+r>>1;
	pair<int,int> ans={-inf,inf},tmp;
	if(x<=mid){
		tmp=ask(u<<1,l,mid,x,y);
		ans.first=max(ans.first,tmp.first);
		ans.second=min(ans.second,tmp.second);
	}
	if(mid<y){
		tmp=ask(u<<1|1,mid+1,r,x,y);
		ans.first=max(ans.first,tmp.first);
		ans.second=min(ans.second,tmp.second);
	}
	return ans;
} 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n,q;
	cin>>n>>q>>a+1;
	for(int i=1;i<=n;i++){
		if(a[i]=='C') s[i]=s[i-1]+1;
		else s[i]=s[i-1]-1;
	}
	build(1,1,n);
	while(q--){
		int x,y;
		cin>>x>>y;
		pair<int,int> tmp=ask(1,1,n,x,y);
		int maxs=max(0,tmp.first-s[x-1]);
		int mins=min(0,tmp.second-s[x-1]);
		cout<<maxs-mins<<"\n";
	}
	return 0;
}

题解：P14598 [COCI 2025/2026 #2] 搭塔 / Tornjevi

文章操作

相关推荐

评论

题解：P14598 [COCI 2025/2026 #2] 搭塔 / Tornjevi