题目分析
线段树、前缀和、\(\text{ST}\) 表题解都有了，我补一发猫树题解吧。
由于每次操作只能将大小改变成跟原来差 \(1\)，所以只需要知道这段操作中的最大值和最小值，最后所求的答案的范围就被卡住了。对于每一次操作，我们把操作序列拦腰斩断，那么分别求两边的范围，最后减去重复的部分即可。
求最小值最大值部分可以用猫树维护，注意猫树空间要额外再开大一些。
贴上代码
#include<bits/stdc++.h>
// #define int long long
#define debug puts("Shiina_Mashiro_kawaii")
#define ok puts("Yes")
#define no puts("No")
#define inf 1e9
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn=4e5+5;
int n,m;
int lmin,lmax,rmin,rmax,ans;
int a[maxn],b[maxn];
int lg[maxn<<2];
string s;
struct cat_tree1{
int cat[25][maxn];
void init_tree(int o,int l,int r){
int mid=(l+r)>>1;
for(register int i=mid-1;i>=l;--i) cat[o][i]=max(cat[o][i+1],a[i]);
for(register int i=mid+2;i<r+1;++i) cat[o][i]=max(cat[o][i-1],a[i]);
}
void build_tree(int o){
int n=1;while(n<o) n<<=1;
for(register int i=o;i<n;++i) a[i]=0;
for(register int j=1,cnt=0;j<=n;j<<=1,++cnt){
for(register int i=0;i<n;++i) cat[cnt][i]=a[i];
for(register int i=0;i<n;i+=j) init_tree(cnt,i,i+j-1);
}
}
int query(int l,int r){
int o=lg[l^r];
if(l==r) return cat[o][l];
else return max(cat[o][l],cat[o][r]);
}
}ct1;
struct cat_tree2{
int cat[25][maxn];
void init_tree(int o,int l,int r){
int mid=(l+r)>>1;
for(register int i=mid-1;i>=l;--i) cat[o][i]=min(cat[o][i+1],b[i]);
for(register int i=mid+2;i<r+1;++i) cat[o][i]=min(cat[o][i-1],b[i]);
}
void build_tree(int o){
int n=1;while(n<o) n<<=1;
for(register int i=o;i<n;++i) b[i]=0;
for(register int j=1,cnt=0;j<=n;j<<=1,++cnt){
for(register int i=0;i<n;++i) cat[cnt][i]=b[i];
for(register int i=0;i<n;i+=j) init_tree(cnt,i,i+j-1);
}
}
int query(int l,int r){
int o=lg[l^r];
if(l==r) return cat[o][l];
else return min(cat[o][l],cat[o][r]);
}
}ct2;
inline void init(){
n=read();m=read();cin>>s;s=" "+s;
for(register int i=1;i<=n;++i){
if(s[i]=='+'){
a[i]=a[i-1]+1;b[i]=b[i-1]+1;
}
else{
a[i]=a[i-1]-1;b[i]=b[i-1]-1;
}
}
int len=2;while(len<n) len<<=1;
len<<=1;
for(register int i=1;i<=len;++i) lg[i]=lg[i>>1]+1;
ct1.build_tree(n+1);ct2.build_tree(n+1);
}
inline void solve(){
init();
while(m--){
int l=read(),r=read();lmin=lmax=rmin=rmax=0;
if(l==1&&r==n){
puts("1");continue;
}
if(l>1){
lmax=max(ct1.query(1,l-1),0);
lmin=min(ct2.query(1,l-1),0);
}
if(r<n){
rmax=ct1.query(r+1,n)-(a[r]-a[l-1]);
rmin=ct2.query(r+1,n)-(a[r]-a[l-1]);
}
if(lmax<rmin||rmax<lmin) ans=lmax-lmin+rmax-rmin+2;
else if(lmax<=rmax) ans=(lmax-lmin)+(rmax-rmin)-lmax+max(lmin,rmin)+1;
else ans=(lmax-lmin)+(rmax-rmin)-rmax+max(lmin,rmin)+1;
printf("%d\n",ans);
}
}
int main(){
int T=read();
while(T--) solve();
}