C++テンプレのりどみ(前半)

どうも、わーはやです。今回は自分のテンプレのコードを解説していきたいと思います。
と言っても、普段あまり使わないやつはリファレンスだけ置いて軽く流します。
長くなりそうなので前半と後半に分けようと思います。前置きはこのあたりにして早速解説していきます。

コンパイルオプション
最初の方
マクロ
シリーズ
入出力
便利なやつまとめ
終わりに

コンパイルオプション

/*#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")//*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wdeprecated-copy"

上三文は定数倍高速化をする時に解放します。詳しくはこちらを参照してください。

qiita.com

下の三文は特定のコンパイルエラーを無視するオプションをつけます。例えば、以下のようなマクロを書きます。

#define rep(i, n) for(int i = 0; i < n; ++i)
const std::string s = "VvyLw";
rep(i, s.size()) {
  // 処理
}

この時、-Wallオプションをつけると次のようなエラーが出ます。

warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]

これはfor文内のs.size()の型がsize_tで、size_tが符号なし整数型なのでiをintと置いているせいで、i<s.size()の時に型が一致しない状態で比較しているというエラーが出ています。このようなちょっとしたエラーを無視するために置いています。

最初の方

#include <bits/stdc++.h>
using namespace std;

これはまあ、いいですね。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

これはg++拡張にあるtreeというデータ構造を使うために置いてます。 std::setに似ていますが、k番目の要素を取り出すことができる便利なデータ構造です。

このデータ構造が輝く例 atcoder.jp

ACコード atcoder.jp

詳しくは以下を参照してください。

hogloid.hatenablog.com

namespace VvyLw {
inline void wa_haya_exe() noexcept { cin.tie(nullptr) -> sync_with_stdio(false); }
void solve();
} // VvyLw

wa_haya_exeは入出力高速化の関数です。関数名はXのユーザーIDから取って来ました。 solveは問題を解くためのコードを書く関数です。

mt19937 EhaL(hash<string>()("Huitloxopetl"));
mt19937 Random() {
  random_device seed_gen;
  mt19937 engine {seed_gen()};
  return engine;
}

ハッシュと乱数生成のコードです。 EhaLは昔何かに使おうとしていましたが、使わなくなって放置しています。 Randomは後半のLady_sANDy::rext関数で使います。

using Timer = chrono::system_clock::time_point;
[[maybe_unused]] Timer start, stop;
#if local
void now(Timer &t){ t = chrono::system_clock::now(); }
void time(const Timer &t1, const Timer &t2){ cerr << chrono::duration_cast<chrono::milliseconds>(t2-t1).count() << "ms\n"; }
#else
[[maybe_unused]] void now(Timer &t){ void(0); }
[[maybe_unused]] void time(const Timer &t1, const Timer &t2){ void(0); }
#endif

これはローカルで実行時間を計測する時に使います。

マクロ

#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0; i<(n); ++i)
#define rep2(i,n) for(ll i=0; i<(n); ++i)
#define rep3(i,a,b) for(ll i=(a); i<=(b); ++i)
#define rep4(i,a,b,c) for(ll i=(a); i<=(b); i+=(c))
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rvp1(n) for(ll i=(n); --i>=0;)
#define rvp2(i,n) for(ll i=(n); --i>=0;)
#define rvp3(i,a,b) for(ll i=(a); i>=(b); i--)
#define rvp4(i,a,b,c) for(ll i=(a); i>=(b); i-=(c))
#define rvp(...) overload4(__VA_ARGS__,rvp4,rvp3,rvp2,rvp1)(__VA_ARGS__)
#define all1(v) v.begin(),v.end()
#define all2(v,a) v.begin(),v.begin()+a
#define all3(v,a,b) v.begin()+a,v.begin()+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(v) v.rbegin(),v.rend()
#define rall2(v,a) v.rbegin(),v.rbegin()+a
#define rall3(v,a,b) v.rbegin()+a,v.rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define each1(elem,v) for(auto &elem: v)
#define each2(x,y,v) for(auto &[x,y]: v)
#define each3(x,y,z,v) for(auto &[x,y,z]: v)
#define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__)
#define sqrp1(n) for(ll i=0; i*i<(n); ++i)
#define sqrp2(i,n) for(ll i=0; i*i<(n); ++i)
#define sqrp3(i,a,b) for(ll i=(a); i*i<=(b); ++i)
#define sqrp(...) overload3(__VA_ARGS__,sqrp3,sqrp2,sqrp1)(__VA_ARGS__)

tatyam様の記事を参考に作ったfor文のマクロシリーズ。本当にありがとうございます。

シリーズ

using ll = long long;
using ld = long double;
using uint = unsigned;
using ul = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;

型宣言シリーズ。

template <class T> using L = numeric_limits<T>;
constexpr int dx[]={0,0,0,-1,1,-1,-1,1,1};
constexpr int dy[]={0,-1,1,0,0,-1,1,-1,1};
constexpr int MOD = 0x3b800001;
constexpr int M0D = 1e9+7;
constexpr int INF = 1<<30;
constexpr ll LINF = (1LL<<61)-1;
constexpr ld DINF = L<ld>::infinity();
template <class T> constexpr T LIM = L<T>::max();
#if __cplusplus >= 202100L
constexpr ld PI = numbers::pi;
constexpr ld E = numbers::e;
#else
const ld PI = acos(-1);
const ld E = 2.718281828459045;
#endif

定数シリーズ。 dx, dyはグリッド操作で使うことがあります。 PIとEの定義はC++20以降かどうかで場合分けしております。

namespace vectors {
template <class T> using V = vector<T>;
using vi = V<ll>;
using vu = V<ul>;
using vd = V<ld>;
using vc = V<char>;
using vs = V<string>;
using vb = V<bool>;
using wi = V<vi>;
using wu = V<vu>;
using wd = V<vd>;
using wc = V<vc>;
using ws = V<vs>;
using wb = V<vb>;
template <class T, class U> inline V<U> ndiv(T&& n, U&& v) noexcept {
  return V<U>(forward<T>(n), forward<U>(v));
}
template <class T, class... Ts> inline decltype(auto) ndiv(T&& n, Ts&&... v) noexcept {
  return V<decltype(ndiv(forward<Ts>(v)...))>(forward<T>(n), ndiv(forward<Ts>(v)...));
}
template <class T> constexpr V<T>& operator++(V<T>& v) noexcept { each(el,v) el++; return v; }
template <class T> constexpr V<T>& operator--(V<T>& v) noexcept { each(el,v) el--; return v; }
template <class T, class U> constexpr V<T>& operator+=(V<T>& v, const U x) noexcept { each(el,v) el+=x; return v; }
template <class T, class U> constexpr V<T>& operator-=(V<T>& v, const U x) noexcept { each(el,v) el-=x; return v; }
template <class T, class U> constexpr V<T>& operator*=(V<T>& v, const U x) noexcept { each(el,v) el*=x; return v; }
template <class T, class U> constexpr V<T>& operator/=(V<T>& v, const U x) noexcept { each(el,v) el/=x; return v; }
template <class T, class U> constexpr V<T>& operator%=(V<T>& v, const U x) noexcept { each(el,v) el%=x; return v; }
template <class T, class U> constexpr V<T> operator+(const V<T>& v, const U x) noexcept { V<T> res = v; res+=x; return res; }
template <class T, class U> constexpr V<T> operator-(const V<T>& v, const U x) noexcept { V<T> res = v; res-=x; return res; }
template <class T, class U> constexpr V<T> operator*(const V<T>& v, const U x) noexcept { V<T> res = v; res*=x; return res; }
template <class T, class U> constexpr V<T> operator/(const V<T>& v, const U x) noexcept { V<T> res = v; res/=x; return res; }
template <class T, class U> constexpr V<T> operator%(const V<T>& v, const U x) noexcept { V<T> res = v; res%=x; return res; }
} // vectors
using namespace vectors;

std::vectorを改造しました。vectors::ndivはn次元vectorが作れる便利な関数です。

使用例

auto v = ndiv(3, 2, 1);

これで以下のような2次元vectorが宣言できます。

$\begin{bmatrix} 1 & 1 \\ 1 & 1 \\ 1 & 1 \\ \end{bmatrix}$

ご覧の通り、最後の値が初期値になります。これをよく使うのは3次元以上のvectorが必要な時です。3次元DPを書くときなどで使います。

あとは演算子系ですね。
例えば以下のようなコードを書きます。

int n;
std::cin >> n;
std::vector<int> a(n);
for(auto &el: a) std::cin >> el;
--a;

--aでaの値が全部デクリメントされました。
これで何が嬉しいかというと、例えば入力が1-indexedで与えられた時、0-indexedに直すのが簡単です。

namespace pairs {
template <class T, class U> using P = pair<T, U>;
template <class T> using PP = P<T,T>;
using pi = PP<ll>;
using pd = PP<ld>;
using pc = PP<char>;
using ps = PP<string>;
template <class T> constexpr PP<T> operator+(const PP<T>& a, const PP<T>& b) noexcept { return {a.first + b.first, a.second + b.second}; }
template <class T> constexpr PP<T> operator-(const PP<T>& a, const PP<T>& b) noexcept { return {a.first - b.first, a.second - b.second}; }
template <class T> constexpr PP<T> operator-(const PP<T>& a) noexcept { return {-a.first, -a.second}; }
template <class T, class U> constexpr PP<T> operator*(const PP<T>& a, const U& b) noexcept { return {a.first * b, a.second * b}; }
template <class T, class U> constexpr PP<T> operator/(const PP<T>& a, const U& b) noexcept { return {a.first / b, a.second / b}; }
template <class T> constexpr PP<T>& operator+=(PP<T>& a, const PP<T>& b) noexcept { return a = a + b; }
template <class T> constexpr PP<T>& operator-=(PP<T>& a, const PP<T>& b) noexcept { return a = a - b; }
template <class T, class U> constexpr PP<T>& operator*=(PP<T>& a, const U& b) noexcept { return a = a * b; }
template <class T, class U> PP<T>& operator/=(PP<T>& a, const U& b) noexcept { return a = a / b; }
template <class T> constexpr bool operator==(const PP<T> &p, const PP<T> &q) noexcept { return p.first==q.first && p.second==q.second; }
template <class T> constexpr bool operator!=(const PP<T> &p, const PP<T> &q) noexcept { return !(p==q); }
template <class T> constexpr bool operator<(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second<q.second; return p.first<q.first; }
template <class T> constexpr bool operator<=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first<q.first; }
template <class T> constexpr bool operator>(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; }
template <class T> constexpr bool operator>=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; }
template <class T, class U> constexpr bool operator==(const P<T,U> &p, const P<T,U> &q) noexcept { return p.first==q.first && p.second==q.second; }
template <class T, class U> constexpr bool operator!=(const P<T,U> &p, const P<T,U> &q) noexcept { return !(p==q); }
template <class T, class U> constexpr bool operator<(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second<q.second; return p.first<q.first; }
template <class T, class U> constexpr bool operator<=(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first<q.first; }
template <class T, class U> constexpr bool operator>(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; }
template <class T, class U> constexpr bool operator>=(const P<T,U> &p, const P<T,U> &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; }
template <class T> inline PP<T> rotate(const PP<T>& a){ return {-a.second, a.first}; } // 90 degree ccw
template <class T> inline pd rotate(const PP<T>& a, const int ang) {
  assert(0<=ang && ang<360);
  const ld rad=PI*ang/180;
  return {a.first*cosl(rad)-a.second*sinl(rad), a.first*sinl(rad)+a.second*cosl(rad)};
}
template <class T> inline T dot(const PP<T>& a, const PP<T>& b){ return a.first * b.first + a.second * b.second; }
template <class T> inline T cross(const PP<T>& a, const PP<T>& b){ return dot(rotate(a), b); }
template <class T> inline T square(const PP<T>& a){ return dot(a, a); }
template <class T> inline ld grad(const PP<T>& a){ assert(a.first); return 1.0L * a.second / a.first; }
template <class T> inline ld abs(const PP<T>& a){ return hypotl(a.first, a.second); }
template <class T> inline T lcm(const PP<T>& a){ return std::lcm(a.first, a.second); }
template <class T> inline T gcd(const PP<T>& a){ return std::gcd(a.first, a.second); }
template <class T> inline PP<T> extgcd(const PP<T> &p) {
  T x=1,y=0,t1=0,t2=0,t3=1,a,b;
  tie(a,b)=p;
  while(b) {
    t1=a/b,a-=t1*b;
    swap(a,b);
    x-=t1*t2;
    swap(x,t2);
    y-=t1*t3;
    swap(y,t3);
  }
  return {x,y};
}
template <class T> inline PP<T> normalize(PP<T> a) {
  if(a == PP<T>{}) return a;
  a /= gcd(a);
  if(a < PP<T>{}) a = -a;
  return a;
}
template <class T, class U> inline P<U,T> swap(const P<T,U> &p){ P<U,T> ret={p.second,p.first}; return ret; }
template <class T, class U> inline V<P<U,T>> swap(const V<P<T,U>> &vp) {
  V<P<U,T>> ret;
  each(el,vp) ret.emplace_back(swap(el));
  return ret;
}
template <class T, class U> inline V<T> first(const V<P<T,U>> &vp) {
  V<T> res;
  each(el,vp) res.emplace_back(el.first);
  return res;
}
template <class T, class U> inline V<U> second(const V<P<T,U>> &vp) {
  V<U> res;
  each(el,vp) res.emplace_back(el.second);
  return res;
}
} // pairs
using namespace pairs;

長い！
tatyam様のpair系ライブラリから拝借してきたものにいくつか追加したものです。
ありがとうございます。

pairs::swapはpair自体の要素を入れ替えます。
pairs::first, pairs::secondはstd::vector<std::pair<T, U>>が与えられた時に、first側のvector, second側のvectorを返す関数です。

template <size_t N> using ti = array<ll, N>;
using tri = ti<3>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqr = priority_queue<T,V<T>,greater<T>>;
template <class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using TREE = tree<T,null_type,greater<T>,rb_tree_tag,tree_order_statistics_node_update>;
template <class T, class U> inline bool chmax(T& a, const U& b){ if(a<b){ a=b; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& a, const U& b){ if(a>b){ a=b; return 1; } return 0; }
template <class T, class U> inline bool overflow_if_add(const T a, const U b){ return (LIM<T>-a)<b; }
template <class T, class U> inline bool overflow_if_mul(const T a, const U b){ return (LIM<T>/a)<b; }

型宣言シリーズ2と便利関数。名前が長い型を省略するなどをしています。priority_queue(昇順)とか先ほどのtreeとか長いのでね。
chmax, chminは値更新のやつ。
overflow_if*はオーバーフローを検知する関数です。

入出力

namespace IO {
ostream &operator<<(ostream &dest, i128 value) {
  ostream::sentry s(dest);
  if(s) {
    u128 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 <class T, class U> istream& operator>>(istream &is, P<T, U> &p){ is >> p.first >> p.second; return is; }
template <class T, size_t N> istream& operator>>(istream &is, array<T, N> &a){ each(el,a) is >> el; return is; }
template <class T> istream& operator>>(istream &is, V<T> &v){ each(el,v) is >> el; return is; }
template <class T> istream& operator>>(istream &is, deque<T> &dq){ each(el,dq) is >> el; return is; }
template <class T> inline bool in(T& x){ cin >> x; return 1; }
template <class Head, class... Tail> inline bool in(Head& head, Tail&... tail){ in(head); in(tail...); return 1; }
template <class T, class U> ostream& operator<<(ostream &os, const P<T, U> &p){ os << p.first << ' ' << p.second; return os; }
template <class T, size_t N> ostream& operator<<(ostream &os, const array<T, N> &a){ if(a.size()){ os << a.front(); for(auto i=a.begin(); ++i!=a.end();){ os << ' ' << *i; } } return os; }
template <class T> ostream& operator<<(ostream &os, const V<T> &v){ if(v.size()){ os << v.front(); for(auto i=v.begin(); ++i!=v.end();){ os << ' ' << *i; } } return os; }
template <class K, class V> ostream& operator<<(ostream &os, const map<K, V> &m){ if(m.size()){ os << m.begin()->first << ' ' << m.begin()->second; for(auto i=m.begin(); ++i!=m.end();){ os << '\n' << i->first << ' ' << i->second; } } return os; }
template <class T> ostream& operator<<(ostream &os, const set<T> &st){ if(st.size()){ os << *st.begin(); for(auto i=st.begin(); ++i!=st.end();){ os << ' ' << *i; } } return os; }
template <class T> ostream& operator<<(ostream &os, const multiset<T> &ms){ if(ms.size()){ os << *ms.begin(); for(auto i=ms.begin(); ++i!=ms.end();){ os << ' ' << *i; } } return os; }
template <class T> ostream& operator<<(ostream &os, const deque<T> &dq){ if(dq.size()){ os << dq.front(); for(auto i=dq.begin(); ++i!=dq.end();){ os << ' ' << *i; } } return os; }
inline void out(){ cout << '\n'; }
template <bool flush=false, class T> inline void out(const T& x){ cout << x << '\n'; if(flush) cout.flush(); }
template <bool flush=false, class Head, class... Tail> inline void out(const Head& head, const Tail&... tail){ cout << head << ' '; out<flush>(tail...); }
template <bool flush=false, class T> inline void vout(const T& v){ cout << v << '\n'; if(flush) cout.flush(); }
template <bool flush=false, class T> inline void vout(const V<T>& v){ rep(v.size()) cout << v[i] << '\n'; if(flush) cout.flush(); }
template <bool flush=false, class Head, class... Tail> inline void vout(const Head& head, const Tail&... tail){ cout << head << '\n'; vout<flush>(tail...); }
inline void fix(short x){ cout << fixed << setprecision(x); }
inline void alpha(){ cout << boolalpha; }
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define UL(...) ul __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type,name,size) V<type> name(size); in(name)
#define WEC(type,name,h,w) V<V<type>> name(h,V<type>(w)); in(name)
#define fin(...) do{ out(__VA_ARGS__); return; }while(false)
} // IO
using namespace IO;

長いですね。

ostream &operator<<(ostream &dest, i128 value) {
  ostream::sentry s(dest);
  if(s) {
    u128 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;
}

これは__int128_t型の値を出力するために使います。
kenkoooo様の記事から拝借しました。ありがとうございます。

template <class T, class U> istream& operator>>(istream &is, P<T, U> &p){ is >> p.first >> p.second; return is; }
template <class T, size_t N> istream& operator>>(istream &is, array<T, N> &a){ each(el,a) is >> el; return is; }
template <class T> istream& operator>>(istream &is, V<T> &v){ each(el,v) is >> el; return is; }
template <class T> istream& operator>>(istream &is, deque<T> &dq){ each(el,dq) is >> el; return is; }
template <class T> inline bool in(T& x){ cin >> x; return 1; }
template <class Head, class... Tail> inline bool in(Head& head, Tail&... tail){ in(head); in(tail...); return 1; }

入力をまとめた関数です。IO::inを使います。
演算子オーバーロードを使って、std::cinでstd::pair, std::array, std::vector, std::dequeの入力が可能です。

template <class T, class U> ostream& operator<<(ostream &os, const P<T, U> &p){ os << p.first << ' ' << p.second; return os; }
template <class T, size_t N> ostream& operator<<(ostream &os, const array<T, N> &a){ if(a.size()){ os << a.front(); for(auto i=a.begin(); ++i!=a.end();){ os << ' ' << *i; } } return os; }
template <class T> ostream& operator<<(ostream &os, const V<T> &v){ if(v.size()){ os << v.front(); for(auto i=v.begin(); ++i!=v.end();){ os << ' ' << *i; } } return os; }
template <class K, class V> ostream& operator<<(ostream &os, const map<K, V> &m){ if(m.size()){ os << m.begin()->first << ' ' << m.begin()->second; for(auto i=m.begin(); ++i!=m.end();){ os << '\n' << i->first << ' ' << i->second; } } return os; }
template <class T> ostream& operator<<(ostream &os, const set<T> &st){ if(st.size()){ os << *st.begin(); for(auto i=st.begin(); ++i!=st.end();){ os << ' ' << *i; } } return os; }
template <class T> ostream& operator<<(ostream &os, const multiset<T> &ms){ if(ms.size()){ os << *ms.begin(); for(auto i=ms.begin(); ++i!=ms.end();){ os << ' ' << *i; } } return os; }
template <class T> ostream& operator<<(ostream &os, const deque<T> &dq){ if(dq.size()){ os << dq.front(); for(auto i=dq.begin(); ++i!=dq.end();){ os << ' ' << *i; } } return os; }
inline void out(){ cout << '\n'; }
template <bool flush=false, class T> inline void out(const T& x){ cout << x << '\n'; if(flush) cout.flush(); }
template <bool flush=false, class Head, class... Tail> inline void out(const Head& head, const Tail&... tail){ cout << head << ' '; out<flush>(tail...); }
template <bool flush=false, class T> inline void vout(const T& v){ cout << v << '\n'; if(flush) cout.flush(); }
template <bool flush=false, class T> inline void vout(const V<T>& v){ rep(v.size()) cout << v[i] << '\n'; if(flush) cout.flush(); }
template <bool flush=false, class Head, class... Tail> inline void vout(const Head& head, const Tail&... tail){ cout << head << '\n'; vout<flush>(tail...); }

出力をまとめた関数です。IO::out, IO::voutを使います。
IO::voutは、vectorを出力する時で答えが改行形式の時やvector<std::string>を出力する時など使います。
std::pair, std::array, std::vector, std::map, std::set, std::multiset, std::dequeがstd::coutで出力できます。
また、flushするかどうか選べます。デフォルトはflushしません。

inline void fix(const short x){ cout << fixed << setprecision(x); }
inline void alpha(){ cout << boolalpha; }

IO::fixは小数点の精度を調整できます。
IO::alphaはboolを出力する時にtrue, falseが返るようになります。実用性はわかりません。

#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define UL(...) ul __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type,name,size) V<type> name(size); in(name)
#define WEC(type,name,h,w) V<V<type>> name(h,V<type>(w)); in(name)
#define fin(...) do{ out(__VA_ARGS__); return; }while(false)

入力マクロです。

INT(x,y);

と書くだけでint x, yが入力できます。便利ですね。
finは出力した後、プログラムを終了します。

便利なやつまとめ

#ifdef local
//https://gist.github.com/naskya/1e5e5cd269cfe16a76988378a60e2ca3
#include <../debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) static_cast<void>(0)
#endif
#define elif else if
#define eid(el,v) size_t(&el-&v[0])
#define bif(bit,tar) if(((bit)>>(tar))&1)
#define nxp(x) next_permutation(all(x))
#define prp(x) prev_permutation(all(x))
#define strpl(s,a,b) regex_replace(s,regex(a),b)
#define rgxsr(s,rgx) regex_search(s,regex(rgx))

マクロまとめです。 debugはローカルで動くデバッグマクロです。コンパイルオプションに-Dlocalをつけると、動くようになります。 debug_print.hppの使い方は以下のサイトを参照してください。

https://blog.naskya.net/post/0002/blog.naskya.net

マクロでelifが使えます。
eidは範囲for文の時にインデックスを渡してくれます。

// e.g.
for(const auto &el: a) {
  IO::out(eid(el, a));
}

bifはbit全探索時にしか使いません。
next_permutation, prev_permutationは長いので短くしました。
strplは文字列の入れ替えを行います。
rgxsrは文字列の探索を行います。
どちらも正規表現での操作なので計算量は(わからないですが)重いです。

inline void YES(const bool ok=1){ out(ok?"YES":"NO"); }
inline void NO(const bool ok=1){ YES(!ok); }
inline void Yes(const bool ok=1){ out(ok?"Yes":"No"); }
inline void No(const bool ok=1){ Yes(!ok); }
inline void yes(const bool ok=1){ out(ok?"yes":"no"); }
inline void no(const bool ok=1){ yes(!ok); }

YesNo系。

template <class T> inline T sqr(const T x){ return x*x; }
template <class T> inline T cub(const T x){ return x*x*x; }
template <class T> inline T Mod(const T x, const T m){ return (x+m)%m; }
template <class T> inline T Pow(T a, T b, const T mod=0) {
  T res=1;
  if(mod) {
    res%=mod;
    a%=mod;
  }
  while(b>0) {
    if(b&1) res*=a;
    if(mod) res%=mod;
    a*=a;
    if(mod) a%=mod;
    b>>=1;
  }
  return res;
}
inline ll Ceil(const ld x, const ll m){ return ceil(x/m); }
inline ld Round(const ld x, const ll m, const short fx=0){ if(!fx) return round(x/m); const ul y=Pow<ul>(10,fx); return round((x*y)/m)/y; }
inline ld Log(const ll x, const ld base=2){ return log2(x)/log2(base); }

計算系の関数が置いてあります。使い方は見ての通りです。
zia_qu::Powは繰り返し二乗法を使っています。

inline int bitdigit(const ll x){ return 64-__builtin_clzll(x); }
inline int popcnt(const ll x){ return __builtin_popcountll(x); }
inline int fione(const ll x){ return __builtin_ffsll(x); }
inline int zrcnt(const ll x){ return __builtin_ctzll(x); }
template <class T=ll> inline bool scope(const T a, const T x, const T b){ return a <= x && x <= b; }

C++のビルトイン関数を使って便利そうな関数を作りました。
bitdigitは2進数で表した時の桁数を返します。
popcntは2進数で表した時の1の個数を返します。
fioneは最初に現れる1の位置を返します。
zrcntは最初に1が現れるまで0が何個あるか返します。
~~zia_qu::fioneとzia_qu::zrcntはそのうち消えそうな気がする。~~

他にもビルトイン関数を知りたい方はこちらをご覧ください。

gcc.gnu.org

C++20以降は#include <bit>で色々できるのでそちらを使った方がよさそうです。
zia_qu::scopeは $a \le x \le b$ を判定します。std::clampと似ています。

inline bool isupper(const char c){ return std::isupper(c); }
inline bool isupper(const string &s){ bool ok=1; each(el,s) ok&=isupper(el); return ok; }
inline bool islower(const char c){ return std::islower(c); }
inline bool islower(const string &s){ bool ok=1; each(el,s) ok&=islower(el); return ok; }
inline bool isalpha(const char c){ return std::isalpha(c); }
inline bool isalpha(const string &s){ bool ok=1; each(el,s) ok&=isalpha(el); return ok; }
inline bool isdigit(const char c){ return std::isdigit(c); }
inline bool isdigit(const string &s){ bool ok=1, neg=s.front()=='-'; each(el,s){ if(neg){ neg=0; continue; } ok&=isdigit(el); } return ok; }
inline bool isalnum(const char c){ return std::isalnum(c); }
inline bool isalnum(const string &s){ bool ok=1; each(el,s) ok&=isalnum(el); return ok; }
inline bool isspace(const char c){ return std::isspace(c); }
inline bool isspace(const string &s){ bool ok=1; each(el,s) ok&=isspace(el); return ok; }
inline bool ispunct(const char c){ return std::ispunct(c); }
inline bool ispunct(const string &s){ bool ok=1; each(el,s) ok&=ispunct(el); return ok; }
inline bool isprint(const char c){ return std::isprint(c); }
inline bool isprint(const string &s){ bool ok=1; each(el,s) ok&=isprint(el); return ok; }

isシリーズ。C言語のisはintを返すので環境によって返ってくる値が異なります。
そのせいで

bool ok = true;
for(int i = 0; i < n; ++i) {
  ok&=std::isupper(s[i]);
}
std::cout << ok << '\n';

といった操作の時に、std::isupperの値が偶数だった時にfalseが返り、間違った値が出力されることがあります。

今まで
bool ok=1;
if(条件) ok=0;
を
ok &= (条件);
で通してたけど&=は
ok = (ok & 条件);と同義だからislowerとかisalnumみたいに中身が偶数だと死んでしまうおそれがあるんだよな
— VvyLw (@wa_haya_exe) 2023年6月13日

あぶねえAtCoderで試したらisalnumは何を入力しても8って出たので環境によって違うのかもしれん
知見とか言って早とちりした全て忘れてくれ pic.twitter.com/vM7QLaxBby
— VvyLw (@wa_haya_exe) 2023年6月13日

islowerも暴れてた
もうわけわからんな pic.twitter.com/wVR9DrJxMy
— VvyLw (@wa_haya_exe) 2023年6月13日

こういったミスを消し去るために返り値を全部boolにしました。

inline ll strins(string &s, const ll id, const string &t){ s.insert(id,t); return s.size(); }
inline string toupper(string s){ each(c,s) c=std::toupper(c); return s; }
inline string tolower(string s){ each(c,s) c=std::tolower(c); return s; }

zia_qu::strinsは文字列を任意の位置に挿入する関数です。挿入後の文字数を返します。 zia_qu::toupper, zia_qu::tolowerは文字列をすべて大文字、小文字にします。

inline vi ten_to_adic(ll n, const short base) {
  vi res;
  while(n) {
    res.emplace_back(n%base);
    n/=base;
  }
  return res;
}
inline ll adic_to_ten(const vi &v, const short base) {
  ll res=0;
  each(el,v) {
    res+=Pow<ll>(base,eid(el,v))*el;
  }
  return res;
}

Etisが教えてくれた関数。10進数とn進数の変換ができます。
最近はあまり使われていないですが、それは次の関数たちのせいです。

本家

github.com

inline string to_hex(const ll x) {
  stringstream ss;
  ss<<hex<<x;
  string s=ss.str();
  //s=toupper(s);
  return s;
}
inline string to_oct(const ll x) {
  stringstream s;
  s<<oct<<x;
  return s.str();
}
inline string to_bin(const ll x) {
  stringstream ss;
  ss<<bitset<64>(x);
  string s=ss.str();
  reverse(all(s));
  s.resize(ten_to_adic(x,2).size());
  reverse(all(s));
  return s;
}
inline ll to_ten(const string &s, const short base){ return stoll(s,nullptr,base); }
inline i128 stoL(const string &s) {
  assert(isdigit(s));
  bool neg=s.front()=='-';
  i128 ret = 0;
  each(el,s) {
    if(neg) {
      neg=0;
      continue;
    }
    ret = 10 * ret + el - '0';
  }
  if(s.front()=='-') ret=-ret;
  return ret;
}

zia_qu::to_hex, zia_qu::to_oct, zia_qu::to_binは10進数をそれぞれ16進数, 8進数, 2進数に変換する関数です。
zia_qu::to_tenはn進数を10進数に変換する関数です。
はい、この関数たちのせいでzia_qu::ten_to_adic, zia_qu::adic_to_tenの出番が減っております。
この2つの関数を使うときは10進数を任意の進数に変換する時だけになります。
16, 8, 2進数の時は使うことがなくなってしまいました。えてぃすまん。

inline i128 stoL(const string &s) {
  assert(isdigit(s));
  bool neg=s.front()=='-';
  i128 ret = 0;
  each(el,s) {
    if(neg) {
      neg=0;
      continue;
    }
    ret = 10 * ret + el - '0';
  }
  if(s.front()=='-') ret=-ret;
  return ret;
}

文字列を__int128_tに変換する関数です。

template <class... Ts> constexpr ul sygcd(const Ts... a) noexcept { vector v=initializer_list<common_type_t<Ts...>>{a...}; ul g=0; each(el,v) g=gcd(g,el); return g; }
template <class... Ts> constexpr ul sylcm(const Ts... a) noexcept { vector v=initializer_list<common_type_t<Ts...>>{a...}; ul l=1; each(el,v) l=lcm(l,el); return l; }
template <class... Ts> constexpr auto symin(const Ts... a) noexcept { return min(initializer_list<common_type_t<Ts...>>{a...}); }
template <class... Ts> constexpr auto symax(const Ts... a) noexcept { return max(initializer_list<common_type_t<Ts...>>{a...}); }

これはPythonみたいな感じにそれぞれ最大公約数, 最小公倍数, 最小値, 最大値が求められる関数です。

// e.g.
IO::out(zia_qu::symax(14,52,30,41)); // 52

std::max({14,52,30,41})

やっていることはこれと同じです。

template <class K, class V> inline V vlmin(const map<K,V> &m){
    const auto pr = *min_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
    return pr.second;
}
template <class K, class V> inline V vlmax(const map<K,V> &m){
    const auto pr = *max_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
    return pr.second;
}
template <class K, class V> inline K vlmin_k(const map<K,V> &m){
    const auto pr = *min_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
    return pr.first;
}
template <class K, class V> inline K vlmax_k(const map<K,V> &m){
    const auto pr = *max_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
    return pr.first;
}

std::mapで使える便利な関数です。 zia_qu::kylは任意のvalueが入っているkeysをvectorで返します。
zia_qu::kymin, zia_qu::kymax, zia_qu::kymin_v, zia_qu::kymax_vはそれぞれkeyの最小値, keyの最大値, keyが最小値の時のvalue, keyが最大値の時のvalueを返します。
zia_qu::vlmin, zia_qu::vlmax, zia_qu::vlmin_k, zia_qu::vlmax_kはそれぞれvalueの最小値, valueの最大値, valueが最小値の時のkey, valueが最大値の時のkeyを返します。

std::map<int,int> m;
m[2]=4;
m[3]=4;
m[1]=4;
m[5]=2;
m[6]=2;
m[12]=2;
IO::out(zia_qu::vlmax_k(m)); // 1
IO::out(zia_qu::vlmin_k(m)); // 5

当てはまるkeyが複数ある時はその中で最小のkeyを返します。

終わりに

後半戦に続く......。