题意:
初始$x$值为$1$,给定一个长度为$n$的操作序列,$’+’$表示$x=x+1$,$’-‘$表示$x=x-1$,再给定$m$个询问,每次给定两个数$l,r$,忽视从第$l$到第$r$这$r-l+1$个操作,问剩下的操作中可以得到不同数的个数。
数据范围:$1\leq n,m\leq 2\times 10^5,1\leq l\leq r\leq n$
题解:
考虑到这是一个连续操作,所以在一次操作序列中的所有操作,出现的数必然在$[min,max]$之间,所以只需要每次找到区间$min$和$max$即可,记录一个前缀最大最小和后缀最大最小。
每次删除$[l,r]$的操作相当于只操作$[1,l-1]$和$[r+1,n]$,那么我们可以$O(1)$得到$[1,l-1]$的区间最大和最小,$O(1)$得到$[r+1,n]$的区间最大最小,则得到了该区间由$s[r]$上升的最大$up$和下降的最大$down$,之后再得到其由$a[l-1]$上升$up$和由$a[l-1]$下降$down$,即得到了真正的不操作$[l,r]$序列的后的区间最大最小值。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T Read(){
T s = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
return s * f;
}
#define read() Read<int>()
#define readl() Read<long long>()
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
char s[N];
int a[N];
int pmax[N], pmin[N], smax[N], smin[N];
int n, m, l, r;
void solve() {
scanf("%d%d", &n, &m);
scanf("%s", s + 1);
for(int i = 1, v = 0; i <= n; ++i) {
if(s[i] == '+') ++v;
else --v;
a[i] = v;
}
pmax[0] = pmin[0] = 0;
for(int i = 1; i <= n; ++i) {
pmax[i] = max(a[i], pmax[i - 1]);
pmin[i] = min(a[i], pmin[i - 1]);
}
smax[n + 1] = -INF, smin[n + 1] = INF;
for(int i = n; i >= 2; --i) {
smax[i] = max(smax[i + 1], a[i]);
smin[i] = min(smin[i + 1], a[i]);
}
while(m--) {
scanf("%d%d", &l, &r);
int lmax = pmax[l - 1], lmin = pmin[l - 1];
int rmax = smax[r + 1], rmin = smin[r + 1];
int res = 0;
if(rmax == -INF) {
res = lmax - lmin + 1;
}
else {
int up = rmax - a[r];
int down = a[r] - rmin;
int mx = max(lmax, a[l - 1] + up);
int mn = min(lmin, a[l - 1] - down);
res = mx - mn + 1;
}
printf("%d\n", res);
}
}
int main()
{
int T = 1;
scanf("%d", &T);
for(int i = 1; i <= T; ++i) solve();
return 0;
}