莫隊アルゴリズム学習ノート(一)——普通莫隊

前言
モチームアルゴリズムを学ぶ前に、これはとても深いアルゴリズムだと思っていました.(実際には、それは非常に深いアルゴリズムである)このアルゴリズムは、ブロックと暴力の2つのアルゴリズムを玄学的に統合し、時間的複雑度O(N N)O(Nsqrt N)O(NN)の複数の区間問合せを解くオフラインアルゴリズムを構築した.
具体的な紹介
まず,クエリ中のl l lが存在する区間を第1キーワードとし,r r rの位置を第2キーワードとしてソートする.
次に,まず最初の質問を暴力的に解き,L Lポインタを最初の質問のl l lに向け,R Rポインタを最初の質問のr r rに向けることができる.
次に,i i i番目の問題については,いずれも現在問い合わせている区間[l i,r i][l_i,r_i][li,ri]の答えを前回問い合わせた区間[l i−1,r i−1][l_{i−1},r_{i−1}[li−1,ri−1]の答えから推定することができる.L Lポインタをl i−1 l＿から{i−1}li−1という位置からl i l_へi liは少しずつ移動し、移動しながら答えを更新し(答えを更新する過程は通常、元の答えを減算し、更新後の新しい答えを加える)、R R Rポインタに対する操作は似ている.
テンプレートの問題
このような説明は具体的ではありませんが、以下にテンプレートの問題を見てみましょう.【洛谷2709】小Bの質問
L i n k Link Link
【洛谷2709】小Bの問い合わせの問題解はブログ【洛谷2709】小Bの問い合わせ(莫隊テンプレート問題)を参照.
私のブログのコードを例にとると、具体的にいくつかの場所を見てみましょう.
最初の場所:読み込んだ質問をソートする方法.
シーケンスの情報を読み込みながら、シーケンスをブロックすることができます.

// 34 
pos[i]=(i-1)/sqrt(n)+1;//     

次に、各クエリを読み込むときに、各クエリ区間の境界l l lとr rを格納するだけでなく、このクエリが何番目に読み込まれたかも格納します.

// 35 
for(i=1;i<=Q;++i) read(q[i].l),read(q[i].r),q[i].pos=i;//         

このようにして、質問をソートすることができます.

// 26~29 
bool cmp(Query x,Query y)//     cmp()  
{
	//         ，        l       ，       ， r     l           
	// l         ， r     ，      
	//  ，                                 ，             
    return pos[x.l]<pos[y.l]||(pos[x.l]==pos[y.l]&&(pos[x.l]&1?x.r<y.r:x.r>y.r));
}
// 36 
sort(q+1,q+Q+1,cmp);//     

2つ目の場所:現在の質問の答えを前回の質問の答えからどのように移すか.
これはモキューアルゴリズムの比較コアの部分であるはずです.ここではL Lポインタを例にとると、R R Rポインタの動作も同様であり、具体的には私のコードを参考にすることができる.
第1の場合、L// 43 ans-=cnt[a[L]]*cnt[a[L]],--cnt[a[L]],ans+=cnt[a[L]]*cnt[a[L]],++L; // cnt[] ， ans 。 ans （ cnt[a[L]] ）， cnt[a[L]]（ cnt[a[L]] 1）， ans （ cnt[a[L]] ）， L 1 （ ， ， ）
第2の場合、L>q[i]である.l L>q[i].l L>q[i].l:

// 44 
--L,ans[q[i].pos]-=cnt[a[L]]*cnt[a[L]],++cnt[a[L]],ans[q[i].pos]+=cnt[a[L]]*cnt[a[L]];
//  L   1，   ans       ，   cnt[a[L]]（ cnt[a[L]] 1），   ans      （             ，        ，   ，       ）

複雑度分析
コードを分析しました.最後に、時間の複雑さを分析します.
L L Lポインタの場合、①ブロック内を移動する場合があります.各ブロックの大きさはNsqrt Nであるため、移動の時間的複雑度はO(N)O(sqrt N)O(N)であり、Q Q Q個の問い合わせがあるため、総複雑度はO(Q N)O(Qsqrt N)O(QN)である.②次のブロックに移動しました.各ブロックの大きさがNsqrt Nであるため、次のブロックに移動する度の複雑度はO(N)O(sqrt N)O(N)であり、またNsqrt N個のブロックが合計されるため、この場合の総複雑度はO(N)O(N)O(N)O(N)である.以上より、L Lポインタの移動複雑度は、おおよそO(QN)O(Qsqrt N)O(QN)である.
R R Rポインタの場合、L Lポインタが存在するブロックが変わらない限り、R R Rポインタが指す位置は常に**単調に増加(または減少)**し、すなわち、同じブロック内のL L Lポインタの場合、R R Rポインタの移動複雑度はO(N)O(N)O(N)O(N)であることが分かる.また、合計Nsqrt N個のブロックがあるので、R Rポインタの総移動複雑度はO(N N)O(Nsqrt N)O(NN)である.
従って、総計の複雑度はO((N+Q)N)O((N+Q)sqrt N)O((N+Q)N)であり、一般的にはN=QN=QN=Qであるため、時間的複雑度をO(N)O(Nsqrt N)O(NN)と近似することができ、これは比較的速いはずである.
莫隊アルゴリズムは、このような玄学的なアルゴリズムであり、巧みな暴力に相当する.
例題
付注、もう一つの例題:【洛谷1494】[国家合宿隊]小Zの靴下
L i n k Link Link
【洛谷1494】[国家合宿隊]小Zの靴下の問題解詳しくはブログ【洛谷1494】[国家合宿隊]小Zの靴下(莫隊)を参照