CF-1473D

68/100

题意：

现在给你一个只含有”+”，”-“的字符串，前者每次对数字+1，后者每次对数字-1，和一个初始数字$0$，然后给定两个端点$l,r$，问从$1$开始到$l-1$再从$r+1$开始到$n$进行操作一共可以得到几个不同的数字。

题解：

这一看前面的操作就可以维护一个最大最小值即可，但是后面那半部分的操作我没想到，直接用线段树进行了维护，实际上，考虑后半部分进行加减的时候，可以用后缀的方式统计，因为从后往前统计最大值的时候我们可以发现，如果是负值，相当于从当前作为最大值的开始，正值同理，即$suf[i].max=max(0,suf[i+1].max)+mp(s[i])$，$mp$函数用于求当前表示+1，-1，就不需要用线段树维护了。

AC：

const int N=2e5+5;
struct xy{
  int ma,mi;
}pre[N],suf[N];
int cur[N];
int mp(char x){
  return x=='+'?1:-1;
}
signed main() {
  int T;cin>>T;
  while(T--){
    int n,m;cin>>n>>m;
    string s;cin>>s;
    _for(int,i,1,n+1){
      cur[i]=cur[i-1]+mp(s[i-1]);
      pre[i].ma=max(cur[i],pre[i-1].ma);
      pre[i].mi=min(cur[i],pre[i-1].mi);
    }
    suf[n+1].ma=suf[n+1].mi=0;
    _rfor(int,i,n,0){
      suf[i].ma=max(0,suf[i+1].ma)+mp(s[i-1]);
      suf[i].mi=min(0,suf[i+1].mi)+mp(s[i-1]);
    }
    while(m--){
      int l,r;cin>>l>>r;
      int ma1=pre[l-1].ma;
      int ma2=cur[l-1]+suf[r+1].ma;
      int mi1=pre[l-1].mi;
      int mi2=cur[l-1]+suf[r+1].mi;
      cout<<max(ma1,ma2)-min(mi1,mi2)+1<<endl;
    }
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2021/06/17/CF-1473D/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！