这场前 4 题难度不高,后 3 题抽时间看一下。
My Status
A
B
C
D
E
F
G
O
O
O
O
Ø
Ø
Ø
Description
Time Limit: 2 seconds
Memory Limit: 256 megabytes
You have an array a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a 1 , a 2 , … , a n . All a i a_i a i are positive integers.
In one step you can choose three distinct indices i i i , j j j , and k k k (i ≠ j i \neq j i = j ; i ≠ k i \neq k i = k ; j ≠ k j \neq k j = k ) and assign the sum of a j a_j a j and a k a_k a k to a i a_i a i , i. e. make a i = a j + a k a_i = a_j + a_k a i = a j + a k .
Can you make all a i a_i a i lower or equal to d d d using the operation above any number of times (possibly, zero)?
The first line contains a single integer t t t (1 ≤ t ≤ 2000 1 \le t \le 2000 1 ≤ t ≤ 2 0 0 0 ) — the number of test cases.
The first line of each test case contains two integers n n n and d d d (3 ≤ n ≤ 100 3 \le n \le 100 3 ≤ n ≤ 1 0 0 ; 1 ≤ d ≤ 100 1 \le d \le 100 1 ≤ d ≤ 1 0 0 ) — the number of elements in the array a a a and the value d d d .
The second line contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a 1 , a 2 , … , a n (1 ≤ a i ≤ 100 1 \le a_i \le 100 1 ≤ a i ≤ 1 0 0 ) — the array a a a .
Output
For each test case, print YES \texttt{YES} YES , if it’s possible to make all elements a i a_i a i less or equal than d d d using the operation above. Otherwise, print NO \texttt{NO} NO .
You may print each letter in any case (for example, YES \texttt{YES} YES , Yes \texttt{Yes} Yes , yes \texttt{yes} yes , yEs \texttt{yEs} yEs will all be recognized as positive answer).
Example
1 2 3 4 5 6 7 3 5 3 2 3 2 5 4 3 4 2 4 4 5 4 2 1 5 3 6
Output
Note
In the first test case, we can prove that we can’t make all a i ≤ 3 a_i \le 3 a i ≤ 3 .
In the second test case, all a i a_i a i are already less or equal than d = 4 d = 4 d = 4 .
In the third test case, we can, for example, choose i = 5 i = 5 i = 5 , j = 1 j = 1 j = 1 , k = 2 k = 2 k = 2 and make a 5 = a 1 + a 2 = 2 + 1 = 3 a_5 = a_1 + a_2 = 2 + 1 = 3 a 5 = a 1 + a 2 = 2 + 1 = 3 . Array a a a will become [ 2 , 1 , 5 , 3 , 3 ] [2, 1, 5, 3, 3] [ 2 , 1 , 5 , 3 , 3 ] .
After that we can make a 3 = a 5 + a 2 = 3 + 1 = 4 a_3 = a_5 + a_2 = 3 + 1 = 4 a 3 = a 5 + a 2 = 3 + 1 = 4 . Array will become [ 2 , 1 , 4 , 3 , 3 ] [2, 1, 4, 3, 3] [ 2 , 1 , 4 , 3 , 3 ] and all elements are less or equal than d = 4 d = 4 d = 4 .
Solution
先检查是否有所有 a i ≤ d a_i \leq d a i ≤ d 成立。
若不成立,则将 a a a 按升序排序,检查是否有 a 1 + a 2 ≤ d a_1 + a_2 \leq d a 1 + a 2 ≤ d 。若成立,则可用 a 1 + a 2 a_1 + a_2 a 1 + a 2 替换每个大于 d d d 的值,存在可行方案;否则不存在可行方案。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 #if __cplusplus < 201103L #include <cstdio> #include <cstring> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <set> #include <map> #include <vector> #include <string> #include <queue> using namespace std ; #define ffor(_var, _begin, _end, ...) \ for (__typeof__(_end) _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for (__typeof__(_rbegin) _var = _rbegin; _var > _rend; __VA_ARGS__) #define cfor(_var, _cbegin, _cend, ...) \ for (__typeof__(_cend) _var = _cbegin; _var != _cend; __VA_ARGS__) #else #include <bits/stdc++.h> using namespace std ; #define ffor(_var, _begin, _end, ...) \ for (decay<decltype (_end)>::type _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for (decay<decltype (_rbegin)>::type _var = _rbegin; _var > _rend; __VA_ARGS__) #endif typedef long long ll;typedef long double ld;#define ABS(x) ((x) > 0 ? (x) : -(x)) const int INF = 0x3f3f3f3f ; #ifdef __DEBUG__ #if defined _WIN32 #define _WINDEBUG #include <windows.h> inline std ::ostream& __YELLOW__(std ::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } inline std ::ostream& __WHITE__(std ::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE); return s; } inline std ::ostream& __RED__(std ::ostream &s){ HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } #elif defined __linux__ #define _LINUXDEBUG #define __YELLOW__ "\033[33;1m" #define __WHITE__ "\033[0m" #endif #endif #if defined _WINDEBUG || defined _LINUXDEBUG #define ar2vec(_begin, _end) \ vector <decay<iterator_traits<decltype (_begin)>::value_type>::type>(_begin, _end) #define debug(x...) \ do { cout << __YELLOW__ << #x << " -> "; err(x); } while(0) void err () { cout << __WHITE__ << endl ; }template <typename T, typename ... A>void err (T a, A... x) { cout << __RED__ << a << __YELLOW__ << ' ' ; err(x...); }template <template <typename ...> class T , typename t , typename ... A >void err (T <t> a , A ... x ) { for (auto & v : a) cout << __RED__ << v << __YELLOW__ << ' ' ; err(x...); }#else #define ar2vec(...) #define debug(...) #endif const int MAXN = 100 ;int a[MAXN + 10 ];int main () { ios::sync_with_stdio(false ); cin .tie(0 ); int t = 0 ; cin >> t; while (t--) { int n = 0 , d = 0 ; cin >> n >> d; for (int i = 1 ; i <= n; i++) cin >> a[i]; bool flag = true ; for (int i = 1 ; i <= n; i++) if (a[i] > d) { flag = false ; break ; } if (flag) { cout << "YES" << endl ; continue ; } sort(a + 1 , a + n + 1 ); if (a[1 ] + a[2 ] > d) cout << "NO" << endl ; else cout << "YES" << endl ; } return 0 ; }
Description
Time Limit: 2 seconds
Memory Limit: 256 megabytes
Let’s define a multiplication operation between a string a a a and a positive integer x x x : a ⋅ x a \cdot x a ⋅ x is the string that is a result of writing x x x copies of a a a one after another. For example, “abc \texttt{abc} abc ” ⋅ 2 = \cdot~2~= ⋅ 2 = “abcabc \texttt{abcabc} abcabc ”, “a \texttt{a} a ” ⋅ 5 = \cdot~5~= ⋅ 5 = “aaaaa \texttt{aaaaa} aaaaa ”.
A string a a a is divisible by another string b b b if there exists an integer x x x such that b ⋅ x = a b \cdot x = a b ⋅ x = a . For example, “abababab \texttt{abababab} abababab ” is divisible by “ab \texttt{ab} ab ”, but is not divisible by “ababab \texttt{ababab} ababab ” or “aa \texttt{aa} aa ”.
LCM of two strings s s s and t t t (defined as L C M ( s , t ) LCM(s, t) L C M ( s , t ) ) is the shortest non-empty string that is divisible by both s s s and t t t .
You are given two strings s s s and t t t . Find L C M ( s , t ) LCM(s, t) L C M ( s , t ) or report that it does not exist. It can be shown that if L C M ( s , t ) LCM(s, t) L C M ( s , t ) exists, it is unique.
The first line contains one integer q q q (1 ≤ q ≤ 2000 1 \le q \le 2000 1 ≤ q ≤ 2 0 0 0 ) — the number of test cases.
Each test case consists of two lines, containing strings s s s and t t t (1 ≤ ∣ s ∣ , ∣ t ∣ ≤ 20 1 \le |s|, |t| \le 20 1 ≤ ∣ s ∣ , ∣ t ∣ ≤ 2 0 ). Each character in each of these strings is either ‘a \texttt{a} a ’ or ‘b \texttt{b} b ’.
Output
For each test case, print L C M ( s , t ) LCM(s, t) L C M ( s , t ) if it exists; otherwise, print -1 \texttt{-1} -1 . It can be shown that if L C M ( s , t ) LCM(s, t) L C M ( s , t ) exists, it is unique.
Example
Output
Note
In the first test case, “baba \texttt{baba} baba ” = “baba \texttt{baba} baba ” ⋅ 1 = \cdot~1~= ⋅ 1 = “ba \texttt{ba} ba ” ⋅ 2 \cdot~2 ⋅ 2 .
In the second test case, “aaaaaa \texttt{aaaaaa} aaaaaa ” = “aa \texttt{aa} aa ” ⋅ 3 = \cdot~3~= ⋅ 3 = “aaa \texttt{aaa} aaa ” ⋅ 2 \cdot~2 ⋅ 2 .
Solution
注意到 s s s 和 t t t 的长度均不超过 20 20 2 0 ,因此直接模拟即可。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 #if __cplusplus < 201103L #include <cstdio> #include <cstring> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <set> #include <map> #include <vector> #include <string> #include <queue> using namespace std ; #define ffor(_var, _begin, _end, ...) \ for (__typeof__(_end) _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for (__typeof__(_rbegin) _var = _rbegin; _var > _rend; __VA_ARGS__) #define cfor(_var, _cbegin, _cend, ...) \ for (__typeof__(_cend) _var = _cbegin; _var != _cend; __VA_ARGS__) #else #include <bits/stdc++.h> using namespace std ; #define ffor(_var, _begin, _end, ...) \ for (decay<decltype (_end)>::type _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for (decay<decltype (_rbegin)>::type _var = _rbegin; _var > _rend; __VA_ARGS__) #endif typedef long long ll;typedef long double ld;#define ABS(x) ((x) > 0 ? (x) : -(x)) const int INF = 0x3f3f3f3f ; #ifdef __DEBUG__ #if defined _WIN32 #define _WINDEBUG #include <windows.h> inline std ::ostream& __YELLOW__(std ::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } inline std ::ostream& __WHITE__(std ::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE); return s; } inline std ::ostream& __RED__(std ::ostream &s){ HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } #elif defined __linux__ #define _LINUXDEBUG #define __YELLOW__ "\033[33;1m" #define __WHITE__ "\033[0m" #endif #endif #if defined _WINDEBUG || defined _LINUXDEBUG #define ar2vec(_begin, _end) \ vector <decay<iterator_traits<decltype (_begin)>::value_type>::type>(_begin, _end) #define debug(x...) \ do { cout << __YELLOW__ << #x << " -> "; err(x); } while(0) void err () { cout << __WHITE__ << endl ; }template <typename T, typename ... A>void err (T a, A... x) { cout << __RED__ << a << __YELLOW__ << ' ' ; err(x...); }template <template <typename ...> class T , typename t , typename ... A >void err (T <t> a , A ... x ) { for (auto & v : a) cout << __RED__ << v << __YELLOW__ << ' ' ; err(x...); }#else #define ar2vec(...) #define debug(...) #endif string getsub (string &s) { int n = s.length(); for (int i = 1 ; i <= n; i++) { if (n % i) continue ; string sub = s.substr(0 , i); bool flag = true ; for (int j = i; j < n; j += i) { if (sub != s.substr(j, i)) { flag = false ; break ; } } if (flag) return sub; } return string ("" ); } int main () { ios::sync_with_stdio(false ); cin .tie(0 ); int q = 0 ; cin >> q; while (q--) { string s, t; cin >> s >> t; string s_sub = getsub(s); string t_sub = getsub(t); debug(s_sub); debug(t_sub); if (s_sub != t_sub) cout << -1 << endl ; else { int s_num = s.length() / s_sub.length(); int t_sum = t.length() / t_sub.length(); int lcd = s_num * t_sum / __gcd(s_num, t_sum); debug(s_num, t_sum, lcd); for (int i = 1 ; i < lcd; i++) s_sub += t_sub; cout << s_sub << endl ; } } return 0 ; }
Description
Time Limit: 2 seconds
Memory Limit: 256 megabytes
You have a sequence a a a with n n n elements 1 , 2 , 3 , … , k − 1 , k , k − 1 , k − 2 , … , k − ( n − k ) 1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k) 1 , 2 , 3 , … , k − 1 , k , k − 1 , k − 2 , … , k − ( n − k ) (k ≤ n < 2 k k \le n < 2k k ≤ n < 2 k ).
Let’s call as inversion in a a a a pair of indices i < j i < j i < j such that a [ i ] > a [ j ] a[i] > a[j] a [ i ] > a [ j ] .
Suppose, you have some permutation p p p of size k k k and you build a sequence b b b of size n n n in the following manner: b [ i ] = p [ a [ i ] ] b[i] = p[a[i]] b [ i ] = p [ a [ i ] ] .
Your goal is to find such permutation p p p that the total number of inversions in b b b doesn’t exceed the total number of inversions in a a a , and b b b is lexicographically maximum .
Small reminder: the sequence of k k k integers is called a permutation if it contains all integers from 1 1 1 to k k k exactly once.
Another small reminder: a sequence s s s is lexicographically smaller than another sequence t t t , if either s s s is a prefix of t t t , or for the first i i i such that s i ≠ t i s_i \ne t_i s i = t i , s i < t i s_i < t_i s i < t i holds (in the first position that these sequences are different, s s s has smaller number than t t t ).
The first line contains a single integer t t t (1 ≤ t ≤ 1000 1 \le t \le 1000 1 ≤ t ≤ 1 0 0 0 ) — the number of test cases.
The first and only line of each test case contains two integers n n n and k k k (k ≤ n < 2 k k \le n < 2k k ≤ n < 2 k ; 1 ≤ k ≤ 1 0 5 1 \le k \le 10^5 1 ≤ k ≤ 1 0 5 ) — the length of the sequence a a a and its maximum.
It’s guaranteed that the total sum of k k k over test cases doesn’t exceed 1 0 5 10^5 1 0 5 .
Output
For each test case, print k k k integers — the permutation p p p which maximizes b b b lexicographically without increasing the total number of inversions.
It can be proven that p p p exists and is unique.
Example
Output
Note
In the first test case, the sequence a = [ 1 ] a = [1] a = [ 1 ] , there is only one permutation p = [ 1 ] p = [1] p = [ 1 ] .
In the second test case, the sequence a = [ 1 , 2 ] a = [1, 2] a = [ 1 , 2 ] . There is no inversion in a a a , so there is only one permutation p = [ 1 , 2 ] p = [1, 2] p = [ 1 , 2 ] which doesn’t increase the number of inversions.
In the third test case, a = [ 1 , 2 , 1 ] a = [1, 2, 1] a = [ 1 , 2 , 1 ] and has 1 1 1 inversion. If we use p = [ 2 , 1 ] p = [2, 1] p = [ 2 , 1 ] , then b = [ p [ a [ 1 ] ] , p [ a [ 2 ] ] , p [ a [ 3 ] ] ] = [ 2 , 1 , 2 ] b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2] b = [ p [ a [ 1 ] ] , p [ a [ 2 ] ] , p [ a [ 3 ] ] ] = [ 2 , 1 , 2 ] and also has 1 1 1 inversion.
In the fourth test case, a = [ 1 , 2 , 3 , 2 ] a = [1, 2, 3, 2] a = [ 1 , 2 , 3 , 2 ] , and since p = [ 1 , 3 , 2 ] p = [1, 3, 2] p = [ 1 , 3 , 2 ] then b = [ 1 , 3 , 2 , 3 ] b = [1, 3, 2, 3] b = [ 1 , 3 , 2 , 3 ] . Both a a a and b b b have 1 1 1 inversion and b b b is the lexicographically maximum.
Solution
考虑到 a a a 中的逆序列数目共有 ∑ i = 1 n − k = ( n − k ) ( n − k + 1 ) 2 \sum\limits_{i=1}^{n-k} = \dfrac{(n-k)(n-k+1)}{2} i = 1 ∑ n − k = 2 ( n − k ) ( n − k + 1 ) 个,全部由序列的后半部分 k , ( k − 1 ) , ⋯ , k − ( n − k ) k,(k-1),\cdots,k-(n-k) k , ( k − 1 ) , ⋯ , k − ( n − k ) 所贡献,因此只需要保证 b b b 中的逆序列构造方式和 a a a 相同即可。
因此构造 p = [ 1 , 2 , ⋯ , ( 2 k − n − 1 ) , k , ( k − 1 ) , ⋯ , k − ( n − k ) ] p = [1, 2, \cdots, (2k-n-1),k,(k-1),\cdots,k-(n-k)] p = [ 1 , 2 , ⋯ , ( 2 k − n − 1 ) , k , ( k − 1 ) , ⋯ , k − ( n − k ) ] 即可。容易发现 b b b 序列中的逆序列部分和 p p p 相同。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 #if __cplusplus < 201103L #include <cstdio> #include <cstring> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <set> #include <map> #include <vector> #include <string> #include <queue> using namespace std ; #define ffor(_var, _begin, _end, ...) \ for (__typeof__(_end) _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for (__typeof__(_rbegin) _var = _rbegin; _var > _rend; __VA_ARGS__) #define cfor(_var, _cbegin, _cend, ...) \ for (__typeof__(_cend) _var = _cbegin; _var != _cend; __VA_ARGS__) #else #include <bits/stdc++.h> using namespace std ; #define ffor(_var, _begin, _end, ...) \ for (decay<decltype (_end)>::type _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for (decay<decltype (_rbegin)>::type _var = _rbegin; _var > _rend; __VA_ARGS__) #endif typedef long long ll;typedef long double ld;#define ABS(x) ((x) > 0 ? (x) : -(x)) const int INF = 0x3f3f3f3f ; #ifdef __DEBUG__ #if defined _WIN32 #define _WINDEBUG #include <windows.h> inline std ::ostream& __YELLOW__(std ::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } inline std ::ostream& __WHITE__(std ::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE); return s; } inline std ::ostream& __RED__(std ::ostream &s){ HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } #elif defined __linux__ #define _LINUXDEBUG #define __YELLOW__ "\033[33;1m" #define __WHITE__ "\033[0m" #endif #endif #if defined _WINDEBUG || defined _LINUXDEBUG #define ar2vec(_begin, _end) \ vector <decay<iterator_traits<decltype (_begin)>::value_type>::type>(_begin, _end) #define debug(x...) \ do { cout << __YELLOW__ << #x << " -> "; err(x); } while(0) void err () { cout << __WHITE__ << endl ; }template <typename T, typename ... A>void err (T a, A... x) { cout << __RED__ << a << __YELLOW__ << ' ' ; err(x...); }template <template <typename ...> class T , typename t , typename ... A >void err (T <t> a , A ... x ) { for (auto & v : a) cout << __RED__ << v << __YELLOW__ << ' ' ; err(x...); }#else #define ar2vec(...) #define debug(...) #endif const int MAXN = 1e5 ;int p[MAXN + 10 ];int main () { ios::sync_with_stdio(false ); cin .tie(0 ); int t = 0 ; cin >> t; while (t--) { int n = 0 , k = 0 ; cin >> n >> k; for (int i = 1 ; i <= 2 * k - n - 1 ; i++) p[i] = i; for (int i = 2 * k - n, cnt = k; i <= k; i++) p[i] = cnt--; for (int i = 1 ; i <= k; i++) if (i == k) cout << p[i] << endl ; else cout << p[i] << " " ; } return 0 ; }
Description
Time Limit: 2 seconds
Memory Limit: 256 megabytes
You are given a program that consists of n n n instructions. Initially a single variable x x x is assigned to 0 0 0 . Afterwards, the instructions are of two types:
increase x x x by 1 1 1 ;
decrease x x x by 1 1 1 .
You are given m m m queries of the following format:
query l l l r r r — how many distinct values is x x x assigned to if all the instructions between the l l l -th one and the r r r -th one inclusive are ignored and the rest are executed without changing the order?
The first line contains a single integer t t t (1 ≤ t ≤ 1000 1 \le t \le 1000 1 ≤ t ≤ 1 0 0 0 ) — the number of testcases.
Then the description of t t t testcases follows.
The first line of each testcase contains two integers n n n and m m m (1 ≤ n , m ≤ 2 ⋅ 1 0 5 1 \le n, m \le 2 \cdot 10^5 1 ≤ n , m ≤ 2 ⋅ 1 0 5 ) — the number of instructions in the program and the number of queries.
The second line of each testcase contains a program — a string of n n n characters: each character is either ‘+ \texttt{+} + ’ or ‘- \texttt{-} - ’ — increment and decrement instruction, respectively.
Each of the next m m m lines contains two integers l l l and r r r (1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1 ≤ l ≤ r ≤ n ) — the description of the query.
The sum of n n n over all testcases doesn’t exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2 ⋅ 1 0 5 . The sum of m m m over all testcases doesn’t exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2 ⋅ 1 0 5 .
Output
For each testcase print m m m integers — for each query l l l , r r r print the number of distinct values variable x x x is assigned to if all the instructions between the l l l -th one and the r r r -th one inclusive are ignored and the rest are executed without changing the order.
Example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 4 4 3 3 4 2 3 2 1 2 2 2
Note
The instructions that remain for each query of the first testcase are:
empty program — x x x was only equal to 0 0 0 ;
“- \texttt{-} - ” — x x x had values 0 0 0 and − 1 -1 − 1 ;
“---+ \texttt{---+} ---+ ” — x x x had values 0 0 0 , − 1 -1 − 1 , − 2 -2 − 2 , − 3 -3 − 3 , − 2 -2 − 2 — there are 4 4 4 distinct values among them;
“+--+--+ \texttt{+--+--+} +--+--+ ” — the distinct values are 1 1 1 , 0 0 0 , − 1 -1 − 1 , − 2 -2 − 2 .
Solution
首先考虑到在一段连续的指令序列中,x x x 的赋值序列是连续的;这是因为每条指令只能为 x x x 加 1 1 1 或者减 1 1 1 。因此,只需要维护该段指令序列中 x x x 的最大值和最小值。
考虑维护一个如下的数据结构:
1 2 3 4 5 6 7 8 9 10 11 struct Data { int maxx, minn, add; Data(int _max = 0 , int _min = 0 , int _add = 0 ): maxx(_max), minn(_min), add(_add) {} Data operator + (const Data &d) { return Data(max (maxx, add + d.maxx), min (minn, add + d.minn), add + d.add); } }; #endif
其中 maxx
和 minn
分别为在指令序列此处 x x x 的最大值和最小值,add
代表