本文共 1823 字，大约阅读时间需要 6 分钟。

有个显然的结论:在一段连续的$+-$之后,值域的变化都是连续的

这意味着,变化的过程有个最小值和最大值,中间的所有值都是答案。

所以我们的目的是,找到删除$[l,r]$后的最小值和最大值

不妨分段考虑,删掉$[l,r]$后分裂为两段$[1,l-1]$和$[r+1,n]$

$[1,l-1]$的最大值$mx[l-1]$最小值$[mi[l-1]$可以预处理出来,且预处理当前值为$zhi[i]$

现在的值为$zhi[l-1]$,那么现在考虑$[r+1,n]$段的影响

也就是需要预处理从点$r+1$开始的,$+$比$-$最多的个数$fmax[r+1]$

预处理从点$r+1$开始的,$-$比$+$最多的个数$fmin[r+1]$

倒过来做一遍最大最小连续子段和可以$O(n)$预处理这两个数组

那么最后的最小值为

$ansmi=min(mi[l-1],zhi[l-1]+fmi[r+1])$

最后的最大值为

$ansmx=max(mx[l-1],zhi[l-1]+fmx[r+1])$

于是可以$O(1)$知道答案

#include 
   
    using namespace std;const int maxn = 2e5+10;int n,m,mi[maxn],mx[maxn],zhi[maxn],fmi[maxn],fmx[maxn];char a[maxn];int main(){
   	int t; cin >> t;	while( t-- )	{
   		cin >> n >> m;		for(int i=1;i<=n;i++)		{
   			cin >> a[i];			if( a[i]=='-' )	zhi[i]=zhi[i-1]-1;			else	zhi[i]=zhi[i-1]+1;			mi[i] = min( mi[i-1],zhi[i] );			mx[i] = max( mx[i-1],zhi[i] );		}		fmi[n+1]=fmx[n+1]=0;		for(int i=n;i>=1;i--)		{
   			if( a[i]=='-' )			{
   				fmi[i] = min( -1,fmi[i+1]-1 );				fmx[i] = max( -1,fmx[i+1]-1 ); 			}			else			{
   				fmi[i] = min( 1,fmi[i+1]+1 );				fmx[i] = max( 1,fmx[i+1]+1 ); 			} 		}		for(int i=1;i<=m;i++)		{
   			int l,r; scanf("%d%d",&l,&r);			int ansmi = 0,ansmx = 0;			ansmi = min( zhi[l-1]+fmi[r+1],mi[l-1] );			ansmx = max( zhi[l-1]+fmx[r+1],mx[l-1] );			printf("%d\n",ansmx-ansmi+1);		}			}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112648677 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！