codeforces 1473 D. Program (前缀和 + st表)

题目链接：https://codeforces.com/contest/1473/problem/D

题目大意：
(x) 初始值为 (0), 给定一个"+-"操作序列, 每次操作将 (x) 加一或减一，
有 (m) 个询问 (l, r), 求跳过操作序列中 ([l,r]) 这一段，执行操作序列后 (x) 出现过的不同值的数量

题解：
比赛的时候不够冷静，转化错题意就一直在搞假做法

我们发现，如果将 (+) 看作 (1), (-) 看作 (-1)，那么每次出现新的值，就是操作序列的前缀和序列出现了新的最大/最小值
于是就相当于求两端区间的最值，右端的区间最值还要减去 ([l,r]) 的区间和，答案就是两端区间的最小值和最大值的绝对值之和，还要在加上一个最开始的 (0)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 200010;

int T, n, m;
int a[maxn], c[maxn], lgk[maxn];
int st_i[maxn << 2][22], st_x[maxn << 2][22];
char s[maxn];

int qry_mi(int l, int r){
	if(l > r) return 0;
	int k = lgk[r - l + 1];
	return min(st_i[l][k], st_i[r - (1 << k) + 1][k]);
}

int qry_mx(int l, int r){
	if(l > r) return 0;
	int k = lgk[r - l + 1];
	return max(st_x[l][k], st_x[r - (1 << k) + 1][k]);
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	lgk[1] = 0;
	for(int i = 2 ; i <= 200000 ; ++i){
		lgk[i] = lgk[i >> 1] + 1;
	}
	T = read();
	while(T--){
		n = read(), m = read();
		scanf("%s", s + 1);
		for(int i = 1 ; i <= n ; ++i){
			if(s[i] == '-') a[i] = -1;
			else a[i] = 1;
		} 
		
		for(int i = 1 ; i <= n ; ++i){
			c[i] = c[i - 1] + a[i];
			st_i[i][0] = st_x[i][0] = c[i];
		}
		
		
		for(int j = 1 ; (1 << j) <= n ; ++j){
			for(int i = 1 ; i <= n ; ++i){
				st_i[i][j] = min(st_i[i][j - 1], st_i[i + (1 << (j - 1))][j - 1]);
				st_x[i][j] = max(st_x[i][j - 1], st_x[i + (1 << (j - 1))][j - 1]);
			}			
		}

//		for(int i = 1 ; i <= n ; ++i) printf("%d ", c[i]); printf("
");	
	
		int l, r; 
		for(int i = 1 ; i <= m ; ++i){
			l = read(), r = read();
//			printf("%d %d
", qry_mi(l, r), qry_mx(l, r));
			
			int lai = qry_mi(1, l - 1);
			int lax = qry_mx(1, l - 1);
			int rai = qry_mi(r + 1, n);
			int rax = qry_mx(r + 1, n);	
			
			int ansl = 0, ansr = 0;
			if(lai < 0) ansl = max(ansl, -lai);
			if(rai - (c[r] - c[l - 1]) < 0 && r < n) ansl = max(ansl, -rai + (c[r] - c[l - 1]));
			
			if(lax > 0) ansr = max(ansr, lax);
			if(rax - (c[r] - c[l - 1]) > 0 && r < n) ansr = max(ansr, rax - (c[r] - c[l - 1])); 
			
			printf("%d
", ansl + ansr + 1);
		}
	}
	return 0;
}