比赛链接
神奇的数据结构场 \(\dots\)
A - Bestie You are given an array \(a\) consisting of \(n\) integers \(a_1, a_2, \ldots, a_n\) . Friends asked you to make the greatest common divisor (GCD) of all numbers in the array equal to \(1\) . In one operation, you can do the following:
Select an arbitrary index in the array \(1 \leq i \leq n\) ; Make \(a_i = \gcd(a_i, i)\) , where \(\gcd(x, y)\) denotes the GCD of integers \(x\) and \(y\) . The cost of such an operation is \(n - i + 1\) . You need to find the minimum total cost of operations we need to perform so that the GCD of the all array numbers becomes equal to \(1\) .
Each test consists of multiple test cases. The first line contains an integer \(t\) (\(1 \leq t \leq 5\,000\) ) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer \(n\) (\(1 \leq n \leq 20\) ) — the length of the array.
The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\) ) — the elements of the array.
Output For each test case, output a single integer — the minimum total cost of operations that will need to be performed so that the GCD of all numbers in the array becomes equal to \(1\) .
We can show that it's always possible to do so.
Example 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 9 1 1 1 2 2 2 4 3 3 6 9 4 5 10 15 20 5 120 60 80 40 80 6 150 90 180 120 60 30 6 2 4 6 9 12 18 6 30 60 90 120 125 125
output Note In the first test case, the GCD of the entire array is already equal to \(1\) , so there is no need to perform operations.
In the second test case, select \(i = 1\) . After this operation, \(a_1 = \gcd(2, 1) = 1\) . The cost of this operation is \(1\) .
In the third test case, you can select \(i = 1\) , after that the array \(a\) will be equal to \([1, 4]\) . The GCD of this array is \(1\) , and the total cost is \(2\) .
In the fourth test case, you can select \(i = 2\) , after that the array \(a\) will be equal to \([3, 2, 9]\) . The GCD of this array is \(1\) , and the total cost is \(2\) .
In the sixth test case, you can select \(i = 4\) and \(i = 5\) , after that the array \(a\) will be equal to \([120, 60, 80, 4, 5]\) . The GCD of this array is \(1\) , and the total cost is \(3\) .
思路与做法 注意到 \(\gcd(x,x+1)=1\) , 故答案不超过 3, 简单讨论下就行了
代码参考
Show code
CodeForces_1732A view raw 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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 #include <bits/stdc++.h> template <class Tp >using vc = std::vector<Tp>;struct CustomHash { static uint64_t splitmix64 (uint64_t x) x += 0x9e3779b97f4a7c15 ; x = (x ^ (x >> 30 )) * 0xbf58476d1ce4e5b9 ; x = (x ^ (x >> 27 )) * 0x94d049bb133111eb ; return x ^ (x >> 31 ); } size_t operator () (uint64_t x) const static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now ().time_since_epoch ().count (); return splitmix64 (x + FIXED_RANDOM); } }; using i64 = int64_t ;#define for_(i, l, r, vars...) \ for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \ i <= i##end; \ ++i) #define foreach_ref_(i, container) for (auto &i : (container)) #define run_exec_(expressions, post_process) \ { \ expressions; \ post_process; \ } #define run_return_void_(expressions) run_exec_(expressions, return) #define read_var_(type, name) \ type name; \ std::cin >> name #define read_container_(type, name, size) \ type name(size); \ foreach_ref_(i, name) std::cin >> i template <class Tp >constexpr auto chkmin (Tp &a, Tp b) -> bool return b < a ? a = b, true : false ; } template <class Tp >constexpr auto chkmax (Tp &a, Tp b) -> bool return a < b ? a = b, true : false ; } template <class Tp >constexpr auto ispow2 (Tp i) -> bool return i && (i & -i) == i; } #define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple> > namespace tuple_detail_ {template <std::size_t Begin, class Tuple , std::size_t ... Is>constexpr auto subtuple_impl_ (Tuple &&t, std::index_sequence<Is...>) return std::make_tuple (std::get <Is + Begin>(t)...); } template <class Tuple , class BinOp , std::size_t ... Is>constexpr auto apply2_impl_ (BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) return std::make_tuple ( std::forward<BinOp>(f)(std::get <Is>(lhs), std::get <Is>(rhs))...); } } template <std::size_t Begin, std::size_t Len, class Tuple >constexpr auto subtuple (Tuple &&t) static_assert (Begin <= TPL_SIZE_ (Tuple) && Len <= TPL_SIZE_ (Tuple) && Begin + Len <= TPL_SIZE_ (Tuple), "Out of range" ); return tuple_detail_::subtuple_impl_ <Begin>(t, std::make_index_sequence <Len>()); } template <std::size_t Pos, class Tp , class Tuple >constexpr auto tuple_push (Tp &&v, Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), std::make_tuple (v), subtuple <Pos, TPL_SIZE_ (Tuple) - Pos>(t)); } template <class Tp , class Tuple >constexpr auto tuple_push_front (Tp &&v, Tuple &&t) return tuple_push <0 >(v, t); } template <class Tp , class Tuple >constexpr auto tuple_push_back (Tp &&v, Tuple &&t) return tuple_push <TPL_SIZE_ (Tuple)>(v, t); } template <std::size_t Pos, class Tuple >constexpr auto tuple_pop (Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), subtuple <Pos + 1 , TPL_SIZE_ (Tuple) - Pos - 1 >(t)); } template <class Tuple >constexpr auto tuple_pop_front (Tuple &&t) return tuple_pop <0 >(t); } template <class Tuple >constexpr auto tuple_pop_back (Tuple &&t) return tuple_pop <TPL_SIZE_ (Tuple) - 1 >(t); } template <class Tuple , class BinOp >constexpr auto apply2 (BinOp &&f, Tuple &&lhs, Tuple &&rhs) return tuple_detail_::apply2_impl_ ( f, lhs, rhs, std::make_index_sequence <TPL_SIZE_ (Tuple)>()); } #define OO_PTEQ_(op) \ template <class Tp, class Up> \ constexpr auto operator op(std::pair<Tp, Up> lhs, \ const std::pair<Tp, Up> &rhs) { \ return {lhs.first op rhs.first, lhs.second op rhs.second}; \ } \ template <class... Ts> \ constexpr auto operator op(std::tuple<Ts...> const &lhs, \ std::tuple<Ts...> const &rhs) { \ return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs); \ } \ template <class Tp, class Up> \ constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs, \ const std::pair<Tp, Up> &rhs) { \ lhs.first op## = rhs.first; \ lhs.second op## = rhs.second; \ return lhs; \ } \ template <class... Ts> \ constexpr auto operator op##=(std::tuple<Ts...> &lhs, \ const std::tuple<Ts...> &rhs) { \ return lhs = lhs op rhs; \ } OO_PTEQ_ (+)OO_PTEQ_ (-)OO_PTEQ_ (*)OO_PTEQ_ (/)OO_PTEQ_ (%)OO_PTEQ_ (&)OO_PTEQ_ (|)OO_PTEQ_ (^)OO_PTEQ_ (<<)OO_PTEQ_ (>>)#undef OO_PTEQ_ #undef TPL_SIZE_ template <class Tp , class Up >std::istream &operator >>(std::istream &is, std::pair<Tp, Up> &p) { return is >> p.first >> p.second; } template <class Tp , class Up >std::ostream &operator <<(std::ostream &os, const std::pair<Tp, Up> &p) { return os << p.first << ' ' << p.second; } template <typename ... Ts>std::istream &operator >>(std::istream &is, std::tuple<Ts...> &p) { std::apply ([&](Ts &...targs) { ((is >> targs), ...); }, p); return is; } template <typename ... Ts>std::ostream &operator <<(std::ostream &os, const std::tuple<Ts...> &p) { std::apply ( [&](Ts const &...targs) { std::size_t n{0 }; ((os << targs << (++n != sizeof ...(Ts) ? " " : "" )), ...); }, p); return os; } template <class Ch , class Tr , class Ct , std::enable_if_t <std::is_same_v<decltype (std::declval <Ct>().begin ()), typename Ct::iterator> && std::is_same_v<decltype (std::declval <Ct>().end ()), typename Ct::iterator>> * = nullptr > std::basic_ostream<Ch, Tr> &operator <<(std::basic_ostream<Ch, Tr> &os, const Ct &x) { if (x.begin () == x.end ()) return os; for (auto it = x.begin (); it != x.end () - 1 ; ++it) os << *it << ' ' ; os << x.back (); return os; } using namespace std;auto solve ([[maybe_unused]] int t_ = 0 ) -> void read_var_ (i64, n); read_container_ (vc<i64>, a, n); if (n == 1 ) run_return_void_ (cout << (a[0 ] > 1 ) << '\n' ); i64 g = a[0 ]; for_(i, 1 , n - 1 ) g = gcd (g, a[i]); if (g == 1 ) run_return_void_ (cout << "0\n" ); if (gcd (g, n) == 1 ) run_return_void_ (cout << "1\n" ); if (gcd (g, n - 1 ) == 1 ) run_return_void_ (cout << "2\n" ); cout << "3\n" ; } int main () std::ios::sync_with_stdio (false ); std::cin.tie (nullptr ); int i_ = 0 ; int t_ = 0 ; std::cin >> t_; for (i_ = 0 ; i_ < t_; ++i_) solve (i_); return 0 ; }
B - Ugu A binary string is a string consisting only of the characters 0 and 1. You are given a binary string \(s_1 s_2 \ldots s_n\) . It is necessary to make this string non-decreasing in the least number of operations. In other words, each character should be not less than the previous. In one operation, you can do the following:
Select an arbitrary index \(1 \leq i \leq n\) in the string; For all \(j \geq i\) , change the value in the \(j\) -th position to the opposite, that is, if \(s_j = 1\) , then make \(s_j = 0\) , and vice versa. What is the minimum number of operations needed to make the string non-decreasing?
Each test consists of multiple test cases. The first line contains an integer \(t\) (\(1 \leq t \leq 10^4\) ) — the number of test cases. The description of test cases follows.
The first line of each test cases a single integer \(n\) (\(1 \leq n \leq 10^5\) ) — the length of the string.
The second line of each test case contains a binary string \(s\) of length \(n\) .
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\) .
Output For each test case, output a single integer — the minimum number of operations that are needed to make the string non-decreasing.
Example 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 8 1 1 2 10 3 101 4 1100 5 11001 6 100010 10 0000110000 7 0101010
output Note In the first test case, the string is already non-decreasing.
In the second test case, you can select \(i = 1\) and then \(s = \mathtt{01}\) .
In the third test case, you can select \(i = 1\) and get \(s = \mathtt{010}\) , and then select \(i = 2\) . As a result, we get \(s = \mathtt{001}\) , that is, a non-decreasing string.
In the sixth test case, you can select \(i = 5\) at the first iteration and get \(s = \mathtt{100001}\) . Then choose \(i = 2\) , then \(s = \mathtt{111110}\) . Then we select \(i = 1\) , getting the non-decreasing string \(s = \mathtt{000001}\) .
思路与做法 简单扫一遍就行，注意特判全为 0 的情况
代码参考
Show code
CodeForces_1732B view raw 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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 #include <bits/stdc++.h> struct CustomHash { static uint64_t splitmix64 (uint64_t x) x += 0x9e3779b97f4a7c15 ; x = (x ^ (x >> 30 )) * 0xbf58476d1ce4e5b9 ; x = (x ^ (x >> 27 )) * 0x94d049bb133111eb ; return x ^ (x >> 31 ); } size_t operator () (uint64_t x) const static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now ().time_since_epoch ().count (); return splitmix64 (x + FIXED_RANDOM); } }; using i64 = int64_t ;#define read_var_(type, name) \ type name; \ std::cin >> name template <class Tp >constexpr auto chkmin (Tp &a, Tp b) -> bool return b < a ? a = b, true : false ; } template <class Tp >constexpr auto chkmax (Tp &a, Tp b) -> bool return a < b ? a = b, true : false ; } template <class Tp >constexpr auto ispow2 (Tp i) -> bool return i && (i & -i) == i; } #define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple> > namespace tuple_detail_ {template <std::size_t Begin, class Tuple , std::size_t ... Is>constexpr auto subtuple_impl_ (Tuple &&t, std::index_sequence<Is...>) return std::make_tuple (std::get <Is + Begin>(t)...); } template <class Tuple , class BinOp , std::size_t ... Is>constexpr auto apply2_impl_ (BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) return std::make_tuple ( std::forward<BinOp>(f)(std::get <Is>(lhs), std::get <Is>(rhs))...); } } template <std::size_t Begin, std::size_t Len, class Tuple >constexpr auto subtuple (Tuple &&t) static_assert (Begin <= TPL_SIZE_ (Tuple) && Len <= TPL_SIZE_ (Tuple) && Begin + Len <= TPL_SIZE_ (Tuple), "Out of range" ); return tuple_detail_::subtuple_impl_ <Begin>(t, std::make_index_sequence <Len>()); } template <std::size_t Pos, class Tp , class Tuple >constexpr auto tuple_push (Tp &&v, Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), std::make_tuple (v), subtuple <Pos, TPL_SIZE_ (Tuple) - Pos>(t)); } template <class Tp , class Tuple >constexpr auto tuple_push_front (Tp &&v, Tuple &&t) return tuple_push <0 >(v, t); } template <class Tp , class Tuple >constexpr auto tuple_push_back (Tp &&v, Tuple &&t) return tuple_push <TPL_SIZE_ (Tuple)>(v, t); } template <std::size_t Pos, class Tuple >constexpr auto tuple_pop (Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), subtuple <Pos + 1 , TPL_SIZE_ (Tuple) - Pos - 1 >(t)); } template <class Tuple >constexpr auto tuple_pop_front (Tuple &&t) return tuple_pop <0 >(t); } template <class Tuple >constexpr auto tuple_pop_back (Tuple &&t) return tuple_pop <TPL_SIZE_ (Tuple) - 1 >(t); } template <class Tuple , class BinOp >constexpr auto apply2 (BinOp &&f, Tuple &&lhs, Tuple &&rhs) return tuple_detail_::apply2_impl_ ( f, lhs, rhs, std::make_index_sequence <TPL_SIZE_ (Tuple)>()); } #define OO_PTEQ_(op) \ template <class Tp, class Up> \ constexpr auto operator op(std::pair<Tp, Up> lhs, \ const std::pair<Tp, Up> &rhs) { \ return {lhs.first op rhs.first, lhs.second op rhs.second}; \ } \ template <class... Ts> \ constexpr auto operator op(std::tuple<Ts...> const &lhs, \ std::tuple<Ts...> const &rhs) { \ return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs); \ } \ template <class Tp, class Up> \ constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs, \ const std::pair<Tp, Up> &rhs) { \ lhs.first op## = rhs.first; \ lhs.second op## = rhs.second; \ return lhs; \ } \ template <class... Ts> \ constexpr auto operator op##=(std::tuple<Ts...> &lhs, \ const std::tuple<Ts...> &rhs) { \ return lhs = lhs op rhs; \ } OO_PTEQ_ (+)OO_PTEQ_ (-)OO_PTEQ_ (*)OO_PTEQ_ (/)OO_PTEQ_ (%)OO_PTEQ_ (&)OO_PTEQ_ (|)OO_PTEQ_ (^)OO_PTEQ_ (<<)OO_PTEQ_ (>>)#undef OO_PTEQ_ #undef TPL_SIZE_ template <class Tp , class Up >std::istream &operator >>(std::istream &is, std::pair<Tp, Up> &p) { return is >> p.first >> p.second; } template <class Tp , class Up >std::ostream &operator <<(std::ostream &os, const std::pair<Tp, Up> &p) { return os << p.first << ' ' << p.second; } template <typename ... Ts>std::istream &operator >>(std::istream &is, std::tuple<Ts...> &p) { std::apply ([&](Ts &...targs) { ((is >> targs), ...); }, p); return is; } template <typename ... Ts>std::ostream &operator <<(std::ostream &os, const std::tuple<Ts...> &p) { std::apply ( [&](Ts const &...targs) { std::size_t n{0 }; ((os << targs << (++n != sizeof ...(Ts) ? " " : "" )), ...); }, p); return os; } template <class Ch , class Tr , class Ct , std::enable_if_t <std::is_same_v<decltype (std::declval <Ct>().begin ()), typename Ct::iterator> && std::is_same_v<decltype (std::declval <Ct>().end ()), typename Ct::iterator>> * = nullptr > std::basic_ostream<Ch, Tr> &operator <<(std::basic_ostream<Ch, Tr> &os, const Ct &x) { if (x.begin () == x.end ()) return os; for (auto it = x.begin (); it != x.end () - 1 ; ++it) os << *it << ' ' ; os << x.back (); return os; } using namespace std;auto solve ([[maybe_unused]] int t_ = 0 ) -> void read_var_ (i64, n); read_var_ (string, s); char ch = '1' ; int cnt = 0 ; for (char i : s) if (i == ch) { ++cnt; ch ^= 1 ; } cout << max (0 , cnt - 1 ) << '\n' ; } int main () std::ios::sync_with_stdio (false ); std::cin.tie (nullptr ); int i_ = 0 ; int t_ = 0 ; std::cin >> t_; for (i_ = 0 ; i_ < t_; ++i_) solve (i_); return 0 ; }
C1 - Sheikh (Easy version) This is the easy version of the problem. The only difference is that in this version \(q = 1\) .
You are given an array of integers \(a_1, a_2, \ldots, a_n\) .
The cost of a subsegment of the array \([l, r]\) , \(1 \leq l \leq r \leq n\) , is the value \(f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)\) , where \(\operatorname{sum}(l, r) = a*l + a*{l+1} + \ldots + a*r\) , and \(\operatorname{xor}(l, r) = a_l \oplus a*{l+1} \oplus \ldots \oplus a_r\) (\(\oplus\) stands for bitwise XOR ).
You will have \(q = 1\) query. Each query is given by a pair of numbers \(L_i\) , \(R_i\) , where \(1 \leq L_i \leq R_i \leq n\) . You need to find the subsegment \([l, r]\) , \(L_i \leq l \leq r \leq R_i\) , with maximum value \(f(l, r)\) . If there are several answers, then among them you need to find a subsegment with the minimum length, that is, the minimum value of \(r - l + 1\) .
Each test consists of multiple test cases. The first line contains an integer \(t\) (\(1 \leq t \leq 10^4\) ) — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers \(n\) and \(q\) (\(1 \leq n \leq 10^5\) , \(q = 1\) ) — the length of the array and the number of queries.
The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq 10^9\) ) — array elements.
\(i\) -th of the next \(q\) lines of each test case contains two integers \(L_i\) and \(R_i\) (\(1 \leq L_i \leq R_i \leq n\) ) — the boundaries in which we need to find the segment.
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\) .
It is guaranteed that \(L_1 = 1\) and \(R_1 = n\) .
Output For each test case print \(q\) pairs of numbers \(L_i \leq l \leq r \leq R_i\) such that the value \(f(l, r)\) is maximum and among such the length \(r - l + 1\) is minimum. If there are several correct answers, print any of them.
Example 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 6 1 1 0 1 1 2 1 5 10 1 2 3 1 0 2 4 1 3 4 1 0 12 8 3 1 4 5 1 21 32 32 32 10 1 5 7 1 0 1 0 1 0 1 0 1 7
output Note In the first test case, \(f(1, 1) = 0 - 0 = 0\) .
In the second test case, \(f(1, 1) = 5 - 5 = 0\) , \(f(2, 2) = 10 - 10 = 0\) . Note that \(f(1, 2) = (10 + 5) - (10 \oplus 5) = 0\) , but we need to find a subsegment with the minimum length among the maximum values of \(f(l, r)\) . So, only segments \([1, 1]\) and \([2, 2]\) are the correct answers.
In the fourth test case, \(f(2, 3) = (12 + 8) - (12 \oplus 8) = 16\) .
There are two correct answers in the fifth test case, since \(f(2, 3) = f(3, 4)\) and their lengths are equal.
思路与做法 注意到 \(f(l,r)\leq f(l,r+1)\) , 所以我们枚举 \(l\) 然后二分出最小的 \(r\) 即可
代码参考
Show code
CodeForces_1732C1 view raw 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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 #include <bits/stdc++.h> template <class Tp >using pi = std::pair<Tp, Tp>;template <class Tp >using vc = std::vector<Tp>;struct CustomHash { static uint64_t splitmix64 (uint64_t x) x += 0x9e3779b97f4a7c15 ; x = (x ^ (x >> 30 )) * 0xbf58476d1ce4e5b9 ; x = (x ^ (x >> 27 )) * 0x94d049bb133111eb ; return x ^ (x >> 31 ); } size_t operator () (uint64_t x) const static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now ().time_since_epoch ().count (); return splitmix64 (x + FIXED_RANDOM); } }; using i64 = int64_t ;using pii64 = pi<i64>;#define for_(i, l, r, vars...) \ for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \ i <= i##end; \ ++i) #define all_(a) (a).begin(), (a).end() #define read_var_(type, name) \ type name; \ std::cin >> name template <class Tp >constexpr auto chkmin (Tp &a, Tp b) -> bool return b < a ? a = b, true : false ; } template <class Tp >constexpr auto chkmax (Tp &a, Tp b) -> bool return a < b ? a = b, true : false ; } template <class Tp >constexpr auto ispow2 (Tp i) -> bool return i && (i & -i) == i; } #define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple> > namespace tuple_detail_ {template <std::size_t Begin, class Tuple , std::size_t ... Is>constexpr auto subtuple_impl_ (Tuple &&t, std::index_sequence<Is...>) return std::make_tuple (std::get <Is + Begin>(t)...); } template <class Tuple , class BinOp , std::size_t ... Is>constexpr auto apply2_impl_ (BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) return std::make_tuple ( std::forward<BinOp>(f)(std::get <Is>(lhs), std::get <Is>(rhs))...); } } template <std::size_t Begin, std::size_t Len, class Tuple >constexpr auto subtuple (Tuple &&t) static_assert (Begin <= TPL_SIZE_ (Tuple) && Len <= TPL_SIZE_ (Tuple) && Begin + Len <= TPL_SIZE_ (Tuple), "Out of range" ); return tuple_detail_::subtuple_impl_ <Begin>(t, std::make_index_sequence <Len>()); } template <std::size_t Pos, class Tp , class Tuple >constexpr auto tuple_push (Tp &&v, Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), std::make_tuple (v), subtuple <Pos, TPL_SIZE_ (Tuple) - Pos>(t)); } template <class Tp , class Tuple >constexpr auto tuple_push_front (Tp &&v, Tuple &&t) return tuple_push <0 >(v, t); } template <class Tp , class Tuple >constexpr auto tuple_push_back (Tp &&v, Tuple &&t) return tuple_push <TPL_SIZE_ (Tuple)>(v, t); } template <std::size_t Pos, class Tuple >constexpr auto tuple_pop (Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), subtuple <Pos + 1 , TPL_SIZE_ (Tuple) - Pos - 1 >(t)); } template <class Tuple >constexpr auto tuple_pop_front (Tuple &&t) return tuple_pop <0 >(t); } template <class Tuple >constexpr auto tuple_pop_back (Tuple &&t) return tuple_pop <TPL_SIZE_ (Tuple) - 1 >(t); } template <class Tuple , class BinOp >constexpr auto apply2 (BinOp &&f, Tuple &&lhs, Tuple &&rhs) return tuple_detail_::apply2_impl_ ( f, lhs, rhs, std::make_index_sequence <TPL_SIZE_ (Tuple)>()); } #define OO_PTEQ_(op) \ template <class Tp, class Up> \ constexpr auto operator op(std::pair<Tp, Up> lhs, \ const std::pair<Tp, Up> &rhs) { \ return {lhs.first op rhs.first, lhs.second op rhs.second}; \ } \ template <class... Ts> \ constexpr auto operator op(std::tuple<Ts...> const &lhs, \ std::tuple<Ts...> const &rhs) { \ return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs); \ } \ template <class Tp, class Up> \ constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs, \ const std::pair<Tp, Up> &rhs) { \ lhs.first op## = rhs.first; \ lhs.second op## = rhs.second; \ return lhs; \ } \ template <class... Ts> \ constexpr auto operator op##=(std::tuple<Ts...> &lhs, \ const std::tuple<Ts...> &rhs) { \ return lhs = lhs op rhs; \ } OO_PTEQ_ (+)OO_PTEQ_ (-)OO_PTEQ_ (*)OO_PTEQ_ (/)OO_PTEQ_ (%)OO_PTEQ_ (&)OO_PTEQ_ (|)OO_PTEQ_ (^)OO_PTEQ_ (<<)OO_PTEQ_ (>>)#undef OO_PTEQ_ #undef TPL_SIZE_ template <class Tp , class Up >std::istream &operator >>(std::istream &is, std::pair<Tp, Up> &p) { return is >> p.first >> p.second; } template <class Tp , class Up >std::ostream &operator <<(std::ostream &os, const std::pair<Tp, Up> &p) { return os << p.first << ' ' << p.second; } template <typename ... Ts>std::istream &operator >>(std::istream &is, std::tuple<Ts...> &p) { std::apply ([&](Ts &...targs) { ((is >> targs), ...); }, p); return is; } template <typename ... Ts>std::ostream &operator <<(std::ostream &os, const std::tuple<Ts...> &p) { std::apply ( [&](Ts const &...targs) { std::size_t n{0 }; ((os << targs << (++n != sizeof ...(Ts) ? " " : "" )), ...); }, p); return os; } template <class Ch , class Tr , class Ct , std::enable_if_t <std::is_same_v<decltype (std::declval <Ct>().begin ()), typename Ct::iterator> && std::is_same_v<decltype (std::declval <Ct>().end ()), typename Ct::iterator>> * = nullptr > std::basic_ostream<Ch, Tr> &operator <<(std::basic_ostream<Ch, Tr> &os, const Ct &x) { if (x.begin () == x.end ()) return os; for (auto it = x.begin (); it != x.end () - 1 ; ++it) os << *it << ' ' ; os << x.back (); return os; } using namespace std;auto solve ([[maybe_unused]] int t_ = 0 ) -> void read_var_ (i64, n); read_var_ (i64, q); vc<i64> a (n + 1 ) , psum (n + 1 ) , pxor (n + 1 ) ; for_(i, 1 , n) cin >> a[i]; int _; cin >> _ >> _; partial_sum (all_ (a), psum.begin ()); partial_sum (all_ (a), pxor.begin (), bit_xor<>()); auto calc = [&](i64 l, i64 r) -> i64 { return (psum[r] - psum[l - 1 ]) - (pxor[r] ^ pxor[l - 1 ]); }; auto bs = [&](i64 l) { i64 l_ = l; i64 r = n, mid, ans = r; i64 pans = calc (l_, r); while (l <= r) { mid = r - (r - l) / 2 ; if (calc (l_, mid) == pans) { ans = mid; r = mid - 1 ; } else l = mid + 1 ; } return ans; }; pii64 ans_w{INT64_MIN, INT64_MIN}, ans{0 , 0 }; for_(l, 1 , n, r) { r = bs (l); if (pii64 tmp{calc (l, r), l - r}; ans_w < tmp) { ans_w = tmp; ans = {l, r}; } } cout << ans << '\n' ; } int main () std::ios::sync_with_stdio (false ); std::cin.tie (nullptr ); int i_ = 0 ; int t_ = 0 ; std::cin >> t_; for (i_ = 0 ; i_ < t_; ++i_) solve (i_); return 0 ; }
C2 - Sheikh (Hard Version) This is the hard version of the problem. The only difference is that in this version \(q = n\) .
You are given an array of integers \(a_1, a_2, \ldots, a_n\) .
The cost of a subsegment of the array \([l, r]\) , \(1 \leq l \leq r \leq n\) , is the value \(f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)\) , where \(\operatorname{sum}(l, r) = a*l + a*{l+1} + \ldots + a*r\) , and \(\operatorname{xor}(l, r) = a_l \oplus a*{l+1} \oplus \ldots \oplus a_r\) (\(\oplus\) stands for bitwise XOR ).
You will have \(q\) queries. Each query is given by a pair of numbers \(L_i\) , \(R_i\) , where \(1 \leq L_i \leq R_i \leq n\) . You need to find the subsegment \([l, r]\) , \(L_i \leq l \leq r \leq R_i\) , with maximum value \(f(l, r)\) . If there are several answers, then among them you need to find a subsegment with the minimum length, that is, the minimum value of \(r - l + 1\) .
Each test consists of multiple test cases. The first line contains an integer \(t\) (\(1 \leq t \leq 10^4\) ) — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers \(n\) and \(q\) (\(1 \leq n \leq 10^5\) , \(q = n\) ) — the length of the array and the number of queries.
The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq 10^9\) ) — array elements.
\(i\) -th of the next \(q\) lines of each test case contains two integers \(L_i\) and \(R_i\) (\(1 \leq L_i \leq R_i \leq n\) ) — the boundaries in which we need to find the segment.
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\) .
It is guaranteed that \(L_1 = 1\) and \(R_1 = n\) .
Output For each test case print \(q\) pairs of numbers \(L_i \leq l \leq r \leq R_i\) such that the value \(f(l, r)\) is maximum and among such the length \(r - l + 1\) is minimum. If there are several correct answers, print any of them.
Example 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 6 1 1 0 1 1 2 2 5 10 1 2 2 2 3 3 0 2 4 1 3 1 2 2 3 4 4 0 12 8 3 1 4 1 3 2 4 2 3 5 5 21 32 32 32 10 1 5 1 4 1 3 2 5 3 5 7 7 0 1 0 1 0 1 0 1 7 3 6 2 5 1 4 4 7 2 6 2 7
output 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1 1 1 1 2 2 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 3 4 2 4 4 6 2 4 2 4 4 6 2 4 2 4
Note In all test cases, the first query is considered.
In the first test case, \(f(1, 1) = 0 - 0 = 0\) .
In the second test case, \(f(1, 1) = 5 - 5 = 0\) , \(f(2, 2) = 10 - 10 = 0\) . Note that \(f(1, 2) = (10 + 5) - (10 \oplus 5) = 0\) , but we need to find a subsegment with the minimum length among the maximum values of \(f(l, r)\) . So, only segments \([1, 1]\) and \([2, 2]\) are the correct answers.
In the fourth test case, \(f(2, 3) = (12 + 8) - (12 \oplus 8) = 16\) .
There are two correct answers in the fifth test case, since \(f(2, 3) = f(3, 4)\) and their lengths are equal.
思路与做法 接着 C1 的思路继续
这题最玄幻的一点来了：实际上我们可以不用二分，因为由抽屉原理，我们最多只需要删掉当前区间端点的 \(\operatorname{lb} 10^9\approx 31\) 个非零数即可使 \(f\) 变小，所以直接枚举一下即可
代码参考
Show code
CodeForces_1732C2 view raw 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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 #include <bits/stdc++.h> template <class Tp >using pi = std::pair<Tp, Tp>;template <class Tp >using vc = std::vector<Tp>;struct CustomHash { static uint64_t splitmix64 (uint64_t x) x += 0x9e3779b97f4a7c15 ; x = (x ^ (x >> 30 )) * 0xbf58476d1ce4e5b9 ; x = (x ^ (x >> 27 )) * 0x94d049bb133111eb ; return x ^ (x >> 31 ); } size_t operator () (uint64_t x) const static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now ().time_since_epoch ().count (); return splitmix64 (x + FIXED_RANDOM); } }; using i64 = int64_t ;using pii64 = pi<i64>;#define for_(i, l, r, vars...) \ for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \ i <= i##end; \ ++i) #define foreach_ref_(i, container) for (auto &i : (container)) #define all_(a) (a).begin(), (a).end() #define read_var_(type, name) \ type name; \ std::cin >> name #define read_container_(type, name, size) \ type name(size); \ foreach_ref_(i, name) std::cin >> i template <class Tp >constexpr auto chkmin (Tp &a, Tp b) -> bool return b < a ? a = b, true : false ; } template <class Tp >constexpr auto chkmax (Tp &a, Tp b) -> bool return a < b ? a = b, true : false ; } template <class Tp >constexpr auto ispow2 (Tp i) -> bool return i && (i & -i) == i; } #define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple> > namespace tuple_detail_ {template <std::size_t Begin, class Tuple , std::size_t ... Is>constexpr auto subtuple_impl_ (Tuple &&t, std::index_sequence<Is...>) return std::make_tuple (std::get <Is + Begin>(t)...); } template <class Tuple , class BinOp , std::size_t ... Is>constexpr auto apply2_impl_ (BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) return std::make_tuple ( std::forward<BinOp>(f)(std::get <Is>(lhs), std::get <Is>(rhs))...); } } template <std::size_t Begin, std::size_t Len, class Tuple >constexpr auto subtuple (Tuple &&t) static_assert (Begin <= TPL_SIZE_ (Tuple) && Len <= TPL_SIZE_ (Tuple) && Begin + Len <= TPL_SIZE_ (Tuple), "Out of range" ); return tuple_detail_::subtuple_impl_ <Begin>(t, std::make_index_sequence <Len>()); } template <std::size_t Pos, class Tp , class Tuple >constexpr auto tuple_push (Tp &&v, Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), std::make_tuple (v), subtuple <Pos, TPL_SIZE_ (Tuple) - Pos>(t)); } template <class Tp , class Tuple >constexpr auto tuple_push_front (Tp &&v, Tuple &&t) return tuple_push <0 >(v, t); } template <class Tp , class Tuple >constexpr auto tuple_push_back (Tp &&v, Tuple &&t) return tuple_push <TPL_SIZE_ (Tuple)>(v, t); } template <std::size_t Pos, class Tuple >constexpr auto tuple_pop (Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), subtuple <Pos + 1 , TPL_SIZE_ (Tuple) - Pos - 1 >(t)); } template <class Tuple >constexpr auto tuple_pop_front (Tuple &&t) return tuple_pop <0 >(t); } template <class Tuple >constexpr auto tuple_pop_back (Tuple &&t) return tuple_pop <TPL_SIZE_ (Tuple) - 1 >(t); } template <class Tuple , class BinOp >constexpr auto apply2 (BinOp &&f, Tuple &&lhs, Tuple &&rhs) return tuple_detail_::apply2_impl_ ( f, lhs, rhs, std::make_index_sequence <TPL_SIZE_ (Tuple)>()); } #define OO_PTEQ_(op) \ template <class Tp, class Up> \ constexpr auto operator op(std::pair<Tp, Up> lhs, \ const std::pair<Tp, Up> &rhs) { \ return {lhs.first op rhs.first, lhs.second op rhs.second}; \ } \ template <class... Ts> \ constexpr auto operator op(std::tuple<Ts...> const &lhs, \ std::tuple<Ts...> const &rhs) { \ return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs); \ } \ template <class Tp, class Up> \ constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs, \ const std::pair<Tp, Up> &rhs) { \ lhs.first op## = rhs.first; \ lhs.second op## = rhs.second; \ return lhs; \ } \ template <class... Ts> \ constexpr auto operator op##=(std::tuple<Ts...> &lhs, \ const std::tuple<Ts...> &rhs) { \ return lhs = lhs op rhs; \ } OO_PTEQ_ (+)OO_PTEQ_ (-)OO_PTEQ_ (*)OO_PTEQ_ (/)OO_PTEQ_ (%)OO_PTEQ_ (&)OO_PTEQ_ (|)OO_PTEQ_ (^)OO_PTEQ_ (<<)OO_PTEQ_ (>>)#undef OO_PTEQ_ #undef TPL_SIZE_ template <class Tp , class Up >std::istream &operator >>(std::istream &is, std::pair<Tp, Up> &p) { return is >> p.first >> p.second; } template <class Tp , class Up >std::ostream &operator <<(std::ostream &os, const std::pair<Tp, Up> &p) { return os << p.first << ' ' << p.second; } template <typename ... Ts>std::istream &operator >>(std::istream &is, std::tuple<Ts...> &p) { std::apply ([&](Ts &...targs) { ((is >> targs), ...); }, p); return is; } template <typename ... Ts>std::ostream &operator <<(std::ostream &os, const std::tuple<Ts...> &p) { std::apply ( [&](Ts const &...targs) { std::size_t n{0 }; ((os << targs << (++n != sizeof ...(Ts) ? " " : "" )), ...); }, p); return os; } template <class Ch , class Tr , class Ct , std::enable_if_t <std::is_same_v<decltype (std::declval <Ct>().begin ()), typename Ct::iterator> && std::is_same_v<decltype (std::declval <Ct>().end ()), typename Ct::iterator>> * = nullptr > std::basic_ostream<Ch, Tr> &operator <<(std::basic_ostream<Ch, Tr> &os, const Ct &x) { if (x.begin () == x.end ()) return os; for (auto it = x.begin (); it != x.end () - 1 ; ++it) os << *it << ' ' ; os << x.back (); return os; } using namespace std;auto solve ([[maybe_unused]] int t_ = 0 ) -> void read_var_ (i64, n); read_var_ (i64, q); read_container_ (vc<i64>, a, n); vc<i64> idxp; for_(i, 0 , n - 1 ) if (a[i]) idxp.push_back (i); vc<i64> psum (idxp.size() + 1 ) , pxor (idxp.size() + 1 ) ; for_(i, 0 , idxp.size () - 1 ) psum[i + 1 ] = psum[i] + a[idxp[i]]; for_(i, 0 , idxp.size () - 1 ) pxor[i + 1 ] = pxor[i] ^ a[idxp[i]]; auto calc = [&](i64 l, i64 r) -> i64 { return (psum[r] - psum[l]) - (pxor[r] ^ pxor[l]); }; for_(i, 1 , q, l, r, lp, rp) { cin >> l >> r; lp = lower_bound (all_ (idxp), --l) - idxp.begin (); rp = lower_bound (all_ (idxp), r) - idxp.begin (); pii64 ans_w{calc (lp, rp), l - r}, ans{l, r}; if (!ans_w.first) { ans_w.second = 0 ; ans.second = ans.first + 1 ; } for_(i, lp, min (rp, lp + 31 )) for_(j, max (i + 1 , rp - 31 ), rp) if (pii64 tmp{calc (i, j), idxp[i] - idxp[j - 1 ] - 1 }; ans_w < tmp) { ans_w = tmp; ans = {idxp[i], idxp[j - 1 ] + 1 }; } ++ans.first; cout << ans << '\n' ; } } int main () std::ios::sync_with_stdio (false ); std::cin.tie (nullptr ); int i_ = 0 ; int t_ = 0 ; std::cin >> t_; for (i_ = 0 ; i_ < t_; ++i_) solve (i_); return 0 ; }
D1 - Balance (Easy version) This is the easy version of the problem. The only difference is that in this version there are no "remove" queries.
Initially you have a set containing one element — \(0\) . You need to handle \(q\) queries of the following types:
+ \(x\) — add the integer \(x\) to the set. It is guaranteed that this integer is not contained in the set; ? \(k\) — find the \(k\text{-mex}\) of the set. In our problem, we define the \(k\text{-mex}\) of a set of integers as the smallest non-negative integer \(x\) that is divisible by \(k\) and which is not contained in the set.
The first line contains an integer \(q\) (\(1 \leq q \leq 2 \cdot 10^5\) ) — the number of queries.
The following \(q\) lines describe the queries.
An addition query of integer \(x\) is given in the format + \(x\) (\(1 \leq x \leq 10^{18}\) ). It is guaranteed that \(x\) was not contained in the set.
A search query of \(k\text{-mex}\) is given in the format ? \(k\) (\(1 \leq k \leq 10^{18}\) ).
It is guaranteed that there will be at least one query of type ?.
Output For each query of type ? output a single integer — the \(k\text{-mex}\) of the set.
Examples 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 15 + 1 + 2 ? 1 + 4 ? 2 + 6 ? 3 + 7 + 8 ? 1 ? 2 + 5 ? 1 + 1000000000000000000 ? 1000000000000000000
output 1 2 3 4 5 6 7 3 6 3 3 10 3 2000000000000000000
1 2 3 4 5 6 7 6 + 100 ? 100 + 200 ? 100 + 50 ? 50
output Note In the first example:
After the first and second queries, the set will contain elements \(\{0, 1, 2\}\) . The smallest non-negative number that is divisible by \(1\) and is not contained in the set is \(3\) .
After the fourth query, the set will contain the elements \(\{0, 1, 2, 4\}\) . The smallest non-negative number that is divisible by \(2\) and is not contained in the set is \(6\) .
In the second example:
Initially, the set contains only the element \(\{0\}\) . After adding an integer \(100\) the set contains elements \(\{0, 100\}\) . \(100\text{-mex}\) of the set is \(200\) .After adding an integer \(200\) the set contains elements \(\{0, 100, 200\}\) . \(100\text{-mex}\) of the set is \(300\) .After adding an integer \(50\) the set contains elements \(\{0, 50, 100, 200\}\) . \(50\text{-mex}\) of the set is \(150\) .思路与做法 D1 和 D2 基本都是暴力优化然后均摊复杂度能过，很神奇
我们考虑暴力做法：用 std::set 暴力维护
显然这样插入是 \(O(\log n)\) 的，但是查找是 \(O(\frac{K}{k}\log n)\) 的，其中 \(K\leq 2\times 10^{18}\)
我们发现若某次查询的 \(k\) 之前已经查过了，那我们不需要从 \(x\) 依次枚举，而直接从上一次的进度继续即可
这样的话我们就相当于把许多查询压缩到了一次，这样的话 std::set 里元素被访问的次数均摊下来大概只有 \(O(\log q)\) 次，就可以通过本题了
具体来说就是我们开一个 std::map<int, int> res, 其中 res[k] 表示上一次询问 k 时的答案，则之后再询问 k 的时候只需要从 res[k] 开始搜即可
代码参考
Show code
CodeForces_1732D1 view raw 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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 #include <bits/stdc++.h> struct CustomHash { static uint64_t splitmix64 (uint64_t x) x += 0x9e3779b97f4a7c15 ; x = (x ^ (x >> 30 )) * 0xbf58476d1ce4e5b9 ; x = (x ^ (x >> 27 )) * 0x94d049bb133111eb ; return x ^ (x >> 31 ); } size_t operator () (uint64_t x) const static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now ().time_since_epoch ().count (); return splitmix64 (x + FIXED_RANDOM); } }; template <class Tp , class Hash = CustomHash>using hset = std::unordered_set<Tp, Hash>;using i64 = int64_t ;#define for_(i, l, r, vars...) \ for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \ i <= i##end; \ ++i) #define read_var_(type, name) \ type name; \ std::cin >> name template <class Tp >constexpr auto chkmin (Tp &a, Tp b) -> bool return b < a ? a = b, true : false ; } template <class Tp >constexpr auto chkmax (Tp &a, Tp b) -> bool return a < b ? a = b, true : false ; } template <class Tp >constexpr auto ispow2 (Tp i) -> bool return i && (i & -i) == i; } #define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple> > namespace tuple_detail_ {template <std::size_t Begin, class Tuple , std::size_t ... Is>constexpr auto subtuple_impl_ (Tuple &&t, std::index_sequence<Is...>) return std::make_tuple (std::get <Is + Begin>(t)...); } template <class Tuple , class BinOp , std::size_t ... Is>constexpr auto apply2_impl_ (BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) return std::make_tuple ( std::forward<BinOp>(f)(std::get <Is>(lhs), std::get <Is>(rhs))...); } } template <std::size_t Begin, std::size_t Len, class Tuple >constexpr auto subtuple (Tuple &&t) static_assert (Begin <= TPL_SIZE_ (Tuple) && Len <= TPL_SIZE_ (Tuple) && Begin + Len <= TPL_SIZE_ (Tuple), "Out of range" ); return tuple_detail_::subtuple_impl_ <Begin>(t, std::make_index_sequence <Len>()); } template <std::size_t Pos, class Tp , class Tuple >constexpr auto tuple_push (Tp &&v, Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), std::make_tuple (v), subtuple <Pos, TPL_SIZE_ (Tuple) - Pos>(t)); } template <class Tp , class Tuple >constexpr auto tuple_push_front (Tp &&v, Tuple &&t) return tuple_push <0 >(v, t); } template <class Tp , class Tuple >constexpr auto tuple_push_back (Tp &&v, Tuple &&t) return tuple_push <TPL_SIZE_ (Tuple)>(v, t); } template <std::size_t Pos, class Tuple >constexpr auto tuple_pop (Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), subtuple <Pos + 1 , TPL_SIZE_ (Tuple) - Pos - 1 >(t)); } template <class Tuple >constexpr auto tuple_pop_front (Tuple &&t) return tuple_pop <0 >(t); } template <class Tuple >constexpr auto tuple_pop_back (Tuple &&t) return tuple_pop <TPL_SIZE_ (Tuple) - 1 >(t); } template <class Tuple , class BinOp >constexpr auto apply2 (BinOp &&f, Tuple &&lhs, Tuple &&rhs) return tuple_detail_::apply2_impl_ ( f, lhs, rhs, std::make_index_sequence <TPL_SIZE_ (Tuple)>()); } #define OO_PT_(op) \ template <class Tp, class Up> \ constexpr auto operator op(std::pair<Tp, Up> lhs, \ const std::pair<Tp, Up> &rhs) { \ return {lhs.first op rhs.first, lhs.second op rhs.second}; \ } \ template <class... Ts> \ constexpr auto operator op(std::tuple<Ts...> const &lhs, \ std::tuple<Ts...> const &rhs) { \ return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs); \ } #define OO_PTEQ_(op) \ OO_PT_(op) \ template <class Tp, class Up> \ constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs, \ const std::pair<Tp, Up> &rhs) { \ lhs.first op## = rhs.first; \ lhs.second op## = rhs.second; \ return lhs; \ } \ template <class... Ts> \ constexpr auto operator op##=(std::tuple<Ts...> &lhs, \ const std::tuple<Ts...> &rhs) { \ return lhs = lhs op rhs; \ } OO_PTEQ_ (+)OO_PTEQ_ (-)OO_PTEQ_ (*)OO_PTEQ_ (/)OO_PTEQ_ (%)OO_PTEQ_ (&)OO_PTEQ_ (|)OO_PTEQ_ (^)OO_PTEQ_ (<<)OO_PTEQ_ (>>)OO_PT_ (==)OO_PT_ (!=)OO_PT_ (<)OO_PT_ (<=)OO_PT_ (>)OO_PT_ (>=)#undef OO_PT_ #undef TPL_SIZE_ template <class Tp , class Up >std::istream &operator >>(std::istream &is, std::pair<Tp, Up> &p) { return is >> p.first >> p.second; } template <class Tp , class Up >std::ostream &operator <<(std::ostream &os, const std::pair<Tp, Up> &p) { return os << p.first << ' ' << p.second; } template <typename ... Ts>std::istream &operator >>(std::istream &is, std::tuple<Ts...> &p) { std::apply ([&](Ts &...targs) { ((is >> targs), ...); }, p); return is; } template <typename ... Ts>std::ostream &operator <<(std::ostream &os, const std::tuple<Ts...> &p) { std::apply ( [&](Ts const &...targs) { std::size_t n{0 }; ((os << targs << (++n != sizeof ...(Ts) ? " " : "" )), ...); }, p); return os; } template <class Ch , class Tr , class Ct , std::enable_if_t <std::is_same_v<decltype (std::declval <Ct>().begin ()), typename Ct::iterator> && std::is_same_v<decltype (std::declval <Ct>().end ()), typename Ct::iterator>> * = nullptr > std::basic_ostream<Ch, Tr> &operator <<(std::basic_ostream<Ch, Tr> &os, const Ct &x) { if (x.begin () == x.end ()) return os; for (auto it = x.begin (); it != x.end () - 1 ; ++it) os << *it << ' ' ; os << x.back (); return os; } using namespace std;auto solve ([[maybe_unused]] int t_ = 0 ) -> void read_var_ (i64, q); hset<i64> mp; map<i64, i64> res; mp.insert (0 ); for_(i, 1 , q, k) { char ch; cin >> ch >> k; if (ch == '+' ) { mp.insert (k); continue ; } while (mp.count (res[k])) res[k] += k; cout << res[k] << '\n' ; } } int main () std::ios::sync_with_stdio (false ); std::cin.tie (nullptr ); int i_ = 0 ; solve (i_); return 0 ; }
D2 - Balance (Hard version) This is the hard version of the problem. The only difference is that in this version there are remove queries .
Initially you have a set containing one element — \(0\) . You need to handle \(q\) queries of the following types:
+ \(x\) — add the integer \(x\) to the set. It is guaranteed that this integer is not contained in the set; - \(x\) — remove the integer \(x\) from the set. It is guaranteed that this integer is contained in the set; ? \(k\) — find the \(k\text{-mex}\) of the set. In our problem, we define the \(k\text{-mex}\) of a set of integers as the smallest non-negative integer \(x\) that is divisible by \(k\) and which is not contained in the set.
The first line contains an integer \(q\) (\(1 \leq q \leq 2 \cdot 10^5\) ) — the number of queries.
The following \(q\) lines describe the queries.
An addition query of integer \(x\) is given in the format + \(x\) (\(1 \leq x \leq 10^{18}\) ). It is guaranteed that \(x\) is not contained in the set.
A remove query of integer \(x\) is given in the format - \(x\) (\(1 \leq x \leq 10^{18}\) ). It is guaranteed that \(x\) is contained in the set.
A search query of \(k\text{-mex}\) is given in the format ? \(k\) (\(1 \leq k \leq 10^{18}\) ).
It is guaranteed that there is at least one query of type ?.
Output For each query of type ? output a single integer — the \(k\text{-mex}\) of the set.
Examples 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 18 + 1 + 2 ? 1 + 4 ? 2 + 6 ? 3 + 7 + 8 ? 1 ? 2 + 5 ? 1 + 1000000000000000000 ? 1000000000000000000 - 4 ? 1 ? 2
output 1 2 3 4 5 6 7 8 9 3 6 3 3 10 3 2000000000000000000 3 4
1 2 3 4 5 6 7 8 9 10 11 10 + 100 ? 100 + 200 ? 100 - 100 ? 100 + 50 ? 50 - 50 ? 50
output Note In the first example:
After the first and second queries, the set will contain elements \(\{0, 1, 2\}\) . The smallest non-negative number that is divisible by \(1\) and is not in the set is \(3\) .
After the fourth query, the set will contain the elements \(\{0, 1, 2, 4\}\) . The smallest non-negative number that is divisible by \(2\) and is not in the set is \(6\) .
In the second example:
Initially, the set contains only the element \(\{0\}\) . After adding an integer \(100\) the set contains elements \(\{0, 100\}\) . \(100\text{-mex}\) of the set is \(200\) .After adding an integer \(200\) the set contains elements \(\{0, 100, 200\}\) . \(100\text{-mex}\) of the set \(300\) .After removing an integer \(100\) the set contains elements \(\{0, 200\}\) . \(100\text{-mex}\) of the set is \(100\) .After adding an integer \(50\) the set contains elements \(\{0, 50, 200\}\) . \(50\text{-mex}\) of the set is \(100\) .After removing an integer \(50\) the set contains elements \(\{0, 200\}\) . \(100\text{-mex}\) of the set is \(50\) .思路与做法 和 D1 一样，我们考虑优化暴力做法
D2 加了删除，这样单纯一个 std::map<int, int> res 就不够用了
我们这样处理:
用 std::map<int, std::vector<int>> changed 记录一下答案都可以从哪个 k 转移过来，即 changed[x] 里的元素都是之前查询时枚举到 x 时对应的所有 k 用 std::map<int, std::set<int>> del 记录两次查询 k 之间都删除了哪些会影响答案的数 这样时间复杂度均摊下来就是比 D1 多了个 std::set 带来的 \(O(\log n)\)
代码参考
Show code
CodeForces_1732D2 view raw 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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 #include <bits/stdc++.h> struct CustomHash { static uint64_t splitmix64 (uint64_t x) x += 0x9e3779b97f4a7c15 ; x = (x ^ (x >> 30 )) * 0xbf58476d1ce4e5b9 ; x = (x ^ (x >> 27 )) * 0x94d049bb133111eb ; return x ^ (x >> 31 ); } size_t operator () (uint64_t x) const static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now ().time_since_epoch ().count (); return splitmix64 (x + FIXED_RANDOM); } }; template <class Tp , class Hash = CustomHash>using hset = std::unordered_set<Tp, Hash>;using i64 = int64_t ;#define for_(i, l, r, vars...) \ for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \ i <= i##end; \ ++i) #define read_var_(type, name) \ type name; \ std::cin >> name template <class Tp >constexpr auto chkmin (Tp &a, Tp b) -> bool return b < a ? a = b, true : false ; } template <class Tp >constexpr auto chkmax (Tp &a, Tp b) -> bool return a < b ? a = b, true : false ; } template <class Tp >constexpr auto ispow2 (Tp i) -> bool return i && (i & -i) == i; } #define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple> > namespace tuple_detail_ {template <std::size_t Begin, class Tuple , std::size_t ... Is>constexpr auto subtuple_impl_ (Tuple &&t, std::index_sequence<Is...>) return std::make_tuple (std::get <Is + Begin>(t)...); } template <class Tuple , class BinOp , std::size_t ... Is>constexpr auto apply2_impl_ (BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) return std::make_tuple ( std::forward<BinOp>(f)(std::get <Is>(lhs), std::get <Is>(rhs))...); } } template <std::size_t Begin, std::size_t Len, class Tuple >constexpr auto subtuple (Tuple &&t) static_assert (Begin <= TPL_SIZE_ (Tuple) && Len <= TPL_SIZE_ (Tuple) && Begin + Len <= TPL_SIZE_ (Tuple), "Out of range" ); return tuple_detail_::subtuple_impl_ <Begin>(t, std::make_index_sequence <Len>()); } template <std::size_t Pos, class Tp , class Tuple >constexpr auto tuple_push (Tp &&v, Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), std::make_tuple (v), subtuple <Pos, TPL_SIZE_ (Tuple) - Pos>(t)); } template <class Tp , class Tuple >constexpr auto tuple_push_front (Tp &&v, Tuple &&t) return tuple_push <0 >(v, t); } template <class Tp , class Tuple >constexpr auto tuple_push_back (Tp &&v, Tuple &&t) return tuple_push <TPL_SIZE_ (Tuple)>(v, t); } template <std::size_t Pos, class Tuple >constexpr auto tuple_pop (Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), subtuple <Pos + 1 , TPL_SIZE_ (Tuple) - Pos - 1 >(t)); } template <class Tuple >constexpr auto tuple_pop_front (Tuple &&t) return tuple_pop <0 >(t); } template <class Tuple >constexpr auto tuple_pop_back (Tuple &&t) return tuple_pop <TPL_SIZE_ (Tuple) - 1 >(t); } template <class Tuple , class BinOp >constexpr auto apply2 (BinOp &&f, Tuple &&lhs, Tuple &&rhs) return tuple_detail_::apply2_impl_ ( f, lhs, rhs, std::make_index_sequence <TPL_SIZE_ (Tuple)>()); } #define OO_PT_(op) \ template <class Tp, class Up> \ constexpr auto operator op(std::pair<Tp, Up> lhs, \ const std::pair<Tp, Up> &rhs) { \ return {lhs.first op rhs.first, lhs.second op rhs.second}; \ } \ template <class... Ts> \ constexpr auto operator op(std::tuple<Ts...> const &lhs, \ std::tuple<Ts...> const &rhs) { \ return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs); \ } #define OO_PTEQ_(op) \ OO_PT_(op) \ template <class Tp, class Up> \ constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs, \ const std::pair<Tp, Up> &rhs) { \ lhs.first op## = rhs.first; \ lhs.second op## = rhs.second; \ return lhs; \ } \ template <class... Ts> \ constexpr auto operator op##=(std::tuple<Ts...> &lhs, \ const std::tuple<Ts...> &rhs) { \ return lhs = lhs op rhs; \ } OO_PTEQ_ (+)OO_PTEQ_ (-)OO_PTEQ_ (*)OO_PTEQ_ (/)OO_PTEQ_ (%)OO_PTEQ_ (&)OO_PTEQ_ (|)OO_PTEQ_ (^)OO_PTEQ_ (<<)OO_PTEQ_ (>>)OO_PT_ (==)OO_PT_ (!=)OO_PT_ (<)OO_PT_ (<=)OO_PT_ (>)OO_PT_ (>=)#undef OO_PT_ #undef TPL_SIZE_ template <class Tp , class Up >std::istream &operator >>(std::istream &is, std::pair<Tp, Up> &p) { return is >> p.first >> p.second; } template <class Tp , class Up >std::ostream &operator <<(std::ostream &os, const std::pair<Tp, Up> &p) { return os << p.first << ' ' << p.second; } template <typename ... Ts>std::istream &operator >>(std::istream &is, std::tuple<Ts...> &p) { std::apply ([&](Ts &...targs) { ((is >> targs), ...); }, p); return is; } template <typename ... Ts>std::ostream &operator <<(std::ostream &os, const std::tuple<Ts...> &p) { std::apply ( [&](Ts const &...targs) { std::size_t n{0 }; ((os << targs << (++n != sizeof ...(Ts) ? " " : "" )), ...); }, p); return os; } template <class Ch , class Tr , class Ct , std::enable_if_t <std::is_same_v<decltype (std::declval <Ct>().begin ()), typename Ct::iterator> && std::is_same_v<decltype (std::declval <Ct>().end ()), typename Ct::iterator>> * = nullptr > std::basic_ostream<Ch, Tr> &operator <<(std::basic_ostream<Ch, Tr> &os, const Ct &x) { if (x.begin () == x.end ()) return os; for (auto it = x.begin (); it != x.end () - 1 ; ++it) os << *it << ' ' ; os << x.back (); return os; } using namespace std;auto solve ([[maybe_unused]] int t_ = 0 ) -> void read_var_ (i64, q); hset<i64> mp; map<i64, i64> res; map<i64, set<i64>> del, changed; mp.insert (0 ); for_(i, 1 , q, k) { char ch; cin >> ch >> k; if (ch == '+' ) { mp.insert (k); for (auto &&i : changed[k]) del[i].erase (k); continue ; } if (ch == '-' ) { mp.erase (k); for (auto &&i : changed[k]) del[i].insert (k); continue ; } if (del[k].empty ()) { while (mp.count (res[k])) changed[res[k] += k].insert (k); cout << res[k] << '\n' ; continue ; } cout << *del[k].begin () << '\n' ; } } int main () std::ios::sync_with_stdio (false ); std::cin.tie (nullptr ); int i_ = 0 ; solve (i_); return 0 ; }
E - Location You are given two arrays of integers \(a_1, a_2, \ldots, a_n\) and \(b_1, b_2, \ldots, b_n\) . You need to handle \(q\) queries of the following two types:
\(1\) \(l\) \(r\) \(x\) : assign \(a_i := x\) for all \(l \leq i \leq r\) ;
\(2\) \(l\) \(r\) : find the minimum value of the following expression among all \(l \leq i \leq r\) :
\[ \frac{\operatorname{lcm}(a_i, b_i)}{\gcd(a_i, b_i)}. \]
In this problem \(\gcd(x, y)\) denotes the greatest common divisor of \(x\) and \(y\) , and \(\operatorname{lcm}(x, y)\) denotes the least common multiple of \(x\) and \(y\) .
The first line contains two integers \(n\) and \(q\) (\(1 \leq n, q \leq 5 \cdot 10^4\) ) — the number of numbers in the arrays \(a\) and \(b\) and the number of queries.
The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 5 \cdot 10^4\) ) — the elements of the array \(a\) .
The third line contains \(n\) integers \(b_1, b_2, \ldots, b_n\) (\(1 \leq b_i \leq 5 \cdot 10^4\) ) — the elements of the array \(b\) .
Then \(q\) lines follow, \(j\) -th of which starts with an integer \(t_j\) (\(1 \leq t_j \leq 2\) ) and means that the \(j\) -th query has type \(t_j\) .
If \(t_j = 1\) , it is followed by three integers \(l_j\) , \(r_j\) , and \(x_j\) (\(1 \leq l_j \leq r_j \leq n\) , \(1 \leq x_j \leq 5 \cdot 10^4\) ).
If \(t_j = 2\) , it is followed by two integers \(l_j\) and \(r_j\) (\(1 \leq l_j \leq r_j \leq n\) ).
It is guaranteed that there is at least one query of type \(2\) .
Output For each query of the second type, output the minimum value of the expression.
Examples 1 2 3 4 5 6 7 8 9 10 11 12 13 10 10 6 10 15 4 9 25 2 3 5 30 1 2 3 4 6 9 12 15 18 30 2 1 10 1 7 10 9 2 5 10 1 1 6 14 2 4 7 2 3 9 1 2 9 30 2 1 4 2 3 7 2 5 10
output 1 2 3 4 5 6 7 4 4 10 2 12 5 1 12 16 1 2 2 4 1 2 3 18 1 2 2 10 2 2 3
output Note In the first example:
For the first query we can choose \(i = 4\) . So the value is \(\frac{\operatorname{lcm}(4, 4)}{\gcd(4, 4)} = \frac{4}{4} = 1\) . After the second query the array \(a = [6, 10, 15, 4, 9, 25, 9, 9, 9, 9]\) . For the third query we can choose \(i = 9\) . So the value is \(\frac{\operatorname{lcm}(9, 18)}{\gcd(9, 18)} = \frac{18}{9} = 2\) . In the second:
For the first query we can choose \(i = 4\) . So the value is \(\frac{\operatorname{lcm}(1, 5)}{\gcd(1, 5)} = \frac{5}{1} = 5\) . After the second query the array \(a = [10, 18, 18, 5]\) . After the third query the array \(a = [10, 10, 18, 5]\) . For the fourth query we can choose \(i = 2\) . So the value is \(\frac{\operatorname{lcm}(10, 12)}{\gcd(10, 12)} = \frac{60}{2} = 30\) . 思路与做法 显然要上数据结构，这里参照官方题解写的分块
写分块的话关键在于对每个块怎么维护操作 1
我们先对每个 b[i] 枚举因数 f, 然后每个块上都开个数组 v, v[f] 记录块上含因子 f 的最小 的 b 的值
在将某个块上全部的 a 都改成 \(x\) 的时候，我们首先打个懒标记，因为当需要修改单个元素时候需要首先根据懒标记暴力修改块上的元素来保证正确性。接着设此时块上的答案为 \(B\) , 则修改后的答案 \(B'\) 满足
\[ B'=\min_{f\mid x}\left\{B,\frac{xv_f}{f^2}\right\} \]
注意这题要用 uint32_t, 因为 int64_t 会被卡常，而且结果最大大约为 2.5e9
代码参考
Show code
CodeForces_1732E view raw 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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 #include <bits/stdc++.h> template <class Tp >using vc = std::vector<Tp>;struct CustomHash { static constexpr uint64_t splitmix64 (uint64_t x) x += 0x9e3779b97f4a7c15 ; x = (x ^ (x >> 30 )) * 0xbf58476d1ce4e5b9 ; x = (x ^ (x >> 27 )) * 0x94d049bb133111eb ; return x ^ (x >> 31 ); } static constexpr size_t append (size_t x, size_t y) return x ^ (y >> 1 ) ^ ((y & 1 ) << (sizeof (size_t ) * 8 - 1 )); } size_t operator () (uint64_t x) const static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now ().time_since_epoch ().count (); return splitmix64 (x + FIXED_RANDOM); } template <class Tp , class Up > size_t operator () (std::pair<Tp, Up> const &p) const return append ((*this )(p.first), (*this )(p.second)); } template <typename ... Ts> size_t operator () (std::tuple<Ts...> const &tp) const size_t ret = 0 ; std::apply ( [&](Ts const &...targs) { ((ret = append (ret, (*this )(targs))), ...); }, tp); return ret; } template < class Tp , std::enable_if_t <std::is_same_v<decltype (std::declval <Tp>().begin ()), typename Tp::iterator> && std::is_same_v<decltype (std::declval <Tp>().end ()), typename Tp::iterator>> * = nullptr > size_t operator ()(Tp const &tp) const { size_t ret = 0 ; for (auto &&i : tp) ret = append (ret, (*this )(i)); return ret; } }; using u32 = uint32_t ;#define for_(i, l, r, vars...) \ for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \ i <= i##end; \ ++i) #define foreach_ref_(i, container) for (auto &i : (container)) #define read_var_(type, name) \ type name; \ std::cin >> name #define read_container_(type, name, size) \ type name(size); \ foreach_ref_(i, name) std::cin >> i template <class Tp >constexpr auto chkmin (Tp &a, Tp b) -> bool return b < a ? a = b, true : false ; } template <class Tp >constexpr auto chkmax (Tp &a, Tp b) -> bool return a < b ? a = b, true : false ; } template <class Tp >constexpr auto ispow2 (Tp i) -> bool return i && (i & -i) == i; } #define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple> > namespace tuple_detail_ {template <std::size_t Begin, class Tuple , std::size_t ... Is>constexpr auto subtuple_impl_ (Tuple &&t, std::index_sequence<Is...>) return std::make_tuple (std::get <Is + Begin>(t)...); } template <class Tuple , class BinOp , std::size_t ... Is>constexpr auto apply2_impl_ (BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) return std::make_tuple ( std::forward<BinOp>(f)(std::get <Is>(lhs), std::get <Is>(rhs))...); } } template <std::size_t Begin, std::size_t Len, class Tuple >constexpr auto subtuple (Tuple &&t) static_assert (Begin <= TPL_SIZE_ (Tuple) && Len <= TPL_SIZE_ (Tuple) && Begin + Len <= TPL_SIZE_ (Tuple), "Out of range" ); return tuple_detail_::subtuple_impl_ <Begin>(t, std::make_index_sequence <Len>()); } template <std::size_t Pos, class Tp , class Tuple >constexpr auto tuple_push (Tp &&v, Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), std::make_tuple (v), subtuple <Pos, TPL_SIZE_ (Tuple) - Pos>(t)); } template <class Tp , class Tuple >constexpr auto tuple_push_front (Tp &&v, Tuple &&t) return tuple_push <0 >(v, t); } template <class Tp , class Tuple >constexpr auto tuple_push_back (Tp &&v, Tuple &&t) return tuple_push <TPL_SIZE_ (Tuple)>(v, t); } template <std::size_t Pos, class Tuple >constexpr auto tuple_pop (Tuple &&t) static_assert (TPL_SIZE_ (Tuple) > 0 , "Pop from empty tuple" ); return std::tuple_cat (subtuple <0 , Pos>(t), subtuple <Pos + 1 , TPL_SIZE_ (Tuple) - Pos - 1 >(t)); } template <class Tuple >constexpr auto tuple_pop_front (Tuple &&t) return tuple_pop <0 >(t); } template <class Tuple >constexpr auto tuple_pop_back (Tuple &&t) return tuple_pop <TPL_SIZE_ (Tuple) - 1 >(t); } template <class Tuple , class BinOp >constexpr auto apply2 (BinOp &&f, Tuple &&lhs, Tuple &&rhs) return tuple_detail_::apply2_impl_ ( f, lhs, rhs, std::make_index_sequence <TPL_SIZE_ (Tuple)>()); } #define OO_PTEQ_(op) \ template <class Tp, class Up> \ constexpr auto operator op(std::pair<Tp, Up> lhs, \ const std::pair<Tp, Up> &rhs) { \ return {lhs.first op rhs.first, lhs.second op rhs.second}; \ } \ template <class... Ts> \ constexpr auto operator op(std::tuple<Ts...> const &lhs, \ std::tuple<Ts...> const &rhs) { \ return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs); \ } \ template <class Tp, class Up> \ constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs, \ const std::pair<Tp, Up> &rhs) { \ lhs.first op## = rhs.first; \ lhs.second op## = rhs.second; \ return lhs; \ } \ template <class... Ts> \ constexpr auto operator op##=(std::tuple<Ts...> &lhs, \ const std::tuple<Ts...> &rhs) { \ return lhs = lhs op rhs; \ } OO_PTEQ_ (+)OO_PTEQ_ (-)OO_PTEQ_ (*)OO_PTEQ_ (/)OO_PTEQ_ (%)OO_PTEQ_ (&)OO_PTEQ_ (|)OO_PTEQ_ (^)OO_PTEQ_ (<<)OO_PTEQ_ (>>)#undef OO_PTEQ_ #undef TPL_SIZE_ template <class Tp , class Up >std::istream &operator >>(std::istream &is, std::pair<Tp, Up> &p) { return is >> p.first >> p.second; } template <class Tp , class Up >std::ostream &operator <<(std::ostream &os, const std::pair<Tp, Up> &p) { return os << p.first << ' ' << p.second; } template <typename ... Ts>std::istream &operator >>(std::istream &is, std::tuple<Ts...> &p) { std::apply ([&](Ts &...targs) { ((is >> targs), ...); }, p); return is; } template <typename ... Ts>std::ostream &operator <<(std::ostream &os, const std::tuple<Ts...> &p) { std::apply ( [&](Ts const &...targs) { std::size_t n{0 }; ((os << targs << (++n != sizeof ...(Ts) ? " " : "" )), ...); }, p); return os; } template <class Ch , class Tr , class Ct , std::enable_if_t <std::is_same_v<decltype (std::declval <Ct>().begin ()), typename Ct::iterator> && std::is_same_v<decltype (std::declval <Ct>().end ()), typename Ct::iterator>> * = nullptr > std::basic_ostream<Ch, Tr> &operator <<(std::basic_ostream<Ch, Tr> &os, const Ct &x) { if (x.begin () == x.end ()) return os; for (auto it = x.begin (); it != x.end () - 1 ; ++it) os << *it << ' ' ; os << x.back (); return os; } using namespace std;namespace Bucket_detail__ {template <class Tp , typename Ext>struct BlockInfo final { using self = BlockInfo<Tp, Ext>; const size_t l, r; Tp result; const std::function<void (self &, std::vector<Tp> &)> bfunc; Ext ext; BlockInfo (size_t l, size_t r, std::vector<Tp> &data, std::function<void (self &, std::vector<Tp> &)> bfunc) : l (l), r (r), result (), bfunc (bfunc), ext () { bfunc (*this , data); } void refresh (std::vector<Tp> &data) bfunc (*this , data); } }; template <class Tp >struct BlockInfo <Tp, void > final { using self = BlockInfo<Tp, void >; const size_t l, r; Tp result; const std::function<void (self &, std::vector<Tp> &)> bfunc; BlockInfo (size_t l, size_t r, std::vector<Tp> &data, std::function<void (self &, std::vector<Tp> &)> bfunc) : l (l), r (r), result (), bfunc (bfunc) { bfunc (*this , data); } void refresh (std::vector<Tp> &data) bfunc (*this , data); } }; template <typename Tp, typename Ext = void >class Bucket {public : using self = Bucket<Tp, Ext>; using BInfo = BlockInfo<Tp, Ext>; protected : const size_t bsize; protected : std::vector<Tp> data; std::vector<BInfo> blk; public : Bucket (size_t bsize, std::vector<Tp> const &data_, std::function<void (BInfo &, std::vector<Tp> const &)> bfunc) : bsize (bsize), data (data_), blk () { assert (data.size () > 0 ); size_t _ = (data.size () + bsize - 1 ) / bsize; blk.reserve (_); for (size_t i = 0 ; i < _; ++i) blk.emplace_back ( i * bsize, std::min (data.size (), (i + 1 ) * bsize) - 1 , data, bfunc); } template <class USFunc = std::function<void (BInfo &, std::vector<Tp> &, size_t , size_t )>, class UBFunc = std::function<void (BInfo &, std::vector<Tp> &)>> self &update (size_t l, size_t r, USFunc usfunc, UBFunc ubfunc) { ptrdiff_t bl = (l + bsize - 1 ) / bsize, br = (r + 1 ) / bsize - 1 ; for (ptrdiff_t i = bl; i <= br; ++i) ubfunc (blk[i], data); if (r < bl * bsize) { usfunc (blk[bl - 1 ], data, l, r); } else { if (l < bl * bsize) usfunc (blk[bl - 1 ], data, l, bl * bsize - 1 ); if ((br + 1 ) * bsize <= r) usfunc (blk[br + 1 ], data, (br + 1 ) * bsize, r); } return *this ; } }; } using Bucket_detail__::Bucket;std::vector<uint64_t > factors (uint64_t n) { vector<uint64_t > ret; ret.reserve ((size_t )sqrtl (n) * 2 ); for (uint64_t i = 1 ; i * i <= n; ++i) { if (n % i) continue ; ret.push_back (i); if (uint64_t j = n / i; i != j) ret.push_back (j); } return ret; } struct ExtData { vc<u32> mp; u32 x; ExtData (): mp (50001 ), x (0 ) {} }; auto solve ([[maybe_unused]] int t_ = 0 ) -> void int n, q; cin >> n >> q; read_container_ (vc<u32>, a, n); read_container_ (vc<u32>, b, n); Bucket<u32, ExtData> bucket (200 , a, [&](auto &blk, auto &data) { blk.result = numeric_limits<decltype (blk.result)>::max(); for_(i, blk.l, blk.r) chkmin(blk.result, lcm(data[i], b[i]) / gcd(data[i], b[i])); }) bucket.update ( 0 , n - 1 , [&](auto &blk, auto &data, size_t xl, size_t xr) {}, [&](auto &blk, auto &data) { for_(i, blk.l, blk.r) { auto _ = factors (b[i]); for (u32 f : _) { auto &__ = blk.ext.mp[f]; __ = __ ? min (__, b[i]) : b[i]; } } }); for_(i, 1 , q, tp, l, r) { cin >> tp >> l >> r; --l; --r; if (tp == 1 ) { read_var_ (u32, x); auto _ = factors (x); bucket.update ( l, r, [&](auto &blk, auto &data, size_t xl, size_t xr) { if (blk.ext.x) { for_(i, blk.l, blk.r) data[i] = blk.ext.x; blk.ext.x = 0 ; } for_(i, xl, xr) data[i] = x; blk.refresh (data); }, [&](auto &blk, auto &data) { blk.result = numeric_limits<decltype (blk.result)>::max (); blk.ext.x = x; for (u32 f : _) if (u32 __ = blk.ext.mp[f]; __) chkmin (blk.result, x / f * (__ / f)); }); } else { u32 ans = numeric_limits<u32>::max (); bucket.update ( l, r, [&](auto &blk, auto &data, size_t xl, size_t xr) { if (blk.ext.x) { for_(i, blk.l, blk.r) data[i] = blk.ext.x; blk.ext.x = 0 ; } for_(i, xl, xr) chkmin (ans, lcm (data[i], b[i]) / gcd (data[i], b[i])); }, [&](auto &blk, auto &data) { chkmin (ans, blk.result); }); cout << ans << '\n' ; } } } int main () std::ios::sync_with_stdio (false ); std::cin.tie (nullptr ); int i_ = 0 ; solve (i_); return 0 ; }