题目链接

题意：

有一个变量x初始值为0，有一组只包含“-”和“+”操作序列，“-”代表x的值-1，“+”代表x的值+1。有q次询问，每次询问给出两个整数l和r，表示忽略操作序列中下标为l到r的所有操作，要你计算出忽略这些操作后按顺序执行剩下的所有操作的过程中x可能的值的个数。

分析：

这题有个关键点就是x的变化是逐个+1或者-1，也就是说是连续的，这也就是说只要求出序列过程中x可以到达的最大值和最小值相减再+1就是答案。当时比赛的时候没想到这点，就没有一点思路。知道这点后就很好做了———可以利用前缀和，分别求出从开始到i的最小值和最大值，以及从i到结束的最大值和最小值。忽略一段序列其实就相当于将后半部分剩余的拼接到前半部分的末尾，那么只要求出后半部分序列的变化量然后加到前半部分的末尾再分别就一下最大值和最小值即可（不好表述，看代码）。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 1e6 + 10;
const double PI = acos(-1.0);
int max1[maxn], max2[maxn], min1[maxn], min2[maxn], a[maxn];
char op[maxn];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m >> op + 1;
        a[0] = 0;
        a[1] = a[0] + (op[1] == '-' ? -1 : 1);
        max1[1] = a[1];
        min1[1] = a[1];
        max1[0] = min1[0] = 0;
        for (int i = 2; i <= n; i++) {
            a[i] = a[i - 1] + (op[i] == '-' ? -1 : 1);
            max1[i] = max(max1[i-1], a[i]);//求从开始到i的最大值和最小值
            min1[i] = min(min1[i-1], a[i]);
        }
        max2[n] = a[n];
        min2[n] = a[n];
        //求从i到结尾的最大值和最小值
        for (int i = n-1; i >= 0; i--) {//注意这里i=0也需要求出，不然边界会出问题
            max2[i] = max(max2[i+1], a[i]);
            min2[i] = min(min2[i+1], a[i]);
        }
        while (m--) {
            int l, r;
            cin >> l >> r;
            int mmax = max2[r] - a[r];//后半段变化量的最大值
            int mmin = a[r] - min2[r];//后半段变化量的最小值
            int amax = max(max1[l-1], a[l-1] + mmax);//比较前半段的最大值和前半段末尾加上后半段之后的值，取最大值，下同
            int amin = min(min1[l-1], a[l-1] - mmin);
            cout << amax - amin + 1 << endl;
        }
    }
    return 0;
}