D. Program(思维)

大家好，欢迎来到IT知识分享网。

Problem – D – Codeforces

给你一个由n条指令组成的程序。最初，一个变量z被赋值为0。之后，指令有两种类型:将x增加1;x减去1。你有m个查询，格式如下:查询l r-如果忽略第l条和第r条之间的所有指令，其余的指令在不改变顺序的情况下执行，z被赋给了多少个不同的值?输入第一行包含一个整数t (1 <t< 1000) -测试用例的数量。然后对t个测试用例进行描述。每个测试用例的第一行包含两个整数n和m (1 < n, m < 2 – 105)——程序中指令的数量和查询的数量。每个测试用例的第二行包含一个程序——一个n个字符的字符串:每个字符分别是’+’或’-‘——递增和递减指令。接下来的m行每一行包含两个整数r (1 <l<r <n)-查询的描述。所有测试用例的n和不超过2- 105。m对所有测试用例的和不超过2 – 105。输出对于每个测试用例打印m个整数-对于每个查询l，如果忽略第l个和第r个之间的所有指令，并且在不改变顺序的情况下执行其余指令，则打印变量z赋给的不同值的数量。

Example

input

Copy

2 8 4 -+--+--+ 1 8 2 8 2 5 1 1 4 10 +-++ 1 1 1 2 2 2 1 3 2 3 3 3 1 4 2 4 3 4 4 4 

output

Copy

1 2 4 4 3 

#include <cstdio> #include <cstring> #include <algorithm> #include<iostream> #include<vector> #include<set> #include<map> using namespace std; typedef long long ll; //#define int long long int mil[]; int mal[]; int mir[]; int mar[]; int a[]; void solve() { int n,m; string s; cin >> n >> m >> s;; s = " " + s; for(int i = 1;i <= n + 10;i++) { mil[i] = 1e9; mar[i] = 0; mir[i] = 1e9; mal[i] = 0; } for(int i = 1;i <= n;i++) { if(s[i] == '-') { a[i] = a[i - 1] - 1; } else { a[i] = a[i - 1] + 1; } mal[i] = max(mal[i - 1],a[i]); mil[i] = min(mil[i - 1],a[i]); } mar[n + 1] = a[n],mir[n + 1] = a[n]; for(int i = n;i >= 1;i--) { mar[i] = max(mar[i + 1],a[i]); mir[i] = min(mir[i + 1],a[i]); } while(m--) { int l,r; cin >>l >>r; int ans = 0; if(l == 1&&r == n) { ans = 1; } int x = mil[l - 1]; int y = mal[l - 1]; int o = mir[r + 1]; int p = mar[r + 1]; int k = a[r] - a[l - 1]; o -= k,p -= k; if(x > o) { swap(x,o); swap(y,p); } ans = max(y,p) - x + 1; cout << ans <<"\n"; } } signed main() { // ios::sync_with_stdio(0); // cin.tie(0);cout.tie(0); int t = 1; cin >> t; while(t--) { solve(); } }

3 4 2 3 2 1 2 2 2

 请注意对于第一个测试用例的每个查询，剩下的指令是:1. 空程序-只等于0;2. “-” – æ值为0和1;3.“——+”- æ有值0，-1，-2，-3，-2 -其中有4个不同的值;4. “+——+——+” -不同的值为1,0，- 1，-2。

题解:
我们可以预处理出来前缀的最大值最小值,和后缀的最大值和最小值

对答案的贡献应该就是最大值减最小值

但是这两部分可能会不重合,那么我们让后缀的最大值和最小值减去,中间a[r] – a[l-1]的影响,

这样两个最值区间一定重合,最大减最小即可