staticな変数を使ってこう出来ます
最初に前処理が必要な競技プログラミングのライブラリに重宝します
void f(){ static bool init=0; if(!init){ init=1; //初回実行処理 } //毎回実行する処理 }
staticな変数を使ってこう出来ます
最初に前処理が必要な競技プログラミングのライブラリに重宝します
void f(){ static bool init=0; if(!init){ init=1; //初回実行処理 } //毎回実行する処理 }
gcc拡張により
関数の前に__attribute__(( constructor))を付けると最初に
関数の前に__attribute__(( destructor))を付けると最後に呼ばれます
__attribute__((constructor)) void constructor() { cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(15); }
とかしておくと便利ですclangでは使えなかった気がします(調べてないです)
コード例は抽象化してません
あしからず
コピペありの環境なら一番いいです
思想としてはポインタを使って必要になった時にノードを作るです
構築O(1)です
template<typename T> struct dynamic_segment{ struct node; using np=node*; struct node{ np ch[2]={0,0}; T val=0; }; np root=new node(); np add(int64_t l,int64_t r,int64_t x,T val,np t){ if(!(l<=x&&x<r))return t; if(!t)t=new node(); t->val+=val; if(r-l==1)return t; int64_t m=(l+r)/2; t->ch[0]=add(l,m,x,val,t->ch[0]); t->ch[1]=add(m,r,x,val,t->ch[1]); return t; } T get(int64_t l,int64_t r,int64_t a,int64_t b,np t){ if(!t)return 0; if(b<=l||r<=a)return 0; if(a<=l&&r<=b)return t->val; int64_t m=(l+r)/2; return get(l,m,a,b,t->ch[0])+get(m,r,a,b,t->ch[1]); } void add(int64_t x,T val){root=add(0,1LL<<32,x,val,root);} T get(int64_t l,int64_t r){return get(0,1LL<<32,l,r,root);} };
クエリになりますが、ポインタに慣れてない人はこちらを使うのもいいかも
ICPC等で、計算量に余裕がある場合もおすすめ
普段配列を使うところをmapに置き換えるだけです
unordered_mapにすればになるのでちょっと速くなるかも知れないです
構築O(1)です
template<typename T> struct dynamic_segment{ map<int64_t,T>node; constexpr static int64_t sz=1LL<<32; void add(int64_t x,T val){ x+=sz; while(x){ node[x]+=val; x/=2; } } T get(int64_t l,int64_t r){ l+=sz;r+=sz; T res=0; while(l<r){ if(l&1)res+=node[l++]; if(r&1)res+=node[--r]; l/=2;r/=2; } return res; } };
10^5要素のセグ木を10^5回のループ毎に作らなければいけないみたいなパターンで使えます
使ったノードを初期値に戻す事で使いまわします
template<typename T> struct dynamic_segment{ vector<T>node; vector<int>used; int sz=1,n; dynamic_segment(int n):n(n){ while(sz<n)sz*=2; node.resize(sz*2,0); } void add(int64_t x,T val){ x+=sz; while(x){ node[x]+=val; used.push_back(x); x/=2; } } T get(int64_t l,int64_t r){ l+=sz;r+=sz; T res=0; while(l<r){ if(l&1)res+=node[l++]; if(r&1)res+=node[--r]; l/=2;r/=2; } return res; } void clear(){ for(auto e:used)node[e]=0; used.clear(); } };
テストケースを見れるサイトを公開しました
library-checker-testcases.hotman78.com
sudo git clone https://github.com/yosupo06/library-checker-problems.git cd library-checker-problems
./generate.py -p (問題のファイル名)
とします
例えばunion-findなら
./generate.py -p unionfind
とします
./問題種類/問題名/in に入力
./問題種類/問題名/outに出力
ができてます!
これを事前に読んで欲しいです。
分割統治法の方針でセグ木に乗せられます
これにより、
が出来ます
からなるベクトルを考えると、これがモノイドになっています。
試しにベクトルとベクトルをくっつけてを作ってみます。
の2つが条件を満たすので、maxを取ります
右端も同様です
中央をまたぐやつとまたがないやつを考える分割統治法の王道により
のmaxです
それはそう
よって上手くセグ木に乗せられます(モノイドの要件を満たすのは意味論より明らか)
ps.この方法によって s*t*u=max(0,max(0,s+t),u)みたいな演算をモノイドとして処理出来たりもします(kadaneのアルゴリズムより)
拡大係数行列を考える。
この時、の時のみ解が存在する事が知られている。
転置行列についてもrankは同じであるため、で計算が出来る。
からでが求められる事から転置行列においては2倍の定数倍高速化も可能である。