# Codeforces Educational Round 102 D.Program 线段树合并

## 题解

```struct tree{
int l,r,rval,mx,mi;
tree operator + (const tree &x)const{
tree res;
res.mx = max(mx,rval + x.mx);
res.mi = min(mi,rval + x.mi);
res.rval = rval + x.rval;
return res;
}
void init(){
mx = 0;
mi = INF;
rval = 0;
}
}tr[maxn<<2];```

## 代码

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int t;
int n,m;
string s;
int a[maxn];
const int INF = 1e7;
map<int,int>mp;
struct tree{
int l,r,rval,mx,mi;
tree operator + (const tree &x)const{
tree res;
res.mx = max(mx,rval + x.mx);
res.mi = min(mi,rval + x.mi);
res.rval = rval + x.rval;
return res;
}
void init(){
mx = 0;
mi = INF;
rval = 0;
}
}tr[maxn<<2];
void push_up(int now){
tr[now].mx = max(tr[now<<1].mx,tr[now<<1].rval+tr[now<<1|1].mx);
tr[now].mi = min(tr[now<<1].mi,tr[now<<1].rval+tr[now<<1|1].mi);
tr[now].rval = tr[now<<1].rval + tr[now<<1|1].rval;
}
void build(int now,int l,int r){
tr[now].l = l;
tr[now].r = r;
tr[now].rval = 0;
tr[now].mx = 0;
tr[now].mi = INF;
if(l == r){
tr[now].rval = tr[now].mx = tr[now].mi = a[l];
return;
}
int mid = (l + r) >> 1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
push_up(now);
return;
}
tree query(int now,int l,int r){
if(tr[now].l >= l && tr[now].r <= r){
return tr[now];
}
tree res;
res.init();
int mid = (tr[now].l + tr[now].r) >> 1;
if(r <= mid)
res = query(now<<1,l,r);
if(l > mid)
res = query(now<<1|1,l,r);
else if(l <= mid && r > mid)
res = query(now<<1,l,r) + query(now<<1|1,l,r);
return res;
}
struct que{
int l,r;
bool operator < (const que &b)const{
return this->r < b.r || (this->r == b.r && this->l < b.l);
}
}q[maxn];
tree ansl,ansr,ans;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
cin >> n >> m;
cin >> s;
int now = 0;
for(int i = 0;i < n;++i){
if(s[i] == '-')
a[i+1] = -1;
else a[i+1] = 1;
}
build(1,1,n);
for(int i = 1;i <= m;++i){
cin >> q[i].l >> q[i].r;
ansl.init();
ansr.init();
if(q[i].l == 1 && q[i].r == n){
cout << "1\n";
continue;
}
else if(q[i].l == 1){
ans = query(1,q[i].r+1,n);
}
else if(q[i].r == n){
ans = query(1,1,q[i].l - 1);
}
else{
ans = query(1,1,q[i].l-1) + query(1,q[i].r+1,n);
}
cout << ans.mx - ans.mi + 1 + (ans.mi > 0 || ans.mx < 0) << "\n";
}
}
return 0;
}```