题解 - Codeforces Round #830 (Div. 2)

比赛链接

神奇的数据结构场 \(\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\).

Input

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

input

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

0
1
2
2
1
3
3
0
1

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_1732Aview raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#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))...);
}
}  // namespace tuple_detail_
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?

Input

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

input

8
1
1
2
10
3
101
4
1100
5
11001
6
100010
10
0000110000
7
0101010

output

0
1
2
1
2
3
1
5

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_1732Bview raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#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))...);
}
}  // namespace tuple_detail_
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\).

Input

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

input

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

1 1
1 1
1 1
2 3
2 3
2 4

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_1732C1view raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#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))...);
}
}  // namespace tuple_detail_
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\).

Input

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

input

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 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_1732C2view raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#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))...);
}
}  // namespace tuple_detail_
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.

Input

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

input

15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000

output

3
6
3
3
10
3
2000000000000000000

input

6
+ 100
? 100
+ 200
? 100
+ 50
? 50

output

200
300
150

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_1732D1view raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#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))...);
}
}  // namespace tuple_detail_
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.

Input

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

input

18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
- 4
? 1
? 2

output

3
6
3
3
10
3
2000000000000000000
3
4

input

10
+ 100
? 100
+ 200
? 100
- 100
? 100
+ 50
? 50
- 50
? 50

output

200
300
100
100
50

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_1732D2view raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#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))...);
}
}  // namespace tuple_detail_
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\).

Input

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

input

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
12
2
10
5
2

input

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

5
30

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_1732Eview raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#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))...);
}
}  // namespace tuple_detail_
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;
  }
};
}  // namespace Bucket_detail__
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;
}