結果
| 問題 | No.1441 MErGe |
| ユーザー |
 c--
|
| 提出日時 | 2021-07-26 13:30:34 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 249 ms / 1,000 ms |
| コード長 | 31,994 bytes |
| コンパイル時間 | 4,879 ms |
| コンパイル使用メモリ | 278,184 KB |
| 実行使用メモリ | 9,856 KB |
| 最終ジャッジ日時 | 2024-07-22 03:25:57 |
| 合計ジャッジ時間 | 13,472 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 3 ms
5,376 KB |
| testcase_03 | AC | 4 ms
5,376 KB |
| testcase_04 | AC | 4 ms
5,376 KB |
| testcase_05 | AC | 7 ms
5,376 KB |
| testcase_06 | AC | 7 ms
5,376 KB |
| testcase_07 | AC | 8 ms
5,376 KB |
| testcase_08 | AC | 51 ms
5,376 KB |
| testcase_09 | AC | 50 ms
5,376 KB |
| testcase_10 | AC | 76 ms
5,376 KB |
| testcase_11 | AC | 67 ms
5,376 KB |
| testcase_12 | AC | 76 ms
5,376 KB |
| testcase_13 | AC | 192 ms
9,472 KB |
| testcase_14 | AC | 189 ms
9,472 KB |
| testcase_15 | AC | 215 ms
9,344 KB |
| testcase_16 | AC | 207 ms
9,600 KB |
| testcase_17 | AC | 199 ms
9,216 KB |
| testcase_18 | AC | 160 ms
7,936 KB |
| testcase_19 | AC | 183 ms
8,704 KB |
| testcase_20 | AC | 140 ms
7,808 KB |
| testcase_21 | AC | 125 ms
7,040 KB |
| testcase_22 | AC | 167 ms
6,912 KB |
| testcase_23 | AC | 235 ms
9,856 KB |
| testcase_24 | AC | 247 ms
9,856 KB |
| testcase_25 | AC | 249 ms
9,856 KB |
| testcase_26 | AC | 239 ms
9,856 KB |
| testcase_27 | AC | 229 ms
9,728 KB |
| testcase_28 | AC | 117 ms
9,856 KB |
| testcase_29 | AC | 116 ms
9,856 KB |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
#include <cmath>
#include <complex>
#include <regex>
#ifndef DBG_MACRO_DBG_H
#define DBG_MACRO_DBG_H
#if defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#define DBG_MACRO_UNIX
#elif defined(_MSC_VER)
#define DBG_MACRO_WINDOWS
#endif
#include <algorithm>
#include <chrono>
#include <ctime>
#include <iomanip>
#include <ios>
#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <vector>
#ifdef DBG_MACRO_UNIX
#include <unistd.h>
#endif
#if __cplusplus >= 201703L
#define DBG_MACRO_CXX_STANDARD 17
#elif __cplusplus >= 201402L
#define DBG_MACRO_CXX_STANDARD 14
#else
#define DBG_MACRO_CXX_STANDARD 11
#endif
#if DBG_MACRO_CXX_STANDARD >= 17
#include <optional>
#include <variant>
#endif
namespace dbg {
#ifdef DBG_MACRO_UNIX
inline bool isColorizedOutputEnabled() { return isatty(fileno(stderr)); }
#else
inline bool isColorizedOutputEnabled() { return true; }
#endif
struct time {};
namespace pretty_function {
// Compiler-agnostic version of __PRETTY_FUNCTION__ and constants to
// extract the template argument in `type_name_impl`
#if defined(__clang__)
#define DBG_MACRO_PRETTY_FUNCTION __PRETTY_FUNCTION__
static constexpr size_t PREFIX_LENGTH =
sizeof("const char *dbg::type_name_impl() [T = ") - 1;
static constexpr size_t SUFFIX_LENGTH = sizeof("]") - 1;
#elif defined(__GNUC__) && !defined(__clang__)
#define DBG_MACRO_PRETTY_FUNCTION __PRETTY_FUNCTION__
static constexpr size_t PREFIX_LENGTH =
sizeof("const char* dbg::type_name_impl() [with T = ") - 1;
static constexpr size_t SUFFIX_LENGTH = sizeof("]") - 1;
#elif defined(_MSC_VER)
#define DBG_MACRO_PRETTY_FUNCTION __FUNCSIG__
static constexpr size_t PREFIX_LENGTH =
sizeof("const char *__cdecl dbg::type_name_impl<") - 1;
static constexpr size_t SUFFIX_LENGTH = sizeof(">(void)") - 1;
#else
#error "This compiler is currently not supported by dbg_macro."
#endif
} // namespace pretty_function
// Formatting helpers
template <typename T>
struct print_formatted {
static_assert(std::is_integral<T>::value,
"Only integral types are supported.");
print_formatted(T value, int numeric_base)
: inner(value), base(numeric_base) {}
operator T() const { return inner; }
const char* prefix() const {
switch (base) {
case 8:
return "0o";
case 16:
return "0x";
case 2:
return "0b";
default:
return "";
}
}
T inner;
int base;
};
template <typename T>
print_formatted<T> hex(T value) {
return print_formatted<T>{value, 16};
}
template <typename T>
print_formatted<T> oct(T value) {
return print_formatted<T>{value, 8};
}
template <typename T>
print_formatted<T> bin(T value) {
return print_formatted<T>{value, 2};
}
// Implementation of 'type_name<T>()'
template <typename T>
const char* type_name_impl() {
return DBG_MACRO_PRETTY_FUNCTION;
}
template <typename T>
struct type_tag {};
template <int&... ExplicitArgumentBarrier, typename T>
std::string get_type_name(type_tag<T>) {
namespace pf = pretty_function;
std::string type = type_name_impl<T>();
return type.substr(pf::PREFIX_LENGTH,
type.size() - pf::PREFIX_LENGTH - pf::SUFFIX_LENGTH);
}
template <typename T>
std::string type_name() {
if (std::is_volatile<T>::value) {
if (std::is_pointer<T>::value) {
return type_name<typename std::remove_volatile<T>::type>() + " volatile";
} else {
return "volatile " + type_name<typename std::remove_volatile<T>::type>();
}
}
if (std::is_const<T>::value) {
if (std::is_pointer<T>::value) {
return type_name<typename std::remove_const<T>::type>() + " const";
} else {
return "const " + type_name<typename std::remove_const<T>::type>();
}
}
if (std::is_pointer<T>::value) {
return type_name<typename std::remove_pointer<T>::type>() + "*";
}
if (std::is_lvalue_reference<T>::value) {
return type_name<typename std::remove_reference<T>::type>() + "&";
}
if (std::is_rvalue_reference<T>::value) {
return type_name<typename std::remove_reference<T>::type>() + "&&";
}
return get_type_name(type_tag<T>{});
}
inline std::string get_type_name(type_tag<short>) { return "short"; }
inline std::string get_type_name(type_tag<unsigned short>) {
return "unsigned short";
}
inline std::string get_type_name(type_tag<long>) { return "long"; }
inline std::string get_type_name(type_tag<unsigned long>) {
return "unsigned long";
}
inline std::string get_type_name(type_tag<std::string>) {
return "std::string";
}
template <typename T>
std::string get_type_name(type_tag<std::vector<T, std::allocator<T>>>) {
return "std::vector<" + type_name<T>() + ">";
}
template <typename T1, typename T2>
std::string get_type_name(type_tag<std::pair<T1, T2>>) {
return "std::pair<" + type_name<T1>() + ", " + type_name<T2>() + ">";
}
template <typename... T>
std::string type_list_to_string() {
std::string result;
auto unused = {(result += type_name<T>() + ", ", 0)..., 0};
static_cast<void>(unused);
#if DBG_MACRO_CXX_STANDARD >= 17
if constexpr (sizeof...(T) > 0) {
#else
if (sizeof...(T) > 0) {
#endif
result.pop_back();
result.pop_back();
}
return result;
}
template <typename... T>
std::string get_type_name(type_tag<std::tuple<T...>>) {
return "std::tuple<" + type_list_to_string<T...>() + ">";
}
template <typename T>
inline std::string get_type_name(type_tag<print_formatted<T>>) {
return type_name<T>();
}
// Implementation of 'is_detected' to specialize for container-like types
namespace detail_detector {
struct nonesuch {
nonesuch() = delete;
~nonesuch() = delete;
nonesuch(nonesuch const&) = delete;
void operator=(nonesuch const&) = delete;
};
template <typename...>
using void_t = void;
template <class Default, class AlwaysVoid, template <class...> class Op,
class... Args>
struct detector {
using value_t = std::false_type;
using type = Default;
};
template <class Default, template <class...> class Op, class... Args>
struct detector<Default, void_t<Op<Args...>>, Op, Args...> {
using value_t = std::true_type;
using type = Op<Args...>;
};
} // namespace detail_detector
template <template <class...> class Op, class... Args>
using is_detected =
typename detail_detector::detector<detail_detector::nonesuch, void, Op,
Args...>::value_t;
namespace detail {
namespace {
using std::begin;
using std::end;
#if DBG_MACRO_CXX_STANDARD < 17
template <typename T>
constexpr auto size(const T& c) -> decltype(c.size()) {
return c.size();
}
template <typename T, std::size_t N>
constexpr std::size_t size(const T (&)[N]) {
return N;
}
#else
using std::size;
#endif
} // namespace
template <typename T>
using detect_begin_t = decltype(detail::begin(std::declval<T>()));
template <typename T>
using detect_end_t = decltype(detail::end(std::declval<T>()));
template <typename T>
using detect_size_t = decltype(detail::size(std::declval<T>()));
template <typename T>
struct is_container {
static constexpr bool value =
is_detected<detect_begin_t, T>::value &&
is_detected<detect_end_t, T>::value &&
is_detected<detect_size_t, T>::value &&
!std::is_same<std::string,
typename std::remove_cv<
typename std::remove_reference<T>::type>::type>::value;
};
template <typename T>
using ostream_operator_t =
decltype(std::declval<std::ostream&>() << std::declval<T>());
template <typename T>
struct has_ostream_operator : is_detected<ostream_operator_t, T> {};
} // namespace detail
// Helper to dbg(…)-print types
template <typename T>
struct print_type {};
template <typename T>
print_type<T> type() {
return print_type<T>{};
}
// Forward declarations of "pretty_print"
template <typename T>
inline void pretty_print(std::ostream& stream, const T& value, std::true_type);
template <typename T>
inline void pretty_print(std::ostream&, const T&, std::false_type);
template <typename T>
inline typename std::enable_if<!detail::is_container<const T&>::value &&
!std::is_enum<T>::value,
bool>::type
pretty_print(std::ostream& stream, const T& value);
inline bool pretty_print(std::ostream& stream, const bool& value);
inline bool pretty_print(std::ostream& stream, const char& value);
template <typename P>
inline bool pretty_print(std::ostream& stream, P* const& value);
template <typename T, typename Deleter>
inline bool pretty_print(std::ostream& stream,
std::unique_ptr<T, Deleter>& value);
template <typename T>
inline bool pretty_print(std::ostream& stream, std::shared_ptr<T>& value);
template <size_t N>
inline bool pretty_print(std::ostream& stream, const char (&value)[N]);
template <>
inline bool pretty_print(std::ostream& stream, const char* const& value);
template <typename... Ts>
inline bool pretty_print(std::ostream& stream, const std::tuple<Ts...>& value);
template <>
inline bool pretty_print(std::ostream& stream, const std::tuple<>&);
template <>
inline bool pretty_print(std::ostream& stream, const time&);
template <typename T>
inline bool pretty_print(std::ostream& stream, const print_formatted<T>& value);
template <typename T>
inline bool pretty_print(std::ostream& stream, const print_type<T>&);
template <typename Enum>
inline typename std::enable_if<std::is_enum<Enum>::value, bool>::type
pretty_print(std::ostream& stream, Enum const& value);
inline bool pretty_print(std::ostream& stream, const std::string& value);
#if DBG_MACRO_CXX_STANDARD >= 17
inline bool pretty_print(std::ostream& stream, const std::string_view& value);
#endif
template <typename T1, typename T2>
inline bool pretty_print(std::ostream& stream, const std::pair<T1, T2>& value);
#if DBG_MACRO_CXX_STANDARD >= 17
template <typename T>
inline bool pretty_print(std::ostream& stream, const std::optional<T>& value);
template <typename... Ts>
inline bool pretty_print(std::ostream& stream,
const std::variant<Ts...>& value);
#endif
template <typename Container>
inline typename std::enable_if<detail::is_container<const Container&>::value,
bool>::type
pretty_print(std::ostream& stream, const Container& value);
// Specializations of "pretty_print"
template <typename T>
inline void pretty_print(std::ostream& stream, const T& value, std::true_type) {
stream << value;
}
template <typename T>
inline void pretty_print(std::ostream&, const T&, std::false_type) {
static_assert(detail::has_ostream_operator<const T&>::value,
"Type does not support the << ostream operator");
}
template <typename T>
inline typename std::enable_if<!detail::is_container<const T&>::value &&
!std::is_enum<T>::value,
bool>::type
pretty_print(std::ostream& stream, const T& value) {
pretty_print(stream, value,
typename detail::has_ostream_operator<const T&>::type{});
return true;
}
inline bool pretty_print(std::ostream& stream, const bool& value) {
stream << std::boolalpha << value;
return true;
}
inline bool pretty_print(std::ostream& stream, const char& value) {
const bool printable = value >= 0x20 && value <= 0x7E;
if (printable) {
stream << "'" << value << "'";
} else {
stream << "'\\x" << std::setw(2) << std::setfill('0') << std::hex
<< std::uppercase << (0xFF & value) << "'";
}
return true;
}
template <typename P>
inline bool pretty_print(std::ostream& stream, P* const& value) {
if (value == nullptr) {
stream << "nullptr";
} else {
stream << value;
}
return true;
}
template <typename T, typename Deleter>
inline bool pretty_print(std::ostream& stream,
std::unique_ptr<T, Deleter>& value) {
pretty_print(stream, value.get());
return true;
}
template <typename T>
inline bool pretty_print(std::ostream& stream, std::shared_ptr<T>& value) {
pretty_print(stream, value.get());
stream << " (use_count = " << value.use_count() << ")";
return true;
}
template <size_t N>
inline bool pretty_print(std::ostream& stream, const char (&value)[N]) {
stream << value;
return false;
}
template <>
inline bool pretty_print(std::ostream& stream, const char* const& value) {
stream << '"' << value << '"';
return true;
}
template <size_t Idx>
struct pretty_print_tuple {
template <typename... Ts>
static void print(std::ostream& stream, const std::tuple<Ts...>& tuple) {
pretty_print_tuple<Idx - 1>::print(stream, tuple);
stream << ", ";
pretty_print(stream, std::get<Idx>(tuple));
}
};
template <>
struct pretty_print_tuple<0> {
template <typename... Ts>
static void print(std::ostream& stream, const std::tuple<Ts...>& tuple) {
pretty_print(stream, std::get<0>(tuple));
}
};
template <typename... Ts>
inline bool pretty_print(std::ostream& stream, const std::tuple<Ts...>& value) {
stream << "{";
pretty_print_tuple<sizeof...(Ts) - 1>::print(stream, value);
stream << "}";
return true;
}
template <>
inline bool pretty_print(std::ostream& stream, const std::tuple<>&) {
stream << "{}";
return true;
}
template <>
inline bool pretty_print(std::ostream& stream, const time&) {
using namespace std::chrono;
const auto now = system_clock::now();
const auto us =
duration_cast<microseconds>(now.time_since_epoch()).count() % 1000000;
const auto hms = system_clock::to_time_t(now);
const std::tm* tm = std::localtime(&hms);
stream << "current time = " << std::put_time(tm, "%H:%M:%S") << '.'
<< std::setw(6) << std::setfill('0') << us;
return false;
}
// Converts decimal integer to binary string
template <typename T>
std::string decimalToBinary(T n) {
const size_t length = 8 * sizeof(T);
std::string toRet;
toRet.resize(length);
for (size_t i = 0; i < length; ++i) {
const auto bit_at_index_i = static_cast<char>((n >> i) & 1);
toRet[length - 1 - i] = bit_at_index_i + '0';
}
return toRet;
}
template <typename T>
inline bool pretty_print(std::ostream& stream,
const print_formatted<T>& value) {
if (value.inner < 0) {
stream << "-";
}
stream << value.prefix();
// Print using setbase
if (value.base != 2) {
stream << std::setw(sizeof(T)) << std::setfill('0')
<< std::setbase(value.base) << std::uppercase;
if (value.inner >= 0) {
// The '+' sign makes sure that a uint_8 is printed as a number
stream << +value.inner;
} else {
using unsigned_type = typename std::make_unsigned<T>::type;
stream << +(static_cast<unsigned_type>(-(value.inner + 1)) + 1);
}
} else {
// Print for binary
if (value.inner >= 0) {
stream << decimalToBinary(value.inner);
} else {
using unsigned_type = typename std::make_unsigned<T>::type;
stream << decimalToBinary<unsigned_type>(
static_cast<unsigned_type>(-(value.inner + 1)) + 1);
}
}
return true;
}
template <typename T>
inline bool pretty_print(std::ostream& stream, const print_type<T>&) {
stream << type_name<T>();
stream << " [sizeof: " << sizeof(T) << " byte, ";
stream << "trivial: ";
if (std::is_trivial<T>::value) {
stream << "yes";
} else {
stream << "no";
}
stream << ", standard layout: ";
if (std::is_standard_layout<T>::value) {
stream << "yes";
} else {
stream << "no";
}
stream << "]";
return false;
}
template <typename Enum>
inline typename std::enable_if<std::is_enum<Enum>::value, bool>::type
pretty_print(std::ostream& stream, Enum const& value) {
using UnderlyingType = typename std::underlying_type<Enum>::type;
stream << static_cast<UnderlyingType>(value);
return true;
}
inline bool pretty_print(std::ostream& stream, const std::string& value) {
stream << '"' << value << '"';
return true;
}
#if DBG_MACRO_CXX_STANDARD >= 17
inline bool pretty_print(std::ostream& stream, const std::string_view& value) {
stream << '"' << std::string(value) << '"';
return true;
}
#endif
template <typename T1, typename T2>
inline bool pretty_print(std::ostream& stream, const std::pair<T1, T2>& value) {
stream << "{";
pretty_print(stream, value.first);
stream << ", ";
pretty_print(stream, value.second);
stream << "}";
return true;
}
#if DBG_MACRO_CXX_STANDARD >= 17
template <typename T>
inline bool pretty_print(std::ostream& stream, const std::optional<T>& value) {
if (value) {
stream << '{';
pretty_print(stream, *value);
stream << '}';
} else {
stream << "nullopt";
}
return true;
}
template <typename... Ts>
inline bool pretty_print(std::ostream& stream,
const std::variant<Ts...>& value) {
stream << "{";
std::visit([&stream](auto&& arg) { pretty_print(stream, arg); }, value);
stream << "}";
return true;
}
#endif
template <typename Container>
inline typename std::enable_if<detail::is_container<const Container&>::value,
bool>::type
pretty_print(std::ostream& stream, const Container& value) {
stream << "{";
const size_t size = detail::size(value);
const size_t n = std::min(size_t{10}, size);
size_t i = 0;
using std::begin;
using std::end;
for (auto it = begin(value); it != end(value) && i < n; ++it, ++i) {
pretty_print(stream, *it);
if (i != n - 1) {
stream << ", ";
}
}
if (size > n) {
stream << ", ...";
stream << " size:" << size;
}
stream << "}";
return true;
}
template <typename T, typename... U>
struct last {
using type = typename last<U...>::type;
};
template <typename T>
struct last<T> {
using type = T;
};
template <typename... T>
using last_t = typename last<T...>::type;
class DebugOutput {
public:
// Helper alias to avoid obscure type `const char* const*` in signature.
using expr_t = const char*;
DebugOutput(const char* filepath, int line, const char* function_name)
: m_use_colorized_output(isColorizedOutputEnabled()) {
std::string path = filepath;
const std::size_t path_length = path.length();
if (path_length > MAX_PATH_LENGTH) {
path = ".." + path.substr(path_length - MAX_PATH_LENGTH, MAX_PATH_LENGTH);
}
std::stringstream ss;
ss << ansi(ANSI_DEBUG) << "[" << path << ":" << line << " ("
<< function_name << ")] " << ansi(ANSI_RESET);
m_location = ss.str();
}
template <typename... T>
auto print(std::initializer_list<expr_t> exprs,
std::initializer_list<std::string> types, T&&... values)
-> last_t<T...> {
if (exprs.size() != sizeof...(values)) {
std::cerr
<< m_location << ansi(ANSI_WARN)
<< "The number of arguments mismatch, please check unprotected comma"
<< ansi(ANSI_RESET) << std::endl;
}
return print_impl(exprs.begin(), types.begin(), std::forward<T>(values)...);
}
private:
template <typename T>
T&& print_impl(const expr_t* expr, const std::string* type, T&& value) {
const T& ref = value;
std::stringstream stream_value;
const bool print_expr_and_type = pretty_print(stream_value, ref);
std::stringstream output;
output << m_location;
if (print_expr_and_type) {
output << ansi(ANSI_EXPRESSION) << *expr << ansi(ANSI_RESET) << " = ";
}
output << ansi(ANSI_VALUE) << stream_value.str() << ansi(ANSI_RESET);
if (print_expr_and_type) {
output << " (" << ansi(ANSI_TYPE) << *type << ansi(ANSI_RESET) << ")";
}
output << std::endl;
std::cerr << output.str();
return std::forward<T>(value);
}
template <typename T, typename... U>
auto print_impl(const expr_t* exprs, const std::string* types, T&& value,
U&&... rest) -> last_t<T, U...> {
print_impl(exprs, types, std::forward<T>(value));
return print_impl(exprs + 1, types + 1, std::forward<U>(rest)...);
}
const char* ansi(const char* code) const {
if (m_use_colorized_output) {
return code;
} else {
return ANSI_EMPTY;
}
}
const bool m_use_colorized_output;
std::string m_location;
static constexpr std::size_t MAX_PATH_LENGTH = 20;
static constexpr const char* const ANSI_EMPTY = "";
static constexpr const char* const ANSI_DEBUG = "\x1b[02m";
static constexpr const char* const ANSI_WARN = "\x1b[33m";
static constexpr const char* const ANSI_EXPRESSION = "\x1b[36m";
static constexpr const char* const ANSI_VALUE = "\x1b[01m";
static constexpr const char* const ANSI_TYPE = "\x1b[32m";
static constexpr const char* const ANSI_RESET = "\x1b[0m";
};
// Identity function to suppress "-Wunused-value" warnings in DBG_MACRO_DISABLE
// mode
template <typename T>
T&& identity(T&& t) {
return std::forward<T>(t);
}
template <typename T, typename... U>
auto identity(T&&, U&&... u) -> last_t<U...> {
return identity(std::forward<U>(u)...);
}
} // namespace dbg
#ifndef DBG_MACRO_DISABLE
// Force expanding argument with commas for MSVC, ref:
// https://stackoverflow.com/questions/35210637/macro-expansion-argument-with-commas
// Note that "args" should be a tuple with parentheses, such as "(e1, e2, ...)".
#define DBG_IDENTITY(x) x
#define DBG_CALL(fn, args) DBG_IDENTITY(fn args)
#define DBG_CAT_IMPL(_1, _2) _1##_2
#define DBG_CAT(_1, _2) DBG_CAT_IMPL(_1, _2)
#define DBG_16TH_IMPL(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, \
_14, _15, _16, ...) \
_16
#define DBG_16TH(args) DBG_CALL(DBG_16TH_IMPL, args)
#define DBG_NARG(...) \
DBG_16TH((__VA_ARGS__, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0))
// DBG_VARIADIC_CALL(fn, data, e1, e2, ...) => fn_N(data, (e1, e2, ...))
#define DBG_VARIADIC_CALL(fn, data, ...) \
DBG_CAT(fn##_, DBG_NARG(__VA_ARGS__))(data, (__VA_ARGS__))
// (e1, e2, e3, ...) => e1
#define DBG_HEAD_IMPL(_1, ...) _1
#define DBG_HEAD(args) DBG_CALL(DBG_HEAD_IMPL, args)
// (e1, e2, e3, ...) => (e2, e3, ...)
#define DBG_TAIL_IMPL(_1, ...) (__VA_ARGS__)
#define DBG_TAIL(args) DBG_CALL(DBG_TAIL_IMPL, args)
#define DBG_MAP_1(fn, args) DBG_CALL(fn, args)
#define DBG_MAP_2(fn, args) fn(DBG_HEAD(args)), DBG_MAP_1(fn, DBG_TAIL(args))
#define DBG_MAP_3(fn, args) fn(DBG_HEAD(args)), DBG_MAP_2(fn, DBG_TAIL(args))
#define DBG_MAP_4(fn, args) fn(DBG_HEAD(args)), DBG_MAP_3(fn, DBG_TAIL(args))
#define DBG_MAP_5(fn, args) fn(DBG_HEAD(args)), DBG_MAP_4(fn, DBG_TAIL(args))
#define DBG_MAP_6(fn, args) fn(DBG_HEAD(args)), DBG_MAP_5(fn, DBG_TAIL(args))
#define DBG_MAP_7(fn, args) fn(DBG_HEAD(args)), DBG_MAP_6(fn, DBG_TAIL(args))
#define DBG_MAP_8(fn, args) fn(DBG_HEAD(args)), DBG_MAP_7(fn, DBG_TAIL(args))
#define DBG_MAP_9(fn, args) fn(DBG_HEAD(args)), DBG_MAP_8(fn, DBG_TAIL(args))
#define DBG_MAP_10(fn, args) fn(DBG_HEAD(args)), DBG_MAP_9(fn, DBG_TAIL(args))
#define DBG_MAP_11(fn, args) fn(DBG_HEAD(args)), DBG_MAP_10(fn, DBG_TAIL(args))
#define DBG_MAP_12(fn, args) fn(DBG_HEAD(args)), DBG_MAP_11(fn, DBG_TAIL(args))
#define DBG_MAP_13(fn, args) fn(DBG_HEAD(args)), DBG_MAP_12(fn, DBG_TAIL(args))
#define DBG_MAP_14(fn, args) fn(DBG_HEAD(args)), DBG_MAP_13(fn, DBG_TAIL(args))
#define DBG_MAP_15(fn, args) fn(DBG_HEAD(args)), DBG_MAP_14(fn, DBG_TAIL(args))
#define DBG_MAP_16(fn, args) fn(DBG_HEAD(args)), DBG_MAP_15(fn, DBG_TAIL(args))
// DBG_MAP(fn, e1, e2, e3, ...) => fn(e1), fn(e2), fn(e3), ...
#define DBG_MAP(fn, ...) DBG_VARIADIC_CALL(DBG_MAP, fn, __VA_ARGS__)
#define DBG_STRINGIFY_IMPL(x) #x
#define DBG_STRINGIFY(x) DBG_STRINGIFY_IMPL(x)
#define DBG_TYPE_NAME(x) dbg::type_name<decltype(x)>()
#define dbg(...) \
dbg::DebugOutput(__FILE__, __LINE__, __func__) \
.print({DBG_MAP(DBG_STRINGIFY, __VA_ARGS__)}, \
{DBG_MAP(DBG_TYPE_NAME, __VA_ARGS__)}, __VA_ARGS__)
#else
#define dbg(...) dbg::identity(__VA_ARGS__)
#endif // DBG_MACRO_DISABLE
#endif // DBG_MACRO_DBG_H
// END DEBUG MACRO
//////////////////////////////////////////////////////////////
// START MACROS
//////////////////////////////////////////////////////////////
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= n; ++i)
#define reps(i, s, e) for (ll i = s; i < e; ++i)
#define rrep(i, n) for (ll i = n - 1; 0 <= i; --i)
#define fore(i, a) for (auto& i : a)
#define cina(a) cin >> a;
#define cinb(a, b) cin >> a >> b;
#define cinc(a, b, c) cin >> a >> b >> c;
#define cind(a, b, c, d) cin >> a >> b >> c >> d;
#define cine(a, b, c, d, e) cin >> a >> b >> c >> d >> e;
#define cendl std::cout << endl;
#define pcnt __builtin_popcount
#define forcin(a) \
for (auto& it : a) cin >> it;
#define p(ans) std::cout << ans << endl;
#define p2(ans, ans2) std::cout << ans << " " << ans2 << endl;
#define p3(ans, ans2, ans3) \
std::cout << ans << " " << ans2 << " " << ans3 << endl;
#define p4(ans, ans2, ans3, ans4) \
std::cout << ans << " " << ans2 << " " << ans3 << " " << ans4 << endl;
#define dd(arg) cerr << " | " << #arg << " = | " << arg << " | " << endl;
#define dd2(arg, arg2) \
cerr << "| " << #arg << " = " << arg << " | " << #arg2 << " = " << arg2 \
<< " | " << endl;
#define dd3(arg, arg2, arg3) \
cerr << "| " << #arg << " = " << arg << " | " << #arg2 << " = " << arg2 \
<< " | " << #arg3 << " = " << arg3 << " | " << endl;
#define dd4(arg, arg2, arg3, arg4) \
cerr << "| " << #arg << " = " << arg << " | " << #arg2 << " = " << arg2 \
<< " | " << #arg3 << " = " << arg3 << " | " << #arg4 << " = " << arg4 \
<< " | " << endl;
#define dl(n, l) \
{ \
cerr << " | " << #l << " = "; \
for (int z = 0; z < n; ++z) { \
if (z == n - 1) { \
cerr << l[z] << " | " << endl; \
} else { \
cerr << l[z] << " "; \
} \
} \
};
#define pl(n, l) \
{ \
for (int z = 0; z < n; ++z) { \
if (z == n - 1) { \
cout << l[z] << endl; \
} else { \
cout << l[z] << " "; \
} \
} \
};
#define pb push_back
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define endl '\n'
#define posl(vec, elm) lower_bound(vec.begin(), vec.end(), elm) - vec.begin()
#define posu(vec, elm) upper_bound(vec.begin(), vec.end(), elm) - vec.begin()
template <class T>
inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
template <class T>
inline bool pmap(T& mp) {
cerr << "| ";
for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
cerr << "key: " << itr->first << ", val: " << itr->second << " | ";
}
cerr << endl;
return 0;
}
using ll = long long;
using Real = long double;
using CP = complex<Real>;
using P = pair<ll, ll>;
using st = string;
using vs = vector<string>;
using vc = vector<char>;
using vvi = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using vi = vector<ll>;
const ll MOD1 = 1000000007;
const ll MOD2 = 998244353;
const ll LINF = (1LL << 60);
const int INF = (1000000007);
const Real EPS = 1e-10;
const long double PI = 3.141592653589793238462643383279502884L;
// std::cout << fixed << setprecision(15);
ll lcm(ll x, ll y) { return ll(x / gcd(x, y)) * y; }
bool isprime(ll n) {
if (n == 2) return true;
if (n < 2 || !(n & 1)) return false;
ll i = 3;
while (i <= sqrt(n)) {
if (n % i == 0) return false;
i += 2;
}
return true;
}
vi prime_factors(ll n) {
ll rem = n;
vi p;
for (ll i = 2; i * i <= n; i++) {
while (rem % i == 0) {
rem /= i;
p.pb(i);
}
}
if (rem != 1LL) p.pb(rem);
return p;
}
map<ll, int> prime_factorize_count(ll n) {
map<ll, int> V;
for (ll i = 2; i * i <= n; i++)
while (n % i == 0) V[i]++, n /= i;
if (n > 1) V[n]++;
return V;
}
ll modpow(ll a, ll n, ll mod) {
ll res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
ll nck(ll n, ll k, ll modd) {
ll p = 1, q = 1;
for (ll i = 0; i < k; i++) {
p = p * (n - i) % modd;
q = q * (i + 1) % modd;
}
return p * modpow(q, modd - 2, modd) % modd;
}
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, 1, 0, -1};
vector<P> dydx = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
vi enum_divisors(ll N) {
vi res;
for (ll i = 1; i * i <= N; ++i) {
if (N % i == 0) {
res.push_back(i);
if (N / i != i) res.push_back(N / i);
}
}
sort(res.begin(), res.end());
return res;
}
const int mod = MOD1;
struct mint {
ll x;
mint(ll x = 0) : x((x % mod + mod) % mod) {}
mint operator-() const { return mint(-x); }
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod - a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const { return mint(*this) += a; }
mint operator-(const mint a) const { return mint(*this) -= a; }
mint operator*(const mint a) const { return mint(*this) *= a; }
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t >> 1);
a *= a;
if (t & 1) a *= *this;
return a;
}
mint inv() const { return pow(mod - 2); }
mint& operator/=(const mint a) { return *this *= a.inv(); }
mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
struct combination {
vector<mint> fact, ifact;
combination(int n) : fact(n + 1), ifact(n + 1) {
assert(n < mod);
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * ifact[k] * ifact[n - k];
}
};
void init() {
cin.tie(0);
std::cout.tie(0);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(15);
}
void _main();
int main() {
init();
_main();
};
//////////////////////////////////////////////////////////////
//
//////////////////////////////////////////////////////////////
ll n, q;
//////////////////////////////////////////////////////////////
template <class V, int ME>
class BIT {
public:
V bit[1 << ME], val[1 << ME];
V operator()(int e) {
if (e < 0) return 0;
V s = 0;
e++;
while (e) s += bit[e - 1], e -= e & -e;
return s;
}
void add(int e, V v) {
val[e++] += v;
while (e <= 1 << ME) bit[e - 1] += v, e += e & -e;
}
void set(int e, V v) { add(e, v - val[e]); }
int lower_bound(V val) {
V tv = 0;
int i, ent = 0;
for (i = ME - 1; i >= 0; i--)
if (tv + bit[ent + (1 << i) - 1] < val)
tv += bit[ent + (1 << i) - 1], ent += (1 << i);
return ent;
}
};
BIT<ll, 20> num, sum;
void _main() {
cinb(n, q);
num.add(0, 1);
num.add(n + 1, 1);
ll x;
rep(i, n) {
cina(x);
num.add(i + 1, 1);
sum.add(i + 1, x);
}
while (q--) {
ll t, l, r;
cinc(t, l, r);
if (t == 1) {
ll del = r - l;
while (del--) {
x = num.lower_bound(l + 1);
num.add(x, -1);
}
} else {
l = num.lower_bound(l);
r = num.lower_bound(r + 1);
p(sum(r) - sum(l));
}
}
}