cpp.json + template.cpp(AHC)
| 投稿者 | pitP |
|---|---|
| 言語 | C++23 |
| 更新日時 (JST) | 2026-10-14 20:58:14 |
| サイズ | 190,600 Byte |
| 参照URL | |
日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。
{
// Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the
// same ids are connected.
// Example:
// "Print to console": {
// "prefix": "log",
// "body": [
// "console.log('$1');",
// "$2"
// ],
// "description": "Log output to console"
// }
"template": {
"prefix": "atcoder_cpp_",
"body": [
"#include <bits/stdc++.h>",
"#include <atcoder/all>",
"using namespace std;",
"using namespace atcoder;",
"istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }",
"ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }",
"istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }",
"ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }",
"istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }",
"ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } ",
"",
"typedef long long ll;",
"typedef vector<vector<int>> Graph;",
"typedef pair<int, int> pii;",
"typedef pair<ll, ll> pll;",
"#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)",
"#define rep(i,n) for (int i = 0;i < (int)(n); i++)",
"#define all(x) x.begin(), x.end()",
"#define rall(x) x.rbegin(), x.rend()",
"#define my_sort(x) sort(x.begin(), x.end())",
"#define my_max(x) *max_element(all(x))",
"#define my_min(x) *min_element(all(x))",
"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; }",
"const int INF = (1<<30) - 1;",
"const ll LINF = (1LL<<62) - 1;",
"const int MOD = 998244353;",
"const int MOD2 = 1e9+7;",
"const double PI = acos(-1);",
"vector<int> di = {1,0,-1,0};",
"vector<int> dj = {0,1,0,-1};",
"",
"#ifdef LOCAL",
"# include <debug_print.hpp>",
"# define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)",
"#else",
"# define debug(...) (static_cast<void>(0))",
"#endif",
"",
"int main(){",
" cin.tie(0);",
" ios_base::sync_with_stdio(false);",
"}",
""
],
"description": "template"
},
"codeforces": {
"prefix": "atcoder_cpp_codeforces",
"body": [
"#include <bits/stdc++.h>",
"using namespace std;",
"",
"typedef long long ll;",
"typedef vector<vector<int>> Graph;",
"typedef pair<int, int> pii;",
"typedef pair<ll, ll> pll;",
"#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)",
"#define rep(i,n) for (int i = 0;i < (int)(n); i++)",
"#define all(x) x.begin(), x.end()",
"#define rall(x) x.rbegin(), x.rend()",
"#define my_sort(x) sort(x.begin(), x.end())",
"#define my_max(x) *max_element(all(x))",
"#define my_min(x) *min_element(all(x))",
"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; }",
"const int INF = (1<<30) - 1;",
"const ll LINF = (1LL<<62) - 1;",
"const int MOD = 998244353;",
"const int MOD2 = 1e9+7;",
"const double PI = acos(-1);",
"vector<int> di = {1,0,-1,0};",
"vector<int> dj = {0,1,0,-1};",
"",
"#ifdef LOCAL",
"# include <debug_print.hpp>",
"# define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)",
"#else",
"# define debug(...) (static_cast<void>(0))",
"#endif",
"",
"void solve(){",
"}",
"",
"int main(){",
" cin.tie(0);",
" ios_base::sync_with_stdio(false);",
" int t = 1; ",
" cin >> t;",
" while(t--) solve();",
"}"
],
"description": "codeforces"
},
//
//data structure
//
"sortedset": {
"prefix": "atcoder_data_sortedset",
"body": [
"template<typename T>",
"struct SortedSet{",
" const int BUCKET_RATIO = 50;",
" const int SPLIT_RATIO = 170;",
" vector<vector<T>> a;",
" int sz = 0;",
"",
" SortedSet(){}",
" SortedSet(const vector<T> &vec){",
" vector<T> dat = vec;",
" sort(dat.begin(), dat.end());",
" dat.erase(unique(dat.begin(), dat.end()), dat.end());",
"",
" int n = sz = dat.size();",
" int num_bucket = (int)ceil(sqrt((double)n / (double)BUCKET_RATIO));",
" a.resize(num_bucket);",
" for(int i = 0; i < num_bucket; i++){",
" a[i] = vector<T>(dat.begin() + n * i / num_bucket, dat.begin() + n * (i + 1) / num_bucket);",
" }",
" }",
"",
" bool operator==(const SortedSet& other) {",
" return this->a == other.a;",
" }",
"",
" size_t size() { return sz; }",
"",
" friend ostream& operator<<(ostream& os, const SortedSet& st) {",
" os << \"{ \";",
" for(const auto&vec : st.a){",
" for(const auto& v : vec){",
" os << v << \" \";",
" }",
" }",
" os << \"}\";",
" return os;",
" }",
"",
" pair<int, int> _position(const T &x){",
" int as = a.size();",
" for(int i = 0; i < as; i++){",
" if(x <= a[i].back()) {",
" return make_pair(i, lower_bound(a[i].begin(), a[i].end(), x) - a[i].begin());",
" }",
" }",
" return make_pair(as - 1, lower_bound(a[as - 1].begin(), a[as - 1].end(), x) - a[as - 1].begin());",
" }",
"",
" int count(const T &x){ return this->index_right(x) - this->index(x); }",
"",
" bool add(const T &x){",
" if(sz == 0){",
" a = {{x}};",
" sz = 1;",
" return true;",
" }",
" auto [b, i] = _position(x);",
" if(i != (int)a[b].size() && a[b][i] == x) return false;",
" a[b].insert(a[b].begin() + i, x);",
" sz++;",
" if((int)a[b].size() > (int)a.size() * SPLIT_RATIO){",
" int mid = (int)a[b].size() >> 1;",
" vector<T> head(a[b].begin(), a[b].begin() + mid), tail(a[b].begin() + mid, a[b].end());",
" a.erase(a.begin() + b);",
" a.insert(a.begin() + b, tail);",
" a.insert(a.begin() + b, head);",
" }",
" return true;",
" }",
"",
" T _pop(int b, int i){",
" T ans = a[b][i];",
" a[b].erase(a[b].begin() + i);",
" sz--;",
" if((int)a[b].size() == 0) a.erase(a.begin() + b);",
" return ans;",
" }",
" ",
" bool discard(const T &x){",
" if(sz == 0) return false;",
" auto [b, i] = _position(x);",
" if(i == (int)a[b].size() || a[b][i] != x) return false;",
" _pop(b, i);",
" return true;",
" }",
"",
" optional<T> lt(const T &x){",
" for(int b = (int)a.size() - 1; b >= 0; b--){",
" if(a[b][0] < x){",
" int l = lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" return a[b][l - 1];",
" }",
" }",
" return nullopt;",
" }",
"",
" optional<T> le(const T &x){",
" for(int b = (int)a.size() - 1; b >= 0; b--){",
" if(a[b][0] <= x){",
" int r = upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" return a[b][r - 1];",
" }",
" }",
" return nullopt;",
" }",
"",
" optional<T> gt(const T &x){",
" for(int b = 0; b < (int)a.size(); b++){",
" if(a[b].back() > x){",
" int r = upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" return a[b][r];",
" }",
" }",
" return nullopt;",
" }",
"",
" optional<T> ge(const T &x){",
" for(int b = 0; b < (int)a.size(); b++){",
" if(a[b].back() >= x){",
" int l = lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" return a[b][l];",
" }",
" }",
" return nullopt;",
" }",
"",
" const T& operator[](int i) const {",
" if(i < 0){",
" assert(~i < sz);",
" for(int b = (int)a.size() - 1; b >= 0; b--){",
" i += (int)a[b].size();",
" if (i >= 0) return a[b][i];",
" }",
" }",
" else{",
" assert(i < sz);",
" for(int b = 0; b < (int)a.size(); b++){",
" if(i < (int)a[b].size()) return a[b][i];",
" i -= (int)a[b].size();",
" }",
" }",
" }",
"",
" T pop(int i){",
" if(i < 0){",
" assert(~i < sz);",
" for(int b = (int)a.size() - 1; b >= 0; b--){",
" i += (int)a[b].size();",
" if (i >= 0) return _pop(b, i);",
" }",
" }",
" else{",
" assert(i < sz);",
" for(int b = 0; b < (int)a.size(); b++){",
" if(i < (int)a[b].size()) return _pop(b, i);",
" i -= (int)a[b].size();",
" }",
" }",
" }",
"",
" int index(const T &x){",
" int ans = 0;",
" for(int b = 0; b < (int)a.size(); b++){",
" if(a[b].back() >= x){",
" return ans + lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" }",
" ans += (int)a[b].size();",
" }",
" return ans;",
" }",
"",
" int index_right(const T &x){",
" int ans = 0;",
" for(int b = 0; b < (int)a.size(); b++){",
" if(a[b].back() > x){",
" return ans + upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" }",
" ans += (int)a[b].size();",
" }",
" return ans;",
" }",
"};",
"",
"template<typename T>",
"struct SortedMultiSet{",
" const int BUCKET_RATIO = 50;",
" const int SPLIT_RATIO = 170;",
" vector<vector<T>> a;",
" int sz = 0;",
"",
" SortedMultiSet(){}",
" SortedMultiSet(const vector<T> &vec){",
" vector<T> dat = vec;",
" sort(dat.begin(), dat.end());",
"",
" int n = sz = dat.size();",
" int num_bucket = (int)ceil(sqrt((double)n / (double)BUCKET_RATIO));",
" a.resize(num_bucket);",
" for(int i = 0; i < num_bucket; i++){",
" a[i] = vector<T>(dat.begin() + n * i / num_bucket, dat.begin() + n * (i + 1) / num_bucket);",
" }",
" }",
"",
" bool operator==(const SortedMultiSet& other) {",
" return this->a == other.a;",
" }",
"",
" size_t size() { return sz; }",
"",
" friend ostream& operator<<(ostream& os, const SortedMultiSet& st) {",
" os << \"{ \";",
" for(const auto&vec : st.a){",
" for(const auto& v : vec){",
" os << v << \" \";",
" }",
" }",
" os << \"}\";",
" return os;",
" }",
"",
" pair<int, int> _position(const T &x){",
" int as = a.size();",
" for(int i = 0; i < as; i++){",
" if(x <= a[i].back()) {",
" return make_pair(i, lower_bound(a[i].begin(), a[i].end(), x) - a[i].begin());",
" }",
" }",
" return make_pair(as - 1, lower_bound(a[as - 1].begin(), a[as - 1].end(), x) - a[as - 1].begin());",
" }",
"",
" int count(const T &x) { return this->index_right(x) - this->index(x); }",
"",
" void add(const T &x){",
" if(sz == 0){",
" a = {{x}};",
" sz = 1;",
" return;",
" }",
" auto [b, i] = _position(x);",
" a[b].insert(a[b].begin() + i, x);",
" sz++;",
" if((int)a[b].size() > (int)a.size() * SPLIT_RATIO){",
" int mid = (int)a[b].size() >> 1;",
" vector<T> head(a[b].begin(), a[b].begin() + mid), tail(a[b].begin() + mid, a[b].end());",
" a.erase(a.begin() + b);",
" a.insert(a.begin() + b, tail);",
" a.insert(a.begin() + b, head);",
" }",
" }",
"",
" T _pop(int b, int i){",
" T ans = a[b][i];",
" a[b].erase(a[b].begin() + i);",
" sz--;",
" if((int)a[b].size() == 0) a.erase(a.begin() + b);",
" return ans;",
" }",
" ",
" bool discard(const T &x){",
" if(sz == 0) return false;",
" auto [b, i] = _position(x);",
" if(i == (int)a[b].size() || a[b][i] != x) return false;",
" _pop(b, i);",
" return true;",
" }",
"",
" optional<T> lt(const T &x){",
" for(int b = (int)a.size() - 1; b >= 0; b--){",
" if(a[b][0] < x){",
" int l = lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" return a[b][l - 1];",
" }",
" }",
" return nullopt;",
" }",
"",
" optional<T> le(const T &x){",
" for(int b = (int)a.size() - 1; b >= 0; b--){",
" if(a[b][0] <= x){",
" int r = upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" return a[b][r - 1];",
" }",
" }",
" return nullopt;",
" }",
"",
" optional<T> gt(const T &x){",
" for(int b = 0; b < (int)a.size(); b++){",
" if(a[b].back() > x){",
" int r = upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" return a[b][r];",
" }",
" }",
" return nullopt;",
" }",
"",
" optional<T> ge(const T &x){",
" for(int b = 0; b < (int)a.size(); b++){",
" if(a[b].back() >= x){",
" int l = lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" return a[b][l];",
" }",
" }",
" return nullopt;",
" }",
"",
" const T& operator[](int i) const {",
" if(i < 0){",
" assert(~i < sz);",
" for(int b = (int)a.size() - 1; b >= 0; b--){",
" i += (int)a[b].size();",
" if (i >= 0) return a[b][i];",
" }",
" }",
" else{",
" assert(i < sz);",
" for(int b = 0; b < (int)a.size(); b++){",
" if(i < (int)a[b].size()) return a[b][i];",
" i -= (int)a[b].size();",
" }",
" }",
" }",
"",
" T pop(int i){",
" if(i < 0){",
" assert(~i < sz);",
" for(int b = (int)a.size() - 1; b >= 0; b--){",
" i += (int)a[b].size();",
" if (i >= 0) return _pop(b, i);",
" }",
" }",
" else{",
" assert(i < sz);",
" for(int b = 0; b < (int)a.size(); b++){",
" if(i < (int)a[b].size()) return _pop(b, i);",
" i -= (int)a[b].size();",
" }",
" }",
" }",
"",
" int index(const T &x){",
" int ans = 0;",
" for(int b = 0; b < (int)a.size(); b++){",
" if(a[b].back() >= x){",
" return ans + lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" }",
" ans += (int)a[b].size();",
" }",
" return ans;",
" }",
"",
" int index_right(const T &x){",
" int ans = 0;",
" for(int b = 0; b < (int)a.size(); b++){",
" if(a[b].back() > x){",
" return ans + upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();",
" }",
" ans += (int)a[b].size();",
" }",
" return ans;",
" }",
"};",
""
],
"description": "sortedset"
},
"removable_pq": {
"prefix": "atcoder_data_removable_pq",
"body": [
"struct T{",
" int rate;",
" T(int _rate) : rate(_rate) {}",
"",
" bool operator<(const T& x) const {",
" return this->rate < x.rate;",
" }",
"",
" bool operator==(const T& x) const {",
" return this->rate == x.rate;",
" }",
"};",
"",
"// you cannot erase element not in Q;",
"// only greater",
"template <typename T>",
"struct removable_priority_queue{",
" priority_queue<T> Q, R;",
" removable_priority_queue(){}",
"",
" void push(T x){ Q.push(x); }",
"",
" void erase(T x){ R.push(x); }",
"",
" T top(){",
" assert(!this->empty());",
" while(!R.empty() && R.top() == Q.top()){",
" R.pop();",
" Q.pop();",
" }",
" return Q.top();",
" };",
"",
" int size(){ return Q.size() - R.size(); }",
"",
" bool empty(){ return size() == 0; }",
"};",
""
],
"description": "removable_pq"
},
"RAQRSQ": {
"prefix": "atcoder_data_RAQRSQ",
"body": [
"// verify : https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=9516360#1",
"template<typename T>",
"struct RangeAddRangeSum{",
" int n;",
" atcoder::fenwick_tree<T> fw0, fw1;",
" RangeAddRangeSum(int n) : n(n) {",
" fw0 = atcoder::fenwick_tree<T>(n + 1);",
" fw1 = atcoder::fenwick_tree<T>(n + 1);",
" }",
"",
" void add(int l, int r, T x){",
" fw0.add(l, -x * (T)(l - 1));",
" fw0.add(r, x * (T)(r - 1));",
" fw1.add(l, x);",
" fw1.add(r, -x);",
" }",
"",
" void add(int i, T x) { return add(i, i + 1, x); }",
"",
" // [0, i)",
" T _sum(int i) { return fw0.sum(0, i) + fw1.sum(0, i) * (T)(i - 1); }",
"",
" // [l, r)",
" T sum(int l, int r) { return _sum(r) - _sum(l); }",
"};",
""
],
"description": "RAQRSQ"
},
"sparsetable2d": {
"prefix": "atcoder_data_sparsetable2d",
"body": [
"template<class S, S(*op)(S, S), S(*e)()>",
"struct SparseTable2d{",
" vector<vector<vector<vector<S>>>> table;",
" vector<int> bit_len; // bit_len[i] ... iを超えない最大の指数 (ex bit_len[6] = 2)",
" SparseTable2d(vector<vector<S>> &vec){",
" _build(vec);",
" }",
"",
" void _build(vector<vector<S>> &vec){",
" int H = vec.size(), W = vec[0].size();",
" int logH = 0, logW = 0;",
" while((1 << logH) <= H) logH++;",
" while((1 << logW) <= W) logW++;",
"",
" table.resize(logH, vector(logW, vector((1 << logH), vector<S>((1 << logW), e()))));",
" for(int i = 0; i < H; i++){",
" for(int j = 0; j < W; j++){",
" table[0][0][i][j] = vec[i][j];",
" }",
" }",
"",
" for(int k = 0; k + 1 < logH; k++){",
" for(int i = 0; i + (1 << k) < (1 << logH); i++){",
" for(int j = 0; j < (1 << logW); j++){",
" table[k + 1][0][i][j] = op(table[k][0][i][j], table[k][0][i + (1 << k)][j]);",
" }",
" }",
" }",
"",
" for(int k = 0; k < logH; k++){",
" for(int l = 0; l + 1 < logW; l++){",
" for(int i = 0; i + (1 << k) < (1 << logH); i++){",
" for(int j = 0; j + (1 << l) < (1 << logW); j++){",
" table[k][l + 1][i][j] = op(table[k][l][i][j], table[k][l][i][j + (1 << l)]);",
" }",
" }",
" }",
" }",
"",
" bit_len.resize(max(H, W) + 1, 0);",
" for(int i = 2; i < (int)bit_len.size(); i++){",
" bit_len[i] = bit_len[i >> 1] + 1;",
" }",
" }",
"",
" // [i0, i1) x [j0, j1)",
" S prod(int i0, int i1, int j0, int j1){",
" if(i0 >= i1 || j0 >= j1) return e();",
" int bi = bit_len[i1 - i0];",
" int bj = bit_len[j1 - j0];",
" return op(",
" op(table[bi][bj][i0][j0], table[bi][bj][i1 - (1 << bi)][j0]),",
" op(table[bi][bj][i0][j1 - (1 << bj)], table[bi][bj][i1 - (1 << bi)][j1 - (1 << bj)])",
" );",
" }",
"};",
""
],
"description": "sparsetable2d"
},
"sparsetable": {
"prefix": "atcoder_data_sparsetable",
"body": [
"template <class S, S(*op)(S,S), S(*e)()>",
"struct SparseTable {",
" vector<vector<S>> table;",
" vector<int> bit_len; // bit_len[i] ... iを超えない最大の指数 (ex bit_len[6] = 2)",
" SparseTable(vector<S> &vec){ ",
" _build(vec);",
" }",
"",
" void _build(vector<S> &vec){",
" int N = vec.size();",
" int logN = 0;",
" while((1 << logN) <= N)logN++;",
"",
" table.resize(logN, vector<S>(1 << logN, e()));",
" for(int i = 0; i < N; i++){",
" table[0][i] = vec[i];",
" }",
" for(int i = 0; i + 1 < logN; i++){",
" for(int j = 0; j + (1 << i) < (1 << logN); j++){",
" table[i + 1][j] = op(table[i][j], table[i][j + (1 << i)]);",
" }",
" }",
" bit_len.resize(N + 1, 0);",
" for(int i = 2; i < (int)bit_len.size(); i++){",
" bit_len[i] = bit_len[i >> 1] + 1;",
" }",
" }",
"",
" S get(int p){",
" return table[0][p];",
" }",
"",
" S prod(int l, int r){",
" if (r - l <= 0) return e();",
" int b = bit_len[r - l];",
" return op(table[b][l], table[b][r - (1 << b)]);",
" }",
"};",
""
],
"description": "sparsetable"
},
"rangetree": {
"prefix": "atcoder_data_rangetree",
"body": [
"",
"template <class S, S (*op)(S, S), S (*e)(), class CoordinateType> struct RangeTree {",
" using CT = CoordinateType;",
" using Point = pair<CT, CT>;",
" vector<Point> points;",
" vector<vector<Point>> yx;",
" vector<atcoder::segtree<S,op,e>> seg;",
" int n;",
"",
" void _set(int idx, Point p, S val){",
" int i = lower_bound(yx[idx].begin(), yx[idx].end(), Point{p.second, p.first}) - yx[idx].begin();",
" seg[idx].set(i, val);",
" }",
" S _prod(int idx, CT yl, CT yr){",
" auto comp = [](const Point &lhs, const Point &rhs) {return lhs.first < rhs.first; };",
" int il = lower_bound(yx[idx].begin(), yx[idx].end(), Point{yl, yl}, comp) - yx[idx].begin();",
" int ir = lower_bound(yx[idx].begin(), yx[idx].end(), Point{yr, yr}, comp) - yx[idx].begin();",
" return seg[idx].prod(il, ir);",
" }",
"",
" void add_point(CT x, CT y){",
" points.push_back(Point{x, y});",
" }",
"",
" void build(){",
" sort(points.begin(), points.end());",
" points.erase(unique(points.begin(), points.end()), points.end());",
" n = points.size();",
"",
" yx.resize(2 * n);",
" for(int i = 0; i < n; i++) yx[i + n] = { Point{points[i].second, points[i].first}};",
" for(int i = n - 1; i > 0; i--){",
" auto &lc = yx[2 * i];",
" auto &rc = yx[2 * i + 1];",
" merge(lc.begin(), lc.end(), rc.begin(), rc.end(), back_inserter(yx[i]));",
" yx[i].erase(unique(yx[i].begin(), yx[i].end()), yx[i].end());",
" }",
" for(const auto &v : yx) seg.emplace_back(v.size());",
" }",
"",
" void set(CT x, CT y, S val){",
" int i = lower_bound(points.begin(), points.end(), Point{x, y}) - points.begin() + n;",
" while(i){",
" _set(i, Point{x, y}, val);",
" i = i >> 1;",
" }",
" }",
"",
" S prod(CT xl, CT xr, CT yl, CT yr){",
" auto comp = [](const Point &lhs, const Point &rhs) {return lhs.first < rhs.first; };",
" int l = lower_bound(points.begin(), points.end(), Point{xl, yr}, comp) - points.begin() + n;",
" int r = lower_bound(points.begin(), points.end(), Point{xr, yr}, comp) - points.begin() + n;",
" S sml = e(), smr = e();",
" while(l < r){",
" if(l & 1) sml = op(sml, _prod(l++, yl, yr));",
" if(r & 1) smr = op(_prod(--r, yl, yr), smr);",
" l >>= 1;",
" r >>= 1;",
" }",
"",
" return op(sml, smr);",
" }",
"",
" S get(CT x, CT y){",
" return prod(x, x + 1, y, y + 1);",
" }",
"};"
],
"description": "rangetree"
},
"compress": {
"prefix": "atcoder_data_compress",
"body": [
"template<typename T>",
"struct Compress{",
" vector<int> res;",
" map<T,int> org_2_comp;",
" map<int,T> comp_2_org;",
" Compress(vector<T> &vec, int base=0){init(vec,base);};",
" void init(vector<T> &vec, int base=0){",
" int N = vec.size();",
" res.assign(N,-1);",
" int cnt = base;",
" set<T> st;",
" for(int i=0;i<N;i++) {",
" st.insert(vec[i]);",
" }",
" for(auto itr=st.begin();itr!=st.end();itr++){",
" org_2_comp[*itr] = cnt;",
" comp_2_org[cnt] = *itr;",
" cnt++;",
" }",
" for(int i=0;i<N;i++) {",
" res[i] = org_2_comp[vec[i]];",
" }",
" }",
" // 座圧した値を返す",
" int get(int idx){",
" return res[idx];",
" }",
" // 座圧したリストを返す",
" vector<int> get_comp(){",
" return res;",
" }",
" // 元の値->座圧した値",
" int org2comp(T &val){",
" return org_2_comp[val];",
" }",
" // 座圧した値->元の値",
" T comp2org(int &idx){",
" return comp_2_org[idx];",
" }",
"};",
"",
"template<typename T>",
"struct Compress_multi{ // 同じ値を別に考える",
" vector<int> res;",
" map<T,int> org_2_min_comp, org_2_max_comp;",
" map<int,T> comp_2_org;",
" Compress_multi(vector<T> &vec, int base=0){init(vec,base);};",
" void init(vector<T> &vec, int base=0){",
" int N = vec.size();",
" res.assign(N,-1);",
" int cnt = base;",
" vector<pair<T,int>> val_and_idx(N);",
" rep(i,N) val_and_idx[i] = make_pair(vec[i], i);",
" sort(all(val_and_idx));",
" rep(i,N) {",
" T val = val_and_idx[i].first;",
" int idx = val_and_idx[i].second;",
" if (!org_2_min_comp.count(val)) org_2_min_comp[val] = cnt;",
" if (!org_2_max_comp.count(val)) org_2_max_comp[val] = cnt;",
" chmax(org_2_max_comp[val],cnt);",
" res[idx] = cnt;",
" comp_2_org[cnt] = val;",
" cnt++;",
" }",
" }",
" // 座圧した値を返す",
" int get(int idx){",
" return res[idx];",
" }",
" // 座圧したリストを返す",
" vector<int> get_comp(){",
" return res;",
" }",
" // 座圧した値->元の値",
" T comp2org(int &idx){",
" return comp_2_org[idx];",
" }",
" // 元の値->座圧した値で最小",
" int org2comp_min(T &val){",
" return org_2_min_comp[val];",
" }",
" // 元の値->座圧した値で最大",
" int org2comp_max(T &val){",
" return org_2_max_comp[val];",
" }",
"};",
""
],
"description": "compress"
},
"cumulate": {
"prefix": "atcoder_data_cumulate2d",
"body": [
"struct cumulative_sum_2d{",
" int H,W;",
" vector<vector<ll>> val;",
" vector<vector<ll>> wa;",
" cumulative_sum_2d(int H_input, int W_input){init(H_input,W_input);}",
" void init(int H_input, int W_input){",
" H = H_input;",
" W = W_input;",
" val.assign(H,vector<ll>(W,0ll));",
" wa.assign(H+1,vector<ll>(W+1,0ll));",
" }",
" void set(int i, int j, ll value){",
" val[i][j] = value;",
" }",
" void add(int i, int j, ll value){",
" val[i][j] += value;",
" }",
" void build(){",
" for(int i=0;i<H;i++){",
" for(int j=0;j<W;j++){",
" wa[i+1][j+1] = wa[i][j+1] + wa[i+1][j] - wa[i][j] + val[i][j];",
" }",
" }",
" }",
" // [i1, i2) x [j1, j2)",
" ll query(int i1,int j1, int i2, int j2){",
" return wa[i2][j2] - wa[i2][j1] - wa[i1][j2] + wa[i1][j1];",
" }",
"};",
""
],
"description": "cumulate"
},
"2d_imos": {
"prefix": "atcoder_data_imos2d",
"body": [
"struct imos_2d{",
" int H,W;",
" vector<vector<ll>> imos;",
" imos_2d(int H_input, int W_input){init(H_input, W_input);}",
" void init(int H_input, int W_input){",
" H = H_input;",
" W = W_input;",
" imos.assign(H+1,vector<ll>(W+1,0ll));",
" }",
" //[i1,i2)x[i2,j2)の長方形にvalを足す",
" void add(int i1, int j1, int i2, int j2, int val){",
" imos[i1][j1] += val;",
" imos[i2][j1] -= val;",
" imos[i1][j2] -= val;",
" imos[i2][j2] += val;",
" }",
" void build(){",
" for(int i=0;i<=H;i++){",
" for(int j=0;j<W;j++){",
" imos[i][j+1] += imos[i][j];",
" }",
" }",
" for(int j=0;j<=W;j++){",
" for(int i=0;i<H;i++){",
" imos[i+1][j] += imos[i][j];",
" }",
" }",
" }",
" ll query(int i, int j){",
" return imos[i][j];",
" }",
"};",
""
],
"description": "2d_imos"
},
"doubleheap": {
"prefix": "atcoder_data_doubleheap",
"body": [
"struct DoubleHeap{",
" priority_queue<ll,vector<ll>,greater<ll>> min_hq;",
" priority_queue<ll,vector<ll>> max_hq;",
" map<ll,ll> mp; // {value, count}",
" ll _size = 0;",
" ll _total = 0;",
" DoubleHeap(){}",
" //",
" ll count(ll x){",
" return mp[x];",
" }",
" //",
" ll size(){",
" return _size;",
" }",
" //",
" ll sum(){",
" return _total;",
" }",
" //",
" void insert(ll x){",
" _size++;",
" _total += x;",
" min_hq.push(x);",
" max_hq.push(x);",
" mp[x]++;",
" }",
" // 削除した個数を返す",
" ll erase(ll x, ll n = LINF){",
" if (count(x) < n) n = count(x);",
" _size -= n;",
" _total -= n * x;",
" mp[x] -= n;",
" // if(mp[x]==0) mp.erase(x);",
" while((!min_hq.empty()) && (count(min_hq.top()) == 0)) min_hq.pop();",
" while((!max_hq.empty()) && (count(max_hq.top()) == 0)) max_hq.pop();",
" return n;",
" }",
" // ",
" void discard(ll x){",
" erase(x, 1);",
" }",
" // ",
" ll get_min(){",
" return min_hq.top();",
" };",
" //",
" ll get_max(){",
" return max_hq.top();",
" };",
" //",
" ll pop_min(){",
" ll v = get_min();",
" discard(v);",
" return v;",
" }",
" //",
" ll pop_max(){",
" ll v = get_max();",
" discard(v);",
" return v;",
" }",
" ",
" // debug",
" vector<pair<ll,ll>> dump(){",
" vector<pair<ll,ll>> res; // (value, cnt)",
" for(auto itr = mp.begin(); itr != mp.end(); itr++){",
" res.push_back(make_pair(itr->first, itr->second));",
" }",
" return res;",
" }",
"};",
""
],
"description": "doubleheap"
},
"swag": {
"prefix": "atcoder_data_swag",
"body": [
"//https://qiita.com/Shirotsume/items/4a2837b5895ef9a7aeb1#foldable-stack-%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6",
"template <class T, T (*op)(T,T), T (*e)()>",
"struct SWAG {",
" vector<T> top, bottom, topfold, bottomfold;",
" SWAG(){",
" topfold.push_back(e());",
" bottomfold.push_back(e());",
" }",
" void _pushbottom(T x){",
" bottom.push_back(x);",
" bottomfold.push_back(op(bottomfold.back(), x));",
" }",
" T _popbottom(){",
" auto res = bottom.back();",
" bottom.pop_back();",
" bottomfold.pop_back();",
" return res;",
" }",
" void _pushtop(T x){",
" top.push_back(x);",
" topfold.push_back(op(x, topfold.back()));",
" }",
" T _poptop(){",
" auto res = top.back();",
" top.pop_back();",
" topfold.pop_back();",
" return res;",
" }",
" void push(T x){",
" _pushbottom(x);",
" }",
" void pushleft(T x){",
" _pushtop(x);",
" }",
" T fold(){",
" return op(topfold.back(), bottomfold.back());",
" }",
" T popleft(){",
" if (top.empty()){",
" vector<T> stack_;",
" while(!bottom.empty()){",
" auto x = _popbottom();",
" stack_.push_back(x);",
" }",
" int N = stack_.size();",
" reverse(all(stack_));",
" vector<T> stack1, stack2;",
" for(int i=0;i<N;i++){",
" if (i < (N+1)/2) stack1.push_back(stack_[i]);",
" else stack2.push_back(stack_[i]);",
" }",
" reverse(all(stack2));",
" for(int i=0;i<(N+1)/2;i++){",
" _pushtop(stack1.back());",
" stack1.pop_back();",
" }",
" for(int i=0;i<(N/2);i++){",
" _pushbottom(stack2.back());",
" stack2.pop_back();",
" }",
" }",
" if (top.empty()) return e();",
" else return _poptop();",
" }",
" T pop(){",
" if (bottom.empty()){",
" vector<T> stack_;",
" while(!top.empty()){",
" auto x = _poptop();",
" stack_.push_back(x);",
" }",
" int N = stack_.size();",
" vector<T> stack1, stack2;",
" for(int i=0;i<N;i++){",
" if (i < (N/2)) stack1.push_back(stack_[i]);",
" else stack2.push_back(stack_[i]);",
" }",
" reverse(all(stack2));",
" for(int i=0;i<(N+1)/2;i++){",
" _pushtop(stack2.back());",
" stack2.pop_back();",
" }",
" for(int i=0;i<(N/2);i++){",
" _pushtop(stack1.back());",
" stack1.pop_back();",
" }",
" }",
" if (bottom.empty()) return e();",
" else return _popbottom();",
" }",
"};",
"",
"using S = ll;",
"S op(S a, S b){return min(a, b);}",
"S e(){return LINF;}",
"// SWAG<S,op,e> sw;",
""
],
"description": "swag"
},
"BinaryTrie": {
"prefix": "atcoder_data_binary_trie",
"body": [
"// Binary Trie",
"template<typename INT, size_t MAX_DIGIT> struct BinaryTrie {",
" struct Node {",
" size_t count;",
" Node *prev, *left, *right;",
" Node(Node *prev) : count(0), prev(prev), left(nullptr), right(nullptr) {}",
" };",
" INT lazy;",
" Node *root;",
"",
" // constructor",
" BinaryTrie() : lazy(0), root(emplace(nullptr)) {}",
" inline size_t get_count(Node *v) const { return v ? v->count : 0; }",
"",
" // add and get value of Node",
" inline void add(INT val) {",
" lazy ^= val;",
" }",
" inline INT get(Node *v) {",
" if (!v) return -1;",
" INT res = 0;",
" for (int i = 0; i < MAX_DIGIT; ++i) {",
" if (v == v->prev->right)",
" res |= INT(1)<<i;",
" v = v->prev;",
" }",
" return res ^ lazy;",
" }",
"",
" // find Node* whose value is val",
" Node* find(INT val) {",
" INT nval = val ^ lazy;",
" Node *v = root;",
" for (int i = MAX_DIGIT-1; i >= 0; --i) {",
" bool flag = (nval >> i) & 1;",
" if (flag) v = v->right;",
" else v = v->left;",
" if (!v) return v;",
" }",
" return v;",
" }",
"",
" // insert",
" inline Node* emplace(Node *prev) {",
" return new Node(prev);",
" }",
" void insert(INT val, size_t k = 1) {",
" INT nval = val ^ lazy;",
" Node *v = root;",
" for (int i = MAX_DIGIT-1; i >= 0; --i) {",
" bool flag = (nval >> i) & 1;",
" if (flag && !v->right) v->right = emplace(v);",
" if (!flag && !v->left) v->left = emplace(v);",
" if (flag) v = v->right;",
" else v = v->left;",
" }",
" v->count += k;",
" while ((v = v->prev)) v->count = get_count(v->left) + get_count(v->right);",
" }",
" ",
" // erase",
" Node* clear(Node *v) {",
" if (!v || get_count(v)) return v;",
" delete(v);",
" return nullptr;",
" }",
" bool erase(Node *v, size_t k = 1) {",
" if (!v) return false;",
" v->count -= k;",
" while ((v = v->prev)) {",
" v->left = clear(v->left);",
" v->right = clear(v->right);",
" v->count = get_count(v->left) + get_count(v->right);",
" }",
" return true;",
" }",
" bool erase(INT val) {",
" auto v = find(val);",
" return erase(v);",
" }",
" bool erase_k(INT val, size_t k = 1) {",
" return erase(find(val), k);",
" }",
"",
" // max (with xor-addition of val) and min (with xor-addition of val)",
" Node* get_max(INT val = 0) {",
" INT nval = val ^ lazy;",
" Node* v = root;",
" for (int i = MAX_DIGIT-1; i >= 0; --i) {",
" bool flag = (nval >> i) & 1;",
" if (!v->right) v = v->left;",
" else if (!v->left) v = v->right;",
" else if (flag) v = v->left;",
" else v = v->right;",
" }",
" return v;",
" }",
" Node* get_min(INT val = 0) {",
" return get_max(~val & ((INT(1)<<MAX_DIGIT)-1));",
" }",
"",
" // lower_bound, upper_bound",
" Node* get_cur_node(Node *v, int i) {",
" if (!v) return v;",
" Node *left = v->left, *right = v->right;",
" if ((lazy >> i) & 1) swap(left, right);",
" if (left) return get_cur_node(left, i+1);",
" else if (right) return get_cur_node(right, i+1);",
" return v;",
" }",
" Node* get_next_node(Node *v, int i) {",
" if (!v->prev) return nullptr;",
" Node *left = v->prev->left, *right = v->prev->right;",
" if ((lazy >> (i+1)) & 1) swap(left, right);",
" if (v == left && right) return get_cur_node(right, i);",
" else return get_next_node(v->prev, i+1);",
" }",
" Node* lower_bound(INT val) {",
" INT nval = val ^ lazy;",
" Node *v = root;",
" for (int i = MAX_DIGIT-1; i >= 0; --i) {",
" bool flag = (nval >> i) & 1;",
" if (flag && v->right) v = v->right;",
" else if (!flag && v->left) v = v->left;",
" else if ((val >> i) & 1) return get_next_node(v, i);",
" else return get_cur_node(v, i);",
" }",
" return v;",
" }",
" Node* upper_bound(INT val) {",
" return lower_bound(val + 1);",
" }",
" size_t order_of_val(INT val) {",
" Node *v = root;",
" size_t res = 0;",
" for (int i = MAX_DIGIT-1; i >= 0; --i) {",
" Node *left = v->left, *right = v->right;",
" if ((lazy >> i) & 1) swap(left, right);",
" bool flag = (val >> i) & 1;",
" if (flag) {",
" res += get_count(left);",
" v = right;",
" }",
" else v = left;",
" }",
" return res;",
" }",
"",
" // k-th, k is 0-indexed",
" Node* get_kth(size_t k, INT val = 0) {",
" Node *v = root;",
" if (get_count(v) <= k) return nullptr;",
" for (int i = MAX_DIGIT-1; i >= 0; --i) {",
" bool flag = (lazy >> i) & 1;",
" Node *left = (flag ? v->right : v->left);",
" Node *right = (flag ? v->left : v->right);",
" if (get_count(left) <= k) k -= get_count(left), v = right;",
" else v = left;",
" }",
" return v;",
" }",
"",
" // debug",
" void print(Node *v, string prefix = \"\") {",
" if (!v) return;",
" cout << prefix << \": \" << v->count << endl;",
" print(v->left, prefix + \"0\");",
" print(v->right, prefix + \"1\");",
" }",
" void print() {",
" print(root);",
" }",
" vector<INT> eval(Node *v, int digit) const {",
" vector<INT> res;",
" if (!v) return res;",
" if (!v->left && !v->right) {",
" for (int i = 0; i < get_count(v); ++i) res.push_back(0);",
" return res;",
" }",
" const auto& left = eval(v->left, digit-1);",
" const auto& right = eval(v->right, digit-1);",
" for (auto val : left) res.push_back(val);",
" for (auto val : right) res.push_back(val + (INT(1)<<digit));",
" return res;",
" }",
" vector<INT> eval() const {",
" auto res = eval(root, MAX_DIGIT-1);",
" for (auto &val : res) val ^= lazy;",
" return res;",
" }",
" friend ostream& operator << (ostream &os, const BinaryTrie<INT, MAX_DIGIT> &bt) {",
" auto res = bt.eval();",
" for (auto val : res) os << val << \" \";",
" return os;",
" }",
"};",
"//https://drken1215.hatenablog.com/entry/2020/02/29/035900",
"//BinaryTrie<int,30> trie;",
"//trie.root->count -> 集合のサイズ",
"//trie.get_count(x) -> xの個数",
"//trie.xor_query(val) -> 全体にvalをxor",
"//trie.get(v) -> 遅延伝搬のため，取り出す時は基本的にこれを使う",
"//trie.find(x) -> xがあるか",
"//trie.insert(x,k=1) -> xをk個挿入",
"//trie.erase(x) -> xを1個削除",
"//trie.erase_k(x,k=1) -> xをk個削除",
"//trie.get_max(val = 0) -> valとxorを取った時の最大値",
"//trie.get_min(val = 0) -> valとxorを取った時の最小値",
"//trie.get_kth(x) -> x番目(0-indexed)の値を取り出す．",
"//trie.lower_bound(x) -> ",
"//trie.upper_bound(x) -> ",
"//trie.order_of_val(x) -> xが何番目か(0-indexed),xが集合にある場合のみ有効",
"//trie.get_kth(x) -> 0indexedでx番目の値、x個無いならnullptr(<-int型、!get_kth(val)は可能)",
"",
],
"description": "BinaryTrie"
},
"Segtree_2d": {
"prefix": "atcoder_data_Segtree2d",
"body": [
"template <typename T, typename F>",
"struct SegmentTree2D {",
" private:",
" int id(int h, int w) { return h * 2 * W + w; }",
" public:",
" int H, W;",
" vector<T> seg;",
" const F f;",
" const T I;",
" SegmentTree2D(int h, int w, F _f, const T& i) : f(_f), I(i) { init(h, w); }",
"",
" void init(int h, int w) {",
" H = W = 1;",
" while (H < h) H <<= 1;",
" while (W < w) W <<= 1;",
" seg.assign(4 * H * W, I);",
" }",
"",
" // build にのみ呼ぶ",
" void set(int h, int w, const T& x) { seg[id(h + H, w + W)] = x; }",
"",
" void build() {",
" // w in [W, 2W)",
" for (int w = W; w < 2 * W; w++) {",
" for (int h = H - 1; h; h--) {",
" seg[id(h, w)] = f(seg[id(2 * h + 0, w)], seg[id(2 * h + 1, w)]);",
" }",
" }",
" // h in [0, 2H)",
" for (int h = 0; h < 2 * H; h++) {",
" for (int w = W - 1; w; w--) {",
" seg[id(h, w)] = f(seg[id(h, 2 * w + 0)], seg[id(h, 2 * w + 1)]);",
" }",
" }",
" }",
"",
" T get(int h, int w) { return seg[id(h + H, w + W)]; }",
" // T operator()(int h, int w) const { return seg[id(h + H, w + W)]; }",
"",
" void update(int h, int w, const T& x) {",
" h += H, w += W;",
" seg[id(h, w)] = x;",
" for (int i = h >> 1; i; i >>= 1) {",
" seg[id(i, w)] = f(seg[id(2 * i + 0, w)], seg[id(2 * i + 1, w)]);",
" }",
" for (; h; h >>= 1) {",
" for (int j = w >> 1; j; j >>= 1) {",
" seg[id(h, j)] = f(seg[id(h, 2 * j + 0)], seg[id(h, 2 * j + 1)]);",
" }",
" }",
" }",
"",
" T _inner_query(int h, int w1, int w2) {",
" T res = I;",
" for (; w1 < w2; w1 >>= 1, w2 >>= 1) {",
" if (w1 & 1) res = f(res, seg[id(h, w1)]), w1++;",
" if (w2 & 1) --w2, res = f(res, seg[id(h, w2)]);",
" }",
" return res;",
" }",
"",
" // [ (h1,w1), (h2,w2) ) 半開",
" T prod(int h1, int w1, int h2, int w2) {",
" if (h1 >= h2 || w1 >= w2) return I;",
" T res = I;",
" h1 += H, h2 += H, w1 += W, w2 += W;",
" for (; h1 < h2; h1 >>= 1, h2 >>= 1) {",
" if (h1 & 1) res = f(res, _inner_query(h1, w1, w2)), h1++;",
" if (h2 & 1) --h2, res = f(res, _inner_query(h2, w1, w2));",
" }",
" return res;",
" }",
"};",
"",
"/**",
" * @brief 二次元セグメント木",
" * @docs docs/data-structure-2d/2d-segment-tree.md",
" * https://nyaannyaan.github.io/library/data-structure-2d/2d-segment-tree.hpp",
" */",
"// ",
"// ll f(ll a, ll b){return a + b;}",
"// ll e(){return 0ll;}",
"// SegmentTree2D seg(H,W,f,e());",
""
],
"description": "Segtree_2d"
},
"bit2d": {
"prefix": "atcoder_data_bit2d",
"body": [
"template<typename T>",
"struct BIT2D{",
" int H, W;",
" vector<vector<T>> bit;",
" BIT2D(int _H, int _W) : H(_H), W(_W){",
" bit.resize(H, vector<T>(W, 0));",
" }",
" // data[i][j] += v;",
" void add(int i, int j, T v){",
" for(int a = i + 1; a <= H; a += (a & -a)){",
" for(int b = j + 1; b <= W; b += (b & - b)){",
" bit[a - 1][b - 1] += v;",
" }",
" }",
" }",
" // [0, i) x [0, j)",
" T _sum(int i, int j){",
" T s = 0;",
" for(int a = i; a > 0; a -= (a & -a)){",
" for(int b = j; b > 0; b -= (b & -b)){",
" s += bit[a - 1][b - 1];",
" }",
" }",
" return s;",
" }",
" // [i1, i2) x [j1, j2)",
" T sum(int i1, int j1, int i2, int j2){",
" return _sum(i2, j2) - _sum(i2, j1) - _sum(i1, j2) + _sum(i1, j1);",
" }",
"};",
""
],
"description": "bit2d"
},
"Wavelet_Matrix": {
"prefix": "atcoder_data_wavelet_matrix",
"body": [
"// https://github.com/MitI-7/WaveletMatrix",
"enum {",
" NOTFOUND = 0xFFFFFFFFFFFFFFFFLLU // 18446744073709551615 ~ 1.8x10^20",
"};",
"",
"class SuccinctBitVector {",
"private:",
" const uint64_t size; // ビットベクトルのサイズ",
" static const uint64_t blockBitNum = 16;",
" static const uint64_t LEVEL_L = 512;",
" static const uint64_t LEVEL_S = 16;",
"",
" std::vector<uint64_t> L; // 大ブロック",
" std::vector<uint16_t> S; // 小ブロック",
" std::vector<uint16_t> B; // ビットベクトル",
"",
" uint64_t numOne = 0; // 1bitの数",
"",
"public:",
" explicit SuccinctBitVector(const uint64_t n) : size(n) {",
" const uint64_t s = (n + blockBitNum - 1) / blockBitNum + 1; // ceil(n, blockSize)",
" this->B.assign(s, 0);",
" this->L.assign(n / LEVEL_L + 1, 0);",
" this->S.assign(n / LEVEL_S + 1, 0);",
" }",
"",
" // B[pos] = bit",
" void setBit(const uint64_t bit, const uint64_t pos){",
" assert(bit == 0 or bit == 1);",
" assert(pos < this->size);",
"",
" const uint64_t blockPos = pos / blockBitNum;",
" const uint64_t offset = pos % blockBitNum;",
" if (bit == 1) { B.at(blockPos) |= (1LLU << offset); }",
" else { B.at(blockPos) &= (~(1LLU << offset)); }",
" }",
"",
" // B[pos]",
" uint64_t access(const uint64_t pos) {",
" assert(pos < this->size);",
" const uint64_t blockPos = pos / blockBitNum;",
" const uint64_t offset = pos % blockBitNum;",
" return ((B.at(blockPos) >> offset) & 1);",
" }",
"",
" void build() {",
" uint64_t num = 0;",
" for (uint64_t i = 0; i <= size; i++){",
" if (i % LEVEL_L == 0) {",
" L.at(i / LEVEL_L) = num;",
" }",
" if (i % LEVEL_S == 0) {",
" S.at(i / LEVEL_S) = num - L.at(i / LEVEL_L);",
" }",
" if (i != size and i % blockBitNum == 0) {",
" num += this->popCount(this->B.at(i / blockBitNum));",
" }",
" }",
" this-> numOne = num;",
" }",
"",
" // B[0, pos)のbitの数",
" uint64_t rank(const uint64_t bit, const uint64_t pos) {",
" assert(bit == 0 or bit == 1);",
" assert(pos <= this->size);",
"",
" if (bit) {",
" return L[pos / LEVEL_L] + S[pos / LEVEL_S] + popCount(B[pos / blockBitNum] & ((1 << (pos % blockBitNum)) - 1));",
" }",
" else {",
" return pos - rank(1, pos);",
" }",
" }",
"",
" // rank番目のbitの位置 + 1(rankは1-origin)",
" uint64_t select(const uint64_t bit, const uint64_t rank) {",
" assert(bit == 0 or bit == 1);",
" assert(rank > 0);",
" if (bit == 0 and rank > this->size - this-> numOne) { return NOTFOUND; }",
" if (bit == 1 and rank > this-> numOne) { return NOTFOUND; }",
"",
" // 大ブロックL内を検索",
" uint64_t large_idx = 0;",
" {",
" uint64_t left = 0;",
" uint64_t right = L.size();",
" while (right - left > 1) {",
" uint64_t mid = (left + right) / 2;",
" uint64_t r = L.at(mid);",
" r = (bit) ? r : mid * LEVEL_L - L.at(mid);",
"",
" if (r < rank) {",
" left = mid;",
" large_idx = mid;",
" } else {",
" right = mid;",
" }",
" }",
" }",
"",
" // 小ブロックS内を検索",
" uint64_t small_idx = (large_idx * LEVEL_L) / LEVEL_S;",
" {",
" uint64_t left = (large_idx * LEVEL_L) / LEVEL_S;",
" uint64_t right = std::min(((large_idx + 1) * LEVEL_L) / LEVEL_S, (uint64_t)S.size());",
" while (right - left > 1) {",
" uint64_t mid = (left + right) / 2;",
" uint64_t r = L.at(large_idx) + S.at(mid);",
" r = (bit) ? r :mid * LEVEL_S - r;",
"",
" if (r < rank) {",
" left = mid;",
" small_idx = mid;",
" } else {",
" right = mid;",
" }",
" }",
" }",
"",
" // Bをブロック単位で順番に探索",
" uint64_t rank_pos = 0;",
" {",
" const uint64_t begin_block_idx = (small_idx * LEVEL_S) / blockBitNum;",
" uint64_t total_bit = L.at(large_idx) + S.at(small_idx);",
" if (bit == 0) {",
" total_bit = small_idx * LEVEL_S - total_bit;",
" }",
" for (uint64_t i = 0;; ++i) {",
" uint64_t b = popCount(B.at(begin_block_idx + i));",
" if (bit == 0) {",
" b = blockBitNum - b;",
" }",
" if (total_bit + b >= rank) {",
" uint64_t block = (bit) ? B.at(begin_block_idx + i) : ~B.at(begin_block_idx + i);",
" rank_pos = (begin_block_idx + i) * blockBitNum + selectInBlock(block, rank - total_bit);",
" break;",
" }",
" total_bit += b;",
" }",
" }",
"",
" return rank_pos + 1;",
" }",
"",
" uint64_t getNumOne() const {",
" return numOne;",
" }",
"",
" void debug() {",
" std::cout << \"LEVEL_L(\" << L.size() << \")\" << std::endl;",
" for (uint64_t i = 0 ; i < L.size(); ++i) {",
" std::cout << L.at(i) << \", \";",
" }",
" std::cout << std::endl;",
" std::cout << \"LEVEL_S(\" << S.size() << \")\" << std::endl;",
" for (uint64_t i = 0 ; i < S.size(); ++i) {",
" std::cout << S.at(i) << \", \";",
" }",
" std::cout << std::endl;",
" }",
"",
"private:",
" uint64_t popCount(uint64_t x) {",
" x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);",
" x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);",
" x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;",
" x = x + (x >> 8);",
" x = x + (x >> 16);",
" x = x + (x >> 32);",
" return x & 0x7FLLU;",
" }",
"",
" uint64_t selectInBlock(uint64_t x, uint64_t rank) {",
" uint64_t x1 = x - ((x & 0xAAAAAAAAAAAAAAAALLU) >> 1);",
" uint64_t x2 = (x1 & 0x3333333333333333LLU) + ((x1 >> 2) & 0x3333333333333333LLU);",
" uint64_t x3 = (x2 + (x2 >> 4)) & 0x0F0F0F0F0F0F0F0FLLU;",
"",
" uint64_t pos = 0;",
" for (;; pos += 8){",
" uint64_t rank_next = (x3 >> pos) & 0xFFLLU;",
" if (rank <= rank_next) break;",
" rank -= rank_next;",
" }",
"",
" uint64_t v2 = (x2 >> pos) & 0xFLLU;",
" if (rank > v2) {",
" rank -= v2;",
" pos += 4;",
" }",
"",
" uint64_t v1 = (x1 >> pos) & 0x3LLU;",
" if (rank > v1){",
" rank -= v1;",
" pos += 2;",
" }",
"",
" uint64_t v0 = (x >> pos) & 0x1LLU;",
" if (v0 < rank){",
" rank -= v0;",
" pos += 1;",
" }",
"",
" return pos;",
" }",
"};",
"",
"class WaveletMatrix {",
"private:",
" std::vector<SuccinctBitVector> bit_arrays;",
" std::vector<uint64_t> begin_one; // 各bitに着目したときの1の開始位置",
" std::map<uint64_t, uint64_t> begin_alphabet; // 最後のソートされた配列で各文字の開始位置",
" std::vector<std::vector<uint64_t>> cumulative_sum; // 各bitに着目したときの累積和",
"",
" uint64_t size; // 与えられた配列のサイズ",
" uint64_t maximum_element; // 文字数",
" uint64_t bit_size; // 文字を表すのに必要なbit数",
"",
"public:",
" WaveletMatrix (const std::vector<uint64_t> &array) {",
" assert(array.size() > 0);",
" size = array.size();",
" maximum_element = *max_element(array.begin(), array.end()) + 1;",
" bit_size = get_num_of_bit(maximum_element);",
" if (bit_size == 0) {",
" bit_size = 1;",
" }",
"",
" for (uint64_t i = 0; i < bit_size; ++i) {",
" SuccinctBitVector sv(size);",
" bit_arrays.push_back(sv);",
" }",
" this->begin_one.resize(bit_size);",
" this->cumulative_sum.resize(bit_size + 1, std::vector<uint64_t>(size + 1, 0));",
"",
" for (uint64_t j = 0; j < array.size(); ++j) {",
" this->cumulative_sum.at(0).at(j + 1) = this->cumulative_sum.at(0).at(j) + array[j];",
" }",
"",
" std::vector<uint64_t> v(array);",
" for (uint64_t i = 0; i < bit_size; ++i) {",
"",
" std::vector<uint64_t> temp;",
" // 0をtempにいれてく",
" for (uint64_t j = 0; j < v.size(); ++j) {",
" uint64_t c = v.at(j);",
" uint64_t bit = (c >> (bit_size - i - 1)) & 1; // 上からi番目のbit",
" if (bit == 0) {",
" temp.push_back(c);",
" bit_arrays.at(i).setBit(0, j);",
" }",
" }",
"",
" this->begin_one.at(i) = temp.size();",
"",
" // 1をtempにいれてく",
" for (uint64_t j = 0; j < v.size(); ++j) {",
" uint64_t c = v.at(j);",
" uint64_t bit = (c >> (bit_size - i - 1)) & 1; // 上からi番目のbit",
" if (bit == 1) {",
" temp.push_back(c);",
" bit_arrays.at(i).setBit(1, j);",
" }",
" }",
"",
" for (uint64_t j = 0; j < temp.size(); ++j) {",
" this->cumulative_sum.at(i + 1).at(j + 1) = this->cumulative_sum.at(i + 1).at(j) + temp.at(j);",
" }",
"",
" bit_arrays.at(i).build();",
" v = temp;",
" }",
"",
" // ソートされた配列内での各文字の位置を取得",
" for (int i = v.size() - 1; i >= 0; --i) {",
" this->begin_alphabet[v.at(i)] = i;",
" }",
" }",
"",
" // v[pos]",
" uint64_t access(uint64_t pos) {",
" if (pos >= this->size) { return NOTFOUND; }",
"",
" uint64_t c = 0;",
" for (uint64_t i = 0; i < bit_arrays.size(); ++i) {",
" uint64_t bit = bit_arrays.at(i).access(pos); // もとの数値のi番目のbit",
" c = (c <<= 1) | bit;",
" pos = bit_arrays.at(i).rank(bit, pos);",
" if (bit) {",
" pos += this->begin_one.at(i);",
" }",
" }",
" return c;",
" }",
"",
" // i番目のcの位置 + 1を返す。rankは1-origin",
" uint64_t select(uint64_t c, uint64_t rank) {",
" assert(rank > 0);",
" if (c >= maximum_element) {",
" return NOTFOUND;",
" }",
" if (this->begin_alphabet.find(c) == this->begin_alphabet.end()) {",
" return NOTFOUND;",
" }",
"",
" uint64_t index = this->begin_alphabet.at(c) + rank;",
" for (uint64_t i = 0; i < bit_arrays.size(); ++i){",
" uint64_t bit = ((c >> i) & 1); // 下からi番目のbit",
" if (bit == 1) {",
" index -= this->begin_one.at(bit_size - i - 1);",
" }",
" index = this->bit_arrays.at(bit_size - i - 1).select(bit, index);",
" }",
" return index;",
" }",
"",
" // v[begin_pos, end_pos)で最大値のindexを返す",
" uint64_t maxRange(uint64_t begin_pos, uint64_t end_pos) {",
" return quantileRange(begin_pos, end_pos, end_pos - begin_pos - 1);",
" }",
"",
" // v[begin_pos, end_pos)で最小値のindexを返す",
" uint64_t minRange(uint64_t begin_pos, uint64_t end_pos) {",
" return quantileRange(begin_pos, end_pos, 0);",
" }",
"",
" // v[begin_pos, end_pos)でk番目に小さい数値のindexを返す(kは0-origin)",
" // つまり小さい順に並べてk番目の値",
" uint64_t quantileRange(uint64_t begin_pos, uint64_t end_pos, uint64_t k) {",
" if ((end_pos > size || begin_pos >= end_pos) || (k >= end_pos - begin_pos)) {",
" return NOTFOUND;",
" }",
"",
" uint64_t val = 0;",
" for (uint64_t i = 0; i < bit_size; ++i) {",
" const uint64_t num_of_zero_begin = bit_arrays.at(i).rank(0, begin_pos);",
" const uint64_t num_of_zero_end = bit_arrays.at(i).rank(0, end_pos);",
" const uint64_t num_of_zero = num_of_zero_end - num_of_zero_begin; // beginからendまでにある0の数",
" const uint64_t bit = (k < num_of_zero) ? 0 : 1; // k番目の値の上からi番目のbitが0か1か",
"",
" if (bit) {",
" k -= num_of_zero;",
" begin_pos = this->begin_one.at(i) + begin_pos - num_of_zero_begin;",
" end_pos = this->begin_one.at(i) + end_pos - num_of_zero_end;",
" }",
" else {",
" begin_pos = num_of_zero_begin;",
" end_pos = num_of_zero_begin + num_of_zero;",
" }",
"",
" val = ((val << 1) | bit);",
" }",
"",
" uint64_t left = 0;",
" for (uint64_t i = 0; i < bit_size; ++i) {",
" const uint64_t bit = (val >> (bit_size - i - 1)) & 1; // 上からi番目のbit",
" left = bit_arrays.at(i).rank(bit, left); // cのi番目のbitと同じ数値の数",
" if (bit) {",
" left += this->begin_one.at(i);",
" }",
" }",
"",
" const uint64_t rank = begin_pos + k - left + 1;",
" return select(val, rank) - 1;",
" }",
"",
" // v[0, pos)のcの数",
" uint64_t rank(uint64_t c, uint64_t pos) {",
" assert(pos < size);",
" if (c >= maximum_element) {",
" return 0;",
" }",
" if (this->begin_alphabet.find(c) == this->begin_alphabet.end()) {",
" return 0;",
" }",
"",
" for (uint64_t i = 0; i < bit_size; ++i) {",
" uint64_t bit = (c >> (bit_size - i - 1)) & 1; // 上からi番目のbit",
" pos = bit_arrays.at(i).rank(bit, pos); // cのi番目のbitと同じ数値の数",
" if (bit) {",
" pos += this->begin_one.at(i);",
" }",
" }",
"",
" uint64_t begin_pos = this->begin_alphabet.at(c);",
" return pos - begin_pos;",
" }",
"",
" // v[begin_pos, end_pos)で[min, max)に入る値の個数",
" uint64_t rangeFreq(uint64_t begin_pos, uint64_t end_pos, uint64_t min_c, uint64_t max_c) {",
" if ((end_pos > size || begin_pos >= end_pos) || (min_c >= max_c) || min_c >= maximum_element) {",
" return 0;",
" }",
"",
" const auto maxi_t = rankAll(max_c, begin_pos, end_pos);",
" const auto mini_t = rankAll(min_c, begin_pos, end_pos);",
" return std::get<1>(maxi_t) - std::get<1>(mini_t);",
" }",
"",
" // v[0, pos)でcより小さい文字の数 <- 恐らくv[begin, end)",
" uint64_t rankLessThan(uint64_t c, uint64_t begin, uint64_t end) {",
" auto t = rankAll(c, begin, end);",
" return std::get<1>(t);",
" }",
"",
" // v[0, pos)でcより大きい文字の数 <- 恐らくv[begin, end)",
" uint64_t rankMoreThan(uint64_t c, uint64_t begin, uint64_t end) {",
" auto t = rankAll(c, begin, end);",
" return std::get<2>(t);",
" }",
"",
" // v[begin, end)で(cと同じ値の数、cより小さい値の数、cより大きい値の数)を求める",
" std::tuple<uint64_t, uint64_t, uint64_t> rankAll(const uint64_t c, uint64_t begin, uint64_t end) {",
" assert(end <= size);",
" const uint64_t num = end - begin;",
"",
" if (begin >= end) {",
" return std::make_tuple(0, 0, 0);",
" }",
" if (c >= maximum_element || end == 0) {",
" return std::make_tuple(0, num, 0);",
" }",
"",
" uint64_t rank_less_than = 0, rank_more_than = 0;",
" for (size_t i = 0; i < bit_size && begin < end; ++i) {",
" const uint64_t bit = (c >> (bit_size - i - 1)) & 1;",
"",
" const uint64_t rank0_begin = this->bit_arrays.at(i).rank(0, begin);",
" const uint64_t rank0_end = this->bit_arrays.at(i).rank(0, end);",
" const uint64_t rank1_begin = begin - rank0_begin;",
" const uint64_t rank1_end = end - rank0_end;",
"",
" if (bit) {",
" rank_less_than += (rank0_end - rank0_begin); // i番目のbitが0のものは除外される",
" begin = this->begin_one.at(i) + rank1_begin;",
" end = this->begin_one.at(i) + rank1_end;",
" } else {",
" rank_more_than += (rank1_end - rank1_begin); // i番目のbitが1のものは除外される",
" begin = rank0_begin;",
" end = rank0_end;",
" }",
" }",
"",
" const uint64_t rank = num - rank_less_than - rank_more_than;",
" return std::make_tuple(rank, rank_less_than, rank_more_than);",
" }",
"",
" // T[s, e)で出現回数が多い順にk個の(値，頻度)を返す",
" // 頻度が同じ場合は値が小さいものが優先される",
" std::vector<std::pair<uint64_t, uint64_t>> topk(uint64_t s, uint64_t e, uint64_t k) {",
" assert(s < e);",
" std::vector<std::pair<uint64_t, uint64_t>> result;",
"",
" // (頻度，深さ，値)の順でソート",
" auto c = [](const std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t> &l, const std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t> &r) {",
" // width",
" if (std::get<0>(l) != std::get<0>(r)) {",
" return std::get<0>(l) < std::get<0>(r);",
" }",
" // depth",
" if (std::get<3>(l) != std::get<3>(r)) {",
" return std::get<3>(l) > std::get<3>(r);",
" }",
" // value",
" if (std::get<4>(l) != std::get<4>(r)) {",
" return std::get<4>(l) > std::get<4>(r);",
" }",
" return true;",
" };",
"",
" std::priority_queue<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t>, std::vector<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t>>, decltype(c)> que(c); // width, left, right, depth, value",
" que.push(std::make_tuple(e - s, s, e, 0, 0));",
"",
" while (not que.empty()) {",
" auto element = que.top(); que.pop();",
" uint64_t width, left, right, depth, value;",
" std::tie(width, left, right, depth, value) = element;",
"",
" if (depth >= this->bit_size) {",
" result.emplace_back(std::make_pair(value, right - left));",
" if (result.size() >= k) {",
" break;",
" }",
" continue;",
" }",
"",
" // 0",
" const uint64_t left0 = this->bit_arrays.at(depth).rank(0, left);",
" const uint64_t right0 = this->bit_arrays.at(depth).rank(0, right);",
" if (left0 < right0) {",
" que.push(std::make_tuple(right0 - left0, left0, right0, depth + 1, value));",
" }",
"",
" // 1",
" const uint64_t left1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, left);",
" const uint64_t right1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, right);",
" if (left1 < right1) {",
" que.push(std::make_tuple(right1 - left1, left1, right1, depth + 1, value | (1 << (bit_size - depth - 1))));",
" }",
" }",
"",
" return result;",
" };",
"",
" // T[begin_pos, end_pos)でx <= c < yを満たすcの和を返す",
" uint64_t rangeSum(const uint64_t begin, const uint64_t end, const uint64_t x, const uint64_t y) {",
" return rangeSum(begin, end, 0, 0, x, y);",
" }",
"",
" // T[begin_pos, end_pos)でx <= c < yを満たす最大のcを返す",
" uint64_t prevValue(const uint64_t begin_pos, const uint64_t end_pos, const uint64_t x, uint64_t y) {",
" assert(end_pos <= size);",
" const uint64_t num = end_pos - begin_pos;",
"",
" if (x >= y or y == 0) {",
" return NOTFOUND;",
" }",
" if (y > maximum_element) {",
" y = maximum_element;",
" }",
"",
" if (begin_pos >= end_pos) {",
" return NOTFOUND;",
" }",
" if (x >= maximum_element || end_pos == 0) {",
" return NOTFOUND;",
" }",
"",
" y--; // x <= c <= yにする",
"",
" std::stack<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, bool>> s; // (begin, end, depth, c, tight)",
" s.emplace(std::make_tuple(begin_pos, end_pos, 0, 0, true));",
"",
" while (not s.empty()) {",
" uint64_t b, e, depth, c;",
" bool tight;",
" std::tie(b, e, depth, c, tight) = s.top(); s.pop();",
"",
" if (depth == bit_size) {",
" if (c >= x) {",
" return c;",
" }",
" continue;",
" }",
"",
" const uint64_t bit = (y >> (bit_size - depth - 1)) & 1;",
"",
" const uint64_t rank0_begin = this->bit_arrays.at(depth).rank(0, b);",
" const uint64_t rank0_end = this->bit_arrays.at(depth).rank(0, e);",
" const uint64_t rank1_begin = b - rank0_begin;",
" const uint64_t rank1_end = e - rank0_end;",
"",
" // d番目のbitが0のものを使う",
" const uint64_t b0 = rank0_begin;",
" const uint64_t e0 = rank0_end;",
" if (b0 != e0) { // 範囲がつぶれてない",
" const uint64_t c0 = ((c << 1) | 0);",
" s.emplace(std::make_tuple(b0, e0, depth + 1, c0, tight and bit == 0));",
" }",
"",
" // d番目のbitが1のものを使う",
" const uint64_t b1 = this->begin_one.at(depth) + rank1_begin;",
" const uint64_t e1 = this->begin_one.at(depth) + rank1_end;",
" if (b1 != e1) {",
" if (not tight or bit == 1) {",
" const auto c1 = ((c << 1) | 1);",
" s.emplace(std::make_tuple(b1, e1, depth + 1, c1, tight));",
" }",
" }",
" }",
"",
" return NOTFOUND;",
" }",
"",
" // T[begin_pos, end_pos)でx <= c < yを満たす最小のcを返す",
" uint64_t nextValue(const uint64_t begin_pos, const uint64_t end_pos, const uint64_t x, const uint64_t y) {",
" assert(end_pos <= size);",
" const uint64_t num = end_pos - begin_pos;",
"",
" if (x >= y or y == 0) {",
" return NOTFOUND;",
" }",
"",
" if (begin_pos >= end_pos) {",
" return NOTFOUND;",
" }",
" if (x >= maximum_element || end_pos == 0) {",
" return NOTFOUND;",
" }",
"",
" std::stack<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, bool>> s; // (begin, end, depth, c, tight)",
" s.emplace(std::make_tuple(begin_pos, end_pos, 0, 0, true));",
"",
" while (not s.empty()) {",
" uint64_t b, e, depth, c;",
" bool tight;",
" std::tie(b, e, depth, c, tight) = s.top(); s.pop();",
"",
" if (depth == bit_size) {",
" if (c < y) {",
" return c;",
" }",
" continue;",
" }",
"",
" const uint64_t bit = (x >> (bit_size - depth - 1)) & 1;",
"",
" const uint64_t rank0_begin = this->bit_arrays.at(depth).rank(0, b);",
" const uint64_t rank0_end = this->bit_arrays.at(depth).rank(0, e);",
" const uint64_t rank1_begin = b - rank0_begin;",
" const uint64_t rank1_end = e - rank0_end;",
"",
" // d番目のbitが1のものを使う",
" const uint64_t b1 = this->begin_one.at(depth) + rank1_begin;",
" const uint64_t e1 = this->begin_one.at(depth) + rank1_end;",
" if (b1 != e1) {",
" const auto c1 = ((c << 1) | 1);",
" s.emplace(std::make_tuple(b1, e1, depth + 1, c1, tight and bit == 1));",
" }",
"",
" // d番目のbitが0のものを使う",
" const uint64_t b0 = rank0_begin;",
" const uint64_t e0 = rank0_end;",
" if (b0 != e0) {",
" if (not tight or bit == 0) {",
" const uint64_t c0 = ((c << 1) | 0);",
" s.emplace(std::make_tuple(b0, e0, depth + 1, c0, tight));",
" }",
" }",
" }",
"",
" return NOTFOUND;",
" }",
"",
" // T[s1, e1)とT[s2, e2)に共通して出現する要素を求める",
" std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> intersect(uint64_t _s1, uint64_t _e1, uint64_t _s2, uint64_t _e2) {",
" assert(_s1 < _e1);",
" assert(_s2 < _e2);",
"",
" std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> intersection;",
"",
" std::queue<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t, uint64_t>> que; // s1, e1, s2, e2, depth, value",
" que.push(std::make_tuple(_s1, _e1, _s2, _e2, 0, 0));",
" while (not que.empty()) {",
" auto e = que.front(); que.pop();",
" uint64_t s1, e1, s2, e2, depth, value;",
" std::tie(s1, e1, s2, e2, depth, value) = e;",
"",
" if (depth >= this->bit_size) {",
" intersection.emplace_back(std::make_tuple(value, e1 - s1, e2 - s2));",
" continue;",
" }",
"",
" // 0",
" uint64_t s1_0 = this->bit_arrays.at(depth).rank(0, s1);",
" uint64_t e1_0 = this->bit_arrays.at(depth).rank(0, e1);",
" uint64_t s2_0 = this->bit_arrays.at(depth).rank(0, s2);",
" uint64_t e2_0 = this->bit_arrays.at(depth).rank(0, e2);",
"",
" if (s1_0 != e1_0 and s2_0 != e2_0) {",
" que.push(std::make_tuple(s1_0, e1_0, s2_0, e2_0, depth + 1, value));",
" }",
"",
" // 1",
" uint64_t s1_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, s1);",
" uint64_t e1_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, e1);",
" uint64_t s2_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, s2);",
" uint64_t e2_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, e2);",
"",
" if (s1_1 != e1_1 and s2_1 != e2_1) {",
" que.push(std::make_tuple(s1_1, e1_1, s2_1, e2_1, depth + 1, value | (1 << bit_size - depth - 1)));",
" }",
" }",
"",
" return intersection;",
" };",
"",
"private:",
" uint64_t get_num_of_bit(uint64_t x) {",
" if (x == 0) return 0;",
" x--;",
" uint64_t bit_num = 0;",
" while (x >> bit_num) {",
" ++bit_num;",
" }",
" return bit_num;",
" }",
"",
" uint64_t rangeSum(const uint64_t begin, const uint64_t end, const uint64_t depth, const uint64_t c, const uint64_t x, const uint64_t y) {",
" if (begin == end) {",
" return 0;",
" }",
"",
" if (depth == bit_size) {",
" if (x <= c and c < y) {",
" return c * (end - begin); // 値 * 頻度",
" }",
" return 0;",
" }",
"",
" const uint64_t next_c = ((uint64_t)1 << (bit_size - depth - 1)) | c; // 上からdepth番目のbitを立てる",
" const uint64_t all_one_c = (((uint64_t)1 << (bit_size - depth - 1)) - 1) | next_c; // depth以降のbitをたてる(これ以降全部1を選んだときの値)",
" if(all_one_c < x or y <= c) {",
" return 0;",
" }",
"",
" // [begin, pos)のすべての要素は[x, y)",
" if (x <= c and all_one_c < y) {",
" return this->cumulative_sum.at(depth).at(end) - this->cumulative_sum.at(depth).at(begin);",
" }",
"",
" const uint64_t rank0_begin = this->bit_arrays.at(depth).rank(0, begin);",
" const uint64_t rank0_end = this->bit_arrays.at(depth).rank(0, end);",
" const uint64_t rank1_begin = begin - rank0_begin;",
" const uint64_t rank1_end = end - rank0_end;",
"",
" return rangeSum(rank0_begin, rank0_end, depth + 1, c, x, y) +",
" rangeSum(this->begin_one.at(depth) + rank1_begin, this->begin_one[depth] + rank1_end, depth + 1, next_c, x, y);",
" }",
"};",
"// vector<uint64_t> vec(N);",
"// WaveletMatrix wm(vec);",
"// wm.access(i)",
"// wm.select(val, rank)",
"// wm.maxRange(left, right)",
"// wm.minRange(left, right)",
"// wm.quantileRange(left, right, k)",
"// wm.rank(right)",
"// wm.rangeFreq(left, right, min_val, max_val)",
"// wm.rankLessThan(val, left, right)",
"// wm.rankMoreThan(val, left, right)",
"// wm.rankAll(val, left, right)",
"// wm.topk(left, right, k)",
"// wm.rangeSum(left, right, val_left, val_right)",
"// wm.prevValue(left, right, val_left, val_right)",
"// wm.nextValue(left, right, val_left, val_right)",
"// wm.intersect(left1, right1, left2, right2)",
""
],
"description": "Wavelet_Matrix"
},
//
//math
//
"itertools": {
"prefix": "atcoder_math_itertools",
"body": [
"/**",
" * @brief nHrの配列を返す",
" * ",
" * @tparam T 要素の型",
" * @param arr 長さnの配列",
" * @param r 重複組合せで選ぶ数r",
" * @return vector<vector<T>> nHrの結果を辞書順昇順で返す",
" */",
"template<typename T>",
"vector<vector<T>> combination_with_replacement(vector<T> &arr, int r){",
" vector<vector<T>> res;",
" function<void(vector<T>&, int)> dfs = [&](vector<T> &e, int idx){",
" if ((int)e.size() == r) {",
" res.push_back(e);",
" return;",
" }",
" else {",
" for(int i = idx; i < (int)arr.size(); i++){",
" e.push_back(arr[i]);",
" dfs(e, i);",
" e.pop_back();",
" }",
" }",
" };",
" vector<T> e = {};",
" dfs(e, 0);",
" return res;",
"}",
"",
"/**",
" * @brief nCrの配列を返す",
" * ",
" * @tparam T 要素の型",
" * @param arr 長さnの配列",
" * @param r 組み合わせで選ぶ数r",
" * @return vector<vector<T>> nCrの結果を辞書順昇順で返す",
" */",
"template<typename T>",
"vector<vector<T>> combinations(vector<T> &arr, int r){",
" vector<vector<T>> res;",
" int n = arr.size();",
" function<void(vector<T>&, int)> dfs = [&](vector<T> &e, int idx){",
" if ((int)e.size() == r) {",
" res.push_back(e);",
" return;",
" }",
" if (idx == n) return;",
"",
" if (e.size() + (n - (idx + 1)) >= r) dfs(e, idx + 1);",
"",
" e.push_back(arr[idx]);",
" if (e.size() + (n - (idx + 1)) >= r) dfs(e, idx + 1);",
" e.pop_back();",
" };",
" vector<T> e = {};",
" dfs(e, 0);",
" reverse(res.begin(), res.end());",
" return res;",
"}",
"",
"/**",
" * @brief nPrの配列を返す",
" * ",
" * @tparam T 要素の型",
" * @param arr 長さnの配列",
" * @param r 組み合わせで選ぶ数r",
" * @param dflag 昇順にソートするならtrue(デフォルトはfalse);",
" * @return vector<vector<T>> nPrの結果を返す",
" */",
"template<typename T>",
"vector<vector<T>> permutations(vector<T> &arr, int r, bool dflag=false){",
" vector<vector<T>> res;",
" auto combs = combinations(arr, r);",
" for(auto ptn : combs){",
" do{",
" res.push_back(ptn);",
" }while(next_permutation(all(ptn)));",
" }",
" if(dflag) {",
" auto cmp = [](vector<T> &lhs, vector<T> &rhs){",
" int nl = lhs.size();",
" int nr = rhs.size();",
" for(int i = 0; i < min(nl, nr); i++){",
" if(lhs[i] == rhs[i]) continue;",
" return (lhs[i] < rhs[i]);",
" }",
" return (nl < nr);",
" };",
" sort(all(res), cmp);",
" }",
" return res;",
"}",
"",
"template<typename T>",
"vector<vector<T>> _productRecurse(vector<T> &choices, int repeat, vector<vector<T>> &result){",
" if (repeat == 0) return result;",
"",
" vector<vector<T>> nresult;",
" for(vector<T> re : result){",
" for(T c : choices){",
" vector<T> temp = re;",
" temp.push_back(c);",
" nresult.push_back(temp);",
" }",
" }",
"",
" return _productRecurse(choices, repeat - 1, nresult);",
"}",
"",
"/**",
" * @brief 直積を返す ",
" * ",
" * @tparam T 要素の型",
" * @param arr 長さnの配列",
" * @param r 冪乗",
" * @return vector<vector<T>> product({0, 1, 2}, 2) -> {{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}}",
" */",
"template<typename T>",
"vector<vector<T>> product(vector<T> &arr, int r=1){",
" vector<vector<T>> emptyResult(1, vector<T>{});",
" return _productRecurse(arr, r, emptyResult);",
"}",
""
],
"description": "itertools"
},
"python_like": {
"prefix": "atcoder_math_python_like",
"body": [
"// a // b in Python",
"template<typename T>",
"T floor(T a, T b){",
" if (a >= 0) return a / b;",
" else {",
" if (abs(a) % b == 0){",
" return a/b;",
" }",
" else{",
" return a/b-1;",
" }",
" }",
"}",
"",
"// a % b in Python",
"template<typename T>",
"T div_mod(T a, T b){",
" if (a >= 0) return a % b;",
" else{",
" if (abs(a) % b == 0){",
" return 0;",
" }",
" else{",
" return b - abs(a) % b;",
" }",
" }",
"}",
""
],
"description": "python_like"
},
"fps": {
"prefix": "atcoder_math_fps",
"body": [
"//形式的冪級数",
"//https://qiita.com/gg_hatano/items/3591ddf267092c235a23",
"#define rep2(i, m, n) for (int i = (m); i < (n); ++i)",
"#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)",
"#define drep(i, n) drep2(i, n, 0)",
"template<class T>",
"struct FormalPowerSeries : vector<T> {",
" using vector<T>::vector;",
" using vector<T>::operator=;",
" using F = FormalPowerSeries;",
" ",
" F operator-() const {",
" F res(*this);",
" for (auto &e : res) e = -e;",
" return res;",
" }",
" F &operator*=(const T &g) {",
" for (auto &e : *this) e *= g;",
" return *this;",
" }",
" F &operator/=(const T &g) {",
" assert(g != T(0));",
" *this *= g.inv();",
" return *this;",
" }",
" F &operator+=(const F &g) {",
" int n = (*this).size(), m = g.size();",
" rep(i, min(n, m)) (*this)[i] += g[i];",
" return *this;",
" }",
" F &operator-=(const F &g) {",
" int n = (*this).size(), m = g.size();",
" rep(i, min(n, m)) (*this)[i] -= g[i];",
" return *this;",
" }",
" F &operator<<=(const int d) {",
" int n = (*this).size();",
" (*this).insert((*this).begin(), d, 0);",
" (*this).resize(n);",
" return *this;",
" }",
" F &operator>>=(const int d) {",
" int n = (*this).size();",
" (*this).erase((*this).begin(), (*this).begin() + min(n, d));",
" (*this).resize(n);",
" return *this;",
" }",
" F inv(int d = -1) const {",
" int n = (*this).size();",
" assert(n != 0 && (*this)[0] != 0);",
" if (d == -1) d = n;",
" assert(d > 0);",
" F res{(*this)[0].inv()};",
" while (res.size() < d) {",
" int m = size(res);",
" F f(begin(*this), begin(*this) + min(n, 2*m));",
" F r(res);",
" f.resize(2*m), internal::butterfly(f);",
" r.resize(2*m), internal::butterfly(r);",
" rep(i, 2*m) f[i] *= r[i];",
" internal::butterfly_inv(f);",
" f.erase(f.begin(), f.begin() + m);",
" f.resize(2*m), internal::butterfly(f);",
" rep(i, 2*m) f[i] *= r[i];",
" internal::butterfly_inv(f);",
" T iz = T(2*m).inv(); iz *= -iz;",
" rep(i, m) f[i] *= iz;",
" res.insert(res.end(), f.begin(), f.begin() + m);",
" }",
" return {res.begin(), res.begin() + d};",
" }",
" ",
" // fast: FMT-friendly modulus only",
" F &operator*=(const F &g) {",
" int n = (*this).size();",
" *this = convolution(*this, g);",
" (*this).resize(n);",
" return *this;",
" }",
" F &operator/=(const F &g) {",
" int n = (*this).size();",
" *this = convolution(*this, g.inv(n));",
" (*this).resize(n);",
" return *this;",
" }",
" ",
" // // naive",
" // F &operator*=(const F &g) {",
" // int n = (*this).size(), m = g.size();",
" // drep(i, n) {",
" // (*this)[i] *= g[0];",
" // rep2(j, 1, min(i+1, m)) (*this)[i] += (*this)[i-j] * g[j];",
" // }",
" // return *this;",
" // }",
" // F &operator/=(const F &g) {",
" // assert(g[0] != T(0));",
" // T ig0 = g[0].inv();",
" // int n = (*this).size(), m = g.size();",
" // rep(i, n) {",
" // rep2(j, 1, min(i+1, m)) (*this)[i] -= (*this)[i-j] * g[j];",
" // (*this)[i] *= ig0;",
" // }",
" // return *this;",
" // }",
" ",
" // sparse",
" F &operator*=(vector<pair<int, T>> g) {",
" int n = (*this).size();",
" auto [d, c] = g.front();",
" if (d == 0) g.erase(g.begin());",
" else c = 0;",
" drep(i, n) {",
" (*this)[i] *= c;",
" for (auto &[j, b] : g) {",
" if (j > i) break;",
" (*this)[i] += (*this)[i-j] * b;",
" }",
" }",
" return *this;",
" }",
" F &operator/=(vector<pair<int, T>> g) {",
" int n = (*this).size();",
" auto [d, c] = g.front();",
" assert(d == 0 && c != T(0));",
" T ic = c.inv();",
" g.erase(g.begin());",
" rep(i, n) {",
" for (auto &[j, b] : g) {",
" if (j > i) break;",
" (*this)[i] -= (*this)[i-j] * b;",
" }",
" (*this)[i] *= ic;",
" }",
" return *this;",
" }",
" ",
" // multiply and divide (1 + cz^d)",
" void multiply(const int d, const T c) { ",
" int n = (*this).size();",
" if (c == T(1)) drep(i, n-d) (*this)[i+d] += (*this)[i];",
" else if (c == T(-1)) drep(i, n-d) (*this)[i+d] -= (*this)[i];",
" else drep(i, n-d) (*this)[i+d] += (*this)[i] * c;",
" }",
" void divide(const int d, const T c) {",
" int n = (*this).size();",
" if (c == T(1)) rep(i, n-d) (*this)[i+d] -= (*this)[i];",
" else if (c == T(-1)) rep(i, n-d) (*this)[i+d] += (*this)[i];",
" else rep(i, n-d) (*this)[i+d] -= (*this)[i] * c;",
" }",
" ",
" T eval(const T &a) const {",
" T x(1), res(0);",
" for (auto e : *this) res += e * x, x *= a;",
" return res;",
" }",
" ",
" F operator*(const T &g) const { return F(*this) *= g; }",
" F operator/(const T &g) const { return F(*this) /= g; }",
" F operator+(const F &g) const { return F(*this) += g; }",
" F operator-(const F &g) const { return F(*this) -= g; }",
" F operator<<(const int d) const { return F(*this) <<= d; }",
" F operator>>(const int d) const { return F(*this) >>= d; }",
" F operator*(const F &g) const { return F(*this) *= g; }",
" F operator/(const F &g) const { return F(*this) /= g; }",
" F operator*(vector<pair<int, T>> g) const { return F(*this) *= g; }",
" F operator/(vector<pair<int, T>> g) const { return F(*this) /= g; }",
"};",
"using mint = modint998244353;",
"using fps = FormalPowerSeries<mint>;",
"using sfps = vector<pair<int, mint>>; // (次数，係数)",
" "
],
"description": "fps"
},
"arbitrary": {
"prefix": "atcoder_math_cmb_arbitrary",
"body": [
"struct Barrett {",
" using u32 = unsigned int;",
" using i64 = long long;",
" using u64 = unsigned long long;",
" u32 m;",
" u64 im;",
" Barrett() : m(), im() {}",
" Barrett(int n) : m(n), im(u64(-1) / m + 1) {}",
" constexpr inline i64 quo(u64 n) {",
" u64 x = u64((__uint128_t(n) * im) >> 64);",
" u32 r = n - x * m;",
" return m <= r ? x - 1 : x;",
" }",
" constexpr inline i64 rem(u64 n) {",
" u64 x = u64((__uint128_t(n) * im) >> 64);",
" u32 r = n - x * m;",
" return m <= r ? r + m : r;",
" }",
" constexpr inline pair<i64, int> quorem(u64 n) {",
" u64 x = u64((__uint128_t(n) * im) >> 64);",
" u32 r = n - x * m;",
" if (m <= r) return {x - 1, r + m};",
" return {x, r};",
" }",
" constexpr inline i64 pow(u64 n, i64 p) {",
" u32 a = rem(n), r = m == 1 ? 0 : 1;",
" while (p) {",
" if (p & 1) r = rem(u64(r) * a);",
" a = rem(u64(a) * a);",
" p >>= 1;",
" }",
" return r;",
" }",
"};",
"",
"#define PRIME_POWER_BINOMIAL_M_MAX ((1LL << 30) - 1)",
"#define PRIME_POWER_BINOMIAL_N_MAX 20000000",
"",
"struct prime_power_binomial {",
" int p, q, M;",
" vector<int> fac, ifac, inv;",
" int delta;",
" Barrett bm, bp;",
"",
" prime_power_binomial(int _p, int _q) : p(_p), q(_q) {",
" assert(1 < p && p <= PRIME_POWER_BINOMIAL_M_MAX);",
" assert(_q > 0);",
" long long m = 1;",
" while (_q--) {",
" m *= p;",
" assert(m <= PRIME_POWER_BINOMIAL_M_MAX);",
" }",
" M = m;",
" bm = Barrett(M), bp = Barrett(p);",
" enumerate();",
" delta = (p == 2 && q >= 3) ? 1 : M - 1;",
" }",
"",
" void enumerate() {",
" int MX = min<int>(M, PRIME_POWER_BINOMIAL_N_MAX + 10);",
" fac.resize(MX);",
" ifac.resize(MX);",
" inv.resize(MX);",
" fac[0] = ifac[0] = inv[0] = 1;",
" fac[1] = ifac[1] = inv[1] = 1;",
" for (int i = 2; i < MX; i++) {",
" if (i % p == 0) {",
" fac[i] = fac[i - 1];",
" fac[i + 1] = bm.rem(1LL * fac[i - 1] * (i + 1));",
" i++;",
" } else {",
" fac[i] = bm.rem(1LL * fac[i - 1] * i);",
" }",
" }",
" ifac[MX - 1] = bm.pow(fac[MX - 1], M / p * (p - 1) - 1);",
" for (int i = MX - 2; i > 1; --i) {",
" if (i % p == 0) {",
" ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));",
" ifac[i - 1] = ifac[i];",
" i--;",
" } else {",
" ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));",
" }",
" }",
" }",
"",
" long long Lucas(long long n, long long m) {",
" int res = 1;",
" while (n) {",
" int n0, m0;",
" tie(n, n0) = bp.quorem(n);",
" tie(m, m0) = bp.quorem(m);",
" if (n0 < m0) return 0;",
" res = bm.rem(1LL * res * fac[n0]);",
" int buf = bm.rem(1LL * ifac[n0 - m0] * ifac[m0]);",
" res = bm.rem(1LL * res * buf);",
" }",
" return res;",
" }",
"",
" long long C(long long n, long long m) {",
" if (n < m || n < 0 || m < 0) return 0;",
" if (q == 1) return Lucas(n, m);",
" long long r = n - m;",
" int e0 = 0, eq = 0, i = 0;",
" int res = 1;",
" while (n) {",
" res = bm.rem(1LL * res * fac[bm.rem(n)]);",
" res = bm.rem(1LL * res * ifac[bm.rem(m)]);",
" res = bm.rem(1LL * res * ifac[bm.rem(r)]);",
" n = bp.quo(n);",
" m = bp.quo(m);",
" r = bp.quo(r);",
" int eps = n - m - r;",
" e0 += eps;",
" if (e0 >= q) return 0;",
" if (++i >= q) eq += eps;",
" }",
" if (eq & 1) res = bm.rem(1LL * res * delta);",
" res = bm.rem(1LL * res * bm.pow(p, e0));",
" return res;",
" }",
"};",
"",
"// constraints:",
"// (M <= 1e7 and max(N) <= 1e18) or (M < 2^30 and max(N) <= 2e7)",
"struct arbitrary_mod_binomial {",
" int mod;",
" vector<int> M;",
" vector<prime_power_binomial> cs;",
"",
" arbitrary_mod_binomial(long long md) : mod(md) {",
" assert(1 <= md);",
" assert(md <= PRIME_POWER_BINOMIAL_M_MAX);",
" for (int i = 2; i * i <= md; i++) {",
" if (md % i == 0) {",
" int j = 0, k = 1;",
" while (md % i == 0) md /= i, j++, k *= i;",
" M.push_back(k);",
" cs.emplace_back(i, j);",
" assert(M.back() == cs.back().M);",
" }",
" }",
" if (md != 1) {",
" M.push_back(md);",
" cs.emplace_back(md, 1);",
" }",
" assert(M.size() == cs.size());",
" }",
"",
" long long C(long long n, long long m) {",
" if (mod == 1) return 0;",
" vector<long long> rem, d;",
" for (int i = 0; i < (int)cs.size(); i++) {",
" rem.push_back(cs[i].C(n, m));",
" d.push_back(M[i]);",
" }",
" return atcoder::crt(rem, d).first;",
" }",
"};",
"",
"#undef PRIME_POWER_BINOMIAL_M_MAX",
"#undef PRIME_POWER_BINOMIAL_N_MAX",
"",
"/**",
" * @brief 任意mod二項係数",
" * @docs docs/modulo/arbitrary-mod-binomial.md",
" */",
"// arbitrary_mod_binomial coef(MOD);",
"// coef.C(N,K);",
""
],
"description": "arbitrary"
},
"combination": {
"prefix": "atcoder_math_cmb",
"body": [
"//https://drken1215.hatenablog.com/entry/2018/06/08/210000",
"//COMinit()を忘れない!!!",
"const ll NMAX = 202020;",
"const ll MOD = 998244353;",
"//const int MOD = 1e9+7;",
"",
"ll fac[NMAX],finv[NMAX],inv[NMAX];",
"",
"void COMinit(){",
" fac[0] = fac[1] = 1LL;",
" finv[0] = finv[1] = 1LL;",
" inv[1] = 1LL;",
" for (int i=2;i<NMAX;i++){",
" fac[i] = fac[i-1] * i % MOD;",
" inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;",
" finv[i] = finv[i-1] * inv[i] % MOD;",
" }",
"}",
"",
"ll nCr(int n,int k){",
" if (n<k) return 0LL;",
" if (n < 0 || k < 0) return 0LL;",
" return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;",
"}",
"",
"ll nPr(int n,int k){",
" if (n<k) return 0LL;",
" if (n < 0 || k < 0) return 0LL;",
" return fac[n] * finv[n-k] % MOD;",
"}",
"",
"ll nHr(int n,int r){",
" return nCr(n+r-1,r);",
"}"
],
"description": "combination"
},
"matrix_skeir": {
"prefix": "atcoder_math_matrix_skeir",
"body": [
"mat mat_mul(mat &A, mat &B) {",
" mat C(A.size(), vector<ll>(B[0].size()));",
" for (int i = 0; i < A.size(); ++i) {",
" for (int k = 0; k < B.size(); k++) {",
" for (int j = 0; j < B[0].size(); j++) {",
" C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % M) % M;",
" }",
" }",
" }",
" return C;",
"}",
"",
"mat mat_pow(mat &A, ll k) {",
" mat res(A.size(), vector<ll>(A.size()));",
" for (int i = 0; i < res.size(); i++) {",
" res[i][i] = 1;",
" }",
" while (k > 0) {",
" if (k & 1) res = mat_mul(res, A);",
" A = mat_mul(A, A);",
" k >>= 1;",
" }",
" return res;",
"}"
],
"description": "matrix_skeir"
},
"matrix": {
"prefix": "atcoder_math_matrix",
"body": [
"// https://youtu.be/ylWYSurx10A?t=2352",
"template<typename T>",
"struct Matrix{",
" int h, w;",
" vector<vector<T>> d;",
" Matrix(): h(0), w(0) {}",
" Matrix(int h, int w, T val=0): h(h), w(w), d(h, vector<T>(w,val)) {}",
" Matrix(int n, T val=0): h(n), w(n), d(n, vector<T>(n,val)) {}",
"",
" Matrix& unit(){",
" assert(h == w);",
" rep(i,h) d[i][i] = 1;",
" return *this;",
" }",
"",
" const vector<T>& operator[](int i) const { return d[i];}",
" vector<T>& operator[](int i) { return d[i];}",
"",
" Matrix operator+(const Matrix& a) const {",
" assert(h == a.h && w == a.w);",
" Matrix r(h, w);",
" rep(i,h)rep(j,w){",
" r[i][j] = d[i][j] + a[i][j];",
" }",
" return r;",
" }",
"",
" Matrix &operator+=(const Matrix& a) const {",
" assert(h == a.h && w == a.w);",
" rep(i,h)rep(j,w){",
" (*this)[i][j] += a[i][j];",
" }",
" return (*this);",
" }",
"",
" Matrix operator-(const Matrix& a) const {",
" assert(h == a.h && w == a.w);",
" Matrix r(h, w);",
" rep(i,h)rep(j,w){",
" r[i][j] = d[i][j] - a[i][j];",
" }",
" return r;",
" }",
"",
" Matrix &operator-=(const Matrix& a) const {",
" assert(h == a.h && w == a.w);",
" rep(i,h)rep(j,w){",
" (*this)[i][j] -= a[i][j];",
" }",
" return (*this);",
" }",
"",
" Matrix operator*(const Matrix& a) const {",
" assert(w == a.h);",
" Matrix r(h, a.w);",
" rep(i,h)rep(k,w)rep(j,a.w){",
" r[i][j] += d[i][k] * a[k][j];",
" }",
" return r;",
" }",
"",
" Matrix &operator*=(const Matrix& a) const {",
" assert(w == a.h);",
" vector<vector<T>> nd(h, vector<T>(w));",
" rep(i,h)rep(k,w)rep(j,a.w){",
" nd[i][j] += (*this)[i][k] * a[k][j];",
" }",
" d = move(nd);",
" return (*this);",
" }",
"",
" vector<T> operator*(const vector<T> &a) const {",
" // res[i] = sum{ M[i][j] * x[j] } (j = 0 ... h-1)",
" assert(w == (int)a.size());",
" vector<T> r(h);",
" rep(i,h)rep(j,w){",
" r[i] += (*this)[i][j] * a[j];",
" }",
" return r;",
" }",
"",
" Matrix operator*(const T &a) const {",
" Matrix r(h, w);",
" rep(i,h)rep(j,w){",
" r[i][j] = (*this)[i][j] * a;",
" }",
" return r;",
" }",
"",
" Matrix &operator*=(const T &a) const {",
" vector<vector<T>> nd(h, vector<T>(w));",
" rep(i,h)rep(j,w){",
" nd[i][j] = (*this)[i][j] * a;",
" }",
" d = move(nd);",
" return (*this);",
" }",
"",
" bool operator==(const Matrix &a){",
" if(h != a.h || w != a.w) return false;",
" rep(i,h)rep(j,w){",
" if((*this)[i][j] != a[i][j]) return false;",
" }",
" return true;",
" }",
"",
" friend ostream &operator<<(ostream &os, Matrix &a){",
" rep(i,a.h){",
" os << (i == 0 ? '[' : ' ');",
" rep(j,a.w) os << (j == 0 ? '[' : ' ') << a[i][j] << (j == a.w - 1 ? \"]\" : \",\");",
" os << (i == a.h - 1 ? \"]\" : \",\") << '\\n';",
" }",
" return os;",
" }",
"",
"",
" pair<int, int> shape() {return {this->h, this->w};}",
"",
" static Matrix eye(int n){",
" Matrix mat(n, n);",
" mat.unit();",
" return mat;",
" }",
"",
" Matrix pow(long long t) const {",
" assert(h == w);",
" if(!t) Matrix(h, h).unit();",
" if(t == 1) return *this;",
" Matrix r = pow(t >> 1);",
" r = r * r;",
" if(t & 1) r = r * (*this);",
" return r;",
" }",
"",
" T det(){",
" assert(h == w);",
" vector<vector<T>> dc = d;",
" T res = 1;",
" rep(k,h){",
" for(int i = k; i < h; i++){",
" if(dc[i][k] == 0) continue;",
" if(i != k){",
" swap(dc[i], dc[k]);",
" res = -res;",
" }",
" }",
" if(dc[k][k] == 0) return 0;",
" res *= dc[k][k];",
" T inv = T(1) / dc[k][k];",
" rep(j,h) dc[k][j] *= inv;",
" for(int i = k + 1; i < h; i++){",
" T c = dc[i][k];",
" for(int j = k; j < h; j++) dc[i][j] -= dc[k][j] * c;",
" }",
" }",
" return res;",
" }",
"",
" Matrix inv(){",
" assert(h == w);",
" int n = h;",
" // (A E) -> (E, invA)",
" Matrix AE(n, 2 * n);",
" rep(i,n){",
" rep(j,n) AE[i][j] = d[i][j];",
" AE[i][i + n] = 1;",
" }",
"",
" rep(r, n){",
" int pivot = -1;",
" for(int i = r; i < n; i++){",
" if(AE[i][r] != 0){",
" pivot = i;",
" break;",
" }",
" }",
" // 逆行列が存在しない",
" if(pivot == -1) return Matrix();",
" swap(AE[r], AE[pivot]);",
"",
" for(int j = r + 1; j < 2 * n; j++) AE[r][j] /= AE[r][r];",
" rep(i,n)if(i != r){",
" for(int j = r + 1; j < 2 * n; j++){",
" AE[i][j] -= AE[i][r] * AE[r][j];",
" }",
" }",
" }",
"",
" Matrix r(n, n);",
" rep(i,n)rep(j,n) r[i][j] = AE[i][j + n];",
" return r;",
" }",
"",
" // !! not verify !!",
" vector<T> linear_equation(vector<T> b){",
" Matrix invA = (*this).inv();",
" if(invA.h == 0) return {};",
" return invA * b;",
" }",
"};",
"",
"// Matrix<T> mat(h, w);",
"// Matrix<T> identity = Matrix<T>::eye(n);",
"// pii hw = mat.shape();",
"// T determinant = A.det();",
"// Matrix<T> powA = A.pow(K);",
"// Matrix<T> invA = A.pow(K);",
"// vector<T> x = A.linear_equation(b);",
""
],
"description": "matrix"
},
"Millar_Rabin": {
"prefix": "atcoder_math_Miller_Rabin",
"body": [
"// A ^ N を M で割ったあまり",
"template<class T> T pow_mod(T A, T N, T M) {",
" T res = 1 % M;",
" A %= M;",
" while (N) {",
" if (N & 1) res = (res * A) % M;",
" A = (A * A) % M;",
" N >>= 1;",
" }",
" return res;",
"}",
"",
"// Miller-Rabin 素数判定",
"bool Miller_Rabin(long long N) {",
" if (N <= 1) return false;",
" if (N == 2) return true;",
" if (N % 2 == 0) return false;",
" vector<long long> A = {2, 325, 9375, 28178, 450775,",
" 9780504, 1795265022};",
" long long s = 0, d = N - 1;",
" while (d % 2 == 0) {",
" ++s;",
" d >>= 1;",
" }",
" for (auto a : A) {",
" if (a % N == 0) return true;",
" long long t, x = pow_mod<__int128_t>(a, d, N);",
" if (x != 1) {",
" for (t = 0; t < s; ++t) {",
" if (x == N - 1) break;",
" x = __int128_t(x) * x % N;",
" }",
" if (t == s) return false;",
" }",
" }",
" return true;",
"}",
""
],
"description": "Millar_Rabin"
},
"math": {
"prefix": "atcoder_math_Pollard",
"body": [
"// https://algo-method.com/tasks/553/editorial",
"// Miller-Rabin 素数判定法",
"template<class T> T pow_mod(T A, T N, T M) {",
" T res = 1 % M;",
" A %= M;",
" while (N) {",
" if (N & 1) res = (res * A) % M;",
" A = (A * A) % M;",
" N >>= 1;",
" }",
" return res;",
"}",
"",
"bool is_prime(long long N) {",
" if (N <= 1) return false;",
" if (N == 2 || N == 3) return true;",
" if (N % 2 == 0) return false;",
" vector<long long> A = {2, 325, 9375, 28178, 450775,",
" 9780504, 1795265022};",
" long long s = 0, d = N - 1;",
" while (d % 2 == 0) {",
" ++s;",
" d >>= 1;",
" }",
" for (auto a : A) {",
" if (a % N == 0) return true;",
" long long t, x = pow_mod<__int128_t>(a, d, N);",
" if (x != 1) {",
" for (t = 0; t < s; ++t) {",
" if (x == N - 1) break;",
" x = __int128_t(x) * x % N;",
" }",
" if (t == s) return false;",
" }",
" }",
" return true;",
"}",
"",
"// Pollard のロー法",
"long long gcd(long long A, long long B) {",
" A = abs(A), B = abs(B);",
" if (B == 0) return A;",
" else return gcd(B, A % B);",
"}",
" ",
"long long pollard(long long N) {",
" if (N % 2 == 0) return 2;",
" if (is_prime(N)) return N;",
"",
" auto f = [&](long long x) -> long long {",
" return (__int128_t(x) * x + 1) % N;",
" };",
" long long step = 0;",
" while (true) {",
" ++step;",
" long long x = step, y = f(x);",
" while (true) {",
" long long p = gcd(y - x + N, N);",
" if (p == 0 || p == N) break;",
" if (p != 1) return p;",
" x = f(x);",
" y = f(f(y));",
" }",
" }",
"}",
"",
"vector<long long> prime_factorize(long long N) {",
" if (N == 1) return {};",
" long long p = pollard(N);",
" if (p == N) return {p};",
" vector<long long> left = prime_factorize(p);",
" vector<long long> right = prime_factorize(N / p);",
" left.insert(left.end(), right.begin(), right.end());",
" sort(left.begin(), left.end());",
" return left;",
"}",
""
],
"description": "math"
},
"is_prime": {
"prefix": "atcoder_math_isprime",
"body": [
"//O(sqrt(N))",
"bool is_prime(ll n){",
" for(ll i=2;i*i<=n;i++){",
" if (n % i == 0) return false;",
" }",
" return true;",
"}",
""
],
"description": "is_prime"
},
"euler_phi": {
"prefix": "atcoder_math_euler_phi",
"body": [
"",
"ll euler_phi(ll n){",
" ll res = n;",
" for(ll i = 2; i * i <= n; i++){",
" if (n % i) continue;",
" res = res - res / i;",
" while((n % i) == 0) n /= i;",
" }",
" if (n != 1) res = res - res / n;",
" return res;",
"}",
""
],
"description": "euler_phi"
},
"Eratosthenes": {
"prefix": "atcoder_math_Eratosthenes",
"body": [
"// https://qiita.com/drken/items/3beb679e54266f20ab63",
"struct Eratosthenes{",
" int N;",
" vector<bool> isprime;",
" vector<int> minfactor, mobius;",
" Eratosthenes(int N_max = 1e7){init(N_max);}",
" //初期化",
" void init(int N_max = 1e7){",
" int N = N_max;",
" isprime.assign(N+1,true);",
" minfactor.assign(N+1,-1);",
" mobius.assign(N+1,1);",
" //Eratosthenes O(NloglogN)",
" isprime[0] = false;",
" isprime[1] = false;",
" for(int p=2;p<=N;p++){",
" if (!isprime[p])continue;",
" minfactor[p] = p;",
" mobius[p] = -1;",
" //pの倍数の処理",
" for(int q=2*p;q<=N;q+=p){",
" isprime[q] = false;",
" if (minfactor[q] == -1){",
" minfactor[q] = p;",
" }",
" if ((q/p) % p == 0) mobius[q] = 0;",
" else mobius[q] *= -1;",
" }",
" }",
" }",
" //素数判定,O(1)",
" bool judge_prime(int num){",
" return isprime[num];",
" }",
" //素数列挙,O(N)",
" vector<int> list_primes(int num = -1){",
" if (num == -1) num = N;",
" vector<int> primes;",
" for(int p=0;p<=num;p++){",
" if (isprime[p]) primes.push_back(p);",
" }",
" return primes;",
" }",
" //高速素因数分解,O(logN),{(素因数,個数)...}",
" vector<pii> factorize(int x){",
" vector<pii> ans;",
" while(x > 1){",
" int p = minfactor[x];",
" int e = 0;",
" while(minfactor[x] == p){",
" x /= p;",
" e++;",
" }",
" ans.push_back(make_pair(p,e));",
" }",
" return ans;",
" }",
" //高速約数列挙 O(240(N <= 1e6),1344(N <= 1e9))",
" vector<int> divisors(int x){",
" vector<int> ans; ans.push_back(1);",
" vector<pii> facts = factorize(x);",
" for(auto [p,e]:facts){",
" int s = ans.size();",
" for(int i=0;i<s;i++){",
" int v = 1;",
" for(int j=0;j<e;j++){",
" v *= p;",
" ans.push_back(ans[i] * v);",
" }",
" }",
" }",
" sort(all(ans));",
" return ans;",
" }",
" //オイラーのphi関数",
" ll euler_phi(int x){",
" auto facts = factorize(x);",
" ll res = x;",
" for(auto [p, e]:facts){",
" res = res - res / p;",
" }",
" return res;",
" }",
" //メビウス関数",
" //mobius[1] = 1",
" //nが素数pで2回以上割り切れる -> mobius[n] = 0",
" //mobius[n] = pow(-1,Nの素数の種類)",
" int my_mobius(int x){",
" return mobius[x];",
" }",
"};",
"",
"// f -> F, 累積和Fを求める",
"template<typename T>",
"vector<T> fast_zeta(vector<T> &f){",
" vector<T> res = f;",
" int N = f.size() - 1; ",
" Eratosthenes er(N);",
" for(int p=2;p<=N;p++){",
" if (!er.judge_prime(p)) continue;",
" for(int k=(N/p);k>0;k--){",
" res[k] += res[k * p];",
" }",
" }",
" return res;",
"}",
"",
"// F -> f, 累積和Fを分解する",
"template<typename T>",
"vector<T> fast_mobius(vector<T> &F){",
" vector<T> res = F;",
" int N = F.size() - 1; ",
" Eratosthenes er(N);",
" for(int p=2;p<=N;p++){",
" if (!er.judge_prime(p)) continue;",
" for(int k=1;k<=(N/p);k++){",
" res[k] -= res[k * p];",
" }",
" }",
" return res;",
"}",
"",
"template<typename T>",
"vector<T> gcd_conv(vector<T> &f, vector<T> &g){",
" int N = max(f.size(), g.size());",
" vector<T> F(N+1) , G(N+1), H(N+1);",
" for(int i=0;i<f.size();i++){",
" F[i] = f[i];",
" }",
" for(int i=0;i<g.size();i++){",
" G[i] = g[i];",
" }",
" F = fast_zeta(F);",
" G = fast_zeta(G);",
" for(int i=1;i<=N;i++){",
" H[i] = F[i] * G[i];",
" }",
" H = fast_mobius(H);",
" return H;",
"}",
""
],
"description": "Eratosthenes"
},
"factorize": {
"prefix": "atcoder_math_factorize",
"body": [
"vector<pll> prime_factorize(ll n){",
" vector<pll> res;",
" for(ll i = 2; i * i <= n ; i++){",
" if(n % i != 0ll)continue;",
" ll tmp = 0ll;",
" while(n % i == 0ll){",
" tmp++;",
" n /= i;",
" }",
" res.push_back(make_pair(i,tmp));",
" }",
" if (n != 1ll) res.push_back(make_pair(n,1ll));",
" return res;",
"}",
""
],
"description": "factorize"
},
"make_divisors": {
"prefix": "atcoder_math_divisors",
"body": [
"vector<ll> make_divisors(ll n){",
" vector<ll> divisors;",
" ll i = 1;",
" while (i * i <= n){",
" if (n % i == 0){",
" divisors.push_back(i);",
" if (i != (n/i)) divisors.push_back(n/i);",
" }",
" i++;",
" }",
" sort(all(divisors));",
" return divisors;",
"}",
""
],
"description": "make_divisors"
},
"modpow": {
"prefix": "atcoder_math_modpow",
"body": [
"long long modpow(long long x, long long n, long long MOD) {",
" long long ret = 1;",
" while (n > 0) {",
" if (n & 1) ret = ret * x % MOD; // n の最下位bitが 1 ならば x^(2^i) をかける",
" x = x * x % MOD;",
" n >>= 1; // n を1bit 左にずらす",
" }",
" return ret;",
"}",
""
],
"description": "modpow"
},
//
// graph theory
//
"dijkstra": {
"prefix": "atcoder_graph_dijkstra",
"body": [
"using Edge = pair<ll, int>;",
"using Graph = vector<vector<Edge>>;",
"vector<ll> dijkstra(int st, Graph &g){",
" int N = g.size();",
" vector<ll> dist(N, LINF);",
" dist[st] = 0ll;",
" using P = pair<ll, int>;",
" priority_queue<P, vector<P>, greater<P>> pq;",
" pq.emplace(P{0ll, st});",
" while(!pq.empty()){",
" ll time = pq.top().first;",
" int now = pq.top().second;",
" pq.pop();",
" if (time > dist[now])continue;",
" for(auto e : g[now]){",
" ll c = e.first;",
" int nxt = e.second;",
" if (c + time < dist[nxt]){",
" dist[nxt] = c + time;",
" pq.push(P{c + time, nxt});",
" }",
" }",
" }",
" return dist;",
"}",
""
],
"description": "dijkstra"
},
"bfs": {
"prefix": "atcoder_graph_bfs",
"body": [
"vector<ll> bfs(int st, Graph &g){",
" int N = g.size();",
" queue<int> que;",
" que.push(st);",
" vector<ll> dist(N,LINF);",
" dist[st] = 0;",
" while(!que.empty()){",
" auto now = que.front();que.pop();",
" for(auto nxt : g[now]){",
" if (dist[nxt] != LINF)continue;",
" dist[nxt] = dist[now] + 1;",
" que.push(nxt);",
" }",
" }",
" return dist;",
"}",
""
],
"description": "bfs"
},
"bellman_ford": {
"prefix": "atcoder_graph_bellman_ford",
"body": [
"// https://yukicoder.me/submissions/968942",
"using Edge = tuple<ll, int, int>; // (weight, now, nxt)",
"pair<vector<ll>, vector<ll>> bellman_ford(int V, int st, vector<Edge> &edges){",
" vector<ll> dist(V, LINF), negative(V, false); // negative[i] ... iが負閉路に含まれるならtrue",
" dist[st] = 0;",
" for(int i = 0; i < V - 1; i++){",
" bool update = false;",
" for(auto &e : edges){",
" ll weight;",
" int now, nxt;",
" tie(weight, now, nxt) = e;",
" if(dist[now] != LINF && dist[nxt] > dist[now] + weight){",
" dist[nxt] = dist[now] + weight;",
" update = true;",
" }",
" }",
" if(!update)return make_pair(dist, negative);",
" }",
"",
" for(int i = 0; i < V; i++){",
" for(auto &e : edges){",
" ll weight;",
" int now, nxt;",
" tie(weight, now, nxt) = e;",
" if(dist[now] != LINF && dist[nxt] > dist[now] + weight){",
" dist[nxt] = dist[now] + weight;",
" negative[nxt] = true;",
" }",
" if(negative[now]) negative[nxt] = true;",
" }",
" }",
"",
" return make_pair(dist, negative);",
"}",
""
],
"description": "bellman_ford"
},
"warshall_floyd": {
"prefix": "atcoder_graph_warshall_floyd",
"body": [
"void warshall_floyd(vector<vector<ll>> &dist){",
" int N = dist.size();",
" for(int i=0;i<N;i++) dist[i][i] = 0ll;",
" for(int k=0;k<N;k++){",
" for(int i=0;i<N;i++){",
" for(int j=0;j<N;j++){",
" chmin(dist[i][j], dist[i][k] + dist[k][j]);",
" }",
" }",
" }",
"}",
"// 負閉路はdist[i][i] < 0となるiがあるか",
"// 経路復元...https://zeosutt.hatenablog.com/entry/2015/05/05/045943",
"// prev[i][j]...iからjの最短経路でjの一つ前の点",
"// 初期化:prev[i][j]...i",
"// 更新:prev[i][j] = prev[k][j]",
"// 復元:dijkstraと同じように。now = prev[start][now]で更新",
""
],
"description": "warshall_floyd"
},
"topological_sort": {
"prefix": "atcoder_graph_topological_sort",
"body": [
"vector<int> topological_sort(Graph &g){",
" int N = g.size();",
" vector<int> deg(N);",
" for(int from_=0;from_<N;from_++){",
" for(auto nxt_: g[from_]){",
" deg[nxt_]++;",
" }",
" }",
" queue<int> que;",
" rep(i,N){",
" if (deg[i] == 0) que.push(i);",
" }",
" vector<int> res;",
" while(!que.empty()){",
" auto now = que.front(); que.pop();",
" res.push_back(now);",
" for(auto nxt:g[now]){",
" deg[nxt]--;",
" if (deg[nxt] == 0){",
" que.push(nxt);",
" }",
" }",
" }",
" return res;",
"}",
""
],
"description": "topological_sort"
},
//
// tree algorithm
//
"LCT": {
"prefix": "atcoder_tree_LinkCutTree",
"body": [
"",
"// https://judge.yosupo.jp/submission/206333",
"//【Link-Cut Tree（可換モノイド）】",
"/*",
"* Link_cut_tree<S, op, o>(int n) : O(n)",
"* 値 o() をもった n 頂点で初期化する．",
"* 要素は可換モノイド (S, op, o) の元とする．",
"*",
"* Link_cut_tree<S, op, o>(vS a) : O(n log n)",
"* 値 a[0..n) をもった n 頂点で初期化する．",
"*",
"* cut(int i) : ならし O(log n)",
"* 頂点 i とその親との間の辺を切断する．",
"* 制約：i は根でない．",
"*",
"* cut(int s, int t) : ならし O(log n)",
"* 辺 s-t を切断する（辺がなければ何もしない）",
"*",
"* link(int s, int t) : ならし O(log n)",
"* 頂点 s と根 t に対し，親から子への辺 s→t を繋ぐ．",
"* 制約：t は根である．",
"*",
"* set_root(int rt) : ならし O(log n)",
"* 頂点 rt を根にする．",
"*",
"* S sum(int i) : ならし O(log n)",
"* 根から頂点 i まで（両端含む）の頂点の値の総和を返す．",
"*",
"* set(int i, S x) : ならし O(log n)",
"* 頂点 i の値を x に変更する．",
"*",
"* add(int i, S x) : ならし O(log n)",
"* 頂点 i の値に x を加える．",
"*",
"* bool connectedQ(int s, int t) : ならし O(log n)",
"* 頂点 s, t が連結かを返す．",
"*/",
"template <class S, S(*op)(S, S), S(*o)()>",
"class Link_cut_tree {",
" // 参考 : https://www.slideshare.net/iwiwi/2-12188845",
" // 参考 : https://ei1333.github.io/library/structure/lct/link-cut-tree.hpp.html",
"",
" // splay 木（平衡二分探索木）のノード",
" // key は Link-Cut 木のノードの深さとし，左ほど浅く右ほど深いものとする．",
" struct Node {",
" S val; // 頂点の値",
" S acc; // 部分木のノードの総和",
" bool rev; // 部分木が反転されているか",
" Node* p; // 親へのポインタ（heavy path 内部または外部）",
" Node* l, * r; // 左右の子へのポインタ",
"",
" Node(S val = o()) : val(val), acc(val), rev(false), p(nullptr), l(nullptr), r(nullptr) {}",
"",
" // 自身が根かを返す．",
" bool rootQ() {",
" // 親が設定されていなければもちろん根である．",
" // そうでなくてもそれが heavy path 外部の親であれば自身は根である．",
" return !p || (p->l != this && p->r != this);",
" }",
"",
" // 自身の情報を子の情報をもとにして更新する．",
" void pushup() {",
" acc = op(l ? l->acc : o(), op(val, r ? r->acc : o()));",
" }",
"",
" void pushdown() {",
" // 反転フラグが立っていたら実際に反転しフラグを折る．",
" if (rev) {",
" rev = false;",
" swap(l, r);",
"",
" // 自分の子については反転フラグを flip しておくだけにする．",
" if (l) l->rev = !l->rev;",
" if (r) r->rev = !r->rev;",
" }",
"",
" // 自身の情報（acc）を子の情報をもとにして更新する．",
" pushup();",
" }",
"",
" // 右回転する．",
" void rotR() {",
" Node* my_p = p, * my_pp = my_p->p;",
"",
" // 自分の親と自分の右の子（あれば）を繋ぐ．",
" if (my_p->l = r) r->p = my_p;",
" my_p->pushup();",
"",
" // 自身と自分の親の親子関係を逆転させる．",
" r = my_p; my_p->p = this;",
" pushup();",
"",
" // 自身と自分の親の親（あれば）を繋ぐ．",
" if (p = my_pp) {",
" if (my_pp->l == my_p) my_pp->l = this;",
" if (my_pp->r == my_p) my_pp->r = this;",
" }",
" }",
"",
" // 左回転する．",
" void rotL() {",
" Node* my_p = p, * my_pp = my_p->p;",
"",
" // 自分の親と自分の左の子（あれば）を繋ぐ．",
" if (my_p->r = l) l->p = my_p;",
" my_p->pushup();",
"",
" // 自身と自分の親の親子関係を逆転させる．",
" l = my_p; my_p->p = this;",
" pushup();",
"",
" // 自身と自分の親の親（あれば）を繋ぐ．",
" if (p = my_pp) {",
" if (my_pp->l == my_p) my_pp->l = this;",
" if (my_pp->r == my_p) my_pp->r = this;",
" }",
" }",
"",
" // 自身を heavy path 内の根に持ってくる（スプレー操作）",
" void splay() {",
" pushdown();",
"",
" // 自身が根でないかぎり操作を続ける．",
" while (!rootQ()) {",
" Node* my_p = p;",
"",
" // 自分の親が根である場合",
" if (my_p->rootQ()) {",
" my_p->pushdown();",
" pushdown();",
"",
" // 適切な回転操作を行う．",
" if (my_p->l == this) rotR();",
" else rotL();",
" }",
" // 自分の親が根でない場合",
" else {",
" Node* my_pp = my_p->p;",
" my_pp->pushdown();",
" my_p->pushdown();",
" pushdown();",
"",
" // 自分の親の親から自分まで同方向に枝が伸びている場合は zig-zig ステップ，",
" // さもなくば zig-zag ステップを実行する．",
" if (my_pp->l == my_p) {",
" // zig-zig ステップ",
" if (my_p->l == this) my_p->rotR(), rotR();",
" // zig-zag ステップ",
" else rotL(), rotR();",
" }",
" else {",
" // zig-zig ステップ",
" if (my_p->r == this) my_p->rotL(), rotL();",
" // zig-zag ステップ",
" else rotR(), rotL();",
" }",
" }",
" }",
" }",
" };",
"",
" int n; // 頂点数",
" vector<Node> vs; // 頂点のリスト",
"",
" // 木の根から頂点 v までを 1 つの heavy path にし，v を heavy path 内の根とする．",
" void expose(Node* v) {",
" auto v0(v);",
"",
" // rt : 作成途中の heavy path の根",
" Node* rt = nullptr;",
"",
" while (v) {",
" // v をいまの heavy path 内の根にもってくる．",
" v->splay();",
"",
" // v の右の子を切り離し，作成途中の heavy path を繋ぐ．",
" v->r = rt;",
" rt = v;",
" v->pushup();",
"",
" // 1 つ上の heavy path に移動する．",
" v = v->p;",
" }",
"",
" // v を構築した heavy path 内の根とする．",
" v0->splay();",
" }",
"",
" // 頂点 v とその親との間の辺を切断する．",
" void cut(Node* v) {",
" // 木の根から v までの heavy path を繋ぐ．",
" expose(v);",
"",
" // v の親は v より 1 つ浅いので v の左の子孫になっている．",
" Node* l = v->l;",
"",
" // v とその親の間の辺を切断する．",
" v->l = nullptr;",
" l->p = nullptr;",
"",
" v->pushup();",
" }",
"",
" // 頂点 v, vp を繋ぎ，v の親を vp とする（v は根であること）",
" void link(Node* v, Node* vp) {",
" // それぞれの木の根から v, vp までの heavy path を繋ぐ．",
" expose(v);",
" expose(vp);",
"",
" // vp と v の間の辺を繋ぐ（v の方が深いので v を vp の右の子とする）",
" v->p = vp;",
" vp->r = v;",
"",
" vp->pushup();",
" }",
"",
" // 頂点 v を木の根にする．",
" void evert(Node* v) {",
" expose(v);",
" v->rev = !v->rev;",
" }",
"",
"public:",
" // 値 o() をもった n 頂点で初期化する．",
" Link_cut_tree(int n) : n(n), vs(n) { }",
"",
" // 値 a[0..n) をもった n 頂点で初期化する．",
" Link_cut_tree(const vector<S>& a) : n((int)a.size()), vs(n) {",
" // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum",
"",
" rep(i, n) vs[i].val = vs[i].acc = a[i];",
" }",
"",
" // 頂点 i とその親との間の辺を切断する．",
" void cut(int i) {",
" cut(&vs[i]);",
" }",
"",
" // 辺 s-t を切断する（なければ何もしない）",
" void cut(int s, int t) {",
" // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum",
"",
" if (s == t) return;",
" expose(&vs[s]), expose(&vs[t]);",
" if (!vs[s].p) return;",
"",
" if (vs[t].l == &vs[s]) {",
" Node* l = vs[t].l;",
" vs[t].l = nullptr;",
" l->p = nullptr;",
" vs[t].pushup();",
" }",
" else {",
" expose(&vs[s]);",
" Node* l = vs[s].l;",
" vs[s].l = nullptr;",
" l->p = nullptr;",
" vs[s].pushup();",
" }",
" }",
"",
" // 頂点 s と根 t に対し，親から子への辺 s→t を繋ぐ．",
" void link(int s, int t) {",
" // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum",
"",
" link(&vs[t], &vs[s]);",
" }",
"",
" // 頂点 rt を根にする．",
" void set_root(int rt) {",
" // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum",
"",
" evert(&vs[rt]);",
" }",
"",
" // 根から頂点 i まで（両端含む）の頂点の値の総和を返す．",
" S sum(int i) {",
" // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum",
"",
" expose(&vs[i]);",
" return vs[i].acc;",
" }",
"",
" // 頂点 i の値を x に変更する．",
" void set(int i, S x) {",
" expose(&vs[i]);",
" vs[i].val = x;",
" vs[i].pushup();",
" }",
"",
" // 頂点 i の値に x を加える．",
" void add(int i, S x) {",
" // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum",
"",
" expose(&vs[i]);",
" vs[i].val = op(x, vs[i].val);",
" vs[i].pushup();",
" }",
"",
" // 頂点 s, t が連結かを返す．",
" bool connectedQ(int s, int t) {",
" // verify : https://atcoder.jp/contests/abc350/tasks/abc350_g",
"",
" if (s == t) return true;",
" expose(&vs[s]), expose(&vs[t]);",
" return vs[s].p;",
" }",
"",
"#ifdef _MSC_VER",
" friend ostream& operator<<(ostream& os, Link_cut_tree LCT) {",
" rep(i, LCT.n) {",
" LCT.set_root(i);",
" os << LCT.sum(i) << \" \";",
" }",
" return os;",
" }",
"#endif",
"};"
],
"description": "LCT"
},
"LCA": {
"prefix": "atcoder_tree_LCA",
"body": [
"//https://algo-logic.info/lca/",
"struct LCA{",
" vector<vector<int>> doubling; //doubling[k][u]...頂点uからpow(2,k)遡った頂点番号",
" vector<int> dist; //dist[u]...頂点uからrootまでの距離",
" LCA(const Graph &G , int root = 0){ init(G,root) ;}",
" ",
" void init(const Graph &G , int root = 0){",
" int N = G.size();",
" int logN = 1;",
" while((1<<logN) <= N) logN++;",
" doubling.assign(logN,vector<int>(N,-1));",
" dist.assign(N,-1);;",
" dfs(G,root,-1,0);",
" for (int k=0;k<logN-1;k++){",
" for (int now=0;now<N;now++){",
" if (doubling[k][now] < 0) doubling[k+1][now] = -1;",
" else doubling[k+1][now] = doubling[k][doubling[k][now]];",
" }",
" }",
" }",
" void dfs(const Graph &G, int now, int par , int depth){",
" doubling[0][now] = par;",
" dist[now] = depth;",
" for(auto nxt : G[now]){",
" if (nxt == par) continue;",
" dfs(G,nxt,now,depth+1);",
" }",
" }",
" int query(int u, int v){// 頂点uと頂点vのLCA",
" if (dist[u] < dist[v]) swap(u,v);",
" int logN = doubling.size();",
" //LCAまでの距離を同じにする、O(logN)",
" for (int k=0;k<logN;k++){",
" if ((dist[u] - dist[v]) >> k & 1){",
" u = doubling[k][u];",
" }",
" }",
" if (u == v) return u;",
" for (int k=logN-1;k>=0;k--){",
" if (doubling[k][u] != doubling[k][v]){",
" u = doubling[k][u];",
" v = doubling[k][v];",
" }",
" }",
" return doubling[0][u];",
" }",
" int get_dist(int u,int v){",
" return dist[u] + dist[v] - 2 * dist[query(u,v)];",
" }",
" bool is_on_path(int u,int v, int target){",
" return get_dist(u,v) == get_dist(u,target) + get_dist(target,v);",
" }",
"};"
],
"description": "LCA"
},
"HLD": {
"prefix": "atcoder_tree_hld",
"body": [
"// HL-Decomposition",
"// vid: id of v after HL-Decomposition",
"// inv: inv[vid[v]] = v",
"// par: id of parent",
"// depth",
"// subsize: size of subtree",
"// head: head-id in the heavy-path",
"// prev, next: prev-id, next-id in the heavy-path",
"// type: the id of tree for forest",
"// vend: the last-id of node in v-subtree",
"typedef vector<vector<int> > Graph;",
"struct HLDecomposition {",
" int n;",
" Graph G;",
" vector<int> vid, inv, par, depth, subsize, head, prev, next, type;",
" ",
" // construct",
" HLDecomposition() { }",
" HLDecomposition(const Graph &G_) :",
" n((int)G_.size()), G(G_),",
" vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1),",
" head(n), prev(n, -1), next(n, -1), type(n) { }",
" void build(vector<int> roots = {0}) {",
" int curtype = 0, pos = 0;",
" for (auto r : roots) decide_heavy_edge(r), reconstruct(r, curtype++, pos);",
" }",
" void decide_heavy_edge(int r) {",
" stack<pair<int,int> > st;",
" par[r] = -1, depth[r] = 0;",
" st.emplace(r, 0);",
" while (!st.empty()) {",
" int v = st.top().first;",
" int &i = st.top().second;",
" if (i < (int)G[v].size()) {",
" int e = G[v][i++];",
" if (e == par[v]) continue;",
" par[e] = v, depth[e] = depth[v] + 1;",
" st.emplace(e, 0);",
" }",
" else {",
" st.pop();",
" int maxsize = 0;",
" for (auto e : G[v]) {",
" if (e == par[v]) continue;",
" subsize[v] += subsize[e];",
" if (maxsize < subsize[e]) maxsize = subsize[e], prev[e] = v, next[v] = e;",
" }",
" }",
" }",
" }",
" void reconstruct(int r, int curtype, int &pos) {",
" stack<int> st({r});",
" while (!st.empty()) {",
" int start = st.top(); st.pop();",
" for (int v = start; v != -1; v = next[v]) {",
" type[v] = curtype;",
" vid[v] = pos++;",
" inv[vid[v]] = v;",
" head[v] = start;",
" for (auto e : G[v]) if (e != par[v] && e != next[v]) st.push(e);",
" }",
" }",
" }",
" ",
" // node query [u, v], f([left, right])",
" void foreach_nodes(int u, int v, const function<void(int,int)> &f) {",
" while (true) {",
" if (vid[u] > vid[v]) swap(u, v);",
" f(max(vid[head[v]], vid[u]), vid[v]);",
" if (head[u] != head[v]) v = par[head[v]];",
" else break;",
" }",
" }",
" ",
" // edge query [u, v], f([left, right])",
" void foreach_edges(int u, int v, const function<void(int,int)> &f) {",
" while (true) {",
" if (vid[u] > vid[v]) swap(u, v);",
" if (head[u] != head[v]) {",
" f(vid[head[v]], vid[v]);",
" v = par[head[v]];",
" }",
" else {",
" if (u != v) {",
" f(vid[u]+1, vid[v]);",
" }",
" break;",
" }",
" }",
" }",
"",
" // https://atcoder.jp/contests/abc138/submissions/38833623",
" void subtree_nodes(int v, const function<void(int,int)> &f) {",
" f(vid[v],vid[v]+subsize[v]);",
" }",
"",
" // https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7464630#1",
" void subtree_edges(int v, const function<void(int,int)> &f) {",
" f(vid[v] + 1, vid[v] + subsize[v]);",
" }",
"",
" // LCA",
" int lca(int u, int v) {",
" while (true) {",
" if (vid[u] > vid[v]) swap(u, v);",
" if (head[u] == head[v]) return u;",
" v = par[head[v]];",
" }",
" }",
"};",
"// https://drken1215.hatenablog.com/entry/2018/08/14/193500",
"// HLDecomposition hld(g);",
"// hld.build();",
"//",
"// [path_query]",
"// hld.foreach_nodes(v, u, [&](int l, int r) {seg.apply(l,r+1,x);});",
"// hld.foreach_edges(v, u, [&](int l, int r) {ans += seg.prod(l,r+1,x);}); // range sum",
"// hld.foreach_edges(v, u, [&](int l, int r) {ans = max(ans, seg.prod(l,r+1,x));}); // range max",
"//",
"// [subtree_query]",
"// hld.subtree_nodes(v,[&](int l, int r) {seg.apply(l,r,x);});",
"// hld.subtree_edges(v,[&](int l, int r) {seg.apply(l,r,x);});",
"// ",
"// 頂点iに対応するid -> hld.vid[i]",
"// ex) 頂点iの値を変更 -> seg.set(hld.vid[i], A[i])"
],
"description": "HLD"
},
"rerooting": {
"prefix": "atcoder_tree_rerooting",
"body": [
"template<class E, class V, E (*merge)(E, E), E (*e)(), E (*put_edge)(V, int), V (*put_vertex)(E, int)>",
"struct RerootingDP {",
" struct edge{",
" int from, to, idx, rev_idx;",
" };",
" RerootingDP (int _n = 0) : n(_n) { es.resize(n);}",
" void add_edge(int u, int v, int idx1, int idx2){",
" es[u].push_back({u,v,idx1,idx2});",
" es[v].push_back({v,u,idx2,idx1});",
" }",
" V build(int v = 0){",
" root = v;",
" vis.resize(n,0);",
" outs.resize(n);",
" return dfs(root);",
" }",
" vector<V> reroot(){",
" reverse_edge.resize(n);",
" reverse_edge[root] = e();",
" answers.resize(n);",
" bfs(root);",
" return answers;",
" }",
" private:",
" int n, root;",
" vector<vector<edge>> es;",
" vector<int> vis;",
" vector<vector<E>> outs;",
" vector<E> reverse_edge;",
" vector<V> answers;",
" V dfs(int v){",
" vis[v]++;",
" E val = e();",
" for (auto &p : es[v]){",
" if (vis[p.to] > 0 && p.to != es[v].back().to) swap(p,es[v].back());",
" if (vis[p.to] > 0) continue;",
" E nval = put_edge(dfs(p.to),p.idx);",
" outs[v].emplace_back(nval);",
" val = merge(val,nval);",
" }",
" return put_vertex(val,v);",
" }",
" void bfs(int v){",
" int siz = outs[v].size();",
" vector<E> lui(siz+1), rui(siz+1);",
" lui[0] = e(), rui[siz] = e();",
" for (int i = 0; i < siz; i++) lui[i+1] = merge(lui[i],outs[v][i]);",
" for (int i = siz-1; i >= 0; i--) rui[i] = merge(outs[v][i],rui[i+1]);",
" for (int i = 0; i < siz; i++){",
" reverse_edge[es[v][i].to] = put_edge(put_vertex(merge(merge(lui[i],rui[i+1]),reverse_edge[v]),v),es[v][i].rev_idx);",
" bfs(es[v][i].to);",
" }",
" answers[v] = put_vertex(merge(lui[siz],reverse_edge[v]), v);",
" }",
"};",
"",
"// Education dp subtree",
"// https://atcoder.jp/contests/dp/submissions/37662999",
"using T_monoid = mint; // E",
"using T_DP = mint; // V",
"",
"T_monoid merge(T_monoid a, T_monoid b){",
" return a * b;",
"}",
"T_monoid e(){",
" return mint(1);",
"}",
"T_monoid put_edge(T_DP x, int i){",
" return x + 1;",
"}",
"T_DP put_vertex(T_monoid x, int v){",
" return x;",
"}",
"// 参考",
"// https://trap.jp/post/1702/",
"",
"// https://null-mn.hatenablog.com/entry/2020/04/14/124151 ",
"// fがput_edge, gがput_vertex",
"// 辺の情報が必要なときはedge[i]を作る、また頂点の情報が必要な時はvertex[v]を作る",
""
],
"description": "rerooting"
},
//
// string algorithm
//
"toint": {
"prefix": "atcoder_string_toint",
"body": [
"struct string_converter {",
" char start = 0;",
" char type(const char &c) const { return (islower(c) ? 'a' : isupper(c) ? 'A' : isdigit(c) ? '0' : 0); }",
" int convert(const char &c) {",
" if(!start) start = type(c);",
" return c - start;",
" }",
" int convert(const char &c, const string &chars) { return chars.find(c); }",
" template <typename T> auto convert(const T &v) {",
" vector<decltype(convert(v[0]))> ret;",
" ret.reserve(v.size());",
" for(auto &&e : v) ret.emplace_back(convert(e));",
" return ret;",
" }",
" template <typename T> auto convert(const T &v, const string &chars) {",
" vector<decltype(convert(v[0], chars))> ret;",
" ret.reserve(v.size());",
" for(auto &&e : v) ret.emplace_back(convert(e, chars));",
" return ret;",
" }",
" int operator()(const char &v, char s = 0) {",
" start = s;",
" return convert(v);",
" }",
" int operator()(const char &v, const string &chars) { return convert(v, chars); }",
" template <typename T> auto operator()(const T &v, char s = 0) {",
" start = s;",
" return convert(v);",
" }",
" template <typename T> auto operator()(const T &v, const string &chars) { return convert(v, chars); }",
"} toint;",
"https://twitter.com/noimi_kyopro/status/1613160018769252361",
"// cout << toint('1') << endl; // 1",
"// cout << toint('a') << endl; // 0",
"// cout << toint('A') << endl; // 0",
"// cout << toint('B') << endl; // 1",
"// string MOJI = \"ABC123abc\";",
"// for(auto x:MOJI) cout << toint(x) << endl; // 0 1 2 1 2 3 0 1 2",
"// vector<int> c = toint(MOJI);",
"// for(auto x:c) cout << x << endl; // 0 1 2 -16 -15 -14 32 33 34",
"// cout << toint('#',\"#.\") << endl; // 0",
"// cout << toint('.',\"#.\") << endl; // 1",
""
],
"description": "toint"
},
"rolling_hash": {
"prefix": "atcoder_string_rollinghash",
"body": [
"struct RollingHash{",
" static const int B = 3;",
" long long base[B] = {114514, 1919, 810};",
" long long mod[B] = {1000000007, 1000000009, 998244353};",
"",
" int N;",
" vector<vector<long long>> hash;",
" vector<vector<long long>> pw;",
" RollingHash(string &S){",
" N = S.size();",
" hash.resize(B);",
" pw.resize(B);",
" for(int b = 0; b < B; b++){",
" hash[b].resize(N + 1, 0);",
" pw[b].resize(N + 1, 1);",
"",
" for(int i = 0; i < N; i++){",
" hash[b][i + 1] = (hash[b][i] * base[b] + S[i]) % mod[b];",
" pw[b][i + 1] = pw[b][i] * base[b] % mod[b];",
" }",
" }",
" }",
"",
" vector<long long> get(int l, int r){",
" vector<long long> res(B);",
" for(int b = 0; b < B; b++){",
" res[b] = (hash[b][r] - (hash[b][l] * pw[b][r - l]) % mod[b] + mod[b]) % mod[b];",
" }",
" return res;",
" }",
"",
" int LCP(int l1, int r1, int l2, int r2){",
" // O(log|S|)",
" // return LCP between S[l1, r1) and S[l2, r2)",
" int len = min(r1 - l1, r2 - l2);",
" int ok = -1, ng = len + 1;",
" while(abs(ok - ng) > 1){",
" int mid = (ok + ng) / 2;",
" if (get(l1, l1 + mid) == get(l2, l2 + mid)) ok = mid;",
" else ng = mid;",
" }",
" return ok;",
" }",
"};",
""
],
"description": "rolling_hash"
},
"Trie": {
"prefix": "atcoder_string_trie",
"body": [
"//https://algo-logic.info/trie-tree/",
"/* Trie 木： 文字の種類(char_size)、int型で0に対応する文字(base)",
" insert(word): 単語 word を Trie 木に挿入する",
" search(word): 単語 word が Trie 木にあるか判定する",
" start_with(prefix): prefix が一致する単語が Trie 木にあるか判定する",
" count(): 挿入した単語の数を返す",
" size(): Trie 木の頂点数を返す",
" 計算量：insert, search ともに O(M)（Mは単語の長さ）",
"*/",
"template <int char_size, int base>",
"struct Trie {",
" struct Node { // 頂点を表す構造体",
" vector<int> next; // 子の頂点番号を格納。存在しなければ-1",
" vector<int> accept; // 末端がこの頂点になる単語の word_id を保存",
" int c; // base からの間隔をint型で表現したもの",
" int common; // いくつの単語がこの頂点を共有しているか",
" Node(int c_) : c(c_), common(0) {",
" next.assign(char_size, -1);",
" }",
" };",
"",
" vector<Node> nodes; // trie 木本体",
" int root;",
" Trie() : root(0) {",
" nodes.push_back(Node(root));",
" }",
"",
" // 単語の挿入",
" void insert(const string &word, int word_id) {",
" int node_id = 0;",
" for (int i = 0; i < (int)word.size(); i++) {",
" int c = (int)(word[i] - base);",
" int &next_id = nodes[node_id].next[c];",
" if (next_id == -1) { // 次の頂点が存在しなければ追加",
" next_id = (int)nodes.size();",
" nodes.push_back(Node(c));",
" }",
" ++nodes[node_id].common;",
" node_id = next_id;",
" }",
" ++nodes[node_id].common;",
" nodes[node_id].accept.push_back(word_id);",
" }",
" void insert(const string &word) {",
" insert(word, nodes[0].common);",
" }",
"",
" // 単語とprefixの検索",
" bool search(const string &word, bool prefix = false) {",
" int node_id = 0;",
" for (int i = 0; i < (int)word.size(); i++) {",
" int c = (int)(word[i] - base);",
" int &next_id = nodes[node_id].next[c];",
" if (next_id == -1) { // 次の頂点が存在しなければ終了",
" return false;",
" }",
" node_id = next_id;",
" }",
" return (prefix) ? true : nodes[node_id].accept.size() > 0;",
" }",
"",
" // prefix を持つ単語が存在するかの検索",
" bool start_with(const string &prefix) {",
" return search(prefix, true);",
" }",
"",
" // 挿入した単語の数",
" int count() const {",
" return (nodes[0].common);",
" }",
" // Trie木のノード数 , ただしrootも含む",
" int size() const {",
" return ((int)nodes.size());",
" }",
" ",
" // node_id = tmpの下に文字c(c = 0,1,..25)で終わる文字があるか",
" bool match(int tmp, int c){",
" int nxt_id = nodes[tmp].next[c];",
" return (nxt_id != -1) && (nodes[nxt_id].accept.size() > 0);",
" }",
"};",
"//Trie<26,'a'> trie;",
"",
""
],
"description": "Trie"
},
//
// AHC
//
"ahc_main": {
"prefix": "atcoder_ahc_main",
"body": [
"#include <bits/stdc++.h>",
"#include <atcoder/all>",
"using namespace std;",
"using namespace atcoder;",
"istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }",
"ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }",
"istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }",
"ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }",
"istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }",
"ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); }",
"",
"typedef long long ll;",
"typedef pair<int, int> pii;",
"typedef pair<ll, ll> pll;",
"#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)",
"#define rep(i,n) for (int i = 0;i < (int)(n); i++)",
"#define all(x) x.begin(), x.end()",
"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; }",
"",
"#ifdef LOCAL",
" #include <debug_print.hpp>",
" #define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)",
"#else",
" #define debug(...) (static_cast<void>(0))",
"#endif",
"",
"// https://github.com/thun-c/thunder_library/blob/main/thunder/lib/timer.cpp",
"/// 軽量な実行時間計測器。",
"/// `reset()` で計測開始を更新し、`elapsed()` で経過秒(float)を返す。",
"struct Timer {",
" chrono::steady_clock::time_point t_begin;",
"",
" Timer() { reset(); }",
"",
" /// 計測開始時刻を現在時刻に戻す。",
" void reset() { t_begin = chrono::steady_clock::now(); }",
"",
" /// 計測開始からの経過時間を秒で返す。",
" float elapsed() const {",
" return chrono::duration<float>(chrono::steady_clock::now() - t_begin).count();",
" }",
"} timer;",
"",
"// https://atcoder.jp/contests/ahc063/submissions/74942932",
"struct RNG {",
" uint64_t s[2];",
" RNG(uint64_t seed) { reset(seed); }",
" RNG() { reset(time(0)); }",
" using result_type = uint32_t;",
" static constexpr uint32_t min() { return numeric_limits<uint32_t>::min(); }",
" static constexpr uint32_t max() { return numeric_limits<uint32_t>::max(); }",
" uint32_t operator()() { return randomInt32(); }",
" static inline uint64_t rotl(const uint64_t x, int k) { return (x << k) | (x >> (64 - k)); }",
" inline void reset(uint64_t seed) {",
" struct splitmix64_state {",
" uint64_t s;",
" uint64_t splitmix64() {",
" uint64_t result = (s += 0x9E3779B97f4A7C15);",
" result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;",
" result = (result ^ (result >> 27)) * 0x94D049BB133111EB;",
" return result ^ (result >> 31);",
" }",
" };",
" splitmix64_state sm{seed};",
" s[0] = sm.splitmix64();",
" s[1] = sm.splitmix64();",
" }",
" uint64_t next() {",
" const uint64_t s0 = s[0];",
" uint64_t s1 = s[1];",
" const uint64_t result = rotl(s0 * 5, 7) * 9;",
" s1 ^= s0;",
" s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16);",
" s[1] = rotl(s1, 37);",
" return result;",
" }",
" inline uint32_t randomInt32() { return next(); }",
" inline uint64_t randomInt64() { return next(); }",
" inline uint32_t random32(uint32_t r) { return (((uint64_t)randomInt32()) * r) >> 32; }",
" inline uint64_t random64(uint64_t r) { return randomInt64() % r; }",
" inline uint32_t randomRange32(uint32_t l, uint32_t r) { return l + random32(r - l + 1); }",
" inline uint64_t randomRange64(uint64_t l, uint64_t r) { return l + random64(r - l + 1); }",
" inline double randomDouble() { return (double)randomInt32() / 4294967296.0; }",
" inline double randomDoubleOpen01() { return (randomInt32() + 1.0) / 4294967297.0; }",
" inline float randomFloat() { return (float)randomInt32() / 4294967296.0; }",
" inline double randomRangeDouble(double l, double r) { return l + randomDouble() * (r - l); }",
" inline double randomGaussian(double mean = 0.0, double stddev = 1.0) {",
" double u1 = randomDoubleOpen01();",
" double u2 = randomDouble();",
" double z = sqrt(-2.0 * log(u1)) * cos(2.0 * 3.141592653589793238 * u2);",
" return mean + stddev * z;",
" }",
" template <class T> void shuffle(vector<T>& v) {",
" int sz = v.size();",
" for (int i = sz; i > 1; i--) swap(v[i - 1], v[random32(i)]);",
" }",
" template <class T> void shuffle(T* fr, T* to) {",
" int sz = distance(fr, to);",
" for (int i = sz; i > 1; i--) swap(fr[i - 1], fr[random32(i)]);",
" }",
" template <class T> inline int sample_index(vector<T> const& v) { return random32(v.size()); }",
" template <class T> inline T sample(vector<T> const& v) { return v[sample_index(v)]; }",
"} rng(42);",
"",
"struct Input {",
" void input() {",
" }",
"};",
"",
"struct Solver {",
" const Input& input;",
"",
" explicit Solver(const Input& input) : input(input) {}",
"",
" void solve() {",
" timer.reset();",
" }",
"",
" void print() const {",
" }",
"};",
"",
"int main() {",
" ios::sync_with_stdio(false);",
" cin.tie(nullptr);",
"",
" Input input;",
" input.input();",
"",
" Solver solver(input);",
" solver.solve();",
" solver.print();",
" return 0;",
"}",
""
],
"description": "ahc_main"
},
"fastset": {
"prefix": "atcoder_ahc_fastset",
"body": [
"// 整数集合 [0, n) に対する insert/erase/next/prev が O(log n / log 64) の 64 分木。",
"// std::set<int> より高速。",
"//",
"// Usage:",
"// FastSet fs(N);",
"// fs.insert(i);",
"// fs.erase(i);",
"// fs.contains(i); // O(1)",
"// fs.next(i); // i 以上の最小値。なければ N。",
"// fs.prev(i); // i 以下の最大値。なければ -1。",
"// fs.min_val(); // 最小値",
"// fs.max_val(); // 最大値",
"// fs.empty();",
"struct FastSet {",
" static constexpr int B = 64;",
" int n_, log_;",
" vector<vector<uint64_t>> d_;",
"",
" FastSet() : n_(0), log_(0) {}",
" explicit FastSet(int n) : n_(n), log_(0) {",
" if (n == 0) return;",
" int m = n;",
" do {",
" d_.push_back(vector<uint64_t>((m + B - 1) / B, 0));",
" m = (m + B - 1) / B;",
" } while (m > 1);",
" log_ = (int)d_.size();",
" }",
"",
" void insert(int i) {",
" for (int h = 0; h < log_; h++) {",
" d_[h][i / B] |= 1ULL << (i % B);",
" i /= B;",
" }",
" }",
"",
" void erase(int i) {",
" for (int h = 0; h < log_; h++) {",
" d_[h][i / B] &= ~(1ULL << (i % B));",
" if (d_[h][i / B]) break;",
" i /= B;",
" }",
" }",
"",
" bool contains(int i) const { return (d_[0][i / B] >> (i % B)) & 1; }",
" bool empty() const { return d_[log_ - 1][0] == 0; }",
"",
" // i 以上の最小値。なければ n_ を返す。",
" int next(int i) const {",
" for (int h = 0; h < log_; h++) {",
" int b = i / B;",
" if (b >= (int)d_[h].size()) break;",
" uint64_t f = d_[h][b] >> (i % B);",
" if (!f) { i = b + 1; continue; }",
" i += __builtin_ctzll(f);",
" for (int g = h - 1; g >= 0; g--)",
" i = i * B + __builtin_ctzll(d_[g][i]);",
" return i;",
" }",
" return n_;",
" }",
"",
" // i 以下の最大値。なければ -1 を返す。",
" int prev(int i) const {",
" for (int h = 0; h < log_; h++) {",
" if (i < 0) break;",
" int b = i / B;",
" uint64_t f = d_[h][b] << (B - 1 - i % B);",
" if (!f) { i = b - 1; continue; }",
" i -= __builtin_clzll(f);",
" for (int g = h - 1; g >= 0; g--)",
" i = i * B + 63 - __builtin_clzll(d_[g][i]);",
" return i;",
" }",
" return -1;",
" }",
"",
" int min_val() const { return next(0); }",
" int max_val() const { return prev(n_ - 1); }",
"};"
],
"description": "fastset"
},
"hashmap": {
"prefix": "atcoder_ahc_hashmap",
"body": [
"// open addressing, linear probing。unordered_map より高速。",
"// Key にはハッシュ適用済みの値を渡す。n は格納要素数の 16 倍程度。",
"// clear() は O(1)（stamp インクリメントのみ）。",
"//",
"// Usage:",
"// HashMap<uint64_t, int> seen(beam_width * 16);",
"// auto [exists, idx] = seen.get_index(hash);",
"// if (!exists) seen.set(idx, hash, node_id);",
"// int v = seen.get(idx);",
"// seen.clear(); // 次ターンへ O(1)",
"template<class Key, class T>",
"struct HashMap {",
" uint32_t n_;",
" uint32_t current_stamp_ = 1;",
" vector<uint32_t> stamp_;",
" vector<pair<Key, T>> data_;",
"",
" explicit HashMap(uint32_t n) {",
" if (n % 2 == 0) ++n;",
" n_ = n;",
" stamp_.assign(n_, 0);",
" data_.resize(n_);",
" }",
"",
" // {存在するか, index} を返す。set/get には index を使う。",
" pair<bool, int> get_index(Key key) const {",
" uint32_t i = (uint32_t)(key % n_);",
" while (stamp_[i] == current_stamp_) {",
" if (data_[i].first == key) return {true, (int)i};",
" if (++i == n_) i = 0;",
" }",
" return {false, (int)i};",
" }",
"",
" void set(int i, Key key, T value) {",
" stamp_[i] = current_stamp_;",
" data_[i] = {key, value};",
" }",
"",
" T get(int i) const { return data_[i].second; }",
"",
" void clear() {",
" if (++current_stamp_ == 0) {",
" fill(stamp_.begin(), stamp_.end(), 0);",
" current_stamp_ = 1;",
" }",
" }",
"};"
],
"description": "hashmap"
},
"conntable": {
"prefix": "atcoder_ahc_conntable",
"body": [
"// 3x3 局所連結性テーブル。8近傍ビットマスク（256通り）の連結成分数を事前計算。",
"// conn8=true で8連結（斜め隣接あり）、false で4連結（上下左右のみ）。",
"//",
"// 近傍ビット配置:",
"// 0 1 2",
"// 3 C 4",
"// 5 6 7",
"//",
"// Usage:",
"// ConnTable<> ct; // 8連結（デフォルト）",
"// ConnTable<false> ct; // 4連結",
"// uint8_t mask = ct.neighbors(grid, r, c, H, W); // grid[r][c] が 0/1 の2次元配列",
"// int comp = ct.components(mask); // 中心セルを除いた連結成分数",
"// bool safe = ct.can_remove(mask); // 削除しても連結性が保たれるか",
"//",
"// // 典型: セル(r,c)を安全に削除できるか確認して消す",
"// if (ct.can_remove(ct.neighbors(grid, r, c, H, W))) grid[r][c] = 0;",
"template<bool conn8 = true>",
"struct ConnTable {",
" uint8_t table[256];",
"",
" ConnTable() {",
" for (int mask = 0; mask < 256; mask++)",
" table[mask] = count_components(mask);",
" }",
"",
" int components(uint8_t mask) const { return table[mask]; }",
" bool can_remove(uint8_t mask) const { return table[mask] <= 1; }",
"",
" template<class Grid>",
" uint8_t neighbors(const Grid& grid, int r, int c, int H, int W) const {",
" static const int dr[] = {-1,-1,-1, 0, 0, 1, 1, 1};",
" static const int dc[] = {-1, 0, 1,-1, 1,-1, 0, 1};",
" uint8_t mask = 0;",
" for (int k = 0; k < 8; k++) {",
" int nr = r + dr[k], nc = c + dc[k];",
" if (nr >= 0 && nr < H && nc >= 0 && nc < W && grid[nr][nc])",
" mask |= 1 << k;",
" }",
" return mask;",
" }",
"",
"private:",
" static int count_components(int mask) {",
" static const int adj8[8][4] = {",
" {1, 3, -1, -1}, // 0",
" {0, 2, 3, 4}, // 1",
" {1, 4, -1, -1}, // 2",
" {0, 1, 5, 6}, // 3",
" {1, 2, 6, 7}, // 4",
" {3, 6, -1, -1}, // 5",
" {3, 4, 5, 7}, // 6",
" {4, 6, -1, -1}, // 7",
" };",
" static const int adj4[8][4] = {",
" {1, 3, -1, -1}, // 0",
" {0, 2, -1, -1}, // 1",
" {1, 4, -1, -1}, // 2",
" {0, 5, -1, -1}, // 3",
" {2, 7, -1, -1}, // 4",
" {3, 6, -1, -1}, // 5",
" {5, 7, -1, -1}, // 6",
" {4, 6, -1, -1}, // 7",
" };",
" const auto& adj = conn8 ? adj8 : adj4;",
" int comp = 0;",
" uint8_t visited = 0;",
" for (int i = 0; i < 8; i++) {",
" if (!((mask >> i) & 1) || (visited >> i) & 1) continue;",
" comp++;",
" uint8_t stk = 1 << i;",
" visited |= 1 << i;",
" while (stk) {",
" int u = __builtin_ctz(stk);",
" stk &= stk - 1;",
" for (int k = 0; k < 4 && adj[u][k] != -1; k++) {",
" int v = adj[u][k];",
" if (((mask >> v) & 1) && !((visited >> v) & 1)) {",
" visited |= 1 << v;",
" stk |= 1 << v;",
" }",
" }",
" }",
" }",
" return comp;",
" }",
"};",
"ConnTable<> conn_table; // 8連結。4連結が必要なら ConnTable<false> を別途宣言。",
""
],
"description": "conntable"
},
"dial": {
"prefix": "atcoder_ahc_dial",
"body": [
"// Dial's アルゴリズム（バケットキュー）。辺コストが小さい整数のとき priority_queue より高速。",
"// 時間計算量: O(V + E + max_dist)、空間計算量: O(V + E + max_cost)",
"// max_cost = 最大辺コスト（BFS なら 1）",
"// max_dist = 探索する最大距離（省略時は全到達頂点を探索）",
"//",
"// Usage:",
"// vector<vector<pair<int,int>>> adj(N); // adj[v] = {{neighbor, weight}, ...}",
"// auto dist = dial(start, N, adj, 1); // BFS: 全頂点",
"// auto dist = dial(start, N, adj, max_cost); // 全頂点",
"// auto dist = dial(start, N, adj, max_cost, max_dist); // 距離 max_dist 以内",
"vector<int> dial(int start, int n,",
" const vector<vector<pair<int,int>>>& adj, int max_cost, int max_dist = -1) {",
" const int D = max_cost + 1;",
" vector<int> dist(n, INT_MAX);",
" vector<vector<int>> bucket(D);",
" dist[start] = 0;",
" bucket[0].push_back(start);",
" int pending = 1;",
" for (int d = 0; pending > 0; d++) {",
" int bi = d % D;",
" pending -= (int)bucket[bi].size();",
" for (int v : bucket[bi]) {",
" if (dist[v] != d) continue;",
" for (auto [u, w] : adj[v]) {",
" if (dist[v] + w < dist[u]) {",
" dist[u] = dist[v] + w;",
" if (max_dist < 0 || dist[u] <= max_dist) {",
" bucket[dist[u] % D].push_back(u);",
" pending++;",
" }",
" }",
" }",
" }",
" bucket[bi].clear();",
" }",
" return dist;",
"}",
""
],
"description": "dial"
},
"sa": {
"prefix": "atcoder_ahc_sa",
"body": [
"// 焼きなまし法（Simulated Annealing）",
"//",
"// Usage:",
"// SA<ll> sa(start_temp, end_temp, time_limit); // スコアの型を指定",
"//",
"// // 基本パターン",
"// while (timer.elapsed() < time_limit) {",
"// double temp = sa.temperature(); // 温度を1回だけ取得",
"// ll diff = new_score - cur_score; // diff > 0 が悪化（コスト最小化）",
"// if (sa.accept(diff, temp)) { /* 採用 */ }",
"// }",
"//",
"// // 受理ライン（スコア計算を途中打ち切りするとき）",
"// double temp = sa.temperature();",
"// ll line = sa.threshold(temp); // 先に受理ラインを確定",
"// ll new_score = 0;",
"// for (int i = 0; i < N; i++) {",
"// new_score += calc_partial(i);",
"// if (new_score - cur_score > line) break; // 越えると確定したら打ち切り",
"// }",
"// if (new_score - cur_score <= line) { /* 採用 */ }",
"//",
"// // 温度スケジュール",
"// sa.temperature(); // 指数（デフォルト）: 序盤に広く探索",
"// sa.temperature_linear(); // 線形: シンプル",
"template<class T = double>",
"struct SA {",
" double start_temp, end_temp, time_limit;",
"",
" // -log(U), U~Uniform(0,1) のルックアップテーブル（分位点中点法）",
" struct MinusLogTable {",
" static constexpr int SIZE = 1 << 12;",
" double table[SIZE];",
" MinusLogTable() {",
" for (int i = 0; i < SIZE; i++)",
" table[i] = -log((i + 0.5) / SIZE);",
" }",
" double operator()() const {",
" return table[rng.random32(SIZE)];",
" }",
" } minus_log_table;",
"",
" // 指数温度スケジュールのルックアップテーブル（構築時に事前計算）",
" struct TempTable {",
" static constexpr int SIZE = 1 << 12;",
" double table[SIZE];",
" void init(double start_temp, double end_temp) {",
" for (int i = 0; i < SIZE; i++)",
" table[i] = start_temp * pow(end_temp / start_temp, (i + 0.5) / SIZE);",
" }",
" double operator()(double ratio) const {",
" return table[min(SIZE - 1, (int)(ratio * SIZE))];",
" }",
" } temp_table;",
"",
" SA(double start_temp, double end_temp, double time_limit)",
" : start_temp(start_temp), end_temp(end_temp), time_limit(time_limit) {",
" temp_table.init(start_temp, end_temp);",
" }",
"",
" double ratio() const {",
" return min(1.0, (double)timer.elapsed() / time_limit);",
" }",
"",
" double temperature() const {",
" return temp_table(ratio());",
" }",
" double temperature_linear() const {",
" return start_temp + (end_temp - start_temp) * ratio();",
" }",
"",
" // diff <= threshold(temp) なら受理。先に1回呼んで途中打ち切りに使う。",
" T threshold(double temp) const { return static_cast<T>(temp * minus_log_table()); }",
" T threshold() const { return threshold(temperature()); }",
"",
" // diff > 0 が悪化（コスト最小化）。threshold() と数学的に等価。",
" bool accept(T diff, double temp) const {",
" if (diff <= 0) return true;",
" return diff <= threshold(temp);",
" }",
" bool accept(T diff) const {",
" if (diff <= 0) return true;",
" return diff <= threshold(temperature());",
" }",
"};"
],
"description": "sa"
},
"Bayes": {
"prefix": "atcoder_ahc_Bayes",
"body": [
"// 離散ベイズ推定器。状態 0..N-1 の事後分布を log 空間で管理する。",
"// likelihood[i] = P(obs | state=i) の計算は問題依存（ノイズモデルから導く）。",
"//",
"// Usage:",
"// BayesEstimator be(N); // 一様事前分布",
"// BayesEstimator be(prior); // カスタム事前分布 prior[i] = P(state=i)",
"// be.update(likelihood); // likelihood[i] = P(obs | state=i)",
"// be.update_log(log_likelihood); // log尤度を直接渡す版（高速）",
"// double p = be.prob(i); // P(state=i | 全観測)",
"// int s = be.argmax(); // 最大事後確率の状態",
"// vector<double> ps = be.probs(); // 全確率を vector で取得",
"//",
"// 典型的な log 尤度の計算例（update_log に渡す）:",
"// // ガウスノイズ: クエリに正規分布ノイズが乗る場合",
"// for (int i = 0; i < N; i++) log_lik[i] = -(obs-expected[i])*(obs-expected[i]) / (2*sigma*sigma);",
"//",
"// // 二値ノイズ: 正解率 p で正しい答えが返ってくる場合",
"// for (int i = 0; i < N; i++) log_lik[i] = log(obs == true_val[i] ? p : 1.0-p);",
"struct BayesEstimator {",
" int n;",
" vector<double> log_prob;",
"",
" explicit BayesEstimator(int n) : n(n), log_prob(n, -log((double)n)) {}",
" explicit BayesEstimator(vector<double> prior) : n(prior.size()), log_prob(prior.size()) {",
" for (int i = 0; i < n; i++) log_prob[i] = log(prior[i]);",
" normalize();",
" }",
"",
" void update(const vector<double>& likelihood) {",
" for (int i = 0; i < n; i++) log_prob[i] += log(likelihood[i]);",
" normalize();",
" }",
" void update_log(const vector<double>& log_likelihood) {",
" for (int i = 0; i < n; i++) log_prob[i] += log_likelihood[i];",
" normalize();",
" }",
"",
" void normalize() {",
" double mx = *max_element(log_prob.begin(), log_prob.end());",
" double s = 0;",
" for (int i = 0; i < n; i++) s += exp(log_prob[i] - mx);",
" double log_s = mx + log(s);",
" for (int i = 0; i < n; i++) log_prob[i] -= log_s;",
" }",
"",
" double prob(int i) const { return exp(log_prob[i]); }",
" int argmax() const { return max_element(log_prob.begin(), log_prob.end()) - log_prob.begin(); }",
" vector<double> probs() const {",
" vector<double> p(n);",
" for (int i = 0; i < n; i++) p[i] = prob(i);",
" return p;",
" }",
"};"
],
"description": "Bayes"
},
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)
#define rep(i,n) for (int i = 0;i < (int)(n); i++)
#define all(x) x.begin(), x.end()
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; }
#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif
// 軽量な実行時間計測器。グローバルに timer が1つある。
// 時計を間引いて読むかは呼び出し側で決める。
//
// Usage:
// timer.reset(); // 計測開始時刻を現在時刻に戻す
// float t = timer.elapsed(); // 計測開始からの経過時間を秒で返す
//
// // 基本パターン
// while (timer.elapsed() < time_limit) { ... }
//
// // 時計の読み取りを間引く（近傍が軽くて秒間数百万回まわるとき）
// if (cnt % 64 == 0 && timer.elapsed() >= time_limit) break;
struct Timer {
Timer() { reset(); }
void reset() { t_begin = chrono::steady_clock::now(); }
float elapsed() const {
return chrono::duration<float>(chrono::steady_clock::now() - t_begin).count();
}
private:
chrono::steady_clock::time_point t_begin;
} timer;
// xoroshiro128**。グローバルに rng が1つある（シード 345）。
// result_type / min() / max() / operator() を持つので、std の分布
// (uniform_int_distribution など) の engine としてもそのまま渡せる。
//
// Usage:
// RNG my_rng(123); // シードを指定して作る
// rng.reset(42); // シードを再設定する
//
// // 整数
// uint32_t a = rng(); // 32bit 乱数。std の分布に渡す engine 用
// uint32_t b = rng.random32(n); // [0, n) の整数。n > 0
// uint64_t c = rng.random64(n); // [0, n) の整数（64bit）。n > 0
// uint32_t d = rng.randomRange32(l, r); // [l, r] の整数。両端を含む。l <= r
// uint64_t e = rng.randomRange64(l, r); // [l, r] の整数（64bit）。両端を含む
//
// // 実数
// double p = rng.randomDouble(); // [0, 1) の実数
// float q = rng.randomFloat(); // [0, 1) の実数（float）
// double x = rng.randomRangeDouble(l, r); // [l, r) の実数
// double g = rng.randomGaussian(mean, stddev); // 正規分布 N(mean, stddev^2)。既定は N(0, 1)
//
// // コンテナ
// rng.shuffle(v); // vector をシャッフルする
// rng.shuffle(a, a + n); // [fr, to) をシャッフルする
// int i = rng.sample_index(v); // 添字を一様に選ぶ。v は非空
// auto y = rng.sample(v); // 要素を一様に選ぶ。v は非空
struct RNG {
using result_type = uint32_t;
static constexpr uint32_t min() { return 0; }
static constexpr uint32_t max() { return numeric_limits<uint32_t>::max(); }
RNG(uint64_t seed) { reset(seed); }
RNG() { reset(time(0)); }
void reset(uint64_t seed) {
struct splitmix64_state {
uint64_t s;
uint64_t splitmix64() {
uint64_t result = (s += 0x9E3779B97f4A7C15);
result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
return result ^ (result >> 31);
}
};
splitmix64_state sm{seed};
s[0] = sm.splitmix64();
s[1] = sm.splitmix64();
}
uint32_t operator()() { return next32(); }
uint32_t random32(uint32_t r) { return (uint64_t(next32()) * r) >> 32; }
uint64_t random64(uint64_t r) { return uint64_t((__uint128_t(next64()) * r) >> 64); }
uint32_t randomRange32(uint32_t l, uint32_t r) { return l + random32(r - l + 1); }
uint64_t randomRange64(uint64_t l, uint64_t r) { return l + random64(r - l + 1); }
double randomDouble() { return double(next32()) / 4294967296.0; }
float randomFloat() { return float(next32()) / 4294967296.0f; }
double randomRangeDouble(double l, double r) { return l + randomDouble() * (r - l); }
double randomGaussian(double mean = 0.0, double stddev = 1.0) {
double u1 = (next32() + 1.0) / 4294967297.0;
double u2 = randomDouble();
return mean + stddev * sqrt(-2.0 * log(u1)) * cos(2.0 * 3.141592653589793238 * u2);
}
template <class T> void shuffle(vector<T>& v) {
for (int i = (int)v.size(); i > 1; i--) swap(v[i - 1], v[random32(i)]);
}
template <class T> void shuffle(T* fr, T* to) {
int sz = (int)distance(fr, to);
for (int i = sz; i > 1; i--) swap(fr[i - 1], fr[random32(i)]);
}
template <class T> int sample_index(const vector<T>& v) { return random32((uint32_t)v.size()); }
template <class T> T sample(const vector<T>& v) { return v[sample_index(v)]; }
private:
uint64_t s[2];
static uint64_t rotl(uint64_t x, int k) { return (x << k) | (x >> (64 - k)); }
uint64_t next64() {
const uint64_t s0 = s[0];
uint64_t s1 = s[1];
const uint64_t result = rotl(s0 * 5, 7) * 9;
s1 ^= s0;
s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16);
s[1] = rotl(s1, 37);
return result;
}
uint32_t next32() { return (uint32_t)next64(); }
} rng(345);
// 焼きなまし法（Simulated Annealing）。スコアの型 T を指定する。
// コスト最小化。スコア最大化のときは accept(cur - neu, temp) と符号を反転させる。
// end_temp は正であること（指数スケジュールの pow のため）。
// 構築時に開始時刻を1回記録する。進捗は (now - 開始) / (end_time - 開始)。
// end_time は timer.elapsed() と同じ時計での終了時刻。温度の間引きは Solver 側で行う。
//
// Usage:
// SA<ll> sa(start_temp, end_temp, end_time); // 例: end_time = 2.85
//
// double t1 = sa.temperature(); // 指数スケジュールの温度。序盤に広く探索する
// double t2 = sa.temperature_linear(); // 線形スケジュールの温度
// ll line = sa.threshold(temp); // 受理ライン。diff <= line なら受理
// bool ok = sa.accept(diff, temp); // diff > 0 が悪化。温度は呼び出し側で1回取って渡す
//
// // 基本パターン
// while (timer.elapsed() < end_time) {
// double temp = sa.temperature(); // 温度は1回だけ取る
// ll diff = new_score - cur_score; // diff > 0 が悪化
// if (sa.accept(diff, temp)) { /* 採用 */ }
// }
//
// // 受理ライン（スコア計算を途中打ち切りするとき）
// double temp = sa.temperature();
// ll line = sa.threshold(temp); // 先に受理ラインを確定させる
// ll new_score = 0;
// for (int i = 0; i < N; i++) {
// new_score += calc_partial(i);
// if (new_score - cur_score > line) break; // 越えると確定したら打ち切る
// }
// if (new_score - cur_score <= line) { /* 採用 */ }
template<class T = double>
struct SA {
double start_temp, end_temp, end_time;
SA(double start_temp, double end_temp, double end_time)
: start_temp(start_temp), end_temp(end_temp), end_time(end_time),
t_begin(timer.elapsed()) {
for (int i = 0; i < TABLE_SIZE; i++) {
minus_log_table[i] = -log((i + 0.5) / TABLE_SIZE);
temp_table[i] = start_temp * pow(end_temp / start_temp, (i + 0.5) / TABLE_SIZE);
}
}
double temperature() const {
return temp_table[min(TABLE_SIZE - 1, (int)(ratio() * TABLE_SIZE))];
}
double temperature_linear() const {
return start_temp + (end_temp - start_temp) * ratio();
}
T threshold(double temp) const {
return static_cast<T>(temp * minus_log_table[rng.random32(TABLE_SIZE)]);
}
bool accept(T diff, double temp) const {
if (diff <= 0) return true;
return diff <= threshold(temp);
}
private:
static constexpr int TABLE_SIZE = 1 << 12;
double minus_log_table[TABLE_SIZE];
double temp_table[TABLE_SIZE];
double t_begin;
double ratio() const {
double dur = end_time - t_begin;
if (dur <= 0) return 1.0;
return min(1.0, (timer.elapsed() - t_begin) / dur);
}
};
// open addressing, linear probing。unordered_map より高速。
// Key にはハッシュ適用済みの値を渡す。
//
// Usage:
// HashMap<uint64_t, int> seen(beam_width * 16); // n は格納要素数の 16 倍程度
//
// auto [exists, idx] = seen.get_index(hash); // {存在するか, slot}。set/get には slot を渡す
// seen.set(idx, hash, node_id); // slot に (key, value) を書く
// int v = seen.get(idx); // slot の値を返す
// seen.clear(); // 中身を捨てる。O(1)
//
// // 基本パターン（ビームサーチの重複除去）
// auto [exists, idx] = seen.get_index(hash);
// if (!exists) seen.set(idx, hash, node_id);
// seen.clear(); // 次ターンへ
template<class Key, class T>
struct HashMap {
explicit HashMap(uint32_t n) {
if (n % 2 == 0) ++n;
n_ = n;
stamp_.assign(n_, 0);
data_.resize(n_);
}
pair<bool, int> get_index(Key key) const {
uint32_t i = (uint32_t)(key % n_);
uint32_t start = i;
while (stamp_[i] == current_stamp_) {
if (data_[i].first == key) return {true, (int)i};
if (++i == n_) i = 0;
if (i == start) return {false, (int)i};
}
return {false, (int)i};
}
void set(int i, Key key, T value) {
stamp_[i] = current_stamp_;
data_[i] = {key, value};
}
T get(int i) const { return data_[i].second; }
void clear() {
if (++current_stamp_ == 0) {
fill(stamp_.begin(), stamp_.end(), 0);
current_stamp_ = 1;
}
}
private:
uint32_t n_;
uint32_t current_stamp_ = 1;
vector<uint32_t> stamp_;
vector<pair<Key, T>> data_;
};
// 整数集合 [0, n) に対する insert / erase / next / prev が O(log n / log 64) の 64 分木。
// std::set<int> より高速。
//
// Usage:
// FastSet fs(N); // 宇宙 [0, N) の空集合を作る
//
// fs.insert(i); // i を追加する
// fs.erase(i); // i を削除する
// bool b = fs.contains(i); // i が含まれるか。O(1)
// bool e = fs.empty(); // 空なら true
// int x = fs.next(i); // i 以上の最小値。なければ N
// int y = fs.prev(i); // i 以下の最大値。なければ -1
// int mn = fs.min_val(); // 最小値。空なら N
// int mx = fs.max_val(); // 最大値。空なら -1
//
// // 基本パターン（残っている要素を昇順に舐める）
// for (int i = fs.min_val(); i < N; i = fs.next(i + 1)) { ... }
struct FastSet {
FastSet() : n_(0), log_(0) {}
explicit FastSet(int n) : n_(n), log_(0) {
if (n == 0) return;
int m = n;
do {
d_.push_back(vector<uint64_t>((m + B - 1) / B, 0));
m = (m + B - 1) / B;
} while (m > 1);
log_ = (int)d_.size();
}
void insert(int i) {
for (int h = 0; h < log_; h++) {
d_[h][i / B] |= 1ULL << (i % B);
i /= B;
}
}
void erase(int i) {
for (int h = 0; h < log_; h++) {
d_[h][i / B] &= ~(1ULL << (i % B));
if (d_[h][i / B]) break;
i /= B;
}
}
bool contains(int i) const {
if (log_ == 0) return false;
return (d_[0][i / B] >> (i % B)) & 1;
}
bool empty() const { return log_ == 0 || d_[log_ - 1][0] == 0; }
int next(int i) const {
for (int h = 0; h < log_; h++) {
int b = i / B;
if (b >= (int)d_[h].size()) break;
uint64_t f = d_[h][b] >> (i % B);
if (!f) { i = b + 1; continue; }
i += __builtin_ctzll(f);
for (int g = h - 1; g >= 0; g--)
i = i * B + __builtin_ctzll(d_[g][i]);
return i;
}
return n_;
}
int prev(int i) const {
for (int h = 0; h < log_; h++) {
if (i < 0) break;
int b = i / B;
uint64_t f = d_[h][b] << (B - 1 - i % B);
if (!f) { i = b - 1; continue; }
i -= __builtin_clzll(f);
for (int g = h - 1; g >= 0; g--)
i = i * B + 63 - __builtin_clzll(d_[g][i]);
return i;
}
return -1;
}
int min_val() const { return next(0); }
int max_val() const { return prev(n_ - 1); }
private:
static constexpr int B = 64;
int n_, log_;
vector<vector<uint64_t>> d_;
};
// 3x3 局所連結性。あるマスを消したとき、周囲の物体が分裂するかを判定する。
//
// 見ているもの:
// 中心 C は見ない。周囲 8 マスだけを「物体 / 空」に分け、C を除いたあとの
// 連結成分数が 2 以上なら分裂（消せない）。0 または 1 ならつながったまま（消せる）。
//
// 0 1 2
// 3 C 4
// 5 6 7
//
// 引数:
// grid : 2次元配列。grid[row][col] が真なら物体、偽なら空。
// 0/1 の int、bool など、if (grid[r][c]) が使える型なら何でもよい。
// 盤のサイズは grid.size() と grid[0].size() から取る。
// r, c : 消したいマス（0-index）。このマス自身の値は使わない。
//
// conn8=true : 斜めもつながる（8連結）
// conn8=false : 上下左右だけ（4連結）
//
// Usage:
// ConnTable<> conn_table; // 8連結（グローバルに1つ用意してある）
// ConnTable<false> conn4; // 4連結
//
// bool ok = conn_table.can_remove(grid, r, c); // (r,c) を消しても分裂しないなら true
//
// // 基本パターン
// if (conn_table.can_remove(grid, r, c)) grid[r][c] = 0;
template<bool conn8 = true>
struct ConnTable {
ConnTable() {
for (int mask = 0; mask < 256; mask++) table[mask] = count_components(mask);
}
template<class Grid>
bool can_remove(const Grid& grid, int r, int c) const {
int H = (int)grid.size();
int W = H ? (int)grid[0].size() : 0;
return table[neighbors(grid, r, c, H, W)] <= 1;
}
private:
uint8_t table[256];
template<class Grid>
uint8_t neighbors(const Grid& grid, int r, int c, int H, int W) const {
static const int dr[] = {-1,-1,-1, 0, 0, 1, 1, 1};
static const int dc[] = {-1, 0, 1,-1, 1,-1, 0, 1};
uint8_t mask = 0;
for (int k = 0; k < 8; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < H && nc >= 0 && nc < W && grid[nr][nc])
mask |= 1 << k;
}
return mask;
}
static int count_components(int mask) {
static const int adj8[8][4] = {
{1, 3, -1, -1}, {0, 2, 3, 4}, {1, 4, -1, -1}, {0, 1, 5, 6},
{1, 2, 6, 7}, {3, 6, -1, -1}, {3, 4, 5, 7}, {4, 6, -1, -1},
};
static const int adj4[8][4] = {
{1, 3, -1, -1}, {0, 2, -1, -1}, {1, 4, -1, -1}, {0, 5, -1, -1},
{2, 7, -1, -1}, {3, 6, -1, -1}, {5, 7, -1, -1}, {4, 6, -1, -1},
};
const auto& adj = conn8 ? adj8 : adj4;
int comp = 0;
uint8_t visited = 0;
for (int i = 0; i < 8; i++) {
if (!((mask >> i) & 1) || (visited >> i) & 1) continue;
comp++;
uint8_t stk = 1 << i;
visited |= 1 << i;
while (stk) {
int u = __builtin_ctz(stk);
stk &= stk - 1;
for (int k = 0; k < 4 && adj[u][k] != -1; k++) {
int v = adj[u][k];
if (((mask >> v) & 1) && !((visited >> v) & 1)) {
visited |= 1 << v;
stk |= 1 << v;
}
}
}
}
return comp;
}
};
ConnTable<> conn_table; // 8連結。4連結が必要なら ConnTable<false> を別途宣言する。
// 離散ベイズ推定器。状態 0..n-1 の事後分布を log 空間で管理する。
// likelihood[i] = P(obs | state=i) の計算は問題依存（ノイズモデルから導く）。
//
// Usage:
// BayesEstimator be(N); // 一様事前分布
// BayesEstimator be(prior); // カスタム事前分布 prior[i] = P(state=i)
// be.update(likelihood); // likelihood[i] = P(obs | state=i)
// be.update_log(log_likelihood); // log 尤度を直接渡す版
// double p = be.prob(i); // P(state=i | 全観測)
// int s = be.argmax(); // 最大事後確率の状態
// vector<double> ps = be.probs(); // 全確率を vector で返す
//
// 典型的な log 尤度（update_log に渡す）:
// // ガウスノイズ
// for (int i = 0; i < N; i++) log_lik[i] = -(obs-expected[i])*(obs-expected[i]) / (2*sigma*sigma);
// // 二値ノイズ（正解率 p）
// for (int i = 0; i < N; i++) log_lik[i] = log(obs == true_val[i] ? p : 1.0-p);
struct BayesEstimator {
explicit BayesEstimator(int n) : n(n), log_prob(n, -log((double)n)) {}
explicit BayesEstimator(vector<double> prior)
: n((int)prior.size()), log_prob(prior.size()) {
for (int i = 0; i < n; i++) log_prob[i] = log(prior[i]);
normalize();
}
void update(const vector<double>& likelihood) {
for (int i = 0; i < n; i++) log_prob[i] += log(likelihood[i]);
normalize();
}
void update_log(const vector<double>& log_likelihood) {
for (int i = 0; i < n; i++) log_prob[i] += log_likelihood[i];
normalize();
}
double prob(int i) const { return exp(log_prob[i]); }
int argmax() const { return int(max_element(log_prob.begin(), log_prob.end()) - log_prob.begin()); }
vector<double> probs() const {
vector<double> p(n);
for (int i = 0; i < n; i++) p[i] = prob(i);
return p;
}
private:
int n;
vector<double> log_prob;
void normalize() {
double mx = *max_element(log_prob.begin(), log_prob.end());
double s = 0;
for (int i = 0; i < n; i++) s += exp(log_prob[i] - mx);
double log_s = mx + log(s);
for (int i = 0; i < n; i++) log_prob[i] -= log_s;
}
};
// Dial's アルゴリズム（バケットキュー）。辺コストが小さい整数のとき priority_queue より高速。
// max_cost = 最大辺コスト（BFS なら 1）
// max_dist = 探索する最大距離（省略時は全到達頂点を探索）
// 未到達は INT_MAX。
//
// Usage:
// vector<vector<pair<int,int>>> adj(N); // adj[v] = {{隣接, 重み}, ...}
// auto dist = dial(start, N, adj, 1); // BFS
// auto dist = dial(start, N, adj, max_cost); // 全頂点
// auto dist = dial(start, N, adj, max_cost, max_dist); // 距離 max_dist 以内
vector<int> dial(int start, int n, const vector<vector<pair<int, int>>>& adj,
int max_cost, int max_dist = -1) {
const int D = max_cost + 1;
vector<int> dist(n, INT_MAX);
vector<vector<int>> bucket(D);
dist[start] = 0;
bucket[0].push_back(start);
int pending = 1;
for (int d = 0; pending > 0; d++) {
int bi = d % D;
for (size_t k = 0; k < bucket[bi].size(); k++) {
int v = bucket[bi][k];
if (dist[v] != d) continue;
for (auto [u, w] : adj[v]) {
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
if (max_dist < 0 || dist[u] <= max_dist) {
bucket[dist[u] % D].push_back(u);
pending++;
}
}
}
}
pending -= (int)bucket[bi].size();
bucket[bi].clear();
}
return dist;
}
struct Solver {
Solver() { timer.reset(); }
void read() {}
void solve() {}
void print() const {}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Solver solver;
solver.read();
solver.solve();
solver.print();
return 0;
}