迷いませんか？

継続しないを座右の銘に

並列二分探索（パラレルバイナリサーチ）

C/C++ プログラミング 競技プログラミング

パラレルバイナリサーチ（並列二分探索）

CODE THANKS FESTIVAL2017Hが想定解はLCAでしたが並列二分探索でも解けるらしいのでやりたくなりました
並列に二分探索したくない？したいね
基本的にはこのブログをというかすべてです
英語読める人、圧倒的にそっち読んだほうがいいと思います。そして僕に教えてください

一般にQ個のクエリがあるとき、N人のメンバーそれぞれについていくつ処理したときに条件が満たされますか？という問題っぽい
普通に愚直にやると一個クエリ処理、N人調べる、もう一個処理...となりO(NQ)となりますね（実際にはクエリ処理計算量がコレにかかります）
目標としてはO( (N+Q) log Q)だと思います(クエリ処理あたりの細かいやつは無視です今は)
ここで何も考えず一人ずついくつクエリが必要かを二分探索するとO(NQ log Q)になります
明らかに悪化しているんですが並列二分探索って言ってるしN人同時に二分探索行えば軽く収まりそうですね
意味がわからないね

それぞれの人に対しlo[i]とhi[i]を持ちます、意味するところは察してください
すると一回一回のループである人が条件を満たしているか調べるのは(lo[i]+hi[i])/2個クエリを処理したときだけでいいので全部でN回ですね
そして一回一回クエリも全部処理するのでO(N+Q)となります
二分探索なのでこれにlog QがかかってO( (N+Q) log Q)になるのでうれしくなります
なんかよくわからないね

Meteors(SPOJ)

ブログで題材にされている問題です
まあ解かないとダメだろうとなり解くことにします

問題概要

N人のメンバーとM個の区画があり、N人にM個の区画が振り分けられています
この区画は環状につながっています
誰がその区画を担当しているかはO_i(1 ≤ i ≤ M)(1 ≤ O_i ≤ N)として与えられます
また、それぞれのメンバーが担当する区画に合わせてP_i(1 ≤ i ≤ N)(1 ≤ P_i ≤ 109)個の隕石が降り注ぐ必要があります
K回、L_i〜R_iまでの区画にA_i個ずつ隕石が降り注ぐというクエリが与えられます

それぞれのメンバーは何回目の隕石落下で目標を達成できるでしょう

解法

区間加算の点取得がBITで楽にできることをこれの解法を見てて知りました（区間加算区間和を考えればまあ自明っぽかった）
それぞれのクエリはBITを用いてL_iにA_iを、R_i+1に-A_iを足すことで達成できるのでQ個合わせて(O(Q log M))
それぞれの人について達成しているかは担当している区画全部見て和を調べるしかないので全員合わせてO(M log M)ですね
この二つを全部でlog Q回行うためO((Q + M) log M log Q)となります（あってるんだろうか）

めんどくさいのでchangedを持ち、変化なくなったら終了としました
実装としてはmid[(lo[i]+hi[i])/2]にiをpush_back
REP(q, k)を回してクエリ処理していき、mid[q]に入っている人を調べていきます
そうすればそれぞれの人について一回しか見なくて済みますね
このとき、その人の担当する区画を全部見て足すわけですが、最悪ケース考えるとなんと1018余裕で超えます、N WAしました悲しいね
その人の目標値を超えたタイミングでbreakしましょう
下のコードのBITは0indexedにしてます

int n, m, k;
ll p[314514];
vector<int> o[314514];
int l[314514], r[314514], a[314514];
int hi[314514], lo[314514];
BIT bit;

void apply(int k){ if(l[k] > r[k]){
        bit.add(l[k], a[k]);
        bit.add(0, a[k]);
        bit.add(r[k]+1, -a[k]);
    }else{
        bit.add(l[k], a[k]);
        bit.add(r[k]+1, -a[k]);
    }
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    REP(i, m){
        int O;
        cin >> O; O--;
        o[O].push_back(i);
    }
    REP(i, n)
        cin >> p[i];
    cin >> k;
    REP(i, k){
        cin >> l[i] >> r[i] >> a[i];
        l[i]--; r[i]--;
    }
    REP(i, 314514){
        lo[i] = 0; hi[i] = k;
    }

    bool changed = 1;
    while(changed){
        changed = 0;
        bit = BIT(m+1);
        vector<int> mid[314514];
        REP(i, n)
            if(lo[i] != hi[i])
                mid[(lo[i]+hi[i])/2].push_back(i);

        REP(q, k){
            apply(q);
            for(auto mem : mid[q]){
                changed = 1;
                ll sum = 0;
                for(auto sec : o[mem]){
                    sum += bit.get(sec);
                    if(sum >= p[mem]) break;
                }

                if(sum >= p[mem])
                    hi[mem] = q;
                else
                    lo[mem] = q+1;
            }
        }
    }
    REP(i, n){
        if(lo[i] >= k)
            cout << "NIE" << endl;
        else
            cout << lo[i]+1 << endl;
    }
}

Code Thanks Festival 2017 H - Union Sets

えー本番解けなかったのでね
LCAかけないからそっちも書くべきっぽいので並列二分探索書いた後書きます

問題概要

N個の集合のうち、ある二つの要素が属している集合を併合する操作をM回行います
このとき、要素X_iとY_iが何回目の操作で同じ集合に属すかという質問クエリがQ個与えられます
答えてください

解法

これも単純に考えたらO(MQ)ですね
質問の方がクエリになってますが実質クエリは操作の方ですね
並列二分探索によりO((M+Q) log M)になります（UnionFindの計算量は軽いから無視します(あの記号よくわからないので)）

int N, M, Q;
int a[114514], b[114514];
int x[114514], y[114514];
int lo[114514], hi[114514];
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    REP(i, M)
        cin >> a[i] >> b[i];
    cin >> Q;
    REP(i, Q){
        cin >> x[i] >> y[i];
        lo[i] = 0; hi[i] = M;
    }
 
    bool changed = 1;
    while(changed){
        changed = 0;
        Union_find uf(N+1);
        vector<int> mid[114514];
        REP(i, Q)
            if(hi[i]!=lo[i])
                mid[(lo[i]+hi[i])/2].push_back(i);
 
        REP(i, M){
            uf.unite(a[i], b[i]);
            
            for(auto q : mid[i]){
                changed = 1;
                if(uf.same(x[q], y[q]))
                    hi[q] = i;
                else
                    lo[q] = i+1;
            }
        }
    }
    REP(i, Q){
        if(lo[i] >= M)
            cout << -1 << endl;
        else
            cout << lo[i]+1 << endl;
    }
}

明らかにこっちのほうが簡単だね
これから並列二分探索の問題は解いていきたいね（そんなたくさんでなさそう）