Submission #72532515
Source Code Expand
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>
#include <random>
#include <bitset>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define vall(A) A.begin(), A.end()
#define vin(A) for (ll iiii = 0, sz = A.size(); iiii < sz; iiii++){cin >> A[iiii];}
#define vout(A) for(ll iiii = 0, sz = A.size(); iiii < sz; iiii++){cout << A[iiii] << " \n"[iiii == sz-1];}
#define vout2d(A) for (ll iiii = 0, HHHH = A.size(), WWWW = (A.empty() ? 0 : A[0].size()); iiii < HHHH; iiii++){for (ll jjjj = 0; jjjj < WWWW; jjjj++){cout << A[iiii][jjjj] << " \n"[jjjj==WWWW-1];}}
#define vsum(A) [&](const auto &vveecc){ll ssuumm = 0; for(auto &vvaalluuee : vveecc){ssuumm += vvaalluuee;} return ssuumm;}(A)
#define adjustedvin(A) for (ll iiii = 1, sz = A.size(); iiii < sz; iiii++){cin >> A[iiii];}
#define adjustedvout(A) for(ll iiii = 1, sz = A.size(); iiii < sz; iiii++){cout << A[iiii] << " \n"[iiii == sz-1];}
#define adjustedvout2d(A) for (ll iiii = 1, HHHH = A.size(), WWWW = (A.empty() ? 0 : A[0].size()); iiii < HHHH; iiii++){for (ll jjjj = 1; jjjj < WWWW; jjjj++){cout << A[iiii][jjjj] << " \n"[jjjj==WWWW-1];}}
vector<ull> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904, 9223372036854775808ull};
vector<ull> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000, 10000000000000000000ull};
vector<ll> di{0,1,0,-1};
vector<ll> dj{1,0,-1,0};
namespace a1073741824{
//library
namespace AVL{
//AVLset.hpp
/// @brief AVL木による重複なし集合
/// @tparam T 木に載せる要素の型
template <typename T>
struct AVLset {
private:
/// @brief AVLset用ノード
/// @tparam TTT
template<typename TTT>
struct AVLsetNode{
TTT key; //値
AVLsetNode* left;
AVLsetNode* right;
AVLsetNode* parent; //親へのポインタ
int size; //この部分木に含まれるノードの総数
int height; //部分木から各ノードへの経路長の最大値
AVLsetNode(TTT k, AVLsetNode* p = nullptr) : key(k), left(nullptr), right(nullptr), parent(p), size(1), height(1) {}
};
int treesize = 0;//全体の要素数
public:
AVLsetNode<T>* root;
AVLset() : root(nullptr) {}
///双方向イテレーターの実装
class iterator {
public:
AVLsetNode<T>* current;
const AVLset<T>* tree; // 所属する木へのポインタ
// コンストラクタで木への参照を受け取る
iterator(AVLsetNode<T>* node, const AVLset<T>* t) : current(node), tree(t) {}
T& operator*() const {
if (current == nullptr) {
cerr << "Error: Getting element of end() iterator" << endl;
assert(false);
}
return current->key;
}
bool operator==(const iterator& other) const { return current == other.current; }
bool operator!=(const iterator& other) const { return current != other.current; }
// --- 前方移動 (++) ---
iterator& operator++() {
// 1. end() からの移動（不正操作）
if (current == nullptr) {
cerr << "Error: Incrementing end() iterator." << endl;
assert(false);
}
// 2. 通常の移動ロジック
if (current->right != nullptr) {
current = current->right;
while (current->left != nullptr)
current = current->left;
} else {
AVLsetNode<T>* p = current->parent;
while (p != nullptr && current == p->right) {
current = p;
p = p->parent;
}
current = p;
}
return *this;
}
// --- 後方移動 (--) ---
iterator& operator--() {
// 1. end() からの復帰（特殊処理）
if (current == nullptr) {
// 木が空の場合は戻れない
if (tree->root == nullptr) {
cerr << "Error: Decrementing iterator of empty tree." << endl;
assert(false);
}
// 木の最大値（一番右）へ移動
current = tree->getMaxNode(tree->root);
return *this;
}
// 2. 通常の移動ロジック
if (current->left != nullptr) {
current = current->left;
while (current->right != nullptr)
current = current->right;
} else {
AVLsetNode<T>* p = current->parent;
while (p != nullptr && current == p->left) {
current = p;
p = p->parent;
}
// 3. begin() の手前に戻ろうとした場合（不正操作）
if (p == nullptr) {
// 移動先がない（＝自分が最小値だった）
cerr << "Error: Decrementing begin() iterator." << endl;
assert(false);
}
current = p;
}
return *this;
}
};
/// @brief 最小値を指すイテレーターを取得する。
iterator begin() const {
return iterator(getMinNode(root), this);
}
/// @brief 最大値を指すイテレーターを取得する。
iterator prevend() const{
return iterator(getMaxNode(root),this);
}
/// @brief 最大値の次を指すイテレーターを取得する。
iterator end() const {
return iterator(nullptr, this);
}
// --- ヘルパー関数（公開・内部兼用） ---
AVLsetNode<T>* getMinNode(AVLsetNode<T>* n) const {
if (!n) return nullptr;
while (n->left) n = n->left;
return n;
}
AVLsetNode<T>* getMaxNode(AVLsetNode<T>* n) const {
if (!n) return nullptr;
while (n->right) n = n->right;
return n;
}
/// @brief 指定したkeyを挿入する。すでにあれば何も起きない
/// @param key
void insert(const T& key) {
root = insertNode(root, nullptr, key);
}
/// @brief 指定した要素を指すイテレーターを返す。なければend()が返される。
/// @param key
/// @return
iterator find(const T& key) {
AVLsetNode<T>* curr = root;
while (curr) {
if (key == curr->key) return iterator(curr, this);
else if (key < curr->key) curr = curr->left;
else curr = curr->right;
}
return end();
}
// イテレータが指す要素を1つだけ削除し、次の要素へのイテレータを返す
iterator eraseone(iterator pos) {
if (pos == end()) return end();
AVLsetNode<T>* targetNode = pos.current; // イテレータからノードを取得
// ケースA: 子が2つある場合
// この場合、deleteNodeDirect内部で「後継ノード(nextItが指す先)」が物理的に削除され、
// その値が targetNode にコピーされます。
// つまり、targetNode はメモリ上には残りますが、中身が「次の要素」に入れ替わります。
if (targetNode->left != nullptr && targetNode->right != nullptr) {
// 削除操作を実行
// (内部で targetNode->key が書き換わり、後継ノードが delete されます)
deleteNodeDirect(targetNode);
// targetNode の場所には「削除した値の次の値」が入っているため、
// 更新された targetNode を指すイテレータを返せば正解です。
// (pos は内部的に targetNode を指しているので、そのまま pos を返せばOKですが、
// 念のため再構築して返します)
return pos;
//return iterator(targetNode, this);
}
// ケースB: 子が0個 または 1個の場合
// この場合、targetNode そのものが物理的に delete されます。
// そのため、削除前に「次のイテレータ」を確保しておく従来の方法が有効です。
else {
iterator nextIt = pos;
++nextIt; // 次へ進めておく
deleteNodeDirect(targetNode);
return nextIt; // 退避しておいたイテレータを返す
}
}
// 削除
iterator eraseone(const T& key) {
return eraseone(find(key));
}
// 範囲 [first, last) の要素をすべて削除する
// 戻り値: 削除された範囲の直後のイテレータ（つまり last）
iterator range_erase(iterator first, iterator last) {
while (first != last) {
AVLsetNode<T>* node = first.current; // Iteratorのcurrentにアクセスできる前提
// 【バグ修正】
// firstが2つの子を持つ場合、内部実装では「後継ノード(右の最小)」が物理的に削除されます。
// もし、その「後継ノード」が「last」そのものであった場合、
// eraseを実行すると last イテレーターが無効化(メモリ解放)されてしまいます。
if (node->left != nullptr && node->right != nullptr) {
// 物理的に削除される予定の後継ノードを探す
AVLsetNode<T>* successor = node->right;
while (successor->left != nullptr) {
successor = successor->left;
}
// 「終了地点(last)」が「物理削除されるノード」と一致してしまった場合
if (last.current == successor) {
// この場合、範囲 [first, last) には first 1つしか要素がありません。
// (successorはBSTにおいて直後の要素であるため)
// 1. 削除実行
// 値のSwapが行われ、successor(元のlast)がdeleteされます。
// この時点で引数の last は無効になります。
eraseone(first);
// 2. ループ終了
// 元の first ノードには、コピーされた successor(last) の値が入っています。
// つまり、現在の node こそが、新しい「last」相当の位置です。
// 無効になった last と比較する前に、正しいイテレータを返して終了します。
return iterator(node, this);
}
}
// 通常ケース: last が巻き添えになることはないので安全に進める
first = eraseone(first);
}
return last;
}
/// @brief 指定した要素keyがあるかを検索する。
/// @param key
/// @return keyがあればtrue なければfalse
int count(const T& key) {
AVLsetNode<T>* current = root;
while (current != nullptr) {
if (key == current->key) return 1;
else if (key < current->key) current = current->left;
else current = current->right;
}
return 0;
}
/// @brief 要素数を取得
/// @return 要素数
int size(){
return treesize;
}
/// @brief 空であるか判定
/// @return treesize==0
bool empty(){
return treesize == 0;
}
/// @brief 指定したkey以上の最小要素を指すイテレーターを取得する。なければend()が返される。
/// @param key
/// @return iterator
iterator lower(const T& key){
AVLsetNode<T>* curr = root;
AVLsetNode<T>* ok_node = nullptr;
while (curr != nullptr){
if (curr->key < key){
curr = curr->right;
}
else{
ok_node = curr;
curr = curr->left;
}
}
return iterator(ok_node, this);
}
/// @brief 指定したkeyより大きい最小要素を指すイテレーターを取得する。なければend()が返される。
/// @param key
/// @return iterator
iterator upper(const T& key){
AVLsetNode<T>* curr = root;
AVLsetNode<T>* ok_node = nullptr;
while (curr != nullptr){
if (curr->key <= key){
curr = curr->right;
}
else{
ok_node = curr;
curr = curr->left;
}
}
return iterator(ok_node, this);
}
/// @brief 全要素を消す。
void clear(){
deque<AVLsetNode<T>*> Q;
Q.push_back(root);
while (!Q.empty()){
if (Q.front()->left != nullptr){
Q.push_back(Q.front()->left);
}
if (Q.front()->right != nullptr){
Q.push_back(Q.front()->right);
}
delete Q.front();
Q.pop_front();
}
root = nullptr;//すべて初期化。
treesize = 0;
}
/// @brief index(0-indexed)でk番目の要素にアクセスする。
/// @param k
/// @return
iterator getkth(const int &k){
if (k < 0){
cerr << "Index out of bounds(index must be non-negative)" << endl;
assert(false);
}
if (k >= treesize){
return end();
//cerr << "Index out of bounds(right out)" << endl;
//assert(false);
}
return iterator(findKthNode(root, k), this);
}
iterator operator[](const int &k){
return getkth(k);
}
/// @brief イテレーターが指す場所のindex(0-indexed)を返す。
/// @param pos
/// @return index
int getindex(const iterator& it){
//end()のindexはtreesize
if (it == end()) return treesize;
AVLsetNode<T>* node = it.current;
// --- Step 1: 自分の左部分木のサイズをカウント ---
int idx = getSize(node->left);
// --- Step 2: 根に向かって遡る ---
AVLsetNode<T>* curr = node;
while (curr->parent != nullptr) {
// 自分が親の「右の子」である場合
if (curr == curr->parent->right) {
// 親(1つ) + 親の左部分木(getSize) を加算
idx += 1 + getSize(curr->parent->left);
}
// 上へ移動
curr = curr->parent;
}
return idx;
}
/// @brief 全要素を小さい順に表示
void display() {
std::cout << "\n\n";
inOrder(root);
std::cout << "\n\n";
}
private:
// --- ヘルパー関数 ---
//部分木サイズを取得
int getSize(AVLsetNode<T>* n) {
if (n == nullptr) return 0;
return n->size;
}
// 高さとサイズを同時に更新する関数
void updateNode(AVLsetNode<T>* n) {
if (n != nullptr) {
n->height = 1 + std::max(getHeight(n->left), getHeight(n->right));
n->size = 1 + getSize(n->left) + getSize(n->right); // ★サイズ計算
}
}
int getHeight(AVLsetNode<T>* n) {
if (n == nullptr) return 0;
return n->height;
}
int getBalance(AVLsetNode<T>* n) {
if (n == nullptr) return 0;
return getHeight(n->left) - getHeight(n->right);
}
// 右回転 (親ポインタ更新付き)
AVLsetNode<T>* rightRotate(AVLsetNode<T>* y) {
AVLsetNode<T>* x = y->left;
AVLsetNode<T>* T2 = x->right;
// 回転
x->right = y;
y->left = T2;
// 親の更新
if (T2) T2->parent = y;
x->parent = y->parent; // xはyの元の親を継承
y->parent = x; // yの親はxになる
// 高さ、部分木の要素数更新
updateNode(y);
updateNode(x);
return x;
}
// 左回転 (親ポインタ更新付き)
AVLsetNode<T>* leftRotate(AVLsetNode<T>* x) {
AVLsetNode<T>* y = x->right;
AVLsetNode<T>* T2 = y->left;
// 回転
y->left = x;
x->right = T2;
// 親の更新
if (T2) T2->parent = x;
y->parent = x->parent;
x->parent = y;
// 高さ、部分木の要素数更新
updateNode(x);
updateNode(y);
return y;
}
// 挿入ロジック (親ポインタの設定を追加)
AVLsetNode<T>* insertNode(AVLsetNode<T>* node, AVLsetNode<T>* parent, const T& key) {
// 1. 通常のBST挿入
if (node == nullptr){// 親をセット
treesize++;
return new AVLsetNode<T>(key, parent);
}
if (key < node->key)
node->left = insertNode(node->left, node, key);
else if (key > node->key)
node->right = insertNode(node->right, node, key);
else
return node;
// 2. 高さ更新
updateNode(node);
// 3. バランスチェック & 回転
int balance = getBalance(node);
// LL
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// RR
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// LR
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// RL
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 特定のノードを物理的に削除し、親を遡ってバランス調整する
void deleteNodeDirect(AVLsetNode<T>* node) {
if (node == nullptr) return;
treesize--;//削除されるので一個減らす
// ---------------------------------------------------
// 1. 子が2つある場合
// 後継者（右の最小）と値を入れ替え、削除対象を後継者にする
// ---------------------------------------------------
if (node->left != nullptr && node->right != nullptr) {
AVLsetNode<T>* successor = getMinNode(node->right);
// 値だけコピー（本来はstd::moveなどが好ましい）
node->key = successor->key;
// 削除対象を successor に変更して、以下の「子0or1」の処理に流す
node = successor;
}
// ---------------------------------------------------
// 2. 子が0個 または 1個の場合（nodeは削除されるノード）
// ---------------------------------------------------
AVLsetNode<T>* child = (node->left != nullptr) ? node->left : node->right;
AVLsetNode<T>* parent = node->parent;
// 子がいる場合、子の親ポインタを更新
if (child != nullptr) {
child->parent = parent;
}
// 親のリンクを更新
if (parent == nullptr) {
// 根を削除する場合
root = child;
} else {
if (node == parent->left) {
parent->left = child;
} else {
parent->right = child;
}
}
// ノード自体のメモリ解放
delete node;
// ---------------------------------------------------
// 3. 削除した場所の親からルートまで遡ってバランス調整
// ---------------------------------------------------
AVLsetNode<T>* curr = parent;
while (curr != nullptr) {
// 高さ、サイズの更新
updateNode(curr);
// バランスチェック
int balance = getBalance(curr);
// 親へのポインタを繋ぎ変えるため、回転後の新しい部分木の根を受け取る
AVLsetNode<T>* newSubRoot = curr;
// LL Case
if (balance > 1 && getBalance(curr->left) >= 0) {
newSubRoot = rightRotate(curr);
}
// LR Case
else if (balance > 1 && getBalance(curr->left) < 0) {
curr->left = leftRotate(curr->left);
newSubRoot = rightRotate(curr);
}
// RR Case
else if (balance < -1 && getBalance(curr->right) <= 0) {
newSubRoot = leftRotate(curr);
}
// RL Case
else if (balance < -1 && getBalance(curr->right) > 0) {
curr->right = rightRotate(curr->right);
newSubRoot = leftRotate(curr);
}
// 回転が行われた場合、親から見たリンクも修正が必要
// (rightRotate等の内部でparentは更新されるが、
// 「親のleft/rightのどちらか」という情報はここで更新する)
AVLsetNode<T>* p = newSubRoot->parent;
if (p != nullptr) {
if (curr == p->left) p->left = newSubRoot;
else p->right = newSubRoot;
} else {
root = newSubRoot;
}
// 次の親へ（回転した場合は新しい親の上へ）
curr = newSubRoot->parent;
}
}
// 再帰探索ロジック
AVLsetNode<T>* findKthNode(AVLsetNode<T>* node, int k) {
if (node == nullptr){
cerr << "There are fatal bugs in this AVL tree" << endl;
assert(false);
}
// 左部分木のサイズを取得
int leftSize = getSize(node->left);
if (k == leftSize) {
// 左側の数がちょうど k 個なら、現在のノードが k 番目 (0-indexed)
return node;
} else if (k < leftSize) {
// k が左のサイズより小さいなら、左部分木の中に答えがある
return findKthNode(node->left, k);
} else {
// k が左より大きいなら、右部分木へ。
// 探すべき順位は、(k - 左の数 - 自分1つ分) になる
return findKthNode(node->right, k - leftSize - 1);
}
}
void inOrder(AVLsetNode<T>* root) {
if (root != nullptr) {
inOrder(root->left);
// T型を cout で出力できる必要がある
std::cout << root->key << " ";
inOrder(root->right);
}
}
};
//AVLmap.hpp
/// @brief AVL木による連想配列
/// @tparam T 木に載せる要素の型
template <typename T, typename U>
struct AVLmap {
private:
/// @brief AVLmap用ノード
/// @tparam TTT UUU
template <typename TTT, typename UUU>
struct AVLmapNode {
TTT key; //連想配列のキー
UUU value; //連想配列に入れる値
AVLmapNode* left;
AVLmapNode* right;
AVLmapNode* parent; //親へのポインタ
int size; //この部分木に含まれるノードの総数
int height; //部分木から各ノードへの経路長の最大値
AVLmapNode(TTT k, UUU v, AVLmapNode* p = nullptr) : key(k), value(v), left(nullptr), right(nullptr), parent(p), size(1), height(1) {}
};
int treesize = 0;//全体の要素数
public:
AVLmapNode<T,U>* root;
AVLmap() : root(nullptr) {}
///双方向イテレーターの実装
class iterator {
public:
AVLmapNode<T,U>* current;
const T &key = current->key;
U &value = current->value;
const AVLmap<T,U>* tree; // 所属する木へのポインタ
// コンストラクタで木への参照を受け取る
iterator(AVLmapNode<T,U>* node, const AVLmap<T,U>* t) : current(node), tree(t) {}
pair<T,U>& operator*() const {
if (current == nullptr) {
cerr << "Error: Getting element of end() iterator" << endl;
assert(false);
}
return make_pair(current->key, current->value);
}
bool operator==(const iterator& other) const { return current == other.current; }
bool operator!=(const iterator& other) const { return current != other.current; }
// --- 前方移動 (++) ---
iterator& operator++() {
// 1. end() からの移動（不正操作）
if (current == nullptr) {
cerr << "Error: Incrementing end() iterator." << endl;
assert(false);
}
// 2. 通常の移動ロジック
if (current->right != nullptr) {
current = current->right;
while (current->left != nullptr)
current = current->left;
} else {
AVLmapNode<T,U>* p = current->parent;
while (p != nullptr && current == p->right) {
current = p;
p = p->parent;
}
current = p;
}
return *this;
}
// --- 後方移動 (--) ---
iterator& operator--() {
// 1. end() からの復帰（特殊処理）
if (current == nullptr) {
// 木が空の場合は戻れない
if (tree->root == nullptr) {
cerr << "Error: Decrementing iterator of empty tree." << endl;
assert(false);
}
// 木の最大値（一番右）へ移動
current = tree->getMaxNode(tree->root);
return *this;
}
// 2. 通常の移動ロジック
if (current->left != nullptr) {
current = current->left;
while (current->right != nullptr)
current = current->right;
} else {
AVLmapNode<T,U>* p = current->parent;
while (p != nullptr && current == p->left) {
current = p;
p = p->parent;
}
// 3. begin() の手前に戻ろうとした場合（不正操作）
if (p == nullptr) {
// 移動先がない（＝自分が最小値だった）
cerr << "Error: Decrementing begin() iterator." << endl;
assert(false);
}
current = p;
}
return *this;
}
};
/// @brief 最小値を指すイテレーターを取得する。
iterator begin() const {
return iterator(getMinNode(root), this);
}
/// @brief 最大値を指すイテレーターを取得する。
iterator prevend() const{
return iterator(getMaxNode(root),this);
}
/// @brief 最大値の次を指すイテレーターを取得する。
iterator end() const {
return iterator(nullptr, this);
}
// --- ヘルパー関数（公開・内部兼用） ---
AVLmapNode<T,U>* getMinNode(AVLmapNode<T,U>* n) const {
if (!n) return nullptr;
while (n->left) n = n->left;
return n;
}
AVLmapNode<T,U>* getMaxNode(AVLmapNode<T,U>* n) const {
if (!n) return nullptr;
while (n->right) n = n->right;
return n;
}
/// @brief 指定した{key,value}を挿入する。すでにあれば何も起きない
/// @param key
/// @param value
void insert(const T& key, const U& value) {
root = insertNode(root, nullptr, key, value);
}
/// @brief 指定した要素を指すイテレーターを返す。なければend()が返される。
/// @param key
/// @return
iterator find(const T& key) {
AVLmapNode<T,U>* curr = root;
while (curr) {
if (key == curr->key) return iterator(curr, this);
else if (key < curr->key) curr = curr->left;
else curr = curr->right;
}
return end();
}
U& operator[](const T& key){
bool succeed_to_insert = false;
U* returned_pointer;
root = insertNode_and_ret_velue(root, nullptr, key, succeed_to_insert, returned_pointer);
return *returned_pointer;
}
// イテレータが指す要素を1つだけ削除し、次の要素へのイテレータを返す
iterator eraseone(iterator pos) {
if (pos == end()) return end();
AVLmapNode<T,U>* targetNode = pos.current; // イテレータからノードを取得
// ケースA: 子が2つある場合
// この場合、deleteNodeDirect内部で「後継ノード(nextItが指す先)」が物理的に削除され、
// その値が targetNode にコピーされます。
// つまり、targetNode はメモリ上には残りますが、中身が「次の要素」に入れ替わります。
if (targetNode->left != nullptr && targetNode->right != nullptr) {
// 削除操作を実行
// (内部で targetNode->key が書き換わり、後継ノードが delete されます)
deleteNodeDirect(targetNode);
// targetNode の場所には「削除した値の次の値」が入っているため、
// 更新された targetNode を指すイテレータを返せば正解です。
// (pos は内部的に targetNode を指しているので、そのまま pos を返せばOKですが、
// 念のため再構築して返します)
return pos;
//return iterator(targetNode, this);
}
// ケースB: 子が0個 または 1個の場合
// この場合、targetNode そのものが物理的に delete されます。
// そのため、削除前に「次のイテレータ」を確保しておく従来の方法が有効です。
else {
iterator nextIt = pos;
++nextIt; // 次へ進めておく
deleteNodeDirect(targetNode);
return nextIt; // 退避しておいたイテレータを返す
}
}
// 削除
iterator eraseone(const T& key) {
return eraseone(find(key));
}
/// @brief 範囲 [first, last) の要素をすべて削除する
/// @param first
/// @param last
/// @return last
iterator range_erase(iterator first, iterator last) {
while (first != last) {
AVLmapNode<T,U>* node = first.current; // Iteratorのcurrentにアクセスできる前提
// 【バグ修正】
// firstが2つの子を持つ場合、内部実装では「後継ノード(右の最小)」が物理的に削除されます。
// もし、その「後継ノード」が「last」そのものであった場合、
// eraseを実行すると last イテレーターが無効化(メモリ解放)されてしまいます。
if (node->left != nullptr && node->right != nullptr) {
// 物理的に削除される予定の後継ノードを探す
AVLmapNode<T,U>* successor = node->right;
while (successor->left != nullptr) {
successor = successor->left;
}
// 「終了地点(last)」が「物理削除されるノード」と一致してしまった場合
if (last.current == successor) {
// この場合、範囲 [first, last) には first 1つしか要素がありません。
// (successorはBSTにおいて直後の要素であるため)
// 1. 削除実行
// 値のSwapが行われ、successor(元のlast)がdeleteされます。
// この時点で引数の last は無効になります。
eraseone(first);
// 2. ループ終了
// 元の first ノードには、コピーされた successor(last) の値が入っています。
// つまり、現在の node こそが、新しい「last」相当の位置です。
// 無効になった last と比較する前に、正しいイテレータを返して終了します。
return iterator(node, this);
}
}
// 通常ケース: last が巻き添えになることはないので安全に進める
first = eraseone(first);
}
return last;
}
/// @brief 指定した要素keyがあるかを検索する。
/// @param key
/// @return keyがあればtrue なければfalse
bool contains(const T& key) {
AVLmapNode<T,U>* current = root;
while (current != nullptr) {
if (key == current->key) return true;
else if (key < current->key) current = current->left;
else current = current->right;
}
return false;
}
/// @brief 要素数を取得
/// @return 要素数
int size(){
return treesize;
}
/// @brief 空であるか判定
/// @return treesize==0
bool empty(){
return treesize == 0;
}
/// @brief 指定したkey以上の最小要素を指すイテレーターを取得する。なければend()が返される。
/// @param key
/// @return iterator
iterator lower(const T& key){
AVLmapNode<T,U>* curr = root;
AVLmapNode<T,U>* ok_node = nullptr;
while (curr != nullptr){
if (curr->key < key){
curr = curr->right;
}
else{
ok_node = curr;
curr = curr->left;
}
}
return iterator(ok_node, this);
}
/// @brief 指定したkeyより大きい最小要素を指すイテレーターを取得する。なければend()が返される。
/// @param key
/// @return iterator
iterator upper(const T& key){
AVLmapNode<T,U>* curr = root;
AVLmapNode<T,U>* ok_node = nullptr;
while (curr != nullptr){
if (curr->key <= key){
curr = curr->right;
}
else{
ok_node = curr;
curr = curr->left;
}
}
return iterator(ok_node, this);
}
/// @brief 全要素を消す。
void clear(){
deque<AVLmapNode<T,U>*> Q;
Q.push_back(root);
while (!Q.empty()){
if (Q.front()->left != nullptr){
Q.push_back(Q.front()->left);
}
if (Q.front()->right != nullptr){
Q.push_back(Q.front()->right);
}
delete Q.front();
Q.pop_front();
}
root = nullptr;//すべて初期化。
treesize = 0;
}
/// @brief index(0-indexed)でk番目の要素にアクセスする。
/// @param k
/// @return
iterator getkth(int k){
if (k < 0){
cerr << "Index out of bounds(index must be non-negative)" << endl;
assert(false);
}
if (k >= treesize){
return end();
//cerr << "Index out of bounds(right out)" << endl;
//assert(false);
}
return iterator(findKthNode(root, k), this);
}
/// @brief イテレーターが指す場所のindex(0-indexed)を返す。
/// @param pos
/// @return index
int getindex(const iterator& it){
//end()のindexはtreesize
if (it == end()) return treesize;
AVLmapNode<T,U>* node = it.current;
// --- Step 1: 自分の左部分木のサイズをカウント ---
int idx = getSize(node->left);
// --- Step 2: 根に向かって遡る ---
AVLmapNode<T,U>* curr = node;
while (curr->parent != nullptr) {
// 自分が親の「右の子」である場合
if (curr == curr->parent->right) {
// 親(1つ) + 親の左部分木(getSize) を加算
idx += 1 + getSize(curr->parent->left);
}
// 上へ移動
curr = curr->parent;
}
return idx;
}
/// @brief 全要素を小さい順に表示
void display() {
inOrder(root);
std::cout << "\n";
}
private:
// --- ヘルパー関数 ---
//部分木サイズを取得
int getSize(AVLmapNode<T,U>* n) {
if (n == nullptr) return 0;
return n->size;
}
// 高さとサイズを同時に更新する関数
void updateNode(AVLmapNode<T,U>* n) {
if (n != nullptr) {
n->height = 1 + std::max(getHeight(n->left), getHeight(n->right));
n->size = 1 + getSize(n->left) + getSize(n->right); // ★サイズ計算
}
}
int getHeight(AVLmapNode<T,U>* n) {
if (n == nullptr) return 0;
return n->height;
}
int getBalance(AVLmapNode<T,U>* n) {
if (n == nullptr) return 0;
return getHeight(n->left) - getHeight(n->right);
}
// 右回転 (親ポインタ更新付き)
AVLmapNode<T,U>* rightRotate(AVLmapNode<T,U>* y) {
AVLmapNode<T,U>* x = y->left;
AVLmapNode<T,U>* T2 = x->right;
// 回転
x->right = y;
y->left = T2;
// 親の更新
if (T2) T2->parent = y;
x->parent = y->parent; // xはyの元の親を継承
y->parent = x; // yの親はxになる
// 高さ、部分木の要素数更新
updateNode(y);
updateNode(x);
return x;
}
// 左回転 (親ポインタ更新付き)
AVLmapNode<T,U>* leftRotate(AVLmapNode<T,U>* x) {
AVLmapNode<T,U>* y = x->right;
AVLmapNode<T,U>* T2 = y->left;
// 回転
y->left = x;
x->right = T2;
// 親の更新
if (T2) T2->parent = x;
y->parent = x->parent;
x->parent = y;
// 高さ、部分木の要素数更新
updateNode(x);
updateNode(y);
return y;
}
// 挿入ロジック (親ポインタの設定を追加)
AVLmapNode<T,U>* insertNode(AVLmapNode<T,U>* node, AVLmapNode<T,U>* parent, const T& key, const U& value){
// 1. 通常のBST挿入
if (node == nullptr){// 親をセット
treesize++;
return new AVLmapNode<T,U>(key, value, parent);
}
if (key < node->key)
node->left = insertNode(node->left, node, key, value);
else if (key > node->key)
node->right = insertNode(node->right, node, key, value);
else
return node;
// 2. 高さ更新
updateNode(node);
// 3. バランスチェック & 回転
int balance = getBalance(node);
// LL
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// RR
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// LR
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// RL
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
AVLmapNode<T,U>* insertNode_and_ret_velue(AVLmapNode<T,U>* node, AVLmapNode<T,U>* parent, const T& key, bool &succeed_to_insert, U*& returned_pointer){
// 1. 通常のBST挿入
if (node == nullptr){// 親をセット
succeed_to_insert = true;
treesize++;
AVLmapNode<T,U>* tempnode = new AVLmapNode<T,U>(key, *(new U), parent);
returned_pointer = &(tempnode->value);
return tempnode;
}
pair<AVLmapNode<T,U>*, U*> temp;
if (key < node->key){
node->left = insertNode_and_ret_velue(node->left, node, key, succeed_to_insert, returned_pointer);
}
else if (key > node->key){
node->right = insertNode_and_ret_velue(node->right, node, key, succeed_to_insert, returned_pointer);
}
else{
returned_pointer = &(node->value);
return node;
}
if (!succeed_to_insert){return node;}//もし新しく挿入してないなら木を回転させる必要はない
// 2. 高さ更新
updateNode(node);
// 3. バランスチェック & 回転
int balance = getBalance(node);
// LL
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// RR
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// LR
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// RL
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 特定のノードを物理的に削除し、親を遡ってバランス調整する
void deleteNodeDirect(AVLmapNode<T,U>* node) {
if (node == nullptr) return;
treesize--;//削除されるので一個減らす
// ---------------------------------------------------
// 1. 子が2つある場合
// 後継者（右の最小）と値を入れ替え、削除対象を後継者にする
// ---------------------------------------------------
if (node->left != nullptr && node->right != nullptr) {
AVLmapNode<T,U>* successor = getMinNode(node->right);
// 値だけコピー（本来はstd::moveなどが好ましい）
node->key = successor->key;
// 削除対象を successor に変更して、以下の「子0or1」の処理に流す
node = successor;
}
// ---------------------------------------------------
// 2. 子が0個 または 1個の場合（nodeは削除されるノード）
// ---------------------------------------------------
AVLmapNode<T,U>* child = (node->left != nullptr) ? node->left : node->right;
AVLmapNode<T,U>* parent = node->parent;
// 子がいる場合、子の親ポインタを更新
if (child != nullptr) {
child->parent = parent;
}
// 親のリンクを更新
if (parent == nullptr) {
// 根を削除する場合
root = child;
} else {
if (node == parent->left) {
parent->left = child;
} else {
parent->right = child;
}
}
// ノード自体のメモリ解放
delete node;
// ---------------------------------------------------
// 3. 削除した場所の親からルートまで遡ってバランス調整
// ---------------------------------------------------
AVLmapNode<T,U>* curr = parent;
while (curr != nullptr) {
// 高さ、サイズの更新
updateNode(curr);
// バランスチェック
int balance = getBalance(curr);
// 親へのポインタを繋ぎ変えるため、回転後の新しい部分木の根を受け取る
AVLmapNode<T,U>* newSubRoot = curr;
// LL Case
if (balance > 1 && getBalance(curr->left) >= 0) {
newSubRoot = rightRotate(curr);
}
// LR Case
else if (balance > 1 && getBalance(curr->left) < 0) {
curr->left = leftRotate(curr->left);
newSubRoot = rightRotate(curr);
}
// RR Case
else if (balance < -1 && getBalance(curr->right) <= 0) {
newSubRoot = leftRotate(curr);
}
// RL Case
else if (balance < -1 && getBalance(curr->right) > 0) {
curr->right = rightRotate(curr->right);
newSubRoot = leftRotate(curr);
}
// 回転が行われた場合、親から見たリンクも修正が必要
// (rightRotate等の内部でparentは更新されるが、
// 「親のleft/rightのどちらか」という情報はここで更新する)
AVLmapNode<T,U>* p = newSubRoot->parent;
if (p != nullptr) {
if (curr == p->left) p->left = newSubRoot;
else p->right = newSubRoot;
} else {
root = newSubRoot;
}
// 次の親へ（回転した場合は新しい親の上へ）
curr = newSubRoot->parent;
}
}
// 再帰探索ロジック
AVLmapNode<T,U>* findKthNode(AVLmapNode<T,U>* node, int k) {
if (node == nullptr){
cerr << "There are fatal bugs in this AVL tree" << endl;
assert(false);
}
// 左部分木のサイズを取得
int leftSize = getSize(node->left);
if (k == leftSize) {
// 左側の数がちょうど k 個なら、現在のノードが k 番目 (0-indexed)
return node;
} else if (k < leftSize) {
// k が左のサイズより小さいなら、左部分木の中に答えがある
return findKthNode(node->left, k);
} else {
// k が左より大きいなら、右部分木へ。
// 探すべき順位は、(k - 左の数 - 自分1つ分) になる
return findKthNode(node->right, k - leftSize - 1);
}
}
void inOrder(AVLmapNode<T,U>* root) {
if (root != nullptr) {
inOrder(root->left);
// T型を cout で出力できる必要がある
std::cout << root->key << ":" << root->value << " ";
inOrder(root->right);
}
}
};
//AVLmultiset.hpp
/// @brief AVL木による多重集合
/// @tparam T
template <typename T>
struct AVLmultiset {
public:
template <typename TTT>
struct AVLmultisetNode {
TTT key; // intではなくT型にする
AVLmultisetNode* left;
AVLmultisetNode* right;
AVLmultisetNode* parent; //親へのポインタ
int size; //この部分木に含まれるノードの総数
int height;
AVLmultisetNode(TTT k, AVLmultisetNode* p = nullptr) : key(k), left(nullptr), right(nullptr), parent(p), size(1), height(1) {}
};
private: int treesize = 0;//全体の要素数
public:
AVLmultisetNode<T>* root;
AVLmultiset() : root(nullptr) {}
// ==========================================
// 高機能イテレータの実装
// ==========================================
class iterator {
public:
AVLmultisetNode<T>* current;
const AVLmultiset<T>* tree; // 所属する木へのポインタ
// コンストラクタで木への参照を受け取る
iterator(AVLmultisetNode<T>* node, const AVLmultiset<T>* t) : current(node), tree(t) {}
T& operator*() const {
if (current == nullptr) {
cerr << "Error: Getting element of end() iterator" << endl;
assert(false);
}
return current->key;
}
bool operator==(const iterator& other) const { return current == other.current; }
bool operator!=(const iterator& other) const { return current != other.current; }
// --- 前方移動 (++) ---
iterator& operator++() {
// 1. end() からの移動（不正操作）
if (current == nullptr) {
cerr << "Error: Incrementing end() iterator." << endl;
assert(false);
}
// 2. 通常の移動ロジック
if (current->right != nullptr) {
current = current->right;
while (current->left != nullptr)
current = current->left;
} else {
AVLmultisetNode<T>* p = current->parent;
while (p != nullptr && current == p->right) {
current = p;
p = p->parent;
}
current = p;
}
return *this;
}
// --- 後方移動 (--) ---
iterator& operator--() {
// 1. end() からの復帰（特殊処理）
if (current == nullptr) {
// 木が空の場合は戻れない
if (tree->root == nullptr) {
cerr << "Error: Decrementing iterator of empty tree." << endl;
assert(false);
}
// 木の最大値（一番右）へ移動
current = tree->getMaxNode(tree->root);
return *this;
}
// 2. 通常の移動ロジック
if (current->left != nullptr) {
current = current->left;
while (current->right != nullptr)
current = current->right;
} else {
AVLmultisetNode<T>* p = current->parent;
while (p != nullptr && current == p->left) {
current = p;
p = p->parent;
}
// 3. begin() の手前に戻ろうとした場合（不正操作）
if (p == nullptr) {
// 移動先がない（＝自分が最小値だった）
cerr << "Error: Decrementing begin() iterator." << endl;
assert(false);
}
current = p;
}
return *this;
}
};
// --- イテレータ取得 ---
iterator begin() const{
return iterator(getMinNode(root), this);
}
iterator prevend() const{
return iterator(getMaxNode(root), this);
}
iterator end() const{
return iterator(nullptr, this);
}
// --- ヘルパー関数（公開・内部兼用） ---
AVLmultisetNode<T>* getMinNode(AVLmultisetNode<T>* n) const {
if (!n) return nullptr;
while (n->left) n = n->left;
return n;
}
AVLmultisetNode<T>* getMaxNode(AVLmultisetNode<T>* n) const {
if (!n) return nullptr;
while (n->right) n = n->right;
return n;
}
// 挿入 (const T& で参照渡しにしてコピーコスト削減)
void insert(const T& key) {
root = insertNode(root, nullptr, key);
}
/// @brief 指定した要素を指すイテレーターを返す。なければend()が返される。
/// @param key
/// @return
iterator find(const T& key) {
AVLmultisetNode<T>* curr = root;
while (curr) {
if (key == curr->key) return iterator(curr, this);
else if (key < curr->key) curr = curr->left;
else curr = curr->right;
}
return end();
}
/// @brief イテレータが指す要素を1つだけ削除し、次の要素へのイテレータを返す
iterator eraseone(iterator pos) {
if (pos == end()) return end();
AVLmultisetNode<T>* targetNode = pos.current; // イテレータからノードを取得
// ケースA: 子が2つある場合
// この場合、deleteNodeDirect内部で「後継ノード(nextItが指す先)」が物理的に削除され、
// その値が targetNode にコピーされます。
// つまり、targetNode はメモリ上には残りますが、中身が「次の要素」に入れ替わります。
if (targetNode->left != nullptr && targetNode->right != nullptr) {
// 削除操作を実行
// (内部で targetNode->key が書き換わり、後継ノードが delete されます)
deleteNodeDirect(targetNode);
// targetNode の場所には「削除した値の次の値」が入っているため、
// 更新された targetNode を指すイテレータを返せば正解です。
// (pos は内部的に targetNode を指しているので、そのまま pos を返せばOKですが、
// 念のため再構築して返します)
return iterator(targetNode, this);
}
// ケースB: 子が0個 または 1個の場合
// この場合、targetNode そのものが物理的に delete されます。
// そのため、削除前に「次のイテレータ」を確保しておく従来の方法が有効です。
else {
iterator nextIt = pos;
++nextIt; // 次へ進めておく
deleteNodeDirect(targetNode);
return nextIt; // 退避しておいたイテレータを返す
}
}
// 値で検索して1つだけ削除
iterator eraseone(const T& key) {
return eraseone(find(key));
}
// 範囲 [first, last) の要素をすべて削除する
// 戻り値: 削除された範囲の直後のイテレータ（つまり last）
iterator range_erase(iterator first, iterator last) {
while (first != last) {
AVLmultisetNode<T>* node = first.current; // Iteratorのcurrentにアクセスできる前提
// 【バグ修正】
// firstが2つの子を持つ場合、内部実装では「後継ノード(右の最小)」が物理的に削除されます。
// もし、その「後継ノード」が「last」そのものであった場合、
// eraseを実行すると last イテレーターが無効化(メモリ解放)されてしまいます。
if (node->left != nullptr && node->right != nullptr) {
// 物理的に削除される予定の後継ノードを探す
AVLmultisetNode<T>* successor = node->right;
while (successor->left != nullptr) {
successor = successor->left;
}
// 「終了地点(last)」が「物理削除されるノード」と一致してしまった場合
if (last.current == successor) {
// この場合、範囲 [first, last) には first 1つしか要素がありません。
// (successorはBSTにおいて直後の要素であるため)
// 1. 削除実行
// 値のSwapが行われ、successor(元のlast)がdeleteされます。
// この時点で引数の last は無効になります。
eraseone(first);
// 2. ループ終了
// 元の first ノードには、コピーされた successor(last) の値が入っています。
// つまり、現在の node こそが、新しい「last」相当の位置です。
// 無効になった last と比較する前に、正しいイテレータを返して終了します。
return iterator(node, this);
}
}
// 通常ケース: last が巻き添えになることはないので安全に進める
first = eraseone(first);
}
return last;
}
// 検索
bool contains(const T& key) {
AVLmultisetNode<T>* current = root;
while (current != nullptr) {
if (key == current->key) return true;
else if (key < current->key) current = current->left;
else current = current->right;
}
return false;
}
int size(){
return treesize;
}
bool empty(){
return treesize == 0;
}
iterator lower(const T& key){
AVLmultisetNode<T>* curr = root;
AVLmultisetNode<T>* ok_node = nullptr;
while (curr){
if (curr->key < key){
curr = curr->right;
}
else{
ok_node = curr;
curr = curr->left;
}
}
return iterator(ok_node, this);
}
iterator upper(const T& key){
AVLmultisetNode<T>* curr = root;
AVLmultisetNode<T>* ok_node = nullptr;
while (curr){
if (curr->key <= key){
curr = curr->right;
}
else{
ok_node = curr;
curr = curr->left;
}
}
return iterator(ok_node, this);
}
void clear(){
deque<AVLmultisetNode<T>*> Q;
Q.push_back(root);
while (!Q.empty()){
if (Q.front()->left != nullptr){
Q.push_back(Q.front()->left);
}
if (Q.front()->right != nullptr){
Q.push_back(Q.front()->right);
}
delete Q.front();
Q.pop_front();
}
root = nullptr;
treesize = 0;
}
iterator getkth(int k){
if (k < 0){
cerr << "Index out of bounds" << endl;
assert(false);
}
if (k >= treesize){
return end();
}
return iterator(findKthNode(root, k), this);
}
// 表示
void display() {
PrintinOrder(root);
std::cout << std::endl;
}
private: //ここからprivateメンバ関数(内部実装などに使う。)
//部分木サイズを取得
int getSize(AVLmultisetNode<T>* n) {
if (n == nullptr) return 0;
return n->size;
}
// 高さとサイズを同時に更新する関数
void updateNode(AVLmultisetNode<T>* n) {
if (n != nullptr) {
n->height = 1 + std::max(getHeight(n->left), getHeight(n->right));
n->size = 1 + getSize(n->left) + getSize(n->right); // ★サイズ計算
}
}
int getHeight(AVLmultisetNode<T>* n) {
if (n == nullptr) return 0;
return n->height;
}
int getBalance(AVLmultisetNode<T>* n) {
if (n == nullptr) return 0;
return getHeight(n->left) - getHeight(n->right);
}
// 右回転 (親ポインタ更新付き)
AVLmultisetNode<T>* rightRotate(AVLmultisetNode<T>* y) {
AVLmultisetNode<T>* x = y->left;
AVLmultisetNode<T>* T2 = x->right;
// 回転
x->right = y;
y->left = T2;
// 親の更新
if (T2) T2->parent = y;
x->parent = y->parent; // xはyの元の親を継承
y->parent = x; // yの親はxになる
// 高さ、部分木の要素数更新
updateNode(y);
updateNode(x);
return x;
}
// 左回転 (親ポインタ更新付き)
AVLmultisetNode<T>* leftRotate(AVLmultisetNode<T>* x) {
AVLmultisetNode<T>* y = x->right;
AVLmultisetNode<T>* T2 = y->left;
// 回転
y->left = x;
x->right = T2;
// 親の更新
if (T2) T2->parent = x;
y->parent = x->parent;
x->parent = y;
// 高さ、部分木の要素数更新
updateNode(x);
updateNode(y);
return y;
}
// 挿入ロジック (親ポインタの設定を追加)
AVLmultisetNode<T>* insertNode(AVLmultisetNode<T>* node, AVLmultisetNode<T>* parent, const T& key) {
// 1. 通常のBST挿入
if (node == nullptr){// 親をセット
treesize++;
return new AVLmultisetNode<T>(key, parent);
}
if (key < node->key){
node->left = insertNode(node->left, node, key);
}
else{
node->right = insertNode(node->right, node, key);
}
// 2. 高さ更新
updateNode(node);
// 3. バランスチェック & 回転
int balance = getBalance(node);
// LL
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// RR
if (balance < -1 && key >= node->right->key)
return leftRotate(node);
// LR
if (balance > 1 && key >= node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// RL
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 特定のノードを物理的に削除し、親を遡ってバランス調整する
void deleteNodeDirect(AVLmultisetNode<T>* node) {
if (node == nullptr) return;
treesize--;//削除されるので一個減らす
// ---------------------------------------------------
// 1. 子が2つある場合
// 後継者（右の最小）と値を入れ替え、削除対象を後継者にする
// ---------------------------------------------------
if (node->left != nullptr && node->right != nullptr){
AVLmultisetNode<T>* successor = getMinNode(node->right);
// 値だけコピー（本来はstd::moveなどが好ましい）
node->key = move(successor->key);
// 削除対象を successor に変更して、以下の「子0or1」の処理に流す
node = successor;
}
// ---------------------------------------------------
// 2. 子が0個 または 1個の場合（nodeは削除されるノード）
// ---------------------------------------------------
AVLmultisetNode<T>* child = (node->left != nullptr) ? node->left : node->right;
AVLmultisetNode<T>* parent = node->parent;
// 子がいる場合、子の親ポインタを更新
if (child != nullptr) {
child->parent = parent;
}
// 親のリンクを更新
if (parent == nullptr) {
// 根を削除する場合
root = child;
} else {
if (node == parent->left) {
parent->left = child;
} else {
parent->right = child;
}
}
// ノード自体のメモリ解放
delete node;
// ---------------------------------------------------
// 3. 削除した場所の親からルートまで遡ってバランス調整
// ---------------------------------------------------
AVLmultisetNode<T>* curr = parent;
while (curr != nullptr) {
// 高さの更新
updateNode(curr);
// バランスチェック
int balance = getBalance(curr);
// 親へのポインタを繋ぎ変えるため、回転後の新しい部分木の根を受け取る
AVLmultisetNode<T>* newSubRoot = curr;
// LL Case
if (balance > 1 && getBalance(curr->left) >= 0) {
newSubRoot = rightRotate(curr);
}
// LR Case
else if (balance > 1 && getBalance(curr->left) < 0) {
curr->left = leftRotate(curr->left);
newSubRoot = rightRotate(curr);
}
// RR Case
else if (balance < -1 && getBalance(curr->right) <= 0) {
newSubRoot = leftRotate(curr);
}
// RL Case
else if (balance < -1 && getBalance(curr->right) > 0) {
curr->right = rightRotate(curr->right);
newSubRoot = leftRotate(curr);
}
// 回転が行われた場合、親から見たリンクも修正が必要
// (rightRotate等の内部でparentは更新されるが、
// 「親のleft/rightのどちらか」という情報はここで更新する)
AVLmultisetNode<T>* p = newSubRoot->parent;
if (p != nullptr) {
if (curr == p->left) p->left = newSubRoot;
else p->right = newSubRoot;
} else {
root = newSubRoot;
}
// 次の親へ（回転した場合は新しい親の上へ）
curr = newSubRoot->parent;
}
}
// 再帰探索ロジック
AVLmultisetNode<T>* findKthNode(AVLmultisetNode<T>* node, int k) {
// 左部分木のサイズを取得
int leftSize = getSize(node->left);
if (k == leftSize) {
// 左側の数がちょうど k 個なら、現在のノードが k 番目 (0-indexed)
return node;
} else if (k < leftSize) {
// k が左のサイズより小さいなら、左部分木の中に答えがある
return findKthNode(node->left, k);
} else {
// k が左より大きいなら、右部分木へ。
// 探すべき順位は、(k - 左の数 - 自分1つ分) になる
return findKthNode(node->right, k - leftSize - 1);
}
}
//全部の値を出力
void PrintinOrder(AVLmultisetNode<T>* r) {
if (r != nullptr) {
PrintinOrder(r->left);
// T型を cout で出力できる必要がある
std::cout << r->key << " ";
PrintinOrder(r->right);
}
}
};
}
namespace math{
//math.hpp
/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。
/// @param a
/// @param b
/// @param m
/// @return a^b%m
ll modpow(ll a, ll b, ll m){
ll t = a%m;
ll ans = 1;
while (b > 0){
if (b%2){
ans = (ans*t)%m;
}
b /= 2;
t = (t*t)%m;
}
return ans;
}
/// @brief a^nを返す。bに関して線形時間で計算できる。
/// @param a
/// @param n
/// @param m
/// @return a^n
ll powll(ll a, ll n){
ll r = 1;
for (ll i = 1; i <= n; i++){
r *= a;
}
return r;
}
/// @brief 正の整数Nを素因数分解する
/// @param N
/// @return vector<vector<ll> {{素因数1,個数}, {素因数2,個数}, {素因数3,個数}...}
vector<vector<ll>> p_fact(ll N){
if (N == 1){
return vector<vector<ll>> {{1,1}};
}
vector<vector<ll>> R;//戻り値用リスト
const ll M = N;
for (ll i = 2; i <= sqrtl(M); i++){
if (N % i == 0){
ll divide_count = 0;
while (N % i == 0){
divide_count++;
N /= i;
}
R.push_back(vector<ll> {i,divide_count});
}
}
if (N != 1){
R.push_back(vector<ll> {N,1});
}
return R;
}
/// @brief 二次元ベクトル表記の素因数分解リストを受け取って約数の和を求める
/// @param vv
/// @return 約数の和
ll sum_of_divisor(vector<vector<ll>> vv){
if (vv[0][0] == 1){
return 1;
}
ll R = 1;
for (vector<ll> x : vv){
R *= ((ll)powl(x[0],x[1]+1) - 1)/(x[0] - 1);
}
return R;
}
/// @brief 二次元ベクトル表記の素因数分解リストを受け取って約数の種類を求める
/// @param vv
/// @return 約数の種類
ll kind_of_divisor(vector<vector<ll>> vv){
ll R = 1;
for (vector<ll> x : vv){
R *= x[1]+1;
}
return R;
}
/// @brief 1のみを含むデフォルトリストdと、素因数分解の結果pを受け取って、dを約数リストに変換する。
/// @return ない
void search_divisor(vector<ll> &d, vector<vector<ll>> &p, ll depth = 0){
if (depth == p.size()){
sort(vall(d));
return;
}
ll t = d.size();
for (ll i = 1; i <= p[depth][1]; i++){
for (ll j = 0; j < t; j++){
d.push_back(d[j]*powll(p[depth][0], i));
}
}
search_divisor(d, p, depth+1);
}
/// @brief 有理数のceilを求める
/// @param y
/// @param x
/// @return ceil(y/x)
ll cefrac(ll y, ll x);
/// @brief 有理数のfloorを求める
/// @param y
/// @param x
/// @return floor(y/x)
ll flfrac(ll y, ll x){
if ((x^y) > 0){
x = abs(x);
y = abs(y);
return (y-(y%x))/x;
}
else if ((x^y) < 0){
x = abs(x);
y = abs(y);
return -cefrac(y,x);
}
else{
return y/x;
}
}
ll cefrac(ll y, ll x){
if ((x^y) > 0){
x = abs(x);
y = abs(y);
if (y%x == 0){
return y/x;
}
else return 1 + (y-(y%x))/x;
}
else if ((x^y) < 0){
x = abs(x);
y = abs(y);
return -flfrac(y,x);
}
else{
return y/x;
}
}
ll flsqrt(ll N){
if (N){
ll ok = 1;
ll ng = min(N,2000000000LL);
while (ng - ok >= 2){
ll mid = (ok+ng)/2;
if (mid*mid <= N){
ok = mid;
}
else{
ng = mid;
}
}
return ok;
}
else{return 0;}
}
/// @brief エラトステネスの篩
struct Eratosthenes{
vector<ll> P_List;
vector<bool> is_prime;
vector<ll> min_factor;
Eratosthenes(ll N) : is_prime(N+1,1), min_factor(N+1,-1){
is_prime[1] = 0;
min_factor[1] = 1;
for (ll i = 2; i <= N; i++){
if (is_prime[i]){
P_List.push_back(i);
min_factor[i] = i;
for (ll j = 2*i; j <= N; j += i){
is_prime[j] = 0;
if (min_factor[j] == -1){
min_factor[j] = i;
}
}
}
}
}
void chase_prime(const ll &reference, ll x, vector<vector<vector<ll>>> &r){
if (r[reference].empty() || min_factor[x] != r[reference].back()[0]){
r[reference].push_back({min_factor[x], 1});
}
else{
r[reference].back()[1]++;
}
if (x != min_factor[x]){
chase_prime(reference, x/min_factor[x], r);
}
}
vector<vector<vector<ll>>> p_fact(ll N){
vector<vector<vector<ll>>> r(N+1);
r[1].push_back({1,1});
for (ll i = 2; i <= N; i++){
chase_prime(i, i, r);
}
return r;
}
};
/// @brief 一次不定方程式ax+by=1の解を1つ見つける
/// @param a
/// @param b
/// @return {x,y}
pair<ll,ll> axby1(ll a, ll b){
if (a == 1 or b == 1){
if (a == 1){
return {1-b,1};
}
else{
return {1,1-a};
}
}
else if (a>b){
auto p = axby1(a%b, b);
return {p.first, p.second - p.first*(a/b)};
}
else{
swap(a,b);
auto p = axby1(a%b, b);
return {p.second - p.first*(a/b), p.first};
}
}
/// @brief 1/a mod Mを求める
/// @param a
/// @param M
/// @return 1/a mod M
ll inverse_mod(ll a, ll M){
if (__gcd(a,M) != 1){
return -1;
}
return (M+(axby1(a,M).first)%M)%M;
}
/// @brief modint
template<ll M>
struct mll{
ll val;
mll(const ll &x){
val = x%M;
}
void operator=(const ll &x){
val = x%M;
}
void operator=(const mll &a){
val = a.val;
}
mll operator+(const mll &a){
return mll(val+a.val);
}
void operator+=(const mll &a){
val = (val+a.val)%M;
}
mll operator+(const ll &a){
return mll(val+a);
}
void operator+=(const ll &a){
val = (val+a)%M;
}
mll operator-(const mll &a){
return mll(M+val-a.val);
}
void operator-=(const mll &a){
val = (M+val-a.val)%M;
}
mll operator-(const ll &a){
return mll(M+val-a);
}
void operator-=(const ll &a){
val = (M+val-a)%M;
}
mll operator*(const mll &a){
return mll(val*a.val);
}
void operator*=(const mll &a){
val = (val*a.val)%M;
}
mll operator*(const ll &a){
return mll(val*a);
}
void operator*=(const ll &a){
val = (val*a)%M;
}
mll operator/(const mll &a){
return mll(val*inverse_mod(a.val,M));
}
void operator/=(const mll &a){
val = (val*inverse_mod(a.val,M))%M;
}
mll operator/(const ll &a){
return mll(val*inverse_mod(a,M));
}
void operator/=(const ll &a){
val = (val*inverse_mod(a,M))%M;
}
};
//階乗前計算による二項係数mod998244353
struct factorialncr{
private: vector<ll> factorialmod;
private: ll N_MAX_N_MAX;
public:
factorialncr(const ll &N_MAX){
N_MAX_N_MAX = N_MAX;
factorialmod = vector<ll>(N_MAX+1);
factorialmod[0] = 1;
for (ll i = 1; i <= N_MAX; i++){
factorialmod[i] = (i*factorialmod[i-1])%998244353;
}
}
ll nCr(ll n, ll r){
if (r < 0 || n < r || n > N_MAX_N_MAX){
return 0;
}
return (factorialmod[n]*inverse_mod((factorialmod[n-r]*factorialmod[r])%998244353,998244353))%998244353;
}
};
//表の前計算による二項係数modM
struct tablencr{
private: vector<vector<ll>> ncrmodlist;
private: ll N_MAX_N_MAX;
public:
tablencr(const ll &N_MAX, const ll &M){
N_MAX_N_MAX = N_MAX;
ncrmodlist = vector<vector<ll>> (5001, vector<ll>(5001,0));
ncrmodlist[0][0] = 1;
for (ll i = 1; i <= 5000; i++){
for (ll j = 0; j <= i; j++){
if (j == 0 || j == i){
ncrmodlist[i][j] = 1;
}
else{
ncrmodlist[i][j] = (ncrmodlist[i-1][j-1] + ncrmodlist[i-1][j])%M;
}
}
}
}
ll nCr(ll n, ll r){
if (r < 0 || n < r || n > N_MAX_N_MAX){
return 0;
}
return ncrmodlist[n][r];
}
};
//matrix.hpp
/// @brief 64bit整数行列。自動でmod998244353などを取ってくれる。
/// @tparam MMOODD
template<ll MMOODD>
struct matrixll{
vector<vector<ll>> M;
ll H,W;
/// @brief N次単位行列を生成
/// @param N
matrixll(ll N){
H = N;W = N;
M = vector<vector<ll>>(N,vector<ll>(N,0));
for (ll i = 0; i < N; i++){
M[i][i] = 1;
}
}
/// @brief h×w型の、全要素がvの行列を生成
/// @param h
/// @param w
/// @param v
matrixll(ll h, ll w, ll v){
H = h;
W = w;
M = vector<vector<ll>>(H,vector<ll>(W,v));
}
/// @brief 2次元配列を用いて行列を生成
/// @param A
matrixll(vector<vector<ll>> &A){
M = A;
H = A.size();
W = A[0].size();
}
matrixll operator+(const matrixll &T){
if (H != T.H || W != T.W){
cerr << "size error\n";
assert(false);
}
matrixll ans(M);
for (ll i = 0; i < H; i++){
for (ll j = 0; j < W; j++){
ans.M[i][j] += T.M[i][j];
ans.M[i][j] %= MMOODD;
}
}
return ans;
}
void operator+=(const matrixll &T){
if (H != T.H || W != T.W){
cerr << "size error\n";
assert(false);
}
for (ll i = 0; i < H; i++){
for (ll j = 0; j < W; j++){
M[i][j] += T.M[i][j];
M[i][j] %= MMOODD;
}
}
}
matrixll operator-(const matrixll &T){
if (H != T.H || W != T.W){
cerr << "size error\n";
assert(false);
}
matrixll ans(M);
for (ll i = 0; i < H; i++){
for (ll j = 0; j < W; j++){
ans.M[i][j] -= T.M[i][j];
ans.M[i][j] += MMOODD;
ans.M[i][j] %= MMOODD;
}
}
return ans;
}
void operator-=(const matrixll &T){
if (H != T.H || W != T.W){
cerr << "size error\n";
assert(false);
}
for (ll i = 0; i < H; i++){
for (ll j = 0; j < W; j++){
M[i][j] -= T.M[i][j];
M[i][j] += MMOODD;
M[i][j] %= MMOODD;
}
}
}
matrixll operator*(const matrixll &T){
if (W != T.H){
cerr << "size error\n";
assert(false);
}
matrixll ans(H,T.W,0);
for (ll i = 0; i < H; i++){
for (ll j = 0; j < T.W; j++){
for (ll k = 0; k < W; k++){
ans.M[i][j] += M[i][k]*T.M[k][j];
ans.M[i][j] %= MMOODD;
}
}
}
return ans;
}
void operator*=(const matrixll &T){
if (W != T.H){
cerr << "size error\n";
assert(false);
}
matrixll ans(H,T.W,0);
for (ll i = 0; i < H; i++){
for (ll j = 0; j < T.W; j++){
for (ll k = 0; k < W; k++){
ans.M[i][j] += M[i][k]*T.M[k][j];
ans.M[i][j] %= MMOODD;
}
}
}
W = T.W;
M = ans.M;
}
matrixll operator*(const ll &c){
matrixll ans(H,W,0);
for (ll i = 0; i < H; i++){
for (ll j = 0; j < W; j++){
ans.M[i][j] = M[i][j] * c;
ans.M[i][j] %= MMOODD;
}
}
return ans;
}
void operator*=(const ll &c){
for (ll i = 0; i < H; i++){
for (ll j = 0; j < W; j++){
M[i][j] *= c;
M[i][j] %= MMOODD;
}
}
}
/// @brief A^Nを返す。
/// @param A
/// @param N
/// @return A^N
matrixll matrixmodpow(ll N){
matrixll R(H);
matrixll A(M);
for (ll i = 0; i < H; i++){
for (ll j = 0; j < H; j++){
A.M[i][j] %= MMOODD;
}
}
if (N){
while (N){
if (N%2){
R *= A;
}
A *= A;
N /= 2;
}
return R;
}
else{
return R;
}
}
};
//quatient_range.hpp
/// @brief sum[i=1 ~ i=N] i^a * (floor(M/i))^b を計算する
/// @param N
/// @param M
/// @param a
/// @param b
/// @return
ll inv_floor_sum(ll N, ll M, ll a ,ll b){
auto floorsqrt = [](ll N){
ll ok = 1;
ll ng = min(N,2000000000LL);
while (ng - ok >= 2){
ll mid = (ok+ng)/2;
if (mid*mid <= N){
ok = mid;
}
else{
ng = mid;
}
}
return ok;
};
auto lpowl = [](ll x, ll N){
ll r = 1;
for (ll i = 1; i <= N; i++){
r *= x;
}
return r;
};
vector<vector<ll>> nCrtable(a+2,vector<ll>(a+2,0));
nCrtable[0][0] = 1;
for (ll i = 1; i <= a+1; i++){
for (ll j = 0; j <= i; j++){
if (j == 0 || j == i){
nCrtable[i][j] = 1;
}
else{
nCrtable[i][j] = nCrtable[i-1][j-1] + nCrtable[i-1][j];
}
}
}
function<ll(ll,ll)> sum = [&](ll n, ll l){
if (l == 0){
return n;
}
if (l == 1){
return n*(n+1)/2;
}
if (l == 2){
return n*(n+1)*(2*n+1)/6;
}
ll T = 0;
for (ll i = 0; i < l; i++){
T += nCrtable[l+1][i]*sum(n,i);
}
return (lpowl(n+1,l+1)-1-T)/(l+1);
};
ll ans = 0;
ll rootM = floorsqrt(M);
if (N <= M / rootM){//Nが小さいときはそのまま計算して値を返す
for (ll i = 1; i <= N; i++){
ans += lpowl(i,a)*lpowl(M/i,b);
}
return ans;
}
//それ以外の場合は主客転倒を行う
for (ll i = 1; i <= M/rootM; i++){//最初の方をそのまま足す。
ans += lpowl(i,a)*lpowl(M/i,b);
}
for (ll i = rootM-1; i > M/N; i--){
ans += lpowl(i,b)*(sum(M/i,a) - sum(M/(i+1),a));
}
ans += lpowl(M/N,b)*(sum(N,a) - sum(M/((M/N)+1), a));
return ans;
}
//convolution.hpp
vector<ll> powroot998244353{1LL, 998244352LL, 911660635LL, 372528824LL, 69212480LL, 381091786LL, 515872972LL, 273395035LL, 469477650LL, 503794470LL, 464513504LL, 558899782LL, 504969456LL, 840897051LL, 539927980LL, 417009993LL, 725461291LL, 456548895LL, 712494065LL, 542639453LL, 768214923LL, 303507821LL, 438914733LL, 761881641};
vector<ll> powrootinv998244353{1LL, 998244352LL, 86583718LL, 509520358LL, 661054123LL, 863921598LL, 323451984LL, 689146517LL, 379690232LL, 240519260LL, 899368279LL, 920065956LL, 588792270LL, 118574449LL, 847593593LL, 858760106LL, 987418793LL, 177938570LL, 753608159LL, 786906984LL, 331540181LL, 655706071LL, 268754442LL, 191076546};
vector<ll> powroot1224736769{1LL, 1224736768LL, 24506215LL, 992888437LL, 853017291LL, 235319402LL, 269744380LL, 157861287LL, 894223137LL, 600648668LL, 1091208103LL, 382541006LL, 12818149LL, 149218560LL, 746299392LL, 405692663LL, 633223136LL, 672327338LL, 992917013LL, 758198491LL, 1079610480LL, 1056667043LL, 1039331205LL, 1026803890LL, 449603200};
vector<ll> powrootinv1224736769{1LL, 1224736768LL, 1200230554LL, 961581489LL, 796105727LL, 1023008969LL, 406386483LL, 251411652LL, 655108271LL, 1145368249LL, 780593535LL, 38041180LL, 816166160LL, 659160240LL, 1200430513LL, 392462252LL, 15561184LL, 893027826LL, 928760284LL, 497993173LL, 529117122LL, 637457654LL, 931394937LL, 823596420LL, 55047034};
vector<ll> DFT998244353(vector<ll> X, ll K, bool inverse = false){
if (K == 1){
return vector<ll>{(X[0]+X[1])%998244353, (998244353+X[0]-X[1])%998244353};
}
vector<ll> even(1LL<<(K-1));
vector<ll> odd(1LL<<(K-1));
for (ll i = 0; i < (1LL<<(K-1)); i++){
even[i] = (X[i] + X[(1LL<<(K-1))+i])%998244353;
}
ll temp = 1;
if (inverse){
for (ll i = 0; i < (1LL<<(K-1)); i++){
odd[i] = (temp*(998244353 + X[i] - X[(1LL<<(K-1))+i]))%998244353;
temp = (temp*powrootinv998244353[K])%998244353;
}
}
else{
for (ll i = 0; i < (1LL<<(K-1)); i++){
odd[i] = (temp*(998244353 + X[i] - X[(1LL<<(K-1))+i]))%998244353;
temp = (temp*powroot998244353[K])%998244353;
}
}
even = DFT998244353(even,K-1,inverse);
odd = DFT998244353(odd,K-1,inverse);
for (ll i = 0; i < (1LL<<K); i++){
if (i%2){
X[i] = odd[i/2];
}
else{
X[i] = even[i/2];
}
}
return X;
}
vector<ll> DFT1224736769(vector<ll> X, ll K, bool inverse = false){
if (K == 1){
return vector<ll>{(X[0]+X[1])%1224736769, (1224736769+X[0]-X[1])%1224736769};
}
vector<ll> even(1LL<<(K-1));
vector<ll> odd(1LL<<(K-1));
for (ll i = 0; i < (1LL<<(K-1)); i++){
even[i] = (X[i] + X[(1LL<<(K-1))+i])%1224736769;
}
ll temp = 1;
if (inverse){
for (ll i = 0; i < (1LL<<(K-1)); i++){
odd[i] = (temp*(1224736769 + X[i] - X[(1LL<<(K-1))+i]))%1224736769;
temp = (temp*powrootinv1224736769[K])%1224736769;
}
}
else{
for (ll i = 0; i < (1LL<<(K-1)); i++){
odd[i] = (temp*(1224736769 + X[i] - X[(1LL<<(K-1))+i]))%1224736769;
temp = (temp*powroot1224736769[K])%1224736769;
}
}
even = DFT1224736769(even,K-1,inverse);
odd = DFT1224736769(odd,K-1,inverse);
for (ll i = 0; i < (1LL<<K); i++){
if (i%2){
X[i] = odd[i/2];
}
else{
X[i] = even[i/2];
}
}
return X;
}
vector<ll> convolution998244353(vector<ll> A, vector<ll> B){
if (min(A.size(), B.size()) <= 60) {
if (A.size() < B.size()) {
swap(A, B);
}
std::vector<ll> ans(A.size() + B.size() - 1);
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++) {
ans[i + j] += A[i] * B[j];
}
}
for (auto &v : ans){
v %= 998244353;
}
return ans;
}
ll N = A.size()+B.size()-1;
ll log2N = 0;
while ((1LL<<log2N) < N){
log2N++;
}
while (A.size() < (1LL<<log2N)){
A.push_back(0);
}
while (B.size() < (1LL<<log2N)){
B.push_back(0);
}
A = DFT998244353(A,log2N);
B = DFT998244353(B,log2N);
vector<ll> C((1LL<<log2N),0);
for (ll i = 0; i < (1LL<<log2N); i++){
C[i] = (A[i]*B[i])%998244353;
}
C = DFT998244353(C,log2N,1);
ll invpow2log2N = inverse_mod((1LL<<log2N),998244353);
for (ll i = 0; i < (1LL<<log2N); i++){
C[i] = (C[i]*invpow2log2N)%998244353;
}
return C;
}
vector<ll> convolution1224736769(vector<ll> A, vector<ll> B){
if (min(A.size(), B.size()) <= 60) {
if (A.size() < B.size()) {
swap(A, B);
}
std::vector<ll> ans(A.size() + B.size() - 1);
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++) {
ans[i + j] += A[i] * B[j];
}
}
for (auto &v : ans){
v %= 1224736769;
}
return ans;
}
ll N = A.size()+B.size()-1;
ll log2N = 0;
while ((1LL<<log2N) < N){
log2N++;
}
while (A.size() < (1LL<<log2N)){
A.push_back(0);
}
while (B.size() < (1LL<<log2N)){
B.push_back(0);
}
A = DFT1224736769(A,log2N);
B = DFT1224736769(B,log2N);
vector<ll> C((1LL<<log2N),0);
for (ll i = 0; i < (1LL<<log2N); i++){
C[i] = (A[i]*B[i])%1224736769;
}
C = DFT1224736769(C,(1LL<<log2N),1);
ll invpow2log2N = inverse_mod((1LL<<log2N),1224736769);
for (ll i = 0; i < 1048576; i++){
C[i] = (C[i]*invpow2log2N)%1224736769;
}
return C;
}
}
namespace tree_datastructure{
//FenwickTree.hpp
struct FenwickTree{
vector<ll> tree;
vector<ll> B;
ll log2N = 0;
void fill_tree(vector<ll> &ruisekiwaA, ll L, ll R, ll index){
if (index >= pow2ll[log2N]){return;}
if (index == 0){
tree[index] = ruisekiwaA.back();
fill_tree(ruisekiwaA,L,(L+R)/2,1);
return;
}
tree[index] = ruisekiwaA[R] - (L == 0 ? 0 : ruisekiwaA[L-1]);
fill_tree(ruisekiwaA,L,(L+R)/2,2*index);
fill_tree(ruisekiwaA,R+1,(3*R-L+1)/2,2*index+1);
}
FenwickTree(ll howmany, ll value){
while (pow2ll[log2N] < howmany){
log2N++;
}
tree = vector<ll>(pow2ll[log2N], value);
B = vector<ll>(pow2ll[log2N], value);
for (ll i = pow2ll[log2N-1]-1; i >= 1; i--){
tree[i] = tree[2*i]*2;
}
tree[0] = 2*tree[1];
}
FenwickTree(ll howmany, vector<ll> &A){
while (pow2ll[log2N] < howmany){
log2N++;
}
vector<ll> ruisekiwaA(pow2ll[log2N]);
ruisekiwaA[0] = A[0];
for (ll i = 1; i < pow2ll[log2N]; i++){
if (i < howmany){
ruisekiwaA[i] = A[i] + ruisekiwaA[i-1];
}
else{
ruisekiwaA[i] = ruisekiwaA[i-1];
}
}
tree = vector<ll>(pow2ll[log2N],0);
B = A;
while (B.size() < pow2ll[log2N]){
B.push_back(0);
}
fill_tree(ruisekiwaA,0,pow2ll[log2N]-1,0);
}
ll sum_from_origin(ll index){
index++;
if (index == pow2ll[log2N]){
return tree[0];
}
vector<ll> temp(log2N+1);
for (ll i = 0; i <= log2N; i++){
temp[i] = index%2;
index /= 2;
}
reverse(temp.begin(), temp.end());
vector<ll> temp2;
temp2.push_back(0);
temp2.push_back(1);
for (ll i = 2; i <= log2N; i++){
temp2.push_back(0);
temp2[i] = temp2[i-1]*2 + temp[i-1];
}
ll sum = 0;
for (ll i = 0; i <= log2N; i++){
sum += temp[i] * tree[temp2[i]];
}
return sum;
}
/// @brief [l,r]の総和を返す。
/// @param l
/// @param r
/// @return 総和
ll range_sum(ll l, ll r){
if (l == 0){
return sum_from_origin(r);
}
return sum_from_origin(r)-sum_from_origin(l-1);
}
void add(ll index, ll value, ll L = 0, ll d = 0, ll index_on_tree = 0){
if (index_on_tree == 0){
tree[index_on_tree] += value;
add(index,value,0,1,1);
return;
}
if (d == log2N+1){
return;
}
ll R = L + pow2ll[log2N-d]-1;
if (L <= index && index <= R){
tree[index_on_tree] += value;
add(index,value,L,d+1,2*index_on_tree);
}
else{
add(index,value,R+1,d+1,2*index_on_tree+1);
}
}
/// @brief 一か所変える。
/// @param index
void update(ll index, ll value){
add(index,value-B[index]);
B[index] = value;
}
/// @brief 一か所をa倍してbを足す。
/// @param index
/// @param a
/// @param b
void update(ll index, ll a, ll b){
add(index,(a-1)*B[index]+b);
B[index] = B[index]*a + b;
}
};
//SegTree&LazySegTree.hpp
/// @brief 抽象化セグメントツリー
/// @attention コンストラクタ1 SegTree(A, e, op, mapping)
/// @attention コンストラクタ2 SegTree(N, I, e, op, mapping)
/// @tparam info セグ木の各ノードに載せる情報をまとめた構造体の型
/// @tparam func 更新に使う変数をまとめた構造体の型(アフィン変換なら、aとbを持つ構造体など)
/// @param e 載せたものの単位元(sumなら0, maxなら-infなど)
/// @param operation 各ノードに載ってる構造体に対する二項演算をする関数(min,max,sumなど)
/// @param mapping infoに対してfuncを作用させた結果を返す関数(アフィン変換ならx -> ax+b)
template<typename info, typename func>
struct SegTree{
int log2N;//セグ木の高さ-1
info e;///単位元
function<info(info,info)> operation;//各ノードに載ってる構造体に対する二項演算をする関数(min,max,sumなど)
function<info(func,info)> mapping;//更新を行うとどうなるか？(アフィン変換ならx -> ax+b)
/// @brief セグ木を扱うためのノード
struct SegNode{
pair<int,int> range;//自身のカバーする範囲
info I;//自身が持っている情報
SegNode(const int &L, const int &R, const info &eee) : range({L,R}), I(eee){}
SegNode(){};//空コンストラクタ
};
vector<SegNode> tree;//セグ木本体
/// @brief N個のIで初期化
/// @param I 載せたい構造体
/// @param N 載せた個数
/// @param eee 載せたものの単位元(sumなら0, maxなら-infなど)
/// @param op 各ノードに載ってる構造体に対する二項演算をする関数(min,max,sumなど)
/// @param m 更新を行うとどうなるか？(アフィン変換ならx -> ax+b)
SegTree(int N, info I, info eee, function<info(info,info)> op, function<info(func,info)> m){
//基本情報を登録
e = eee;
operation = op;
mapping = m;
//セグ木のサイズを決定
log2N = 0;
while ((1<<log2N) < N){
log2N++;
}
//セグ木に実際に乗せるvectorを構築
tree = vector<SegNode>(1<<(log2N+1));
for (int i = 0; i < N; i++){
tree[i+(1<<log2N)] = SegNode(i,i,I);
}
for (int i = N; i < (1<<log2N); i++){
tree[i+(1<<log2N)] = SegNode(i,i,e);
}
for (int i = (1<<log2N)-1; i >= 1; i--){
tree[i] = SegNode(tree[2*i].range.first,tree[2*i+1].range.second,operation(tree[2*i].I, tree[2*i+1].I));
}
}
/// @brief vector Aで初期化
/// @param I 載せたい構造体
/// @param N 載せた個数
/// @param eee 載せたものの単位元(sumなら0, maxなら-infなど)
/// @param op 各ノードに載ってる構造体に対する二項演算をする関数(min,max,sumなど)
/// @param m 更新を行うとどうなるか？(アフィン変換ならx -> ax+b)
SegTree(vector<info> &A, info eee, function<info(info,info)> op, function<info(func,info)> m){
//基本情報を登録
e = eee;
operation = op;
mapping = m;
//セグ木のサイズを決定
log2N = 0;
int sz = A.size();
while ((1ULL<<log2N) < A.size()){
log2N++;
}
//セグ木に実際に乗せるvectorを構築
tree = vector<SegNode>(1<<(log2N+1));
for (int i = 0; i < sz; i++){
tree[i+(1<<log2N)] = SegNode(i,i,A[i]);
}
for (int i = sz; i < (1<<log2N); i++){
tree[i+(1<<log2N)] = SegNode(i,i,e);
}
for (int i = (1<<log2N)-1; i >= 1; i--){
tree[i] = SegNode(tree[2*i].range.first,tree[2*i+1].range.second,operation(tree[2*i].I, tree[2*i+1].I));
}
}
/// @brief 区間の共通部分が空集合であるか判定
/// @return range1 ⋀ {a,a} == Ø
private: bool not_intersect(const pair<int,int> &range1, const int &a, const int &b){
return max(range1.second,b)-min(range1.first,a) > range1.second+b-range1.first-a;
}
/// @brief range1がrange2に完全に覆われているかを判定
/// @return range1 ⊂ {a,b}
private: bool completely_covered(const pair<int,int> &range1, const int &a, const int &b){
return a <= range1.first && range1.second <= b;
}
public:
/// @brief index閉区間[L,R]において、集計を行う。
/// @param L 左端(左端を含む)
/// @param R 右端(右端を含む)
/// @return [L,R]での集計結果
info range_get(const int &L, const int &R){
info ret = e;
int left = L;
while (left < R+1){
int log2interval = min(__builtin_ctz(left),31-__builtin_clz(R+1-left));
ret = operation(ret, tree[(left+(1<<log2N))>>log2interval].I);
left += 1<<log2interval;
}
return ret;
}
/// @brief index tに対してFをmappingする。
/// @param L index
/// @param F 適用する写像(アフィン変換ならaとbを持った構造体など)
void pointwise_update(const int &t, const func &F){
int start_index = t + (1<<log2N);
tree[start_index].I = mapping(F,tree[start_index].I);
start_index >>= 1;
while (start_index){
tree[start_index].I = operation(tree[2*start_index].I,tree[2*start_index+1].I);
start_index >>= 1;
}
}
/// @brief 左端をLに固定したとき、条件式Gが成り立つ最小の右端indexを返す。もしなければINF(=2147483647)が返ってくる。
/// @attention 判定関数Gは、区間を広げていったときにfalse,false,false,...false,true,true,true...のように、falseが続いた後にtrueが続くものでなければならない。
/// @param L 左端
/// @param G 判定関数...引数a,bがあり、引数aを動かし、引数bを比較対象tに固定した時に引数aによってtrue,falseが変動する。
/// @param t 比較対象
/// @return Gがtrueになる最小右端indexまたは2147483647
int min_right(int L, const function<bool(info,info)> &G, const info &t){
info current_result = e;
checkpoint:
int ctz = L == 0 ? log2N : __builtin_ctz(L);
if (!G(operation(current_result, tree[((1<<log2N)+L)>>ctz].I), t)){
if (tree[((1<<log2N)+L)>>ctz].range.second+1 == 1<<log2N){
return 2147483647;
}
current_result = operation(current_result, tree[((1<<log2N)+L)>>ctz].I);
L = tree[((1<<log2N)+L)>>ctz].range.second+1;
goto checkpoint;
}
for (int i = ctz-1; i >= 0; i--){
if (!G(operation(current_result, tree[((1<<log2N)+L)>>i].I), t)){
current_result = operation(current_result, tree[((1<<log2N)+L)>>i].I);
L = tree[((1<<log2N)+L)>>i].range.second+1;
goto checkpoint;
}
}
return L;
}
/// @brief 右端をRに固定したとき、条件式Gが成り立つ最大の左端indexを返す。もしなければ-INF-1(=-2147483648)が返ってくる。
/// @attention 判定関数Gは、区間を広げていったときにfalse,false,false,...false,true,true,true...のように、falseが続いた後にtrueが続くものでなければならない。
/// @param R 右端
/// @param G 判定関数...引数a,bがあり、引数aを動かし、引数bを比較対象tに固定した時に引数aによってtrue,falseが変動するようなものである。
/// @param t 比較対象
/// @return Gがtrueになる最大左端index
int max_left(int R, const function<bool(info,info)> &G, const info &t){
info current_result = e;
checkpoint:
int cto = __builtin_ctz(~R);//cto...count trailing one
if (!G(operation(current_result, tree[((1<<log2N)+R)>>cto].I), t)){
if (tree[((1<<log2N)+R)>>cto].range.first == 0){
return -2147483648;
}
current_result = operation(current_result, tree[((1<<log2N)+R)>>cto].I);
R = tree[((1<<log2N)+R)>>cto].range.first-1;
goto checkpoint;
}
for (int i = cto-1; i >= 0; i--){
if (!G(operation(current_result, tree[((1<<log2N)+R)>>i].I), t)){
current_result = operation(current_result, tree[((1<<log2N)+R)>>i].I);
R = tree[((1<<log2N)+R)>>i].range.first-1;
goto checkpoint;
}
}
return R;
}
};
/// @brief 抽象化遅延セグメントツリー
/// @attention コンストラクタ1 LazySegTree(A, e, op, mapping, composition, id)
/// @attention コンストラクタ2 LazySegTree(N, I, e, op, mapping, composition , id)
/// @tparam info セグ木の各ノードに載せる情報をまとめた構造体の型
/// @tparam func 更新に使う変数をまとめた構造体の型(アフィン変換なら、aとbを持つ構造体など)
/// @param e 載せたものの単位元(sumなら0, maxなら-infなど)
/// @param operation 各ノードに載ってる構造体に対する二項演算をする関数(min,max,sumなど)
/// @param mapping infoに対してfuncを作用させた結果を返す関数(アフィン変換ならx -> ax+b)
/// @param composition func同士の合成結果を1つのfuncにする関数((u,v)でu(v())の結果を返すものとする)(ax+bのあとにcx+dを作用させると実質acx+bc+dになるなど)
/// @param id funcの恒等写像(アフィン変換ならx -> 1x+0)
template<typename info, typename func>
struct LazySegTree{
int log2N;//セグ木の高さ+1
info e;///単位元
function<info(info,info)> operation;//各ノードに載ってる構造体に対する二項演算をする関数(min,max,sumなど)
function<info(func,info)> mapping;//更新を行うとどうなるか？(アフィン変換ならx -> ax+b)
function<func(func,func)> composition;//mを合成した結果(ax+bのあとにcx+dを作用させると実質acx+bc+dになるなど)
func id;//mappingの恒等写像版(アフィン変換ならx -> 1x+0など)
/// @brief セグ木を扱うためのノード
struct SegNode{
pair<int,int> range;//自身のカバーする範囲
info I;//自身が持っている情報
func delay;//遅延情報として残っている写像
bool is_delay = 0;//遅延情報があるかどうか
SegNode(int L, int R, info eee, func ididid) : range({L,R}), I(eee), delay(ididid){}
SegNode(){};//空コンストラクタ
};
vector<SegNode> tree;//セグ木本体
/// @brief N個のIで初期化
/// @param I 載せたい構造体
/// @param N 載せた個数
/// @param eee 載せたものの単位元(sumなら0, maxなら-infなど)
/// @param op 各ノードに載ってる構造体に対する二項演算をする関数(min,max,sumなど)
/// @param m 更新を行うとどうなるか？(アフィン変換ならx -> ax+b)
/// @param c mを合成した結果((u,v)でu(v())の結果を返すものとする)(ax+bのあとにcx+dを作用させると実質acx+bc+dになるなど)
/// @param ididid mの恒等写像版(アフィン変換ならx -> 1x+0)
LazySegTree(int N, info I, info eee, function<info(info,info)> op, function<info(func,info)> m, function<func(func,func)> c, func ididid){
//基本情報を登録
e = eee;
operation = op;
mapping = m;
composition = c;
id = ididid;
//セグ木のサイズを決定
log2N = 0;
while ((1<<log2N) < N){
log2N++;
}
//セグ木に実際に乗せるvectorを構築
tree = vector<SegNode>(1<<(log2N+1));
for (int i = 0; i < N; i++){
tree[i+(1<<log2N)] = SegNode(i,i,I,id);
}
for (int i = N; i < (1<<log2N); i++){
tree[i+(1<<log2N)] = SegNode(i,i,e,id);
}
for (int i = (1<<log2N)-1; i >= 1; i--){
tree[i] = SegNode(tree[2*i].range.first,tree[2*i+1].range.second,operation(tree[2*i].I, tree[2*i+1].I),id);
}
}
/// @brief vector Aで初期化
/// @param I 載せたい構造体
/// @param N 載せた個数
/// @param eee 載せたものの単位元(sumなら0, maxなら-infなど)
/// @param op 各ノードに載ってる構造体に対する二項演算をする関数(min,max,sumなど)
/// @param m 更新を行うとどうなるか？(アフィン変換ならx -> ax+b)
/// @param c mを合成した結果((u,v)でu(v())の結果を返すものとする)(ax+bのあとにcx+dを作用させると実質acx+bc+dになるなど)
/// @param ididid mの恒等写像版(アフィン変換ならx -> 1x+0)
LazySegTree(const vector<info> &A, info eee, function<info(info,info)> op, function<info(func,info)> m, function<func(func,func)> c, func ididid){
//基本情報を登録
e = eee;
operation = op;
mapping = m;
composition = c;
id = ididid;
//セグ木のサイズを決定
log2N = 0;
int sz = A.size();
while ((1ULL<<log2N) < A.size()){
log2N++;
}
//セグ木に実際に乗せるvectorを構築
tree = vector<SegNode>(1<<(log2N+1));
for (int i = 0; i < sz; i++){
tree[i+(1<<log2N)] = SegNode(i,i,A[i],id);
}
for (int i = sz; i < (1<<log2N); i++){
tree[i+(1<<log2N)] = SegNode(i,i,e,id);
}
for (int i = (1<<log2N)-1; i >= 1; i--){
tree[i] = SegNode(tree[2*i].range.first,tree[2*i+1].range.second,operation(tree[2*i].I, tree[2*i+1].I),id);
}
}
/// @brief 区間の共通部分が空集合であるか判定
/// @return range1 ⋀ {a,b} == Ø
private: bool not_intersect(const pair<int,int> &range1, const int &a, const int &b){
return max(range1.second,b)-min(range1.first,a) > range1.second+b-range1.first-a;
}
/// @brief range1がrange2に完全に覆われているかを判定
/// @return range1 ⊂ {a,b}
private: bool completely_covered(const pair<int,int> &range1, const int &a, const int &b){
return a <= range1.first && range1.second <= b;
}
public:
/// @brief 遅延情報の伝播を行う
void tell_info(int index_on_tree){
if (!tree[index_on_tree].is_delay){return;}
if (index_on_tree >= (1<<log2N)){
tree[index_on_tree].delay = id;
tree[index_on_tree].is_delay = 0;
return;
}
//左の子に伝播
tree[2*index_on_tree].I = mapping(tree[index_on_tree].delay,tree[2*index_on_tree].I);
tree[2*index_on_tree].delay = composition(tree[index_on_tree].delay, tree[2*index_on_tree].delay);
tree[2*index_on_tree].is_delay = 1;
//右の子に伝播
tree[2*index_on_tree+1].I = mapping(tree[index_on_tree].delay,tree[2*index_on_tree+1].I);
tree[2*index_on_tree+1].delay = composition(tree[index_on_tree].delay, tree[2*index_on_tree+1].delay);
tree[2*index_on_tree+1].is_delay = 1;
tree[index_on_tree].is_delay = 0;//最後に自分の遅延情報を消す。
tree[index_on_tree].delay = id;
}
deque<int> lazy_node;//区間集計、区間更新に使う。
deque<int> lazy_node_flipped;//区間更新で使う。
/// @brief index閉区間[L,R]において、集計を行う。
/// @param L 左端(左端を含む)
/// @param R 右端(右端を含む)
/// @return [L,R]での集計結果
info range_get(const int &L, const int &R){
int Lstart = L + (1<<log2N);
int Rstart = R+1 + (1<<log2N);
int lm = (Lstart / (Lstart & -Lstart)) >> 1;
int rm = (Rstart / (Rstart & -Rstart)) >> 1;
while (Lstart < Rstart){
if (Rstart <= rm){
lazy_node.push_back(Rstart);
}
if (Lstart <= lm){
lazy_node.push_back(Lstart);
}
Lstart >>= 1;
Rstart >>= 1;
}
while (Lstart){
lazy_node.push_back(Lstart);
Lstart >>=1;
}
while (!lazy_node.empty()){
tell_info(lazy_node.back());
lazy_node.pop_back();
}
info ret = e;
int left = L;
while (left < R+1){
int log2interval = min(__builtin_ctz(left),31-__builtin_clz(R+1-left));
ret = operation(ret, tree[(left+(1<<log2N))>>log2interval].I);
left += 1<<log2interval;
}
return ret;
}
/// @brief index閉区間[L,R]に対してFをmappingする。
/// @param L 左端(左端を含む)
/// @param R 右端(右端を含む)
/// @param F 適用する写像(アフィン変換ならaとbを持った構造体など)
void range_update(const int &L, const int &R, const func &F){
int Lstart = L + (1<<log2N);
int Rstart = R+1 + (1<<log2N);
int lm = (Lstart / (Lstart & -Lstart)) >> 1;
int rm = (Rstart / (Rstart & -Rstart)) >> 1;
while (Lstart < Rstart){
if (Rstart <= rm){
lazy_node.push_back(Rstart);
}
if (Lstart <= lm){
lazy_node.push_back(Lstart);
}
Lstart >>= 1;
Rstart >>= 1;
}
while (Lstart){
lazy_node.push_back(Lstart);
Lstart >>=1;
}
while (!lazy_node.empty()){
tell_info(lazy_node.back());
lazy_node_flipped.push_back(lazy_node.back());
lazy_node.pop_back();
}
int left = L;
while (left < R+1){
int log2interval = min(__builtin_ctz(left),31-__builtin_clz(R+1-left));
tree[(left+(1<<log2N))>>log2interval].I = mapping(F,tree[(left+(1<<log2N))>>log2interval].I);
tree[(left+(1<<log2N))>>log2interval].delay = composition(F,tree[(left+(1<<log2N))>>log2interval].delay);
tree[(left+(1<<log2N))>>log2interval].is_delay = 1;
left += 1<<log2interval;
}
while (!lazy_node_flipped.empty()){
if (lazy_node_flipped.back() >= (1<<log2N)){lazy_node_flipped.pop_back();continue;}
tree[lazy_node_flipped.back()].I = operation(tree[2*lazy_node_flipped.back()].I, tree[2*lazy_node_flipped.back()+1].I);
lazy_node_flipped.pop_back();
}
}
/// @brief 左端をLに固定したとき、条件式Gが成り立つ最小の右端indexを返す。もしなければINF(=2147483647)が返ってくる。
/// @attention 判定関数Gは、区間を広げていったときにfalse,false,false,...false,true,true,true...のように、falseが続いた後にtrueが続くものでなければならない。
/// @param L 左端
/// @param G 判定関数...引数a,bがあり、引数aを動かし、引数bを比較対象tに固定した時に引数aによってtrue,falseが変動する。
/// @param t 比較対象のinfo
/// @return Gがtrueになる最小右端indexまたは2147483647
int min_right(int L, const function<bool(info,info)> &G, const info &t){
info current_result = e;
int ctz_init = L == 0 ? log2N : __builtin_ctz(L);
for (int i = log2N; i > ctz_init; i--){
tell_info(((1<<log2N)+L)>>i);
}
checkpoint:
int ctz = L == 0 ? log2N : __builtin_ctz(L);
tell_info(((1<<log2N)+L)>>ctz);
if (!G(operation(current_result, tree[((1<<log2N)+L)>>ctz].I), t)){
if (tree[((1<<log2N)+L)>>ctz].range.second+1 == 1<<log2N){
return 2147483647;
}
current_result = operation(current_result, tree[((1<<log2N)+L)>>ctz].I);
L = tree[((1<<log2N)+L)>>ctz].range.second+1;
goto checkpoint;
}
for (int i = ctz-1; i >= 0; i--){
tell_info(((1<<log2N)+L)>>i);
if (!G(operation(current_result, tree[((1<<log2N)+L)>>i].I), t)){
current_result = operation(current_result, tree[((1<<log2N)+L)>>i].I);
L = tree[((1<<log2N)+L)>>i].range.second+1;
goto checkpoint;
}
}
return L;
}
/// @brief 右端をRに固定したとき、条件式Gが成り立つ最大の左端indexを返す。もしなければ-INF-1(=-2147483648)が返ってくる。
/// @attention 判定関数Gは、区間を広げていったときにfalse,false,false,...false,true,true,true...のように、falseが続いた後にtrueが続くものでなければならない。
/// @param R 右端
/// @param G 判定関数...引数a,bがあり、引数aを動かし、引数bを比較対象tに固定した時に引数aによってtrue,falseが変動するようなものである。
/// @param t 比較対象のinfo
/// @return Gがtrueになる最大左端indexまたは-2147483648
int max_left(int R, const function<bool(info,info)> &G, const info &t){
info current_result = e;
int cto_init = __builtin_ctz(~R);
for (int i = log2N; i > cto_init; i--){
tell_info(((1<<log2N)+R)>>i);
}
checkpoint:
int cto = __builtin_ctz(~R);//cto...count trailing one
tell_info(((1<<log2N)+R)>>cto);
if (!G(operation(current_result, tree[((1<<log2N)+R)>>cto].I), t)){
if (tree[((1<<log2N)+R)>>cto].range.first == 0){
return -2147483648;
}
current_result = operation(current_result, tree[((1<<log2N)+R)>>cto].I);
R = tree[((1<<log2N)+R)>>cto].range.first-1;
goto checkpoint;
}
for (int i = cto-1; i >= 0; i--){
tell_info(((1<<log2N)+R)>>i);
if (!G(operation(current_result, tree[((1<<log2N)+R)>>i].I), t)){
current_result = operation(current_result, tree[((1<<log2N)+R)>>i].I);
R = tree[((1<<log2N)+R)>>i].range.first-1;
goto checkpoint;
}
}
return R;
}
};
///Trie.hpp
/// @brief ただのTrie木
struct Trie{
struct TrieNode{
char c;//このノードの文字
bool forbidden = false;//禁止されたかどうか
ll stringnum = 0;//何文字分このノードで終わっているか。
unordered_map<char,TrieNode*> child;//子ノードへの参照
TrieNode(char d, ll n){
c = d;
stringnum = n;
}
TrieNode(){}
};
TrieNode root;//trie木の根。文字を持たない('.'を持っている)
Trie(){
root = TrieNode('.', 0);
}
/// @brief 文字列を追加する。追加しようとしたけどダメだったらfalseが返ってくる。
/// @param S
/// @return 追加できたか。
bool addstring(const string &S){
TrieNode *N = &root;
for (ll i = 0; i < S.size(); i++){
if (N->child.count(S[i])){
if (N->child[S[i]]->forbidden){
return false;
}
}
else{
N->child[S[i]] = new TrieNode(S[i],0);
}
if (i == S.size()-1){
N->child[S[i]]->stringnum++;
}
N = N->child[S[i]];
}
return true;
}
/// @brief 接頭辞Sを禁止する。
/// @param S
/// @return 禁止によっていくつの文字が消えたか。
ll forbid(const string &S){
TrieNode *N = &root;
for (ll i = 0; i < S.size(); i++){
if (N->child.count(S[i])){
if (N->child[S[i]]->forbidden){
return 0;
}
}
else{
N->child[S[i]] = new TrieNode(S[i],0);
}
if (i == S.size()-1){
N->child[S[i]]->forbidden = true;
}
N = N->child[S[i]];
}
ll forbidden_string = 0;//DFSでこれより下を全部禁止する
deque<TrieNode*> Q;
Q.push_back(N);
while (!Q.empty()){
TrieNode *node = Q.back();
Q.pop_back();
forbidden_string += node->stringnum;
for (auto v : node->child){
Q.push_back(v.second);
}
}
N->child.clear();
N->stringnum = 0;
return forbidden_string;
}
};
///
}
namespace graph{
//Graph.hpp
struct NoWeightGraph{
ll N;//頂点数
vector<vector<ll>> Edge;//隣接頂点リスト(重みなし)
vector<vector<ll>> D;//直近のBFSで求めた距離リスト。距離のほかに、これを踏む前にどこにいたかも記録してある。{距離, 一個前}
/// @brief 頂点,辺数を指定して自動で入力を受け取ってグラフを構築する
/// @param vertex_num
/// @param edge_num
/// @param directional
NoWeightGraph(ll vertex_num, ll edge_num, bool directional = false){
N = vertex_num;
Edge = vector<vector<ll>>(N+1);
for (ll i = 0; i < edge_num; i++){
ll u,v;
cin >> u >> v;
Edge[u].push_back(v);
if (!directional){
Edge[v].push_back(u);
}
}
}
/// @brief 頂点数を指定して辺のないグラフを構築
/// @param vertex_num
NoWeightGraph(ll vertex_num){
N = vertex_num;
Edge = vector<vector<ll>>(N+1);
}
/// @brief 事前に作った隣接頂点リストでグラフを構築
/// @attention 隣接頂点リストは1-indexedで作る必要がある。
/// @param E
NoWeightGraph(const vector<vector<ll>> &E){
N = E.size()-1;
Edge = E;
}
void add_edge(ll u, ll v, bool directional = false){
Edge[u].push_back(v);
if (!directional){
Edge[v].push_back(u);
}
}
/// @brief 始点を指定し、そこからの距離と、それを実現するためのパス復元用の情報を持ったリストを作成する。
/// @param startpoints
/// @return
vector<vector<ll>> BFS(const vector<ll> &startpoints){
queue<ll> Q;
D = vector<vector<ll>>(N+1,{9223372036854775807, -2});//-2...まだ到達してない, -1...始点, それ以外...一個前の頂点
for (auto v : startpoints){
D[v] = {0, -1};
Q.push(v);
}
while (!Q.empty()){
ll now = Q.front();
Q.pop();
for (auto v : Edge[now]){
if (D[v][1] == -2){
D[v][0] = D[now][0] + 1;
D[v][1] = now;
Q.push(v);
}
}
}
return D;
}
/// @brief 頂点gにたどり着くためのパスを求める。ないなら空のリストが返ってくる
/// @param g
/// @return
vector<ll> path(ll g){
vector<ll> R;
if (D[g][1] == -2){return R;}
while (D[g][1] != -1){
R.push_back(g);
g = D[g][1];
}
R.push_back(g);
reverse(vall(R));
return R;
}
void scc_dfs(vector<vector<ll>> &E, ll now, vector<bool> &used, ll &temp, vector<pair<ll,ll>> &order){
for (auto v : E[now]){
if (used[v]){continue;}
used[v] = true;
scc_dfs(E,v,used,temp,order);
}
order[now].second = temp;
temp++;
}
vector<vector<ll>> SCC(){
vector<vector<ll>> Edge_inverse(N+1);//辺が逆のグラフ
for (ll i = 1; i <= N; i++){
for (auto v : Edge[i]){
Edge_inverse[v].push_back(i);
}
}
ll temp = 1;
vector<bool> used(N+1,0);
vector<pair<ll,ll>> order(N+1);
for (ll i = 1; i <= N; i++){
order[i].first = i;
}
for (ll i = 1; i <= N; i++){
if (!used[i]){
used[i] = true;
scc_dfs(Edge,i,used,temp,order);//一回目のdfsで、帰った順番を記録
}
}
sort(vall(order), [](const pair<ll,ll> &a, const pair<ll,ll> &b){return a.second > b.second;});
order.pop_back();
temp = 1;
vector<ll> groups(N+1,-1);
for (ll i = 0; i < N; i++){
if (groups[order[i].first] == -1){//2回目のBFSで連結成分ごとに分解して、番号をつける
queue<ll> Q;
Q.push(order[i].first);
groups[order[i].first] = temp;
while (!Q.empty()){
ll now = Q.front();
Q.pop();
for (auto v : Edge_inverse[now]){
if (groups[v] == -1){
groups[v] = temp;
Q.push(v);
}
}
}
temp++;
}
}
vector<vector<ll>> small_graph(temp);//縮約されたグラフを構築
for (ll i = 1; i <= N; i++){
for (auto v : Edge[i]){
if (groups[i] != groups[v]){
small_graph[groups[i]].push_back(groups[v]);
}
}
}
vector<ll> into_count(temp,0);//入ってくる辺の数を管理
priority_queue<ll,vector<ll>,greater<ll>> pQ;//入ってくる辺がないような頂点を管理
vector<ll> topological_sort;
for (auto &vec : small_graph){
sort(vall(vec));
vec.erase(unique(vall(vec)),vec.end());
for (auto v : vec){
into_count[v]++;
}
}
for (ll i = 1; i < temp; i++){
if (into_count[i] == 0){
pQ.push(i);
}
}
while (!pQ.empty()){
ll now = pQ.top();
pQ.pop();
topological_sort.push_back(now);
for (auto v : small_graph[now]){
into_count[v]--;
if (into_count[v] == 0){
pQ.push(v);
}
}
}
vector<ll> inv_topological_sort(temp);
for (ll i = 1; i < temp; i++){
inv_topological_sort[topological_sort[i-1]] = i;
}
vector<vector<ll>> ans(temp-1);
for (ll i = 1; i <= N; i++){
ans[inv_topological_sort[groups[i]]-1].push_back(i);
}
return ans;
}
};
struct WeightedGraph{
ll N;
vector<vector<vector<ll>>> Edge;
vector<ll> D;//直近のDijkstraで求めた距離リスト
/// @brief 頂点,辺数を指定して自動で入力を受け取ってグラフを構築する
/// @param vertex_num
/// @param edge_num
/// @param directional
WeightedGraph(ll vertex_num, ll edge_num, bool directional = false){
N = vertex_num;
Edge = vector<vector<vector<ll>>>(N+1);
for (ll i = 0; i < edge_num; i++){
ll u,v,w;
cin >> u >> v >> w;
Edge[u].push_back({v,w});
if (!directional){
Edge[v].push_back({u,w});
}
}
}
/// @brief 頂点数を指定して辺のないグラフを構築
/// @param vertex_num
WeightedGraph(ll vertex_num){
N = vertex_num;
Edge = vector<vector<vector<ll>>>(N+1);
}
/// @brief 事前に作った隣接頂点リストでグラフを構築
/// @param E
WeightedGraph(const vector<vector<vector<ll>>> &E){
N = E.size()-1;
Edge = E;
}
void add_edge(ll u, ll v, ll w, bool directional = false){
Edge[u].push_back({v,w});
if (!directional){
Edge[v].push_back({v,w});
}
}
vector<ll> Djikstra(const vector<ll> &startpoints){
vector<bool> visited(N+1,0);
D = vector<ll>(N+1,9223372036854775807);
priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>> pQ;
for (auto v : startpoints){
pQ.push({0,v});
}
while (!pQ.empty()){
ll dist = pQ.top()[0];
ll now = pQ.top()[1];
pQ.pop();
if (visited[now]){continue;}
visited[now] = 1;
D[now] = dist;
for (auto v : Edge[now]){
if (visited[v[0]]){continue;}
pQ.push({dist+v[1], v[0]});
}
}
return D;
}
};
struct Tree{
ll N;//頂点数
vector<vector<vector<ll>>> Edge;//隣接頂点リスト
vector<vector<ll>> D;//直近のBFSで求めた距離リスト。距離のほかに、これを踏む前にどこにいたかも記録してある。{距離, 一個前}
vector<vector<vector<ll>>> lca_doubling_table;//lcaを求めるためのダブリング表。頂点1を根とする。{どこに行ったか, そこに行くのにかかったコスト}
vector<ll> lca_depth;//lcaを求めるための各頂点の深さ表。
/// @brief 頂点数,重みありかなしかを指定して自動で入力を受け取ってグラフを構築する。
/// @param vertex_num
/// @param weighted
Tree(ll vertex_num, bool weighted = false){
N = vertex_num;
Edge = vector<vector<vector<ll>>>(N+1);
for (ll i = 0; i < N-1; i++){
ll u,v,w;
if (weighted){
cin >> u >> v >> w;
}
else{
cin >> u >> v;
w = 1;
}
Edge[u].push_back({v,w});
Edge[v].push_back({u,w});
}
}
/// @brief 事前に作った隣接頂点リストでグラフを構築。重みも入力する必要がある。{行先, 重み}
/// @attention 1-indexedであり、辺はちょうど(頂点数-1)でなければならない
/// @param E
Tree(const vector<vector<vector<ll>>> &E){
N = E.size()-1;
Edge = E;
}
/// @brief 始点を指定し、そこからの距離と、それを実現するためのパス復元用の情報を持ったリストを作成する
/// @param startpoints
/// @return
vector<vector<ll>> BFS(const vector<ll> &startpoints){
queue<ll> Q;
D = vector<vector<ll>>(N+1,{9223372036854775807, -2});//-2...まだ到達してない, -1...始点, それ以外...一個前の頂点
for (auto v : startpoints){
D[v] = {0, -1};
Q.push(v);
}
while (!Q.empty()){
ll now = Q.front();
Q.pop();
for (auto v : Edge[now]){
if (D[v[0]][1] == -2){
D[v[0]][0] = D[now][0] + v[1];
D[v[0]][1] = now;
Q.push(v[0]);
}
}
}
return D;
}
/// @brief 頂点gにたどり着くためのパスを求める。ないなら空のリストが返ってくる
/// @param g
/// @return
vector<int> path(ll g){
vector<int> R;
if (D[g][1] == -2){return R;}
while (D[g][1] != -1){
R.emplace_back(g);
g = D[g][1];
}
R.push_back(g);
reverse(vall(R));
return R;
}
/// @brief 木の直径とそのパスを求める
/// @return 木の直径の両端を結ぶパスを求める
pair<ll,vector<int>> diameter(){
BFS({1});
ll farthest1 = -1;
ll dist1 = -1;
for (ll i = 1; i <= N; i++){
if (dist1 <= D[i][0]){
farthest1 = i;
dist1 = D[i][0];
}
}
BFS({farthest1});
ll farthest2 = -1;
ll dist2 = -1;
for (ll i = 1; i <= N; i++){
if (dist2 <= D[i][0]){
farthest2 = i;
dist2 = D[i][0];
}
}
return make_pair(dist2, path(farthest2));
}
/// @brief ダブリングテーブルを初期化する
void doubling_init(){
ll M = 1+log2l(N);
lca_doubling_table = vector<vector<vector<ll>>> (N+1, vector<vector<ll>>(M+1,vector<ll>(2,-1)));
lca_depth = vector<ll>(N+1,0);
queue<ll> Q;
vector<bool> used(N+1,0);
Q.push(1);
used[1] = 1;
lca_depth[1] = 0;
while (!Q.empty()){
ll now = Q.front();
Q.pop();
for (auto &v : Edge[now]){
if (used[v[0]]){continue;}
used[v[0]] = 1;
lca_depth[v[0]] = lca_depth[now]+1;
lca_doubling_table[v[0]][0] = {now, v[1]};
Q.push(v[0]);
}
}
for (ll b = 1; b <= M; b++){
for (ll i = 1; i <= N; i++){
if (lca_doubling_table[i][b-1][0] == -1){//2^(b-1)個上がない
lca_doubling_table[i][b] = {-1,-1};
}
else if (lca_doubling_table[lca_doubling_table[i][b-1][0]][b-1][0] == -1){//2^(b-1)個上はあるが、そのさらに2^(b-1)個上がない
lca_doubling_table[i][b] = {-1,-1};
}
else{
lca_doubling_table[i][b][0] = lca_doubling_table[lca_doubling_table[i][b-1][0]][b-1][0];
lca_doubling_table[i][b][1] = lca_doubling_table[i][b-1][1] + lca_doubling_table[lca_doubling_table[i][b-1][0]][b-1][1];
}
}
}
}
ll path_length(ll u, ll v){
ll length = 0;
if (lca_depth[u] < lca_depth[v]) swap(u,v);
ll s = lca_depth[u] - lca_depth[v];
ll t = 0;
while (s){
if (s%2){
length += lca_doubling_table[u][t][1];
u = lca_doubling_table[u][t][0];
}
t++;
s >>= 1;
}
ll r = lca_doubling_table[0].size()-1;
while (u != v){
if (r > 0 && lca_doubling_table[u][r][0] == lca_doubling_table[v][r][0]){
r--;
}
else{
length += lca_doubling_table[u][r][1] + lca_doubling_table[v][r][1];
u = lca_doubling_table[u][r][0];
v = lca_doubling_table[v][r][0];
}
}
return length;
}
ll lca(ll u, ll v){
if (lca_depth[u] < lca_depth[v]) swap(u,v);
ll s = lca_depth[u] - lca_depth[v];
ll t = 0;
while (s){
if (s%2){
u = lca_doubling_table[u][t][0];
}
t++;
s >>= 1;
}
ll r = lca_doubling_table[0].size()-1;
while (u != v){
if (r > 0 && lca_doubling_table[u][r][0] == lca_doubling_table[v][r][0]){
r--;
}
else{
u = lca_doubling_table[u][r][0];
v = lca_doubling_table[v][r][0];
}
}
return u;
}
vector<ll> pathbetween(ll u, ll v){
return {};
}
};
//UnionFind.hpp
/// @brief UnionFind木
/// @tparam nodeinfo
template<typename nodeinfo>
struct UnionFind{
vector<int> A;//根でないとき、どう辿れば根になるか(すでに根なら-1×(要素数))
int groups;//連結成分数
vector<nodeinfo> B;//各根に載っている状態を保存する。
function<void(nodeinfo&, nodeinfo)> merge_info;//異なる連結成分をマージするときの関数
function<void(nodeinfo&)> modify_info;//同一連結成分内に対する操作を行う関数
/// @brief 頂点番号が(0,)1,2...NのUnionFind木を構築する。全部同一の状態で初期化される
/// @param N 頂点数の上限
/// @param e
/// @param one_indexed 1-indexedかどうか
UnionFind(const int &N, const nodeinfo &init, function<void(nodeinfo&, nodeinfo)> mergefunc, function<void(nodeinfo&)> modifyfunc, bool one_indexed = true): A(N+1,-1), groups(one_indexed ? N : N+1), B(N+1, init), merge_info(mergefunc), modify_info(modifyfunc){}
/// @brief nodeの親を見つける
/// @param node
/// @return root
int findroot(int node){
while (A[node] >= 0){
node = A[node];
}
return node;
}
/// @brief node以上のノードをすべてrootに直接接続する
/// @param node
/// @param root
void compress_path(int node, const int &root){
int temp = node;
while (A[temp] >= 0){
temp = A[temp];
A[node] = root;
node = temp;
}
}
/// @brief 二つのノードが同じグループであるかを返す
/// @param node1
/// @param node2
/// @return true/false
bool same_group(int node1, int node2){
int root1 = findroot(node1);
int root2 = findroot(node2);
compress_path(node1, root1);
compress_path(node2, root2);
return root1 == root2;//判定
}
/// @brief node1を含むグループの根が持っている情報を返す。
/// @param node1
/// @return
int howmanynodes(int node1){
int root1 = findroot(node1);
compress_path(node1,root1);
return B[root1];
}
/// @brief node1とnode2を含む2つのグループを合成する。すでに同じなら何もしない。
/// @param node1
/// @param node2
void merge(int node1, int node2){
int root1 = findroot(node1);
int root2 = findroot(node2);
if (root1 == root2){
modify_info(B[root1]);
return;
}
groups--;
if (-A[root1] > -A[root2]){
A[root1] += A[root2];
A[root2] = root1;
merge_info(B[root1], B[root2]);
}
else{
A[root2] += A[root1];
A[root1] = root2;
merge_info(B[root2], B[root1]);
}
}
/// @brief 連結成分ごとに分解し、各成分に属する頂点をまとめたリストを作成する。
/// @param one_indexed 1-indexedかどうか(デフォルトで1-indexed)
/// @return
vector<vector<int>> connected_groups(bool one_indexed = true){
unordered_map<int,vector<int>> B;//仮の答え保存用
vector<int> C(A.size(),-1);//どの連結成分にいるかを管理
for (int i = one_indexed, sz = A.size(); i <= sz-1; i++){
if (A[i] < 0){
B[i].push_back(i);
C[i] = i;
}
}
vector<int> passed_node;//たどっている途中の頂点を保持するスタック
for (int i = one_indexed, sz = A.size(); i <= sz-1; i++){
if (C[i] != -1){
continue;
}
int temp = i;
while (C[temp] == -1){
passed_node.push_back(temp);
temp = A[temp];
}
vector<int> &temp2 = B[C[temp]];
while (!passed_node.empty()){
temp2.push_back(passed_node.back());
C[passed_node.back()] = C[temp];
passed_node.pop_back();
}
}
vector<vector<int>> ret;
for (auto &pvec : B){
ret.push_back(pvec.second);
}
return ret;
}
};
}
namespace string_algorithm{
//kmp_search.hpp
/// @brief kmp_searchに使うスキップテーブルを作成
vector<int> create_partial_match_table(const string &t){
vector<int> table(t.size(),0);
table[0] = -1;
ll j = -1;
for (ll i = 0; i < t.size()-1; i++){
while (j >= 0 && t[i] != t[j]){
j = table[j];
}
table[i+1] = j+1;
j++;
}
return table;
}
/// @brief sの中にtが含まれているかを判定し、あるなら最初に現れる位置を求める
/// @param s
/// @param t
/// @return
int kmp_search(const string &s, const string &t){
auto table = create_partial_match_table(t);
int i = 0, j = 0;
while (i+j < s.size()){
if (s[i+j] == t[j]){
j++;
if (j == t.size()){
return i;
}
}
else{
i = i+j-table[j];
if (j > 0){
j = table[j];
}
}
}
return -1;
}
//rolling_hash.hpp
/// @brief ローリングハッシュの作成、接続など
struct rolling_hash{
__int128_t safe_modpow(__int128_t x, __int128_t n, __int128_t m){
__int128_t r = 1;
x %= m;
if (n){
while (n){
if (n%2){
r *= x;
r %= m;
}
x *= x;
x %= m;
n >>= 1;
}
return r;
}
return 1;
}
pair<__int128_t, __int128_t> lllaxby1(__int128_t a, __int128_t b){
if (a == 1 or b == 1){
if (a == 1){
return {1-b,1};
}
else{
return {1,1-a};
}
}
else if (a>b){
auto p = lllaxby1(a%b, b);
return {p.first, p.second - p.first*(a/b)};
}
else{
swap(a,b);
auto p = lllaxby1(a%b, b);
return {p.second - p.first*(a/b), p.first};
}
}
random_device rd__;
uniform_int_distribution<int> ui1__;
uniform_int_distribution<int> ui2__;
__int128_t B;
__int128_t Binv;
__int128_t R = 1;
vector<__int128_t> alphabet_to_ll;
/// @brief ローリングハッシュライブラリを初期化
rolling_hash(){
mt19937 gen__(rd__());
ui1__ = uniform_int_distribution(134217728, 2147483647);
ui2__ = uniform_int_distribution(1, 2147483647);
//Rが2冪にならないように乱数で初期化
while ((1ll<<(63-__builtin_clzll((ll)R))) == (ll)R){
R = (((ll)ui1__(gen__))<<30) + ui2__(gen__);
}
B = R;
//BをRと互いに素になるように乱数で初期化
while (__gcd(B,R) != 1){
B = (((ll)ui1__(gen__))<<30) + ui2__(gen__);
}
B %= R;
Binv = (R+(lllaxby1(B,R).first)%R)%R;
set<ll> temp;
while (temp.size() < 58){
temp.insert(ui2__(gen__));
}
for (auto &v : temp){
alphabet_to_ll.push_back(v);
}
shuffle(vall(alphabet_to_ll), gen__);
}
/// @brief 文字列Sにおいて、indexが0以上i以下の部分文字列のローリングハッシュを生成する。
/// @param S
/// @return ローリングハッシュを記録した配列
vector<__int128_t> gen_hash(const string &S){
vector<__int128_t> r(S.size());
r[0] = alphabet_to_ll[S[0]-97];
__int128_t temp = B;
for (ll i = 1; i < S.size(); i++){
r[i] = r[i-1] + (alphabet_to_ll[S[i]-97]*temp)%R;
r[i] %= R;
temp *= B;
temp %= R;
}
return r;
}
/// @brief l以上r以下の部分文字列のハッシュを生成する。
/// @param l
/// @param r
/// @return [l,r]のハッシュ
ll get_hash(const vector<__int128_t> &hs, const int &l, const int &r){
__int128_t ret = hs[r] - (l == 0 ? 0 : hs[l-1]);
ret += R;
ret %= R;
ret = (ret*safe_modpow(Binv, l, R))%R;
return ret;
}
/// @brief aのハッシュ、aの長さ、bのハッシュを用いてa+bのハッシュを生成する。
/// @param a
/// @param len_a
/// @param b
/// @return
ll connect_hash(const __int128_t &a, const int &len_a, const __int128_t &b){
return (a+(b*safe_modpow(B,len_a,R))%R)%R;
}
};
}
namespace general_algorithm{
/// @brief 累積和を作成する
template<typename T>
vector<T> cumulative_sum(vector<T> A){
for (ll i = 1, sz = A.size(); i < sz; i++){
A[i] += A[i-1];
}
return A;
}
//RLE.hpp
/// @brief AをRLEした結果を返す。{{何が, 何個}...}の形で返される。
/// @param A
/// @return
template<typename T>
vector<pair<T,ll>> RLEvec(const vector<T> &A){
vector<pair<T,ll>> R;
T previous = A[0];
ll combo = 0;
for (ll i = 0;;){
if (i == A.size()){
R.push_back({previous,combo});
break;
}
if (A[i] == previous){
combo++;
i++;
}
else{
R.push_back({previous, combo});
previous = A[i];
combo = 0;
}
}
return R;
}
/// @brief SをRLEした結果を返す。{{何が, 何個}...}の形で返される。
/// @param A
/// @return
vector<pair<char,ll>> RLEstr(const string &S){
vector<pair<char,ll>> R;
char previous = S[0];
ll combo = 0;
for (ll i = 0;;){
if (i == S.size()){
R.push_back({previous,combo});
break;
}
if (S[i] == previous){
combo++;
i++;
}
else{
R.push_back({previous, combo});
previous = S[i];
combo = 0;
}
}
return R;
}
//LIS.hpp
/// @brief 最長増加部分列（LIS）の長さを返します
/// @tparam Strict 狭義単調増加の場合 true, 広義単調増加の場合 false
/// @tparam Type 数列の要素の型
/// @param v 数列
/// @return 最長増加部分列（LIS）の長さ
/// @note 1.2 最長増加部分列の長さの取得
/// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/lis
template <bool Strict, class Type>
size_t LIS_length(const std::vector<Type>& v){
std::vector<Type> dp;
auto it = dp.begin();
for (const auto& elem : v)
{
if constexpr (Strict)
{
it = std::lower_bound(dp.begin(), dp.end(), elem);
}
else
{
it = std::upper_bound(dp.begin(), dp.end(), elem);
}
if (it == dp.end())
{
dp.push_back(elem);
}
else
{
*it = elem;
}
}
return dp.size();
}
/// @brief 最長増加部分列（LIS）のインデックスを返します
/// @tparam Strict 狭義単調増加の場合 true, 広義単調増加の場合 false
/// @tparam Type 数列の要素の型
/// @param v 数列
/// @return 最長増加部分列（LIS）のインデックス
/// @note 1.4 最長増加部分列の復元
/// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/lis
template <bool Strict, class Type>
std::vector<int> LIS_construction(const std::vector<Type>& v)
{
std::vector<Type> dp;
auto it = dp.begin();
std::vector<int> positions;
for (const auto& elem : v)
{
if constexpr (Strict)
{
it = std::lower_bound(dp.begin(), dp.end(), elem);
}
else
{
it = std::upper_bound(dp.begin(), dp.end(), elem);
}
positions.push_back(static_cast<int>(it - dp.begin()));
if (it == dp.end())
{
dp.push_back(elem);
}
else
{
*it = elem;
}
}
std::vector<int> subseq(dp.size());
int si = static_cast<int>(subseq.size()) - 1;
int pi = static_cast<int>(positions.size()) - 1;
while ((0 <= si) && (0 <= pi))
{
if (positions[pi] == si)
{
subseq[si] = pi;
--si;
}
--pi;
}
return subseq;
}
//all_direction_treedp.hpp
//全方位木DP用の構造体
struct treedpinfo{
ll farthest_vertex = -1;
ll dist = -1;
};
//いくつかの部分木の情報をまとめる
treedpinfo merge_operation(const treedpinfo &a, const treedpinfo &b){
if (a.dist == b.dist){
if (a.farthest_vertex > b.farthest_vertex){
return a;
}
return b;
}
else{
if (a.dist > b.dist){
return a;
}
return b;
}
}
//一個下の部分木の情報をもとに次の頂点に更新する
treedpinfo update_operation(treedpinfo a){
a.dist++;
return a;
}
/// @brief 木DP
/// @param E 隣接頂点リスト
/// @param dp dp配列
/// @param used 訪問記録
/// @param now 今いる場所
/// @param eee dp情報の単位元
void dfs_dp(vector<vector<ll>> &E, vector<treedpinfo> &dp, vector<bool> &used, ll now, treedpinfo &eee){
used[now] = 1;
if (E[now].empty() || (E[now].size() == 1 && now != 1)){
//葉の状態は自分で書く。
dp[now].farthest_vertex = now;
dp[now].dist = 0;
return;
}
treedpinfo r = eee;
for (auto v : E[now]){
if (used[v]){continue;}
dfs_dp(E,dp,used,v,eee);
r = merge_operation(r,dp[v]);
}
dp[now] = update_operation(r);
}
/// @brief 全方位木DP
/// @param E 隣接頂点リスト
/// @param dp 木dpで求めたdp配列
/// @param used 訪問済みリスト(初期化済み)
/// @param now 今いる場所
/// @param from_parent 親からの伝達情報
void dfs_rerooting(vector<vector<ll>> &E, vector<treedpinfo> &dp, vector<bool> &used, ll now, treedpinfo from_parent){
used[now] = 1;
if (E[now].empty() || (E[now].size() == 1 && now != 1)){return;}
ll child_num = 0;
vector<ll> child_index;
for (auto v : E[now]){
if (used[v]){continue;}
child_index.push_back(v);
child_num++;
}
if (child_num == 1){
dp[child_index[0]] = merge_operation(dp[child_index[0]],update_operation(from_parent));
dfs_rerooting(E,dp,used,child_index[0],update_operation(from_parent));
return;
}
vector<treedpinfo> left_ruiseki(child_num);
left_ruiseki.front() = dp[child_index.front()];
vector<treedpinfo> right_ruiseki(child_num);
right_ruiseki.back() = dp[child_index.back()];
for (ll i = 1; i < child_num; i++){
left_ruiseki[i] = merge_operation(left_ruiseki[i-1], dp[child_index[i]]);
right_ruiseki[child_num-i-1] = merge_operation(right_ruiseki[child_num-i], dp[child_index[child_num-i-1]]);
}
for (ll i = 0; i < child_num; i++){
if (i == 0){
auto temp = update_operation(merge_operation(update_operation(right_ruiseki[i+1]),from_parent));
dp[child_index[i]] = merge_operation(dp[child_index[i]],temp);
dfs_rerooting(E,dp,used,child_index[i],temp);
}
else if (i == child_num-1){
auto temp = update_operation(merge_operation(update_operation(left_ruiseki[i-1]),from_parent));
dp[child_index[i]] = merge_operation(dp[child_index[i]],temp);
dfs_rerooting(E,dp,used,child_index[i],temp);
}
else{
auto temp = update_operation(merge_operation(update_operation(merge_operation(left_ruiseki[i-1],right_ruiseki[i+1])),from_parent));
dp[child_index[i]] = merge_operation(dp[child_index[i]],temp);
dfs_rerooting(E,dp,used,child_index[i],temp);
}
}
}
}
}
using namespace a1073741824;
ll f(char c){
if (c == 'A'){
return 1;
}
if (c == 'B'){
return -1;
}
if (c == 'C'){
return 0;
}
return 0;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll N;
cin >> N;
string S;
cin >> S;
vector<ll> A(N+1,0);
for (ll i = 1; i <= N; i++){
A[i] = A[i-1] + f(S[i-1]);
}
tree_datastructure::FenwickTree T(1000003,0);
ll ans = 0;
for (ll i = N; i >= 0; i--){
A[i] += 500000;
ans += T.range_sum(A[i]+1,1000002);
T.update(A[i],1,1);
}
cout << ans << "\n";
}
Submission Info
Submission Time
2026-01-17 21:35:54+0900
Task
E - A > B substring
User
a1073741824
Language
C++23 (GCC 15.2.0)
Score
450
Code Size
151232 Byte
Status
AC
Exec Time
171 ms
Memory
24376 KiB
Compile Error
./Main.cpp: In function 'void a1073741824::math::search_divisor(std::vector<long long int>&, std::vector<std::vector<long long int> >&, ll)':
./Main.cpp:1988:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
1988 | if (depth == p.size()){
| ~~~~~~^~~~~~~~~~~
./Main.cpp: In function 'std::vector<long long int> a1073741824::math::convolution998244353(std::vector<long long int>, std::vector<long long int>)':
./Main.cpp:2599:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2599 | for (int i = 0; i < A.size(); i++) {
| ~~^~~~~~~~~~
./Main.cpp:2600:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2600 | for (int j = 0; j < B.size(); j++) {
| ~~^~~~~~~~~~
./Main.cpp:2616:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
2616 | while (A.size() < (1LL<<log2N)){
| ~~~~~~~~~^~~~~~~~~~~~~~
./Main.cpp:2619:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
2619 | while (B.size() < (1LL<<log2N)){
| ~~~~~~~~~^~~~~~~~~~~~~~
./Main.cpp: In function 'std::vector<long long int> a1073741824::math::convolution1224736769(std::vector<long long int>, std::vector<long long int>)':
./Main.cpp:2643:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2643 | for (int i = 0; i < A.size(); i++) {
| ~~^~~~~~~~~~
./Main.cpp:2644:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2644 | for (int j = 0; j < B.size(); j++) {
| ~~^~~~~~~~~~
./Main.cpp:2660:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
2660 | while (A.size() < (1LL<<log2N)){
| ~~~~~~~~~^~~~~~~~~~~~~~
./Main.cpp:2663:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
2663 | while (B.size() < (1LL<<log2N)){
| ~~~~~~~~~^~~~~~~~~~~~~~
./Main.cpp: In member function 'void a1073741824::tree_datastructure::FenwickTree::fill_tree(std::vector<long long int>&, ll, ll, ll)':
./Main.cpp:2691:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and '__gnu_cxx::__alloc_traits<std::allocator<long long unsigned int>, long long unsigned int>::value_type' {aka 'long long unsigned int'} [-Wsign-compare]
2691 | if (index >= pow2ll[log2N]){return;}
./Main.cpp: In constructor 'a1073741824::tree_datastructure::FenwickTree::FenwickTree(ll, ll)':
./Main.cpp:2704:30: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long unsigned int>, long long unsigned int>::value_type' {aka 'long long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
2704 | while (pow2ll[log2N] < howmany){
./Main.cpp: In constructor 'a1073741824::tree_datastructure::FenwickTree::FenwickTree(ll, std::vector<long long int>&)':
./Main.cpp:2716:30: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long unsigned int>, long long unsigned int>::value_type' {aka 'long long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
2716 | while (pow2ll[log2N] < howmany){
./Main.cpp:2721:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and '__gnu_cxx::__alloc_traits<std::allocator<long long unsigned int>, long long unsigned int>::value_type' {aka 'long long unsigned int'} [-Wsign-compare]
2721 | for (ll i = 1; i < pow2ll[log2N]; i++){
./Main.cpp: In member function 'll a1073741824::tree_datastructure::FenwickTree::sum_from_origin(ll)':
./Main.cpp:2739:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and '__gnu_cxx::__alloc_traits<std::allocator<long long unsigned int>, long long unsigned int>::value_type' {aka 'long long unsigned int'} [-Wsign-compare]
2739 | if (index == pow2ll[log2N]){
./Main.cpp: In member function 'bool a1073741824::tree_datastructure::Trie::addstring(const std::string&)':
./Main.cpp:3338:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3338 | for (ll i = 0; i < S.size(); i++){
| ~~^~~~~~~~~~
./Main.cpp:3348:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3348 | if (i == S.size()-1){
| ~~^~~~~~~~~~~~~
./Main.cpp: In member function 'll a1073741824::tree_datastructure::Trie::forbid(const std::string&)':
./Main.cpp:3361:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3361 | for (ll i = 0; i < S.size(); i++){
| ~~^~~~~~~~~~
./Main.cpp:3371:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3371 | if (i == S.size()-1){
| ~~^~~~~~~~~~~~~
./Main.cpp: In member function 'std::vector<long long int> a1073741824::graph::Tree::pathbetween(ll, ll)':
./Main.cpp:3857:31: warning: unused parameter 'u' [-Wunused-parameter]
3857 | vector<ll> pathbetween(ll u, ll v){
| ~~~^
./Main.cpp:3857:37: warning: unused parameter 'v' [-Wunused-parameter]
3857 | vector<ll> pathbetween(ll u, ll v){
| ~~~^
./Main.cpp: In function 'std::vector<int> a1073741824::string_algorithm::create_partial_match_table(const std::string&)':
./Main.cpp:4001:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4001 | for (ll i = 0; i < t.size()-1; i++){
| ~~^~~~~~~~~~~~
./Main.cpp: In function 'int a1073741824::string_algorithm::kmp_search(const std::string&, const std::string&)':
./Main.cpp:4018:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4018 | while (i+j < s.size()){
| ~~~~^~~~~~~~~~
./Main.cpp:4021:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4021 | if (j == t.size()){
| ~~^~~~~~~~~~~
./Main.cpp: In member function 'std::vector<__int128> a1073741824::string_algorithm::rolling_hash::gen_hash(const std::string&)':
./Main.cpp:4120:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4120 | for (ll i = 1; i < S.size(); i++){
| ~~^~~~~~~~~~
./Main.cpp: In function 'std::vector<std::pair<char, long long int> > a1073741824::general_algorithm::RLEstr(const std::string&)':
./Main.cpp:4198:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4198 | if (i == S.size()){
| ~~^~~~~~~~~~~
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
450 / 450
Status
Set Name
Test Cases
Sample
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt
Case Name
Status
Exec Time
Memory
00_sample_00.txt
AC 10 ms
19656 KiB
00_sample_01.txt
AC 10 ms
19620 KiB
00_sample_02.txt
AC 10 ms
19780 KiB
01_random_03.txt
AC 164 ms
24208 KiB
01_random_04.txt
AC 165 ms
24168 KiB
01_random_05.txt
AC 164 ms
24168 KiB
01_random_06.txt
AC 164 ms
24244 KiB
01_random_07.txt
AC 164 ms
24264 KiB
01_random_08.txt
AC 165 ms
24368 KiB
01_random_09.txt
AC 164 ms
24220 KiB
01_random_10.txt
AC 165 ms
24256 KiB
01_random_11.txt
AC 165 ms
24376 KiB
01_random_12.txt
AC 165 ms
24248 KiB
01_random_13.txt
AC 164 ms
24260 KiB
01_random_14.txt
AC 164 ms
24212 KiB
01_random_15.txt
AC 165 ms
24136 KiB
01_random_16.txt
AC 136 ms
23368 KiB
01_random_17.txt
AC 97 ms
22456 KiB
01_random_18.txt
AC 78 ms
21708 KiB
01_random_19.txt
AC 75 ms
21628 KiB
01_random_20.txt
AC 86 ms
21980 KiB
01_random_21.txt
AC 106 ms
22548 KiB
01_random_22.txt
AC 56 ms
21084 KiB
01_random_23.txt
AC 56 ms
21064 KiB
01_random_24.txt
AC 171 ms
24216 KiB
01_random_25.txt
AC 165 ms
24244 KiB
01_random_26.txt
AC 167 ms
24220 KiB
01_random_27.txt
AC 167 ms
24328 KiB
01_random_28.txt
AC 167 ms
24320 KiB
01_random_29.txt
AC 167 ms
24212 KiB
01_random_30.txt
AC 168 ms
24244 KiB
01_random_31.txt
AC 163 ms
24372 KiB
01_random_32.txt
AC 10 ms
19620 KiB
01_random_33.txt
AC 10 ms
19676 KiB
01_random_34.txt
AC 10 ms
19624 KiB