結果
| 問題 | No.3533 Difficult Counting Problem? |
| コンテスト | |
| ユーザー |
 Today03
|
| 提出日時 | 2026-07-20 12:11:51 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 2,000 ms |
| + 318µs | |
| コード長 | 54,045 bytes |
| 記録 | |
| コンパイル時間 | 1,904 ms |
| コンパイル使用メモリ | 279,384 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-07-20 12:12:40 |
| 合計ジャッジ時間 | 3,255 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 17 |
ソースコード
#ifdef TODAY_KYOPRO
/*
*/
void run() {
II(N);
say(QYN(N == 1, 1, 0));
}
void prep() {}
#else
#define MULTI
//------>8-------- begin kyopro_library/template.hpp --------->8------
//------>8------ begin kyopro_library/base/include.hpp ------->8------
#include <iostream>
#include <algorithm>
#include <type_traits>
#include <vector>
#include <cassert>
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <utility>
#include <chrono>
using namespace std;
//------>8------- end kyopro_library/base/include.hpp -------->8------
//------>8------- begin kyopro_library/base/fastio.hpp ------->8------
//------>8-------- begin kyopro_library/base/type.hpp -------->8------
using i16 = short;
using i32 = int;
using i64 = long long;
using i128 = __int128_t;
using u16 = unsigned short;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using f64 = double;
using f80 = long double;
using ii = i64;
using ll = i64;
using ull = u64;
using vi = vector<ii>;
using vvi = vector<vector<ii>>;
using vvvi = vector<vector<vector<ii>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using ii3 = array<ii, 3>;
using ii4 = array<ii, 4>;
using ii5 = array<ii, 5>;
using lll = i128;
using ulll = u128;
constexpr lll operator""_lll(ull x) { return static_cast<lll>(x); }
using ld = f80;
using str = string;
using vstr = vector<str>;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
template <typename T>
using VVV = vector<vector<vector<T>>>;
template <typename T>
using VVVV = vector<vector<vector<vector<T>>>>;
template <typename T>
using VVVVV = vector<vector<vector<vector<vector<T>>>>>;
template <typename T>
using VVVVVV = vector<vector<vector<vector<vector<vector<T>>>>>>;
template <typename T>
using max_pq = priority_queue<T>;
template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using unset = unordered_set<T>;
template <typename T, typename T2>
using unmap = unordered_map<T, T2>;
template <typename T, typename U>
struct PR : pair<T, U> {
template <typename... Args>
PR(Args... args) : pair<T, U>(args...) {}
using pair<T, U>::first;
using pair<T, U>::second;
PR& operator+=(const PR& r) {
first += r.first;
second += r.second;
return *this;
}
PR& operator-=(const PR& r) {
first -= r.first;
second -= r.second;
return *this;
}
PR& operator*=(const PR& r) {
first *= r.first;
second *= r.second;
return *this;
}
template <typename S>
PR& operator+=(const S& r) {
first += r;
second += r;
return *this;
}
template <typename S>
PR& operator-=(const S& r) {
first -= r;
second -= r;
return *this;
}
template <typename S>
PR& operator*=(const S& r) {
first *= r;
second *= r;
return *this;
}
PR operator+(const PR& r) const { return PR(*this) += r; }
PR operator-(const PR& r) const { return PR(*this) -= r; }
PR operator*(const PR& r) const { return PR(*this) *= r; }
template <typename S>
PR operator+(const S& r) const { return PR(*this) += r; }
template <typename S>
PR operator-(const S& r) const { return PR(*this) -= r; }
template <typename S>
PR operator*(const S& r) const { return PR(*this) *= r; }
PR operator-() const { return PR{-first, -second}; }
};
using pi = PR<ii, ii>;
using vpi = vector<pi>;
using vvpi = vector<vector<pi>>;
using pl = PR<ll, ll>;
using vpl = vector<pl>;
using vvpl = vector<vector<pl>>;
template <typename T, typename U, typename V>
struct TR : tuple<T, U, V> {
using tuple<T, U, V>::tuple;
T& x = get<0>(*this);
U& y = get<1>(*this);
V& z = get<2>(*this);
TR() : tuple<T, U, V>() {}
TR(const T& a, const U& b, const V& c) : tuple<T, U, V>(a, b, c) {}
TR(const TR& other) : tuple<T, U, V>(other), x(get<0>(*this)), y(get<1>(*this)), z(get<2>(*this)) {}
TR(TR&& other) noexcept : tuple<T, U, V>(move(other)), x(get<0>(*this)), y(get<1>(*this)), z(get<2>(*this)) {}
TR& operator=(const TR& other) {
tuple<T, U, V>::operator=(other);
return *this;
}
TR& operator=(TR&& other) noexcept {
tuple<T, U, V>::operator=(move(other));
return *this;
}
};
using ti = TR<ii, ii, ii>;
using vti = vector<ti>;
using vvti = vector<vector<ti>>;
using tl = TR<ll, ll, ll>;
using vtl = vector<ti>;
using vvtl = vector<vector<tl>>;
const i32 INF = 1e9 + 10;
const i64 INFL = 4e18;
const i128 INFLL = 1_lll << 120;
template <typename T>
constexpr T inf = 0;
template <>
constexpr i32 inf<i32> = INF;
template <>
constexpr i64 inf<i64> = INFL;
template <>
constexpr i128 inf<i128> = INFLL;
template <>
constexpr u32 inf<u32> = INF;
template <>
constexpr u64 inf<u64> = INFL;
template <>
constexpr u128 inf<u128> = INFLL;
template <>
constexpr f64 inf<f64> = numeric_limits<f64>::infinity();
template <>
constexpr f80 inf<f80> = numeric_limits<f80>::infinity();
istream& operator>>(istream& is, lll& x) {
int c = is.peek();
while(c == ' ' || c == '\n') is.get(), c = is.peek();
bool neg = false;
if(c == '-') neg = true, is.get();
x = 0;
while(isdigit(is.peek())) x = x * 10 + is.get() - '0';
if(neg) x = -x;
return is;
}
ostream& operator<<(ostream& os, lll x) {
if(x < 0) os << '-', x = -x;
if(x == 0) return os << '0';
string s;
while(x > 0) s += x % 10 + '0', x /= 10;
reverse(s.begin(), s.end());
return os << s;
}
#ifdef TDY
lll abs(lll x) {
if(x < 0) return -x;
return x;
}
lll gcd(lll a, lll b) {
while(b) a %= b, swap(a, b);
return a;
}
#endif
//------>8--------- end kyopro_library/base/type.hpp --------->8------
#include <cstdio>
#include <cstring>
#include <cstdlib>
/// @brief 高速入出力 (fread/fwrite ベース)。cin/cout を透過的に置換する
/// @note 既存の input()/say/line/put/operator<< やマクロ・生 cin/cout がそのまま高速化される。
/// @note 未対応の型 (modint/fraction/set/deque など) は同一バッファを共有する
/// std ストリームへフォールバックするため、書式・順序は従来と一致する。
/// @note operator>>/<< の本体は fastio_impl.hpp で定義する。フォールバック時に io.hpp の
/// グローバル operator<< (tuple/set/deque/array など) を通常の名前検索で見つけるため、
/// template.hpp が io.hpp を include した後に fastio_impl.hpp を include する。
/// @attention using namespace std 前提で裸の cin/cout を使うこと。std::cin / std::cout と
/// 完全修飾で書くと #define により壊れる。
namespace FastIO {
/// @brief pair (および PR など pair 派生型) を判定するコンセプト
template <typename A, typename B>
void pair_probe(const pair<A, B>&);
template <typename T>
concept PairLike = requires(const T& t) { pair_probe(t); };
template <typename>
struct is_vec : false_type {};
template <typename T>
struct is_vec<vector<T>> : true_type {};
template <typename>
struct is_vec2 : false_type {};
template <typename T>
struct is_vec2<vector<vector<T>>> : true_type {};
template <typename>
struct is_vec3 : false_type {};
template <typename T>
struct is_vec3<vector<vector<vector<T>>>> : true_type {};
/// @brief fread で stdin をチャンク読みする streambuf
struct Reader : streambuf {
static constexpr int SZ = 1 << 18;
char buf[SZ];
Reader() { setg(buf, buf, buf); }
int_type underflow() override {
size_t n = fread(buf, 1, SZ, stdin);
setg(buf, buf, buf + n);
return n ? traits_type::to_int_type(buf[0]) : traits_type::eof();
}
/// @brief 1 文字取得して進める (EOF は -1)
int gc() { return this->sbumpc(); }
/// @brief 空白を読み飛ばし、最初の非空白文字を返す (消費済み)
int skip_ws() {
int c = gc();
while(c == ' ' || c == '\n' || c == '\r' || c == '\t') c = gc();
return c;
}
template <typename T>
void read_int(T& x) {
int c = skip_ws();
bool neg = false;
if constexpr(is_signed_v<T>) {
if(c == '-') neg = true, c = gc();
}
T v = 0;
while(c >= '0' && c <= '9') v = v * 10 + (c - '0'), c = gc();
if constexpr(is_signed_v<T>) {
if(neg) v = -v;
}
x = v;
}
void read_i128(lll& x) {
int c = skip_ws();
bool neg = false;
if(c == '-') neg = true, c = gc();
ulll v = 0;
while(c >= '0' && c <= '9') v = v * 10 + (ulll)(c - '0'), c = gc();
x = neg ? -(lll)v : (lll)v;
}
void read_u128(ulll& x) {
int c = skip_ws();
ulll v = 0;
while(c >= '0' && c <= '9') v = v * 10 + (ulll)(c - '0'), c = gc();
x = v;
}
void read_char(char& ch) { ch = (char)skip_ws(); }
void read_str(string& s) {
s.clear();
int c = skip_ws();
while(c != -1 && c != ' ' && c != '\n' && c != '\r' && c != '\t') s += (char)c, c = gc();
}
template <typename F>
void read_float(F& x) {
static string t;
read_str(t);
x = (F)strtold(t.c_str(), nullptr);
}
};
/// @brief fwrite で stdout へ書き出す streambuf
struct Writer : streambuf {
static constexpr int SZ = 1 << 18;
char buf[SZ];
Writer() { setp(buf, buf + SZ); }
~Writer() { flush(); }
void flush() {
if(pbase() != pptr()) fwrite(pbase(), 1, pptr() - pbase(), stdout);
setp(buf, buf + SZ);
}
int_type overflow(int_type c) override {
flush();
if(c != traits_type::eof()) *pptr() = (char)c, pbump(1);
return c;
}
int sync() override {
flush();
fflush(stdout);
return 0;
}
void pc(char c) { this->sputc(c); }
void ps(const char* s, int n) { this->sputn(s, n); }
template <typename T>
void write_int(T x) {
using U = make_unsigned_t<T>;
U u;
bool neg = false;
if constexpr(is_signed_v<T>) {
if(x < 0) neg = true, u = U(0) - (U)x;
else u = (U)x;
} else u = (U)x;
char t[24];
int n = 0;
do t[n++] = (char)('0' + int(u % 10)), u /= 10;
while(u);
if(neg) pc('-');
while(n) pc(t[--n]);
}
void write_i128(lll x) {
bool neg = x < 0;
ulll u = neg ? (ulll)0 - (ulll)x : (ulll)x;
char t[40];
int n = 0;
do t[n++] = (char)('0' + int(u % 10)), u /= 10;
while(u);
if(neg) pc('-');
while(n) pc(t[--n]);
}
void write_u128(ulll u) {
char t[40];
int n = 0;
do t[n++] = (char)('0' + int(u % 10)), u /= 10;
while(u);
while(n) pc(t[--n]);
}
void write_float(long double x) {
char t[64];
int n = snprintf(t, sizeof(t), "%.15Lf", x);
ps(t, n);
}
};
/// @brief 高速入力ラッパ (cin を置換)。未対応型は fb (std::istream) にフォールバック
struct FastIn {
Reader rd;
istream fb{&rd};
template <typename T>
FastIn& operator>>(T& x); // 本体は fastio_impl.hpp
/// @brief std::ws などのマニピュレータ (テンプレート関数のため専用オーバーロードが必要)
FastIn& operator>>(istream& (*f)(istream&)) {
f(fb);
return *this;
}
template <typename T>
void tie(T) {}
};
/// @brief 高速出力ラッパ (cout を置換)。未対応型は fb (std::ostream) にフォールバック
struct FastOut {
Writer wt;
ostream fb{&wt};
FastOut() { fb << fixed << setprecision(15); }
void flush() {
wt.flush();
fflush(stdout);
}
template <typename T>
void write_vec1(const vector<T>& a) {
int n = a.size();
for(int i = 0; i < n; i++) {
*this << a[i];
if(i != n - 1) wt.pc(' ');
}
}
template <typename T>
void write_vec2(const vector<vector<T>>& a) {
int I = a.size();
for(int i = 0; i < I; i++) {
int J = a[i].size();
for(int j = 0; j < J; j++) {
*this << a[i][j];
if(j != J - 1) wt.pc(' ');
}
if(i != I - 1) wt.pc('\n');
}
}
template <typename T>
void write_vec3(const vector<vector<vector<T>>>& a) {
int I = a.size();
for(int i = 0; i < I; i++) {
int J = a[i].size();
for(int j = 0; j < J; j++) {
int K = a[i][j].size();
for(int k = 0; k < K; k++) {
*this << a[i][j][k];
if(k != K - 1) wt.pc(' ');
}
wt.pc('\n');
}
if(i != I - 1) wt.pc('\n');
}
}
template <typename T>
FastOut& operator<<(const T& x); // 本体は fastio_impl.hpp
/// @brief std::endl / std::flush / std::ends などのマニピュレータ
FastOut& operator<<(ostream& (*f)(ostream&)) {
f(fb);
return *this;
}
};
inline FastIn in;
inline FastOut out;
} // namespace FastIO
#define cin FastIO::in
#define cout FastIO::out
//------>8-------- end kyopro_library/base/fastio.hpp -------->8------
//------>8------- begin kyopro_library/base/macro.hpp -------->8------
#define rep1(n) for(ii i = 0; i < (n); i++)
#define rep2(i, n) for(ii i = 0; i < (n); i++)
#define rep3(i, a, b) for(ii i = (a); i < (b); i++)
#define rep4(i, a, b, c) for(ii i = (a); i < (b); i += (c))
#define rep_overload(a, b, c, d, e, ...) e
#define rep(...) rep_overload(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(n) for(ii i = (n) - 1; i >= 0; i--)
#define per2(i, n) for(ii i = (n) - 1; i >= 0; i--)
#define per3(i, a, b) for(ii i = (b) - 1; i >= (a); i--)
#define per4(i, a, b, c) for(ii i = (b) - 1; i >= (a); i -= (c))
#define per_overload(a, b, c, d, e, ...) e
#define per(...) per_overload(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__)
#define fore(x, a) for(auto &x : a)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define QYN(q, a, b) ((q) ? (a) : (b))
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define mkt make_tuple
#define fi first
#define se second
#define applyv(v, f) \
[&]() { \
auto &&_v = (v); \
for(auto &x : _v) \
f(x); \
}()
#define mapv(v, f) \
[&]() { \
auto &&_v = (v); \
using Type = std::decay_t<decltype(f(*_v.begin()))>; \
std::vector<Type> ret; \
ret.reserve(_v.size()); \
for(const auto &x : _v) \
ret.push_back(f(x)); \
return ret; \
}()
#define II(...) \
ii __VA_ARGS__; \
input(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
input(__VA_ARGS__)
#define LLL(...) \
lll __VA_ARGS__; \
input(__VA_ARGS__)
#define IDX(...) \
ii __VA_ARGS__; \
input(__VA_ARGS__); \
input_index(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
input(__VA_ARGS__);
#define CHR(...) \
char __VA_ARGS__; \
input(__VA_ARGS__);
#define LD(...) \
ld __VA_ARGS__; \
input(__VA_ARGS__);
#define VI(A, N) \
vector<ii> A(N); \
input(A);
#define VVI(A, N, M) \
vector<vector<ii>> A(N, vector<ii>(M)); \
input(A);
#define VL(A, N) \
vector<ll> A(N); \
input(A);
#define VVL(A, N, M) \
vector<vector<ll>> A(N, vector<ll>(M)); \
input(A);
#define VPI(A, N) \
vpi A(N); \
input(A);
#define VTI(A, N) \
vti A(N); \
input(A);
#define VI2(A, B, N) \
vector<ii> A(N), B(N); \
rep(i, N) cin >> A[i] >> B[i];
#define VL2(A, B, N) \
vector<ll> A(N), B(N); \
rep(i, N) cin >> A[i] >> B[i];
#define VI3(A, B, C, N) \
vector<ii> A(N), B(N), C(N); \
rep(i, N) cin >> A[i] >> B[i] >> C[i];
#define VL3(A, B, C, N) \
vector<ll> A(N), B(N), C(N); \
rep(i, N) cin >> A[i] >> B[i] >> C[i];
#define VST(A, N) \
vector<string> A(N); \
input(A);
#define IN2(A, B) rep(i, siz(A)) cin >> A[i] >> B[i];
#define IN3(A, B, C) rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i];
#define IN4(A, B, C, D) rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i] >> D[i];
#define IN5(A, B, C, D, E) \
rep(i, siz(A)) cin >> A[i] >> B[i] >> C[i] >> D[i] >> E[i];
//------>8-------- end kyopro_library/base/macro.hpp --------->8------
//------>8--------- begin kyopro_library/base/io.hpp --------->8------
const char NL = '\n';
void flush() { cout.flush(); }
const string Yes = "Yes";
const string No = "No";
const string YES = "YES";
const string NO = "NO";
inline string YesNo(bool f) { return f ? Yes : No; }
inline string YESNO(bool f) { return f ? YES : NO; }
inline string AliBo(bool f) { return f ? "Alice" : "Bob"; }
inline string FiSe(bool f) { return f ? "First" : "Second"; }
template <typename T>
istream& operator>>(istream& is, vector<vector<T>>& v) {
for(auto& x : v)
for(auto& y : x) is >> y;
return is;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
for(auto& x : v) is >> x;
return is;
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
is >> p.first >> p.second;
return is;
}
template <class... T>
void input(T&... a) { (cin >> ... >> a); }
template <class T>
void input_index(T& a) { a--; }
template <class T, class... Ts>
void input_index(T& a, Ts&... b) {
a--;
input_index(b...);
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
os << p.fi << ' ' << p.se;
return os;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const PR<T1, T2>& p) {
os << p.fi << ' ' << p.se;
return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& t) {
os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);
return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const TR<T1, T2, T3>& t) {
os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);
return os;
}
template <typename T1, typename T2, typename T3, typename T4>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4>& t) {
os << ' ' << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t) << ' ' << get<3>(t);
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<vector<T>>>& a) {
int I = a.size();
for(int i = 0; i < I; i++) {
int J = a[i].size();
for(int j = 0; j < J; j++) {
int K = a[i][j].size();
for(int k = 0; k < K; k++) {
os << a[i][j][k];
if(k != K - 1) os << ' ';
}
os << NL;
}
if(i != I - 1) os << NL;
}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& a) {
int I = a.size();
for(int i = 0; i < I; i++) {
int J = a[i].size();
for(int j = 0; j < J; j++) {
os << a[i][j];
if(j != J - 1) os << ' ';
}
if(i != I - 1) cout << NL;
}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
int n = a.size();
for(int i = 0; i < n; i++) {
os << a[i];
if(i != n - 1) os << ' ';
}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& a) {
for(auto itr = a.begin(); itr != a.end(); itr++) {
os << *itr;
if(next(itr) != a.end()) os << ' ';
}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const multiset<T>& a) {
for(auto itr = a.begin(); itr != a.end(); itr++) {
os << *itr;
if(next(itr) != a.end()) os << ' ';
}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const deque<T>& a) {
for(auto itr = a.begin(); itr != a.end(); itr++) {
os << *itr;
if(next(itr) != a.end()) os << ' ';
}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, queue<T> a) {
while(!a.empty()) {
os << a.front();
a.pop();
if(a.size()) os << ' ';
}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, priority_queue<T> a) {
while(!a.empty()) {
os << a.top();
a.pop();
if(a.size()) os << ' ';
}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, priority_queue<T, vector<T>, greater<T>> a) {
while(!a.empty()) {
os << a.top();
a.pop();
if(a.size()) os << ' ';
}
return os;
}
template <typename T, auto N>
ostream& operator<<(ostream& os, array<T, N> a) {
for(int i = 0; i < N; i++) {
os << a[i];
if(i != N - 1) os << ' ';
}
return os;
}
template <class T, class... Ts>
void put(const T& a, const Ts&... b) {
cout << a;
(void)(cout << ... << b);
}
template <class T, class... Ts>
void line(const T& a, const Ts&... b) {
cout << a;
(void)(cout << ... << (cout << ' ', b));
cout << ' ';
}
void say() { cout << '\n'; }
template <class T, class... Ts>
void say(const T& a, const Ts&... b) {
cout << a;
(void)(cout << ... << (cout << ' ', b));
cout << '\n';
}
void esay() {
#ifdef TDY
cerr << endl;
#endif
}
template <class T, class... Ts>
void esay(const T& a, const Ts&... b) {
#ifdef TDY
cerr << a;
(void)(cerr << ... << (cerr << ' ', b));
cerr << endl;
#endif
}
#define O(...) \
{ \
say(__VA_ARGS__); \
return; \
}
//------>8---------- end kyopro_library/base/io.hpp ---------->8------
//------>8-------- begin kyopro_library/base/util.hpp -------->8------
template <typename A, typename B>
A amin(A a, B b) {
if(a > b) return b;
return a;
}
template <typename A, typename B>
A amax(A a, B b) {
if(a < b) return b;
return a;
}
template <typename A, typename B>
bool chmin(A& a, B b) {
if(a > b) {
a = b;
return true;
}
return false;
}
template <typename A, typename B>
bool chmax(A& a, B b) {
if(a < b) {
a = b;
return true;
}
return false;
}
template <typename A, typename B>
A myfloor(A a, B b) {
assert(b != 0);
if(b < 0) a = -a, b = -b;
return a / b - (a % b < 0);
}
template <typename A, typename B>
A myceil(A a, B b) {
assert(b != 0);
if(b < 0) a = -a, b = -b;
return a / b + (a % b > 0);
}
template <typename A, typename B>
A mymod(A a, B b) {
assert(b != 0);
if(b < 0) b = -b;
if(a > 0) return a % b;
return (a % b + b) % b;
}
// コンテナに対する関数
template <typename T>
inline ii siz(const T& v) { return v.size(); }
template <typename T>
T minv(const vector<T>& v) {
if(v.empty()) return inf<T>;
return *ranges::min_element(v);
}
template <typename T>
T maxv(const vector<T>& v) {
if(v.empty()) return -inf<T>;
return *ranges::max_element(v);
}
template <typename T>
T sumv(const vector<T>& v) { return reduce(v.begin(), v.end()); }
template <typename T>
ii minidx(const vector<T>& v) { return ranges::min_element(v) - v.begin(); }
template <typename T>
ii maxidx(const vector<T>& v) { return ranges::max_element(v) - v.begin(); }
template <typename T>
ii lob(const vector<T>& v, const T& x) { return ranges::lower_bound(v, x) - v.begin(); }
template <typename T>
ii upb(const vector<T>& v, const T& x) { return ranges::upper_bound(v, x) - v.begin(); }
template <typename T>
ii findv(const vector<T>& v, const T& x) {
for(ii i = 0; i < siz(v); i++)
if(v[i] == x) return i;
return siz(v);
}
template <typename T>
ii find_lastv(const vector<T>& v, const T& x) {
for(ii i = siz(v) - 1; i >= 0; i--)
if(v[i] == x) return i;
return -1;
}
template <typename T>
void unique(vector<T>& v) {
ranges::sort(v);
v.erase(unique(v.begin(), v.end()), v.end());
}
template <typename T>
vector<T> compress(vector<T> v) {
auto w = v;
unique(w);
for(T& x : v) x = lob(w, x);
return v;
}
ii countv(const auto& a, auto v) {
return count(a.begin(), a.end(), v);
}
void insertv(auto& a, ii idx, auto v) {
assert(idx <= siz(a));
a.insert(a.begin() + idx, v);
}
void erasev(auto& a, ii idx) {
assert(idx < siz(a));
a.erase(a.begin() + idx);
}
// 先頭をoffset個分後ろに
void rotatebackv(auto& a, ii offset) {
offset %= siz(a);
rotate(a.begin(), a.end() - offset, a.end());
}
// 末尾をoffset個分前の方に
void rotatefrontv(auto& a, ii offset) {
offset %= siz(a);
rotate(a.begin(), a.begin() + offset, a.end());
}
auto mksort(const auto& a) {
auto b = a;
sort(all(b));
return b;
}
auto mkinsert(const auto& a, ii idx, auto v) {
auto b = a;
insertv(b, idx, v);
return b;
}
auto mkerase(const auto& a, ii idx) {
auto b = a;
erasev(b, idx);
return b;
}
auto mkpush(const auto& a, auto v) {
auto b = a;
b.push_back(v);
return b;
}
template <typename T>
V<T> mkslice(const V<T>& a, ii l, ii r) {
assert(l <= r && l >= 0 && r <= siz(a));
V<T> b(a.begin() + l, a.begin() + r);
return b;
}
template <typename T>
V<T> mkconcat(const V<T>& a, const V<T>& b) {
auto ret = a;
ret.reserve(siz(a) + siz(b));
for(auto x : b) ret.push_back(x);
return ret;
}
template <typename A, typename B>
vector<PR<A, B>> zip(const vector<A>& a, const vector<B>& b) {
ii n = siz(a);
vector<PR<A, B>> ret(n);
for(ii i = 0; i < n; i++) ret[i] = {a[i], b[i]};
return ret;
}
template <typename A, typename B, typename C>
vector<tuple<A, B, C>> zip(const vector<A>& a, const vector<B>& b, const vector<C>& c) {
ii n = siz(a);
vector<tuple<A, B, C>> ret(n);
for(ii i = 0; i < n; i++) ret[i] = {a[i], b[i], c[i]};
return ret;
}
template <typename A, typename B>
PR<vector<A>, vector<B>> unzip(const vector<PR<A, B>>& p) {
ii n = siz(p);
vector<A> reta(n);
vector<B> retb(n);
for(ii i = 0; i < n; i++) {
reta[i] = p[i].first;
retb[i] = p[i].second;
}
return mkp(reta, retb);
}
template <typename A, typename B, typename C>
TR<vector<A>, vector<B>, vector<C>> unzip(const vector<TR<A, B, C>>& p) {
ii n = siz(p);
vector<A> reta(n);
vector<B> retb(n);
vector<C> retc(n);
for(ii i = 0; i < n; i++) {
auto [a, b, c] = p[i];
reta[i] = a;
retb[i] = b;
retc[i] = c;
}
return mkt(reta, retb, retc);
}
template <typename T>
T pick(max_pq<T>& v) {
T ret = v.top();
v.pop();
return ret;
}
template <typename T>
T pick(min_pq<T>& v) {
T ret = v.top();
v.pop();
return ret;
}
template <typename T>
T pick(queue<T>& v) {
T ret = v.front();
v.pop();
return ret;
}
template <typename T>
T pick(vector<T>& v) {
T ret = v.back();
v.pop_back();
return ret;
}
template <typename T>
T pickf(deque<T>& v) {
T ret = v.front();
v.pop_front();
return ret;
}
template <typename T>
T pickb(deque<T>& v) {
T ret = v.back();
v.pop_back();
return ret;
}
template <typename T>
bool nxperm(T& v) { return next_permutation(v.begin(), v.end()); }
template <typename T>
void operator++(V<T>& a, T) {
for(auto itr = a.begin(); itr != a.end(); itr++) (*itr)++;
}
template <typename T>
void operator--(V<T>& a, T) {
for(auto itr = a.begin(); itr != a.end(); itr++) (*itr)--;
}
template <typename T>
void operator+=(V<T>& a, auto x) {
for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) += x;
}
template <typename T>
void operator-=(V<T>& a, auto x) {
for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) -= x;
}
template <typename T>
void operator*=(V<T>& a, auto x) {
for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) *= x;
}
template <typename T>
void operator/=(V<T>& a, auto x) {
for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) /= x;
}
template <typename T>
void operator%=(V<T>& a, auto x) {
for(auto itr = a.begin(); itr != a.end(); itr++) (*itr) %= x;
}
template <typename T>
V<T> mkvec(ii n, T init) {
return V<T>(n, init);
}
template <typename... Ts>
auto mkvec(ii n, Ts... ts) {
return V<decltype(mkvec(ts...))>(n, mkvec(ts...));
}
template <typename T = i64, typename U>
vector<T> mksum(const vector<U>& v) {
ii n = v.size();
vector<T> ret(n + 1);
for(ii i = 0; i < n; i++) ret[i + 1] = ret[i] + v[i];
return ret;
}
template <typename T>
vector<T> mkpmax(const vector<T>& v) {
ii n = v.size();
vector<T> ret(n + 1, -inf<T>);
for(ii i = 0; i < n; i++) ret[i + 1] = max(ret[i], v[i]);
return ret;
}
template <typename T>
vector<T> mkpmin(const vector<T>& v) {
ii n = v.size();
vector<T> ret(n + 1, inf<T>);
for(ii i = 0; i < n; i++) ret[i + 1] = min(ret[i], v[i]);
return ret;
}
vi mkiota(ii n) {
vi ret(n);
iota(ret.begin(), ret.end(), 0);
return ret;
}
template <typename T>
V<T> mkrev(V<T> A) {
reverse(A.begin(), A.end());
return A;
}
template <typename T>
vi mkinv(const V<T>& A) {
ii n = siz(A);
vi ret(maxv(A) + 1);
for(ii i = 0; i < n; i++) ret[A[i]] = i;
return ret;
}
template <typename T>
vvi mkinvvec(const V<T>& A) {
ii n = siz(A);
vvi ret(maxv(A) + 1);
for(ii i = 0; i < n; i++) ret[A[i]].push_back(i);
return ret;
}
template <typename T>
vi mkfreq(const V<T>& A) {
ii n = siz(A);
vi ret(maxv(A) + 1);
for(ii i = 0; i < n; i++) ret[A[i]]++;
return ret;
}
template <typename T>
vi argsort(const V<T>& A) {
vi idx = mkiota(siz(A));
sort(idx.begin(), idx.end(), [&](ii i, ii j) {
return (A[i] == A[j] ? i < j : A[i] < A[j]);
});
return idx;
}
template <typename T>
ii digit_siz(T n) {
ii ret = 0;
while(n) {
ret++;
n /= 10;
}
return ret;
}
template <typename T>
vector<ii> digits(T n) {
vector<ii> ret;
while(n) {
ret.push_back(n % 10);
n /= 10;
}
reverse(ret.begin(), ret.end());
return ret;
}
i64 tenpow(ii r) {
i64 ret = 1;
while(r--) ret *= 10;
return ret;
}
i64 intpow(i64 x, i64 r) {
i64 ret = 1;
while(r--) ret *= x;
return ret;
}
template <typename T>
T intsqrt(T x) {
i64 sq = (T)sqrtl(ld(x));
while(sq * sq > x) sq--;
while((sq + 1) * (sq + 1) <= x) sq++;
return sq;
}
template <typename T = i128>
T euc_dist(auto ax, auto ay, auto bx, auto by) {
return T(ax - bx) * (ax - bx) + T(ay - by) * (ay - by);
}
template <typename T = i64>
T man_dist(auto ax, auto ay, auto bx, auto by) {
return abs(ax - bx) + abs(ay - by);
}
ii ctoi(char c) {
assert('0' <= c && c <= '9');
return c - '0';
}
ii itoc(ii i) {
assert(0 <= i && i <= 9);
return char('0' + i);
}
vi stov(const str& s, char base = 'a') {
vi ret(s.size());
rep(i, s.size()) ret[i] = s[i] - base;
return ret;
}
str vtos(const vi& a, char base = 'a') {
str ret;
rep(i, a.size()) ret.push_back(char(base + a[i]));
return ret;
}
/// @brief 1であるビットの個数を返す
ii popcount(i32 n) { return __builtin_popcount(n); }
/// @brief 1であるビットの個数を返す
ii popcount(i64 n) { return __builtin_popcountll(n); }
/// @brief popcountの偶奇を返す
ii parity(i32 n) { return __builtin_parity(n); }
/// @brief popcountの偶奇を返す
ii parity(i64 n) { return __builtin_parityll(n); }
/// @brief 最上位ビットの位置を返す
ii topbit(i32 n) { return n ? 31 - __builtin_clz(n) : -1; }
/// @brief 最上位ビットの位置を返す
ii topbit(i64 n) { return n ? 63 - __builtin_clzll(n) : -1; }
/// @brief 2進表現の長さを返す
ii bitsiz(i32 n) { return n ? 32 - __builtin_clz(n) : 1; }
//// @brief 2進表現の長さを返す
ii bitsiz(i64 n) { return n ? 64 - __builtin_clzll(n) : 1; }
/// @brief 最下位ビットの位置を返す
ii bottombit(i32 n) { return n ? __builtin_ctz(n) : -1; }
/// @brief 最下位ビットの位置を返す
ii bottombit(i64 n) { return n ? __builtin_ctzll(n) : -1; }
/// @brief 2のべき乗か否かを返す
bool ispower2(i32 n) { return n && (n & -n) == n; }
/// @brief 0~n-1ビットを立てたビットマスクを返す
ll mkmask(ii n) { return (1LL << n) - 1; }
/// @brief iビット目が立っているか否かを返す
bool hasbit(i64 n, ii i) { return (n >> i & 1); }
/// @brief sの部分集合を返す
vi mksubset(ii s) {
vi ret;
ii t = s;
do {
ret.push_back(t);
--t &= s;
} while(t != s);
return ret;
}
/// @brief 整数nの2進表現を返す
/// @param len ビット数
/// @param rev 反転するか否か
string tobinary(i64 n, ii len = 32, bool rev = false) {
string ret;
rep(i, len) ret += (hasbit(n, rev ? len - 1 - i : i) ? '1' : '0');
return ret;
}
//------>8--------- end kyopro_library/base/util.hpp --------->8------
//------>8---- begin kyopro_library/base/fastio_impl.hpp ----->8------
/// @brief FastIn/FastOut の operator 本体。io.hpp より後に include し、フォールバック時に
/// io.hpp のグローバル operator>>/<< (tuple/set/deque/array など) を名前検索で解決する。
/// @note modint/fraction/geo などの friend 演算子は ADL で解決されるため include 順に依らない。
namespace FastIO {
template <typename T>
FastIn& FastIn::operator>>(T& x) {
if constexpr(is_same_v<T, char>) rd.read_char(x);
else if constexpr(is_same_v<T, bool>) fb >> x;
else if constexpr(is_same_v<T, lll>) rd.read_i128(x);
else if constexpr(is_same_v<T, ulll>) rd.read_u128(x);
else if constexpr(is_integral_v<T>) rd.read_int(x);
else if constexpr(is_floating_point_v<T>) rd.read_float(x);
else if constexpr(is_same_v<T, string>) rd.read_str(x);
else if constexpr(is_vec<T>::value)
for(auto& e : x) *this >> e;
else if constexpr(PairLike<T>) *this >> x.first, *this >> x.second;
else fb >> x;
return *this;
}
template <typename T>
FastOut& FastOut::operator<<(const T& x) {
using D = decay_t<T>;
if constexpr(is_same_v<D, char>) wt.pc(x);
else if constexpr(is_same_v<D, bool>) wt.pc(x ? '1' : '0');
else if constexpr(is_same_v<D, lll>) wt.write_i128(x);
else if constexpr(is_same_v<D, ulll>) wt.write_u128(x);
else if constexpr(is_integral_v<D>) wt.write_int(x);
else if constexpr(is_floating_point_v<D>) wt.write_float((long double)x);
else if constexpr(is_same_v<D, string>) wt.ps(x.data(), (int)x.size());
else if constexpr(is_same_v<D, char*> || is_same_v<D, const char*>) wt.ps(x, (int)strlen(x));
else if constexpr(is_vec3<D>::value) write_vec3(x);
else if constexpr(is_vec2<D>::value) write_vec2(x);
else if constexpr(is_vec<D>::value) write_vec1(x);
else if constexpr(PairLike<D>) {
*this << x.first;
wt.pc(' ');
*this << x.second;
} else fb << x;
return *this;
}
} // namespace FastIO
//------>8----- end kyopro_library/base/fastio_impl.hpp ------>8------
void run();
void prep();
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(15);
prep();
#ifdef MULTI
II(T);
rep(t, T) {
#ifdef TDY
say("============ Case: #", t + 1, " ============");
#endif
run();
}
#else
run();
#endif
}
#ifdef DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif
//------>8--------- end kyopro_library/template.hpp ---------->8------
//------>8 begin kyopro_library/data_structure/sorted_tree.hpp >8------
//------>8 begin kyopro_library/data_structure/ordered_tree_base.hpp >8------
/// @brief 順序統計付き平衡二分探索木 (乱択Treap)
/// @brief SortedTree / SortedMultiTree の内部実装用
///
/// 高速化のためのメモリ設計:
/// - ノードは new/delete でなく vector プール + free list で管理する
/// - 探索の降下で触るデータ (key, l, r) と順序統計用データ (sz, cnt) を
/// 別配列に分離し (hot/cold 分離)、探索時のキャッシュフットプリントを最小化する
/// - 優先度は保存せず「ノード番号 ^ salt のハッシュ」として都度計算する
/// (salt は実行時乱数なので敵対的な入力でも木は偏らない)
/// - 降下ループでは両子ノードを prefetch する。分岐が csel に変換されても
/// 次ノードのロードがメモリ待ちにならず、大きな木では数倍速くなる
template <typename T>
struct OrderedTreeBase {
struct NodeHot {
T key;
int l, r;
};
struct NodeCold {
int sz; // 部分木の要素数 (重複込み)
int cnt; // このキーの重複数
};
vector<NodeHot> hot;
vector<NodeCold> cold;
vector<int> spares; // 削除済みノードの再利用リスト
vector<int> path; // insert/erase 用の経路スタック ((index << 1) | 左に降りたか)
int root = -1;
unsigned int salt;
OrderedTreeBase() {
salt = (unsigned int)chrono::steady_clock::now().time_since_epoch().count();
salt ^= (unsigned int)(uintptr_t)this;
}
/// @brief ノード t の優先度 (murmur3 finalizer によるハッシュ)
unsigned int pri_of(int t) const {
unsigned int x = (unsigned int)t ^ salt;
x ^= x >> 16;
x *= 0x85ebca6bu;
x ^= x >> 13;
x *= 0xc2b2ae35u;
x ^= x >> 16;
return x;
}
static void prefetch_children(const NodeHot* h, int l, int r) {
if(l != -1) __builtin_prefetch(&h[l]);
if(r != -1) __builtin_prefetch(&h[r]);
}
static void prefetch_children_cold(const NodeCold* c, int l, int r) {
if(l != -1) __builtin_prefetch(&c[l]);
if(r != -1) __builtin_prefetch(&c[r]);
}
void upd(NodeHot* h, NodeCold* c, int t) {
int l = h[t].l, r = h[t].r;
c[t].sz = c[t].cnt + (l == -1 ? 0 : c[l].sz) + (r == -1 ? 0 : c[r].sz);
}
int rot_r(NodeHot* h, NodeCold* c, int t) {
int l = h[t].l;
h[t].l = h[l].r;
h[l].r = t;
upd(h, c, t);
upd(h, c, l);
return l;
}
int rot_l(NodeHot* h, NodeCold* c, int t) {
int r = h[t].r;
h[t].r = h[r].l;
h[r].l = t;
upd(h, c, t);
upd(h, c, r);
return r;
}
int new_node(const T& x) {
if(!spares.empty()) {
int id = spares.back();
spares.pop_back();
hot[id] = NodeHot{x, -1, -1};
cold[id] = NodeCold{1, 1};
return id;
}
hot.push_back(NodeHot{x, -1, -1});
cold.push_back(NodeCold{1, 1});
return (int)hot.size() - 1;
}
int merge_nodes(NodeHot* h, NodeCold* c, int l, int r) {
if(l == -1 || r == -1) return l == -1 ? r : l;
if(pri_of(l) > pri_of(r)) {
h[l].r = merge_nodes(h, c, h[l].r, r);
upd(h, c, l);
return l;
} else {
h[r].l = merge_nodes(h, c, l, h[r].l);
upd(h, c, r);
return r;
}
}
/// @brief x を挿入する (allow_dup=false のとき既存キーなら何もしない)
/// @return 実際に挿入 (または cnt 増加) したか
bool insert(const T& x, bool allow_dup) {
// 途中で push_back してもポインタが無効化しないよう先に容量を確保する
if(spares.empty() && hot.size() == hot.capacity()) {
size_t cap = hot.empty() ? 16 : hot.size() * 2;
hot.reserve(cap);
cold.reserve(cap);
}
NodeHot* h = hot.data();
NodeCold* c = cold.data();
path.clear();
int t = root;
while(t != -1) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
if(x < h[t].key) {
path.push_back(t << 1 | 1);
t = l;
} else if(h[t].key < x) {
path.push_back(t << 1);
t = r;
} else {
if(!allow_dup) return false;
c[t].cnt++;
c[t].sz++;
for(int e : path) c[e >> 1].sz++;
return true;
}
}
int cur = new_node(x);
unsigned int cur_pri = pri_of(cur);
bool rotating = true;
while(!path.empty()) {
int e = path.back();
path.pop_back();
int p = e >> 1;
bool went_left = e & 1;
if(went_left) h[p].l = cur;
else h[p].r = cur;
if(rotating && cur_pri > pri_of(p)) {
cur = went_left ? rot_r(h, c, p) : rot_l(h, c, p);
} else {
// 優先度の heap 条件が一度成立したら、それより上で回転は起きない
rotating = false;
c[p].sz++;
cur = p;
}
}
root = cur;
return true;
}
/// @brief x を 1 個削除する
/// @return x が存在したか
bool erase_one(const T& x) {
NodeHot* h = hot.data();
NodeCold* c = cold.data();
path.clear();
int t = root;
while(t != -1) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
if(x < h[t].key) {
path.push_back(t << 1 | 1);
t = l;
} else if(h[t].key < x) {
path.push_back(t << 1);
t = r;
} else {
break;
}
}
if(t == -1) return false;
int sub;
if(c[t].cnt > 1) {
c[t].cnt--;
c[t].sz--;
sub = t;
} else {
sub = merge_nodes(h, c, h[t].l, h[t].r);
spares.push_back(t);
}
if(path.empty()) {
root = sub;
} else {
int e = path.back();
path.pop_back();
int p = e >> 1;
if(e & 1) h[p].l = sub;
else h[p].r = sub;
c[p].sz--;
while(!path.empty()) {
e = path.back();
path.pop_back();
c[e >> 1].sz--;
}
}
return true;
}
/// @brief 全要素数 (重複込み)
int size() const { return root == -1 ? 0 : cold[root].sz; }
bool empty() const { return root == -1; }
void clear() {
hot.clear();
cold.clear();
spares.clear();
root = -1;
}
void reserve(int n) {
hot.reserve(n);
cold.reserve(n);
}
/// @brief x の個数を返す
int count_key(const T& x) const {
const NodeHot* h = hot.data();
int t = root;
while(t != -1) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
if(x < h[t].key) t = l;
else if(h[t].key < x) t = r;
else return cold[t].cnt;
}
return 0;
}
bool contains(const T& x) const { return count_key(x) > 0; }
/// @brief x 未満の要素数 (重複込み)
int rank_lt(const T& x) const {
const NodeHot* h = hot.data();
const NodeCold* c = cold.data();
int res = 0, t = root;
while(t != -1) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
prefetch_children_cold(c, l, r);
if(h[t].key < x) {
res += (l == -1 ? 0 : c[l].sz) + c[t].cnt;
t = r;
} else if(x < h[t].key) {
t = l;
} else {
res += l == -1 ? 0 : c[l].sz;
break;
}
}
return res;
}
/// @brief x 以下の要素数 (重複込み)
int rank_le(const T& x) const {
const NodeHot* h = hot.data();
const NodeCold* c = cold.data();
int res = 0, t = root;
while(t != -1) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
prefetch_children_cold(c, l, r);
if(x < h[t].key) {
t = l;
} else if(h[t].key < x) {
res += (l == -1 ? 0 : c[l].sz) + c[t].cnt;
t = r;
} else {
res += (l == -1 ? 0 : c[l].sz) + c[t].cnt;
break;
}
}
return res;
}
/// @brief k(0-indexed) 番目に小さいキーを out に格納する
/// @return k が範囲内なら true
bool kth(int k, T& out) const {
if(k < 0 || k >= size()) return false;
const NodeHot* h = hot.data();
const NodeCold* c = cold.data();
int t = root;
while(true) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
prefetch_children_cold(c, l, r);
int ls = l == -1 ? 0 : c[l].sz;
if(k < ls) {
t = l;
} else if(k < ls + c[t].cnt) {
out = h[t].key;
return true;
} else {
k -= ls + c[t].cnt;
t = r;
}
}
}
/// @brief 最小のキーを out に格納する
bool find_min(T& out) const {
if(root == -1) return false;
const NodeHot* h = hot.data();
int t = root;
while(h[t].l != -1) t = h[t].l;
out = h[t].key;
return true;
}
/// @brief 最大のキーを out に格納する
bool find_max(T& out) const {
if(root == -1) return false;
const NodeHot* h = hot.data();
int t = root;
while(h[t].r != -1) t = h[t].r;
out = h[t].key;
return true;
}
/// @brief x より大きい最小のキーを out に格納する
bool find_gt(const T& x, T& out) const {
const NodeHot* h = hot.data();
int t = root, best = -1;
while(t != -1) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
if(x < h[t].key) {
best = t;
t = l;
} else {
t = r;
}
}
if(best == -1) return false;
out = h[best].key;
return true;
}
/// @brief x 以上の最小のキーを out に格納する
bool find_ge(const T& x, T& out) const {
const NodeHot* h = hot.data();
int t = root, best = -1;
while(t != -1) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
if(h[t].key < x) {
t = r;
} else {
best = t;
if(!(x < h[t].key)) break; // 等しいキーが見つかったら確定
t = l;
}
}
if(best == -1) return false;
out = h[best].key;
return true;
}
/// @brief x 未満の最大のキーを out に格納する
bool find_lt(const T& x, T& out) const {
const NodeHot* h = hot.data();
int t = root, best = -1;
while(t != -1) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
if(h[t].key < x) {
best = t;
t = r;
} else {
t = l;
}
}
if(best == -1) return false;
out = h[best].key;
return true;
}
/// @brief x 以下の最大のキーを out に格納する
bool find_le(const T& x, T& out) const {
const NodeHot* h = hot.data();
int t = root, best = -1;
while(t != -1) {
int l = h[t].l, r = h[t].r;
prefetch_children(h, l, r);
if(x < h[t].key) {
t = l;
} else {
best = t;
if(!(h[t].key < x)) break; // 等しいキーが見つかったら確定
t = r;
}
}
if(best == -1) return false;
out = h[best].key;
return true;
}
/// @brief 全要素を昇順で返す (重複は個数分含む)
vector<T> to_vector() const {
vector<T> res;
res.reserve(size());
const NodeHot* h = hot.data();
const NodeCold* c = cold.data();
vector<int> stk;
int t = root;
while(t != -1 || !stk.empty()) {
while(t != -1) {
stk.push_back(t);
t = h[t].l;
}
t = stk.back();
stk.pop_back();
for(int i = 0; i < c[t].cnt; i++) res.push_back(h[t].key);
t = h[t].r;
}
return res;
}
};
//------>8 end kyopro_library/data_structure/ordered_tree_base.hpp >8------
/// @brief 順序統計付きの集合 (重複なし)。自前Treap実装
template <typename T>
struct SortedTree {
OrderedTreeBase<T> tr;
T not_found = -1;
/// @brief コンストラクタ
/// @param not_found 指定の値が見つからなかったときに返す値
SortedTree(T not_found = -1) { this->not_found = not_found; }
/// @brief 要素数を返す
int size() const { return tr.size(); }
/// @brief 空か否かを返す
bool empty() const { return tr.empty(); }
/// @brief 全要素を削除する
void clear() { tr.clear(); }
/// @brief x を追加する (既に含まれている場合は何もしない)
/// @return 実際に追加されたか否か
bool insert(T x) { return tr.insert(x, false); }
/// @brief x を削除する
/// @return x が含まれていたか否か
bool erase(T x) { return tr.erase_one(x); }
/// @brief 最小値を返す
T min() {
T ret;
if(!tr.find_min(ret)) return not_found;
return ret;
}
/// @brief 最大値を返す
T max() {
T ret;
if(!tr.find_max(ret)) return not_found;
return ret;
}
/// @brief 最小値を返し、削除する
T pop_min() {
T ret;
if(!tr.find_min(ret)) return not_found;
tr.erase_one(ret);
return ret;
}
/// @brief 最大値を返し、削除する
T pop_max() {
T ret;
if(!tr.find_max(ret)) return not_found;
tr.erase_one(ret);
return ret;
}
/// @brief x が含まれているか否かを返す
bool contains(T x) { return tr.contains(x); }
/// @brief x を削除する
/// @return x が含まれていたか否か
bool discard(T x) { return tr.erase_one(x); }
/// @brief x より大きい最小の値を返す
T gt(T x) {
T ret;
if(!tr.find_gt(x, ret)) return not_found;
return ret;
}
/// @brief x 以上最小の値を返す
T ge(T x) {
T ret;
if(!tr.find_ge(x, ret)) return not_found;
return ret;
}
/// @brief x 未満最大の値を返す
T lt(T x) {
T ret;
if(!tr.find_lt(x, ret)) return not_found;
return ret;
}
/// @brief x 以下の最大の値を返す
T le(T x) {
T ret;
if(!tr.find_le(x, ret)) return not_found;
return ret;
}
/// @brief x より小さい値の個数を返す
int count_lt(T x) { return tr.rank_lt(x); }
/// @brief x 以下の値の個数を返す
int count_le(T x) { return tr.rank_le(x); }
/// @brief x より大きい値の個数を返す
int count_gt(T x) { return tr.size() - tr.rank_le(x); }
/// @brief x 以上の値の個数を返す
int count_ge(T x) { return tr.size() - tr.rank_lt(x); }
/// @brief k(0-indexed) 番目に小さい値を返す
T kth_min(int k) {
T ret;
if(!tr.kth(k, ret)) return not_found;
return ret;
}
/// @brief k(0-indexed) 番目に大きい値を返す
T kth_max(int k) {
T ret;
if(!tr.kth(tr.size() - k - 1, ret)) return not_found;
return ret;
}
/// @brief 全要素を昇順で返す
vector<T> to_vector() const { return tr.to_vector(); }
};
//------>8 end kyopro_library/data_structure/sorted_tree.hpp ->8------
#define TODAY_KYOPRO
#include __FILE__
#endif
// a.cpp
// 2026-07-20 12:11:46