マクロ一覧 - 7K12 blog

ll btest(ll x, ll i); 整数xのi番目ビットが0か1か返す
template <class T> void debug(T ... args); デバッグ出力
ll divc(ll x, ll y); 除算の天井関数 ceil(x / y)
template void fillvv(T b, T e, S x); 二次元配列を値xで埋める
template <class C> ll lcnt(C& c); c.count()をllで返す
template <class C, class X> ll lcnt(C& c, X x); c.count(x)をllで返す
ll llog(ll a, ll b, bool u = false); $\log_a b$ の整数値（u = trueならa進数bの桁数と同値）
ll lpow(ll x, ll n); xのn乗をllで返す
template <class T> ll lsize(T& c); c.size()をllで返す
template <class T> void makevv(ll ys, ll xs, vvt<T>& vv); 二次元配列生成
template <class T> bool orange(ll x, vt<T>& v); // 配列の範囲外チェック
template <class T> bool orange(ll y, ll x, vvt<T>& v); // 二次元配列の範囲外チェック
template <class T> bool range(ll x, vt& v); 配列の範囲内チェック
template <class T> bool range(ll y, ll x, vvt& v); 二次元配列の範囲内チェック
template <class T> T trim(T& t, ll l, ll r): T t を半開区間[l,r)で取り出す
template <> string trim<string>(string& t, ll l, ll r): string t を半開区間[l,r)で取り出す
template <ll i, class T> void tsort(T b, T e): tuple(pair) をi番目の要素でソート

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

//#define BOOST
#ifdef BOOST
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/integer/extended_euclidean.hpp>
using mpi = boost::multiprecision::cpp_int;
using mpf = boost::multiprecision::cpp_dec_float_100;
#endif

using ll=long long; using ld=long double; using ch=char; using st=string; using bl=bool;
using cll=const long long; using cld=const long double; using cch=const char; using cst=const string; using cbl=const bool;
using pll=pair<ll,ll>; using pld=pair<ld,ld>;
template<class T> using vt=vector<T>; template<class T> using vvt=vector<vector<T>>;
using vll=vt<ll>; using vld=vt<ld>; using vch=vt<ch>; using vst=vt<st>; using vbl=vt<bl>;
using vvll=vvt<ll>; using vvch=vvt<ch>; using vvbl=vvt<bl>;
using dll=deque<ll>; using dch=deque<ch>;
using sll=set<ll>; using sch=set<ch>; using sst=set<st>;
using mll=map<ll,ll>; using mch=map<ch,ch>; using mst=map<string,string>;
using vpll=vt<pll>; using vvpll=vvt<pll>; using dpll=deque<pll>; using spll=set<pll>;
using vpld=vt<pld>; using vvpld=vvt<pld>; using dpld=deque<pld>; using spld=set<pld>;
using graph=vvll; using network=vvpll;
#define all(c) (c).begin(),(c).end()                      // begin to end
#define allr(c) (c).rbegin(),(c).rend()                   // rbegin to rend
#define rep(i,b,e) for(ll i=b;i<e;i++)                    // repeat
#define repr(i,b,e) for(ll i=b;e<i;i--)                   // repeat reverse
#define each(e,c) for(auto&e:c)                           // each for
#define inll(...) ll __VA_ARGS__; in(__VA_ARGS__);        // input ll
#define inld(...) ld __VA_ARGS__; in(__VA_ARGS__);        // input ld
#define inch(...) char __VA_ARGS__; in(__VA_ARGS__);      // input char
#define inst(...) string __VA_ARGS__; in(__VA_ARGS__)     // input string
#define invs(name,sz) vst name(sz); in(name)              // input vst
#define invll(name,sz) vll name(sz); in(name)             // input vll
#define invpll(name,sz) vpll name(sz); inp(name)          // input vpll
#define invpld(name,sz) vt<pld> name(sz); inp(name)       // input vpld
#define invvll(name,y,x) vvll name(y,vt<ll>(x)); in(name) // input vvll
#define in_graph(vsz,esz,name,vfix) graph name(vsz); ing(vsz,esz,name,vfix)
#define in_network(vsz,esz,name,vfix) network name(vsz); innet(vsz,esz,name,vfix)
#define in_directed_graph(vsz,esz,name,vfix) graph name(vsz); indg(vsz,esz,name,vfix)
#define in_directed_network(vsz,esz,name,vfix) network name(vsz); indnet(vsz,esz,name,vfix)
const ll inf=2000000000000000000;       // infinity
const ll abc_max=26;                    // alphabet max size
const ll llong_max=9223372036854775807; // 9 * 10^18
const ld pi=3.1415926535;               // 3.14 ...
const size_t str_not_find=string::npos; // string::find()

string stosl(string& s); // 文字列を小文字に変換
string stosu(string& s); // 文字列を大文字に変換
graph to_graph(network& net); // network -> graph
network to_network(graph& g, ll c = 0); // graph -> wgraph
void bit_set(ll& x, ll i, ll b); // 整数xのi番目ビットをbに設定
ll bit_size(ll x); // 2進数にしたときのサイズを取得
string bit_tostr(ll x); // 整数xをstringに変換
template <class C> void fix_c(C& c, ll fix); // 値の調整
template <class C> void fix_cp(ll fix1, ll fix2, C& c); // 値の調整 (pair)
template <class T> void itr_next(T& itr, ll INF = inf); // イテレータのインクリメント
template <class T> void itr_prev(T& itr, ll INF = -inf); // イテレータのデクリメント
template <class C> auto& rat(C&, ll); // 逆順アクセス
template <class C> auto& rat(C&, ll, ll); // 逆順アクセス
graph reverse_graph(graph& g); // 隣接リストを逆順にする
network reverse_network(network& net); // 重み付き隣接リストを逆順にする
template <class T1, class ... T2> bool umax(T1& x, T2 ... args); // xを最大値に更新
template <class T1, class ... T2> bool umin(T1& x, T2 ... args); // xを最小値に更新

ll btest(ll x, ll i); ll divc(ll x, ll y); ll llog(ll a, ll b, bool u);
template <class T> bool orange(ll x, vt<T>& v); template <class T> bool orange(ll y, ll x, vvt<T>& v);
template <class T> bool range(ll x, vt<T>& v); template <class T> bool range(ll y, ll x, vvt<T>& v);
ll btest(ll x, ll i) { return (62 < i) ? 0 : static_cast<ll>(x & (1ll << i)); }
template <class ... T> void debug(T ... args) { for (auto e : { args ... }) cerr << " " << e; cerr << endl; }
ll divc(ll x, ll y) { return x / y + bool(x % y); }
void in(void) {}
template <class H, class ... T> void in(H& head, T& ... tail) { cin >> head; in(tail...); }
template <class T> void in(vt<T>& v) { for (auto& e:v) in(e); }
template <class T> void inp(vt<T>& v) { for (auto& e:v) in(e.first, e.second); }
void ing(ll v, ll e, graph& g, ll vfix) { ll a, b; g.resize(v); rep(i, 0, e) cin >> a >> b, a += vfix, b += vfix, g[a].push_back(b), g[b].push_back(a); }
void innet(ll v, ll e, network& net, ll vfix) { ll a,b,w; net.resize(v); rep(i,0,e) cin>>a>>b>>w,a+=vfix,b+=vfix,net[a].push_back({b,w}),net[b].push_back({a,w});}
void indg(ll v, ll e, graph& g, ll vfix) { ll a, b; g.resize(v); rep(i, 0, e) cin >> a >> b, a += vfix, b += vfix, g[a].push_back(b); }
void indnet(ll v, ll e, network& net, ll vfix) { ll a,b,w; net.resize(v); rep(i,0,e) cin>>a>>b>>w,a+=vfix,b+=vfix,net[a].push_back({b,w}); }
string stosl(string& s) { string res; for (auto e : s) if ('a' <= e && e <= 'z') res.push_back(tolower(e)); return res; }
string stosu(string& s) { string res; for (auto e : s) if ('a' <= e && e <= 'z') res.push_back(toupper(e)); return res; }
void bit_set(ll& x, ll i, ll b) { (b) ? x |= (1ll << i) : x &= ~(1ll << i); }
ll bit_size(ll x) { return llog(2, x, true); }
template <class T, class S> void fillvv(T b, T e, S x) { for(auto it=b;it!=e;it++) std::fill(all((*it)),x); }
template <class C> ll lcnt(C& c) { return ll(c.count()); }
template <class C, class X> ll lcnt(C& c, X x) { return ll(count(all(c), x)); }
ll llog(ll a, ll b, bool u) { ll now = 1, res = (u) ? 1 : 0; while (now < b) res++, now *= a; return (now != b) ? res - 1 : res; }
ll lpow(ll x, ll n) { if (x == 2) return (1ll << n); ll z = 1; rep(i, 0, n) z *= x; return z; }
template <class T> ll lsize(T& c) { return ll(c.size()); }
template <class T> bool orange(ll x, vt<T>& v) { return (x<0||ll(v.size())<= x); }
template <class T> bool orange(ll y, ll x, vvt<T>& v) { return (y<0||ll(v.size())<=y||x<0||ll(v[y].size())<=x); }
template <class... T> void out(T... x) { for(auto& a:{x...}) cout<<fixed<<setprecision(8)<<a<<endl; }
template <class C> void outc(C& c) { for(auto& a:c) cout<<a<<endl; }
ll pcnt(ll x){ bitset<64> b(x); return b.count(); } // C++20 popcount
template <class T> bool range(ll x, vt<T>& v) { return !orange(x, v); }
template <class T> bool range(ll y, ll x, vvt<T>& v) { return !orange(y, x, v); }
char toch(ll x) { return char(x+48); }
string tost(ll x) { return to_string(x); }
ll toll(char c) { return ll(c)-48; }
ll toll(string& s) { return stoll(s); }
graph to_graph(network& net) { graph res(lsize(net)); for(ll i=0;i<lsize(net);i++) for(auto&[next,c]:net[i]) res[i].push_back(next); return res; }
network to_network(graph& g, ll c) { network res(lsize(g)); for(ll i=0;i<lsize(g);i++) for(auto&next:g[i]) res[i].push_back({next,c}); return res; }
template <class C> void fix_c(C& c, ll fix) { for (auto& e : c) e += fix; }
template <class C> void fix_cp(ll fix1, ll fix2, C& c) { for (auto& e : c) { if (fix1 != 0) e.pf += fix1; if (fix2 != 0) e.ps += fix2; } }
template <class T> void itr_next(T& itr, ll INF) { if (*itr != INF) ++itr; }
template <class T> void itr_prev(T& itr, ll INF) { if (*itr != INF) --itr; }
template <class T> void makevv(ll ys, ll xs, vvt<T>& vv) { vv.resize(ys); rep(y,0,ys) vv[y].resize(xs); }
template <class C> auto& rat(C& c, ll i) { return c[lsize(c) - 1 - i]; }
template <class C> auto& rat(C& cc, ll i, ll j) { return cc[lsize(cc) - 1 - i][lsize(cc[lsize(cc) - 1 - i]) - 1 - j]; }
graph reverse_graph(graph& g) { graph res(lsize(g)); rep(i, 0, lsize(g)) for (auto& next : g[i]) res[next].push_back(i); return res; }
network reverse_network(network& net) { network res(lsize(net)); rep(i,0,lsize(net)) for(auto& [next,cost]:net[i]) res[next].push_back({i,cost}); return res; }
template <class T1, class ... T2> bool umax(T1& x, T2 ... args) { if (max({ args ... }) <= x) return false; x = max({ args ... }); return true; }
template <class T1, class ... T2> bool umin(T1& x, T2 ... args) { if (x <= min({ args ... })) return false; x = min({ args ... }); return true; }
template <class T> T trim(T& t, ll l, ll r) { vt<T> res(r-l); rep(i,0,r-l) res[i]=t[i]; return res; }
template <> string trim<string>(string& t, ll l, ll r) { string res(t,l,r); return res; }
template <ll i, class T> void tsort(T b, T e) { sort(b, e, [&](const auto& l, const auto& r) { return get<i>(l) < get<i>(r); }); }

/**********************************/
/********** BEGIN OF LIB **********/
/**********************************/

namespace LIB {}

namespace LIB {
	template <class T = long long, class U = std::less<T>, class F = std::hash<T>> struct AhriSet {
		using ll = long long; using it = typename std::multiset<T, U>::iterator;
		std::multiset<T, U> s; std::unordered_map<T, ll, F> m;
		AhriSet() {} AhriSet(std::vector<ll>& v) { for(auto&e:v) push(e); }
		it begin() { return s.begin(); } void clear(void) { s.clear(),m.clear(); } ll count(T x) { return m[x]; } bool empty(void) { return s.empty(); } it end() { return s.end(); } ll erase(T x) { m.erase(); return s.erase(x); } bool find(T x) { return (s.find(x)!=s.end()); } void insert(T x) { m[x]++,s.insert(x); } it lower_bound(T x) { return s.lower_bound(x); } ll size() { return ll(s.size()); } it upper_bound(T x) { return s.upper_bound(x); } bool operator == (const AhriSet& as) { return (s==as.s); }
		T back() { return *s.rbegin(); } T front() { return *s.begin(); } void push_back(T x) { m[x]++, s.insert(x); } void push_front(T x) { m[x]++,s.insert(x); } T pop_back() { auto res=*s.rbegin(); if(--m[res]==0) m.erase(res); s.erase(s.find(res)); return res; } T pop_front() { auto res=*s.begin(); if(--m[res]==0) m.erase(res); s.erase(s.find(res)); return res; }
		void push(T x) { m[x]++,s.insert(x); } T top(void) { return *s.begin(); } T pop(void) { T res=*s.begin(); if(--m[res]==0) m.erase(res); s.erase(s.find(res)); return res; }
		ll lower_bound_val(T x) { return *s.lower_bound(x); } ll unique_count(const T& x) { return ll(find(x)); } ll unique_size() { return ll(m.size()); } ll upper_bound_val(T x) { return *s.upper_bound(x); } ll erase1(T x) { if(m.count(x)==0) return 0; if(m[x]==1) s.erase(x),m.erase(x); else s.erase(s.find(x)),m[x]--; return 1; }
	};
}

/**********************************/
/*********** END OF LIB ***********/
/**********************************/

using namespace LIB;
//using mint = NT_ModINT< 998244353 >;
//using mint = NT_ModINT< 1000000007 >;