初投稿&AtCoder入茶&入緑

## 目次
- [0. はじめに](#0はじめに)
- [1. 競技プログラミングを始めた理由](#1競技プログラミングを始めた理由)
- [2. 環境開発について](#2環境開発について)
- [3. 言語について](#3言語について)
- [4. 灰色(0~)から茶色(~400)までにしたこと](#4灰色0から茶色400までにしたこと)
- [5. 茶色(400~)から緑(~800)までにしたこと](#5茶色400から緑800までにしたこと)
- [6. まとめ&最後に](#6まとめ最後に)

---


## 0.はじめに
初めまして、大学一年生のKota1tです。今回、趣味で競技プログラミングをしている私が[AtCoder](https://atcoder.jp)で入緑をしたので、なぜ競技プログラミングを始めたのか、どのように入緑(入茶)したか、を書いていきます。初執筆で至らないところも多々あると思いますが、温かい目で見守っていただけると嬉しいです。
![スクリーンショット 2024-12-09 13.30.45.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3913380/519fa596-d1f7-b018-b610-afb86a9da3f0.png)


## 1.競技プログラミングを始めた理由
競技プログラミングやAtCoderについての紹介はここでは省略させてもらいます。
私が競技プログラミングを始めたきっかけは、大学合格後に入学前に与えられた課題の中に問題形式型のプログラミング課題です。私自身、大学入学以前はプログラミングをした事がなく(高校の授業を除く)全くの未経験でした。課題で使用した言語はJavaでしたが、そこで基本的なfor・ifなどの繰り返し処理や分岐処理を学びました。1月末、課題を一通り終わらせた頃、同級生がSNSでAtCoderのレート変動ツイートを見かけそこで競技プログラミングの存在を知りました。私が目を引いたのはAtCoder内にある**レーティング**システムでした。まるでゲームみたいに自分の強さ(?)が視覚化・数値化されていてとても興味を持ちました。
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">課題はよ終わらせて競プロしてみたい</p>&mdash; kota1t (@k0ta1t) <a href="https://twitter.com/k0ta1t/status/1750179308671533556?ref_src=twsrc%5Etfw">January 24, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

## 2.環境開発について
自分はM3 Macで競技プログラミングをしています。
初心者故に環境開発のことは全くわからず(Clang? gcc? なんやそれ...)かなり苦戦しました...
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">環境構築むずい</p>&mdash; kota1t (@k0ta1t) <a href="https://twitter.com/k0ta1t/status/1754054744308662539?ref_src=twsrc%5Etfw">February 4, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
結局大学の先輩に助けてもらいパスを通してもらいました(敗北) <br>
一応以下に参考にしたMacでの競プロ環境開発の記事の一覧です。

https://qiita.com/EvtHorizonCoder/items/145724e16c1b57ab64eb

https://zenn.dev/kotopasi/scraps/a1f4e7deb4fe4e

https://note.com/fuuuuusha/n/n9c16247c49bc

##

Windows環境であれば同大学の[sorachandu](https://qiita.com/sorachandu)氏の以下の記事がオススメです。

https://qiita.com/sorachandu/items/a06e4ed61d169ba067f3

(~~正直初学者であればオンラインエディタやAtCoder内のコードテストでも十分だと思ってます。~~)
環境開発はコーディングを行う上で最初の難関になると思うので頑張ってください

## 3.言語について
競技プログラミングを行う上で言語指定などは特にありませんが、主要な言語は<strong>C++</strong>と**Python**だと思います。特にこだわりがなければこの二つから(個人的にC++)選ぶことをおすすめします。
私はプログラミング課題でJavaを少ししていたので、静的言語に慣れていたのもあってC++を使うことにしました。(~~Pythonだと定数倍TLEするとかもあるらしい?~~)
AtCoder内にC++とPythonのAPG4bという競プロの学習教材?があるので、これをやるのをおすすめします。

https://atcoder.jp/contests/APG4b

https://atcoder.jp/contests/APG4bPython

## 4.灰色(0~)から茶色(~400)までにしたこと
　さてここからはAtCoder内でのAlgorithmレートを400(茶色)まで上げるために行ったいわゆる**精進**の内容を紹介します。茶色はコンテスト内で早解きで2問、もしくは3問解くことが安定できるレベルだと考えています。基本的にタイピングが遅いので私は後者の方で茶色になりました。
 ABCでは最初の2問(A問題とB問題)ではアルゴリズムを使用するというよりは正しく問題の意図を汲み取りその解法をコーディングできるかが重要になると思います。まずはA問題とB問題を安定して解けるまで過去のコンテストの問題を解くことをおすすめします。C++を利用している方ならstd::setとstd::mapを使えるようにしておくといろいろ便利だと思います。次にC問題を解くために覚えたアルゴリズムと構造体を以下に書きます。
1.二分探索
2.累積和
3.DP(動的計画法)
4.スタック
5.キュー
6.優先度付きキュー
7.deque
8.bit全探索
パッと挙げるとこれくらいでしょうか。覚えたといってもロジックを理解しただけで、まだどれも応用して使えるかと言われたらかなり怪しい状態でした。これらの内容は先に紹介した[APG4b](https://atcoder.jp/contests/APG4b)と「競技プログラミングの鉄則」という本を読みました。
あとはA問題とB問題を早く解く&C問題を解けるようにひたすら過去問を解きました。ここで余談ですがABCの過去問を見る際は以下のサイトをおすすめします。

https://kenkoooo.com/atcoder/#/table/

こうしてin茶することができました。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">kota1tさんのCodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)での成績：6183位<br>ぴったし入茶！！<br>💩💩💩💩<br>パフォーマンス：556相当<br>レーティング：379→400 (+21) :)<br>Highestを更新し、8 級になりました！<a href="https://twitter.com/hashtag/AtCoder?src=hash&amp;ref_src=twsrc%5Etfw">#AtCoder</a> <a href="https://twitter.com/hashtag/CodeQUEEN2024%E4%BA%88%E9%81%B8?src=hash&amp;ref_src=twsrc%5Etfw">#CodeQUEEN2024予選</a>(ABC358) <a href="https://t.co/5c6JqgcFtn">https://t.co/5c6JqgcFtn</a></p>&mdash; kota1t (@k0ta1t) <a href="https://twitter.com/k0ta1t/status/1801980739464089665?ref_src=twsrc%5Etfw">June 15, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="qme" dir="ltr">💩💩💩 <a href="https://t.co/OAvAhFWrFs">pic.twitter.com/OAvAhFWrFs</a></p>&mdash; kota1t (@k0ta1t) <a href="https://twitter.com/k0ta1t/status/1801980932880290141?ref_src=twsrc%5Etfw">June 15, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

(~~汚いな...~~)
入茶までにD問題が複数解けたのもあってかなりレートの伸びがよかったです。茶色までに4完すると一回のコンテストで+100貰えてレートがホクホクになりますね。
## 5.茶色(400~)から緑(~800)までにしたこと。
さてここからは入緑までにしたことを(精進)を話します。入緑するためには、先程の入茶までに求められていた問題数が一つ増えたと考えたらわかりやすいと思います。つまりABCで早解き3完(3問正解),もしくは4完することが安定できれば入緑はできると思います。C問題やD問題を安定して解くことが入緑までの鍵だと考えています。ここからは先ほど述べたアルゴリズムを理解し応用・活用することが大事です。主に以下のアルゴリズムはかなり重要だと考えます。
1.二分探索
2.累積和
3.DP(動的計画法)
4.DFS(深さ優先探索)
5.BFS(幅優先探索)
6.スライディングウィンドウ(尺取り法)
7.いもす法

これらの内容を理解し応用した形(bitDPやこれらの組み合わせ)などをコンテストの時間内に書くことが要求されると考えます。私はDPがあまり得意ではなかったので先ほどの鉄則本(競技プログラミングの鉄則)や[EDPC](https://atcoder.jp/contests/dp)で精進しました。(EDPCはあまりしてなかったかも...)
あとこのタイミングあたりで自分のコードのテンプレートができてきたりACLを使えるようにしたりなどライブラリ整理も若干行いました。
一応この記事の一番下に自分のテンプレ載せておきます...(あんまり綺麗ではないのと~~クソ~~長いです)

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">半年入緑しました。感謝 <a href="https://t.co/3CLwgUsXWN">pic.twitter.com/3CLwgUsXWN</a></p>&mdash; kota1t (@k0ta1t) <a href="https://twitter.com/k0ta1t/status/1837495773552169274?ref_src=twsrc%5Etfw">September 21, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

こうして競技プログラミングを始め半年ほどで入緑を果たすことができました。
真面目に取り組んでいる人からしたら少し遅いかもしれません。
## 6.まとめ&最後に
ここまで競技プログラミングを続けることができてなんだかんだよかったなという気持ちでした。競技プログラミングを始め、入緑まで頑張ったことは私の大学生活で数少ない打ち込めた物事でした。これからも続ける予定ですが一旦の目標は入水かなと思ってます。とにかく過去問をひたすらやり自分の苦手分野&知らないことをやるのがレートを上げるうえで重要だと思います。<strong>精進なくして成長なし!</strong>ですね。ここまでお読みいただき、誠にありがとうございます。拙い内容でしたがいかがだったでしょうか。今後もこういった記事を出してきたいと考えているのでその時は是非読んでくださると幸いです。ではまた

```c++:main.cpp
#if !__INCLUDE_LEVEL__
#include __FILE__
int main() {
    //ここに記入
    
}

#else
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, j, n) for (long long i = j; i < (long long)(n); i++)
#define REP(i, j, n) for (long long i = j; i <= (long long)(n); i++)
#define Rep(i, n) rep(i, 0, n)
#define RREP(i, n) REP(i, 0, n)
#define krep(i, j, n) for (long long i = j; i > (long long)(n); i--)
#define KREP(i, j, n) for (long long i = j; i >= (long long)(n); i--)
#define Krep(i, n) krep(i, n, 0)
#define KRep(i, n) KREP(i, n, 0)
#define wh while
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector<int>
#define vll vector<long long>
#define str string
#define vst vector<str>
#define el '\n'
#define spa ' '
#define Yes cout << "Yes" << el
#define No cout << "No" << el
#define YES cout << "YES" << el
#define NO cout << "NO" << el
#define cn continue
#define br cout << endl
#define rt1 return 1
#define rt0 return 0
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>

//  ~^ んぁ〜
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int inf = 1073741823;
const int MOD109 = 1e9 + 7;
const int MOD998 = 998244353;
const ll infl = 1LL << 60;
const string abc = "abcdefghijklmnopqrstuvwxyz";
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string a123 = "123456789";
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
    bool compare = (a < b);
    if (compare) a = b;
    return compare;
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
    bool compare = (a > b);
    if (compare) a = b;
    return compare;
}

ostream &operator<<(ostream &dest, __int128_t value) {
    ostream::sentry s(dest);
    if (s) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) {
            --d;
            *d = '-';
        }
        int len = end(buffer) - d;
        if (dest.rdbuf()->sputn(d, len) != len) {
            dest.setstate(ios_base::badbit);
        }
    }
    return dest;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) {
        os << v[i] << (i + 1 != (int)v.size() ? " " : "");
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end()) os << " ";
        itr--;
    }
    return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << itr->first << " -> " << itr->second << "\n";
    }
    return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

void out() { cout << '\n'; }
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
    cout << a;
    (cout << ... << (cout << ' ', b));
    cout << '\n';
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &in : v) is >> in;
    return is;
}

inline void in(void) { return; }
template <typename First, typename... Rest>
void in(First &first, Rest &...rest) {
    cin >> first;
    in(rest...);
    return;
}

string substrback(string s, size_t p, size_t l) {
    // s=文字列　p＝後ろから数えて何文字目　//l=pから何文字目
    const size_t strl = s.length();
    return s.substr(strl - p, l);
}
// pair型のfirstで比較
bool comparePairs(const pair<ll, ll> &a, const pair<ll, ll> &b) {
    // pairのfirstで比較し、同じであればsecondで比較する
    if (a.first != b.first) return a.first < b.first;
    return a.second < b.second;
}
// pair型のセカンドで比較
bool comparePairs2(const pair<ll, ll> &a, const pair<ll, ll> &b) {
    // pairのseondで比較し、同じであればfirstで比較する
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
}
// nの階乗
ull facto(ll n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * facto(n - 1);
    }
}
// nまでのΣ
ll sigma(ll n) {
    ull sum = 0;
    sum = n * (n + 1) / 2;
    return sum;
}
struct D3 {
    int A, B, index;
};
struct d3 {
    ll a, b, c;
};
// 回文チェック
bool isPalindrome(const string &stri) {
    if (stri.length() <= 1) return true;
    string reversedStr = stri;
    reverse(reversedStr.begin(), reversedStr.end());
    return stri == reversedStr;
}
bool compare(const D3 &a, const D3 &b) {
    if (a.A == b.A) {
        return a.B < b.B;  // Aが同じ場合、Bで昇順にソート
    }
    return a.A > b.A;  // Aで降順にソート
}
// 切り上げ
ll floor(ll x, ll m) {
    ll r = (x % m + m) % m;
    return (x - r) / m;
}
// 累乗
ll power(ll i, int j) {
    if (!j) return 1;
    if (j == 1) return i;

    ll ans = i;
    for (int u = 0; u < j - 1; u++) ans *= i;
    return ans;
}
bool isPrime(ll n) {
    if (n == 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}
struct point {
    double x, y;
};

struct segment {
    point p1, p2;
};

long long isqrt(long long x) {
    long long r = (long long)floor(sqrtl((long double)x));
    while ((r + 1) * (long long)(r + 1) <= x) r++;
    while (r * r > x) r--;
    return r;
}
double distance(const point &a, const point &b) {
    return hypot(a.x - b.x, a.y - b.y);
}

double printsegment(const point &a, const point &b, int T) {
    return distance(a, b) / T;
}

double movelaser(const point &a, const point &b, int S) {
    return distance(a, b) / S;
}
int64_t powmod(int64_t K, int64_t mod) {
    int64_t result = 1;
    int64_t base = 2 % mod;
    while (K > 0) {
        if (K & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        K >>= 1;
    }
    return result;
}

template <class T>
class BitVector {
   private:
    unsigned n, cur, p;
    vector<unsigned> acc, bit;
    vector<T> srsum;

   public:
    BitVector() {}

    BitVector(vector<bool> &b) {
        cur = 0;
        n = b.size();
        acc.resize((n >> 5) + 2, 0);
        bit.resize((n >> 5) + 2, 0);
        srsum.resize(n + 1, 0);
        for (int i = 0; i < n; i++) {
            if (!(i & 31)) {
                cur++;
                acc[cur] = acc[cur - 1];
            }
            if (b[i]) {
                acc[cur] += int(b[i]);
                bit[cur - 1] |= (1U << (32 - (i & 31) - 1));
            }
        }
    }

    inline void srsum_set(const vector<T> &v) {
        for (int i = 0; i < n; i++) {
            srsum[i + 1] = srsum[i] + v[i];
        }
    }

    inline unsigned rank(unsigned k) {
        if (!(k & 31)) return acc[k >> 5];
        return acc[k >> 5] + __builtin_popcount(bit[k >> 5] >> (32 - (k & 31)));
    }

    inline T rank_srsum(unsigned k) { return srsum[k]; }

    inline bool access(unsigned k) { return (rank(k + 1) - rank(k)) == 1; }
};

template <class T>
class WaveletMatrix {
   private:
    unsigned n;
    unsigned bitsize;
    vector<BitVector<T> > b;
    vector<unsigned> zero;
    vector<int> stInd;
    vector<unsigned> compressed;
    vector<T> cmp;
    vector<long long> sum;
    T MI, MA;

    // v[l,r) の中で値がk未満の総和を返す
    long long rank_sum(unsigned l, unsigned r, unsigned k) {
        long long less_sum = 0;
        for (unsigned i = 0; i < bitsize and l < r; i++) {
            const unsigned rank1_l = b[i].rank(l);
            const unsigned rank1_r = b[i].rank(r);
            const unsigned rank0_l = l - rank1_l;
            const unsigned rank0_r = r - rank1_r;
            if (k & (1U << (bitsize - i - 1))) {
                less_sum += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
                l = zero[i] + rank1_l;
                r = zero[i] + rank1_r;
            } else {
                l = rank0_l;
                r = rank0_r;
            }
        }
        return less_sum;
    }

    // v[l,r) の中で値がk未満の個数を返す
    unsigned rank_less(unsigned l, unsigned r, T k) {
        unsigned less = 0;
        for (unsigned i = 0; i < bitsize and l < r; i++) {
            const unsigned rank1_l = b[i].rank(l);
            const unsigned rank1_r = b[i].rank(r);
            const unsigned rank0_l = l - rank1_l;
            const unsigned rank0_r = r - rank1_r;
            if (k & (1U << (bitsize - i - 1))) {
                less += (rank0_r - rank0_l);
                l = zero[i] + rank1_l;
                r = zero[i] + rank1_r;
            } else {
                l = rank0_l;
                r = rank0_r;
            }
        }
        return less;
    }

    // v[l,r) の中で値がk未満の個数と総和を返す
    pair<long long, long long> rank_less_sum(unsigned l, unsigned r, T k) {
        long long less = 0;
        long long less_sum = 0;
        for (unsigned i = 0; i < bitsize and l < r; i++) {
            const unsigned rank1_l = b[i].rank(l);
            const unsigned rank1_r = b[i].rank(r);
            const unsigned rank0_l = l - rank1_l;
            const unsigned rank0_r = r - rank1_r;
            if (k & (1U << (bitsize - i - 1))) {
                less += (rank0_r - rank0_l);
                less_sum += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
                l = zero[i] + rank1_l;
                r = zero[i] + rank1_r;
            } else {
                l = rank0_l;
                r = rank0_r;
            }
        }
        return {less, less_sum};
    }

    inline unsigned compress(const T &x) {
        return lower_bound(cmp.begin(), cmp.end(), x) - begin(cmp);
    }

   public:
    // コンストラクタ
    WaveletMatrix() {}
    WaveletMatrix(vector<T> v) {
        MI = numeric_limits<T>::min();
        MA = numeric_limits<T>::max();
        n = v.size();
        cmp = v;
        sort(cmp.begin(), cmp.end());
        cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
        compressed.resize(n);
        sum.resize(n + 1);
        vector<T> tmp(n);
        vector<unsigned> tmpc(n);
        unsigned size_mx = v.size();
        for (unsigned i = 0; i < n; i++) {
            compressed[i] = distance(cmp.begin(),
                                     lower_bound(cmp.begin(), cmp.end(), v[i]));
            sum[i + 1] = sum[i] + v[i];
        }
        stInd.resize(cmp.size() + 1, -1);
        bitsize = bit_width(size_mx);
        b.resize(bitsize);
        zero.resize(bitsize, 0);
        vector<bool> bit(n, 0);
        for (unsigned i = 0; i < bitsize; i++) {
            for (unsigned j = 0; j < n; j++) {
                bit[j] = compressed[j] & (1U << (bitsize - i - 1));
                zero[i] += unsigned(!bit[j]);
                tmp[j] = v[j];
                tmpc[j] = compressed[j];
            }
            b[i] = BitVector<T>(bit);
            int cur = 0;
            for (unsigned j = 0; j < n; j++) {
                if (!bit[j]) {
                    v[cur] = tmp[j];
                    compressed[cur] = tmpc[j];
                    cur++;
                }
            }
            for (unsigned j = 0; j < n; j++) {
                if (bit[j]) {
                    v[cur] = tmp[j];
                    compressed[cur] = tmpc[j];
                    cur++;
                }
            }
            b[i].srsum_set(v);
        }

        for (unsigned i = 0; i < n; i++) {
            if (stInd[compressed[i]] == -1) {
                stInd[compressed[i]] = i;
            }
        }
    }

    // get v[k]
    T access(unsigned k) {
        unsigned res = 0;
        unsigned cur = k;
        for (unsigned i = 0; i < bitsize; i++) {
            if (b[i].access(cur)) {
                res |= (1U << (bitsize - i - 1));
                cur = zero[i] + b[i].rank(cur);
            } else {
                cur -= b[i].rank(cur);
            }
        }
        return cmp[res];
    }

    // v[0,k) 中でのcの出現回数を返す
    unsigned rank(unsigned k, T c) {
        c = compress(c);
        unsigned cur = k;
        if (stInd[c] == -1) {
            return 0;
        }
        for (unsigned i = 0; i < bitsize; i++) {
            if (c & (1U << (bitsize - i - 1))) {
                cur = zero[i] + b[i].rank(cur);
            } else {
                cur -= b[i].rank(cur);
            }
        }
        return cur - stInd[c];
    }

    // v[l,r) の中でk番目(1-origin)に小さい値を返す
    T kth_smallest(unsigned l, unsigned r, unsigned k) {
        unsigned res = 0;
        for (unsigned i = 0; i < bitsize; i++) {
            unsigned num1 = b[i].rank(r) - b[i].rank(l);
            unsigned num0 = r - l - num1;
            if (num0 < k) {
                res |= (1ULL << (bitsize - i - 1));
                l = zero[i] + b[i].rank(l);
                r = zero[i] + b[i].rank(r);
                k -= num0;
            } else {
                l -= b[i].rank(l);
                r -= b[i].rank(r);
            }
        }
        return cmp[res];
    }

    // v[l,r) の中でk番目(1-origin)に大きい値を返す
    T kth_largest(unsigned l, unsigned r, unsigned k) {
        return kth_smallest(l, r, r - l - k + 1);
    }

    // v[l,r]を昇順ソートした時の先頭k個の総和を返す
    long long kth_ascending_sum(unsigned l, unsigned r, unsigned k) {
        long long res = 0;
        unsigned val = 0;
        for (unsigned i = 0; i < bitsize; i++) {
            const unsigned rank1_l = b[i].rank(l);
            const unsigned rank1_r = b[i].rank(r);
            const unsigned rank0_l = l - rank1_l;
            const unsigned rank0_r = r - rank1_r;
            const unsigned num1 = rank1_r - rank1_l;
            const unsigned num0 = rank0_r - rank0_l;
            if (num0 < k) {
                val |= (1ULL << (bitsize - i - 1));
                res += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
                l = zero[i] + rank1_l;
                r = zero[i] + rank1_r;
                k -= num0;
            } else {
                l = rank0_l;
                r = rank0_r;
            }
        }
        res += int64_t(cmp[val]) * (k);
        return res;
    }

    // v[l,r]を降順ソートした時の先頭k個の総和を返す
    long long kth_descending_sum(unsigned l, unsigned r, unsigned k) {
        return range_sum(l, r) - kth_ascending_sum(l, r, r - l - k);
    }

    // v[l,r) の中で[mink,maxk)に入る値の個数を返す
    unsigned range_freq(unsigned l, unsigned r, T mink, T maxk) {
        mink = compress(mink);
        maxk = compress(maxk);
        if (mink == 0) {
            return rank_less(l, r, maxk);
        }
        return rank_less(l, r, maxk) - rank_less(l, r, mink);
    }

    // v[l,r) の総和を返す
    long long range_sum(unsigned l, unsigned r) { return sum[r] - sum[l]; }

    // v[l,r) の中で[mink,maxk)に入る値の総和を返す
    long long range_sum(unsigned l, unsigned r, T mink, T maxk) {
        mink = compress(mink);
        maxk = compress(maxk);
        return rank_sum(l, r, maxk) - rank_sum(l, r, mink);
    }

    // v[l,r) の中で ∑|v[i]-d| を計算して返す
    long long range_abs(unsigned l, unsigned r, T d) {
        T dnum = rank(r, d) - rank(l, d);
        T dsum = d * dnum;
        T asum = range_sum(l, r);
        auto p = rank_less_sum(l, r, compress(d));
        T less = p.first;
        T less_sum = p.second;
        T more = r - l - dnum - less;
        T more_sum = asum - dsum - less_sum;
        return d * less + more_sum - less_sum - (d * more);
    }

    // v[l,r)の中でvalを超えない最大の値を返す
    T prev_value(unsigned l, unsigned r, T val) {
        int num = range_freq(l, r, MI, val);
        if (num == 0) {
            return MA;
        } else {
            return kth_smallest(l, r, num);
        }
    }

    // v[l,r)の中でval以上の最小の値を返す
    T next_value(unsigned l, unsigned r, T val) {
        int num = range_freq(l, r, MI, val);
        if (num == r - l) {
            return MI;
        } else {
            return kth_smallest(l, r, num + 1);
        }
    }
};

vector<vector<char> > adds(const vector<vector<char> > &grid) {
    int originalRows = grid.size();
    int originalCols = grid[0].size();
    int newRows = originalRows + 2;
    int newCols = originalCols + 2;

    // 新しい二次元ベクトルを`#`で初期化
    vector<vector<char> > borderedGrid(newRows, vector<char>(newCols, '#'));

    // 元のグリッドをコピーして、外枠内に埋め込む
    for (int i = 0; i < originalRows; ++i) {
        for (int j = 0; j < originalCols; ++j) {
            borderedGrid[i + 1][j + 1] = grid[i][j];
        }
    }

    return borderedGrid;
}

void printGrid(const vector<vector<char> > &grid) {
    for (const auto &row : grid) {
        for (const auto &cell : row) {
            cout << cell;
        }
        cout << endl;
    }
}
void printGridint(const vector<vector<int> > &grid) {
    for (const auto &row : grid) {
        for (const auto &cell : row) {
            cout << cell;
        }
        cout << endl;
    }
}
vector<vector<char> > surround(const vector<vector<char> > &grid) {
    int originalRows = grid.size();
    int originalCols = grid[0].size();
    int newRows = originalRows * 3;
    int newCols = originalCols * 3;

    // 新しい二次元ベクトルを作成
    vector<vector<char> > expandedGrid(newRows, vector<char>(newCols));

    // 3x3の各ブロックに元のグリッドをコピー
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            // 各位置にオリジナルのグリッドをコピー
            for (int x = 0; x < originalRows; ++x) {
                for (int y = 0; y < originalCols; ++y) {
                    expandedGrid[i * originalRows + x][j * originalCols + y] =
                        grid[x][y];
                }
            }
        }
    }

    return expandedGrid;
}

vector<vector<int> > surroundint(const vector<vector<int> > &grid) {
    int originalRows = grid.size();
    int originalCols = grid[0].size();
    int newRows = originalRows * 3;
    int newCols = originalCols * 3;

    // 新しい二次元ベクトルを作成
    vector<vector<int> > expandedGrid(newRows, vector<int>(newCols));

    // 3x3の各ブロックに元のグリッドをコピー
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            // 各位置にオリジナルのグリッドをコピー
            for (int x = 0; x < originalRows; ++x) {
                for (int y = 0; y < originalCols; ++y) {
                    expandedGrid[i * originalRows + x][j * originalCols + y] =
                        grid[x][y];
                }
            }
        }
    }

    return expandedGrid;
}

#endif


```