2020-06-20

【gcc拡張】c++でmain関数の前と後に関数を呼ぶ

gcc拡張により
関数の前に__attribute__(( constructor))を付けると最初に
関数の前に__attribute__(( destructor))を付けると最後に呼ばれます

__attribute__((constructor))
void constructor() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);
}

とかしておくと便利ですclangでは使えなかった気がします(調べてないです)

2020-06-20

セグ木の初期化がボトルネックになる際の対処法3選

コード例は抽象化してません
あしからず

1.がちがちの動的セグ木を使う

コピペありの環境なら一番いいです
思想としてはポインタを使って必要になった時にノードを作るです
構築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);}
};

2.急造動的セグ木を使う

クエリ $O(log^2N)$ になりますが、ポインタに慣れてない人はこちらを使うのもいいかも
ICPC等で、計算量に余裕がある場合もおすすめ
普段配列を使うところをmapに置き換えるだけです
unordered_mapにすれば $O(logN)$ になるのでちょっと速くなるかも知れないです
構築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;
    }
};

3.セグ木を使いまわす

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();
    }
};

2020-06-18

yosupo judgeのテストケースを見る方法

その他解説

追記

テストケースを見れるサイトを公開しました
library-checker-testcases.hotman78.com

コマンドプロンプトを開きます

gitを入れます(手順は各自調べてください)

cdコマンドで適当なディレクトリに移動して下の2つのコマンドを打ちます

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に出力
ができてます！

2020-06-17

最大部分配列問題(連続部分列の総和の最大値)をセグ木に載せる

テクニック解説

ark4rk.hatenablog.com

これを事前に読んで欲しいです。
分割統治法の方針でセグ木に乗せられます
これにより、

点更新
[l,r)間の連続部分列における総和の最大値を求める

が出来ます

$( (左端を含む最大部分配列),(右端を含む最大部分配列),(区間の最大部分配列),(区間の総和))$
からなるベクトルを考えると、これがモノイドになっています。

試しにベクトル $s$ とベクトル $t$ をくっつけて $s\times t$ を作ってみます。

$s\times t$ の(左(右)端を含む最大部分配列):

$(sの左端を含む最大部分配列)$
$(sの区間の総和)+(tの左端を含む最大部分配列)$
の2つが条件を満たすので、ｍaxを取ります
右端も同様です

$s\times t$ の区間の最大部分配列:

中央をまたぐやつとまたがないやつを考える分割統治法の王道により
$(sの最大部分配列)$
$(tの最大部分配列)$
$(sの右端を含む最大部分配列)+(tの左端を含む最大部分配列)$
のmaxです

$s\times t$ の総和:

$(sの総和)+(tの総和)$
それはそう

よって上手くセグ木に乗せられます(モノイドの要件を満たすのは意味論より明らか)

ps.この方法によって s*t*u=max(0,max(0,s+t),u)みたいな演算をモノイドとして処理出来たりもします(kadaneのアルゴリズムより)

2020-06-17

Ax=bの解の存在判定をO(N×M×min(N,M))で行う

テクニック解説

拡大係数行列 $(A|b)$ を考える。

この時、 $rank(A)=rank(A|b)$ の時のみ解が存在する事が知られている。

転置行列についてもrankは同じであるため、 $O(N\times M\times min(N,M))$ で計算が出来る。

$rank(A^{t})$ から $O(N^{2})$ で $rank((A|b)^{t})$ が求められる事から転置行列においては2倍の定数倍高速化も可能である。