【模版】莫隊(修正莫隊、樹上莫隊を含む)アルゴリズム
101254 ワード
アルゴリズム
チームアルゴリズムはオフラインで問題を解決するための効率的な暴力アルゴリズムです.前知識点:①①ブロック分け②②s o r t sortキーワード並び替え③③l c a lca lcaクエリー(ツリーツリーツリー列)時間複雑度:O(n(\sqrt｛n｝)O(n*)O(n∗n)空間複雑度:O(n＋n)O(n＋n)O(n＋n＋n)@
アルゴリズムの流れ:一、ブロックサイズを決定します.ブロックサイズはn\sqrt{n}nです.各要素がどのブロックに属するかを決定します.
追加説明:l l l、r r rを現在の照会区間の左右端点とし、L L L、R R Rは照会区間が必要な左右端点とする.
1 1.左の端を右に動かすと、答えに対する貢献はマイナスです.①L Lに迫るL Lをl lで右に移動すると、1桁ずつ移動して、答えを更新します.現在位置の答えを先に更新して、右に移動します.②最終的に私たちの更新答案の区間は［l,L−1］［l,L−1］［L,L−1］です.③L L Lという位置は私達は答えを更新していません.l lを右に移動する時、私達は無関係の照会区間の答えだけを更新します.
2 2.右の端を右に動かすと、答えに対する貢献がプラスになります.①R R R Rに近づいているr rを右に移動すると、1ビットずつ移動して、答えを更新します.まず右に移動して、新しい位置の答えを更新します.②最終的に私たちが解答を更新する区間は[r,R][r,R][r,R]です.③R R R Rという位置は、上記左端点が右に移動する時に照応し、左端点が減少し、右端点が加算された答えを更新しました.多减すると补正されますが、最终的に両者の交差区間は区間[L,R][L,R][L,R]の答えです.
3.左の端を左に移動すると、答えに対する貢献は正しいです.もうこれ以上説明しないで、先に移動して、解答を更新して、[L,l−1][L,l−1][L,l−1]部分の答えを補った.
4.右の端を左に動かすと、答えに対する貢献はマイナスです.もうこれ以上説明しないで、先に解答を更新して、また移動して、[R+1,r][R+1,r]部分の答えを削除しました.
先に更新しますか?それとも先に移動しますか?順番に注意してください.絵を描く方法で先着順を判断することができます.
莫隊の例題:【国家合宿隊】小Zの靴下の例題コード:
莫隊の基礎の上で、改正の操作を加えました.[国家合宿隊]数色/メンテナンスキューの修正と検索が交互に行われます.難しい点は、検索操作は順序付けされたもので、どのような修正がされたかは確認できません.元々は左右の区間を固定すれば、答えを記録することができます.
修正チームを持って延長します.一、修正操作もエンドポイントとして移動します.左右のエンドポイントが検索の左右のエンドポイントに対応する時に、時間の順序を調整して、時間的にも該当するようにします.そのため、s o r t sortの並び替えを調整する必要があります.ブロックサイズはn 2/3 n^｛2/3｝n 2/3です.できないと証明します①左の端のブロックを小さいから大きいまで並べ替えます.②左端点がブロック相であると同時に、右端点があるブロック(右端点でもかまいません.両者はほとんど区別がありません.)を小から大へ並べ替えます.③右エンドポイントのブロックも同じで、クエリの時間順に小さいものから順に並べ替えます.
三、現在の時間を記録する変数t＿i m e timeが右(新しい時間)に近づいてきた時、まず自分で増加してから、答えを更新します.現在時刻を記録している変数t＿i m＿timeが左(古い時間)に近づいてきたら、まず答えを更新してから、自減します.初期値は0 0のため、現在の所在時間として記録されています.
例題コード:
ノードをシーケンスに記録すると、ツリー上の問題はシーケンス問題になります.それで普通のチームの状況になりました.
どのように適切なシーケンスを見つけて、ツリーをシーケンスに変換しますか?普通のd f s dfs dfs順序では問題が解決できない場合、オラ順序の概念を導入する必要があります.オーラル・シーケンスは、ある点を巡回する前と後の両方において、現在のノードを記録する特殊なd f s dfs dfsシーケンスである.このように、シーケンス長は2∗n2＊n 2∗nである.各点は2回記録されます.f＿i r＿fir[]fir[]とl s t[]lst[]の2つの配列は、各ノードがシーケンスにおいて最初に出現し、最後に出現した位置をそれぞれ記録する.v's[]vis[]vis[]は、その時点までに訪問されたことがあるかどうかを示しています.
アルゴリズムプロセス:
ツリー上の2点u u uとv vのl c a lcaをwとし、f＿i r[u]<=f＿i r[v]fir[u]]<=fir[v]fir[u]]==fir[v]とする.
①w wがドットu uであれば(2点はチェーン上にある).経路u−−v−v−vが経験する点は、「f＿i r[u],f＿i r[v]」[fir]、[u],fir[v]、[u]とラベル付けされたサブストリングにある.このような点は経路u−−v−v−u−vが経験した点ではないので、2回の出現点は0 0 0に寄与する.②経路u−−v＞v−u−v上の点はサブストリングの中で一回だけ現れて、それぞれ計算に寄与します.
②w w wがドットu uでない場合(2点は同じチェーンにない).このとき取ったサブストリングの下付きは[l s t[u],f i r[v][lst[u],fir[v][lst[u],fir[v]]に対応します.この2つの点のl c a lcaを記憶します.2点の経路はl c a lca lcaだけがこの段の串内にないからです.左区間の端点はf＿i r＿fir[u]fir[u]を取る必要がないので、[f＿i r[u],l s t[u]−1]、[fir],lst[u]-1]、[fir],lst[u]−1]の区間は余分です.②類の質問に対しては、l c a lca lcaは追加的な添加が必要であり、答えを更新したらl c a lca lcaのv＿v i s visを元に戻す(l c a lcaは連続的なサブ串内にないため).
例題:Count on a tree II例題コード:
チームアルゴリズムはオフラインで問題を解決するための効率的な暴力アルゴリズムです.前知識点:①①ブロック分け②②s o r t sortキーワード並び替え③③l c a lca lcaクエリー(ツリーツリーツリー列)時間複雑度:O(n(\sqrt｛n｝)O(n*)O(n∗n)空間複雑度:O(n＋n)O(n＋n)O(n＋n＋n)@
アルゴリズムの流れ:一、ブロックサイズを決定します.ブロックサイズはn\sqrt{n}nです.各要素がどのブロックに属するかを決定します.
int part = sqrt(n);
int num = ceil((double)n/part);
for(int i = 1; i <= num; i++)
for(int j = (i-1)*part+1; j <= i*part; j++)
bel[j] = i;
bool cmp(pro a, pro b) {return bel[a.l] == bel[b.l] ? a.r < b.r : bel[a.l] < bel[b.l];}
追加説明:l l l、r r rを現在の照会区間の左右端点とし、L L L、R R Rは照会区間が必要な左右端点とする.
1 1.左の端を右に動かすと、答えに対する貢献はマイナスです.①L Lに迫るL Lをl lで右に移動すると、1桁ずつ移動して、答えを更新します.現在位置の答えを先に更新して、右に移動します.②最終的に私たちの更新答案の区間は［l,L−1］［l,L−1］［L,L−1］です.③L L Lという位置は私達は答えを更新していません.l lを右に移動する時、私達は無関係の照会区間の答えだけを更新します.
2 2.右の端を右に動かすと、答えに対する貢献がプラスになります.①R R R Rに近づいているr rを右に移動すると、1ビットずつ移動して、答えを更新します.まず右に移動して、新しい位置の答えを更新します.②最終的に私たちが解答を更新する区間は[r,R][r,R][r,R]です.③R R R Rという位置は、上記左端点が右に移動する時に照応し、左端点が減少し、右端点が加算された答えを更新しました.多减すると补正されますが、最终的に両者の交差区間は区間[L,R][L,R][L,R]の答えです.
3.左の端を左に移動すると、答えに対する貢献は正しいです.もうこれ以上説明しないで、先に移動して、解答を更新して、[L,l−1][L,l−1][L,l−1]部分の答えを補った.
4.右の端を左に動かすと、答えに対する貢献はマイナスです.もうこれ以上説明しないで、先に解答を更新して、また移動して、[R+1,r][R+1,r]部分の答えを削除しました.
先に更新しますか?それとも先に移動しますか?順番に注意してください.絵を描く方法で先着順を判断することができます.
莫隊の例題:【国家合宿隊】小Zの靴下の例題コード:
#include
");
continue;
}
int k = gcd(a, b);
a /= k, b /= k;
printf("%d/%d
",a,b);
}
system("pause");
return 0;
}
莫隊の基礎の上で、改正の操作を加えました.[国家合宿隊]数色/メンテナンスキューの修正と検索が交互に行われます.難しい点は、検索操作は順序付けされたもので、どのような修正がされたかは確認できません.元々は左右の区間を固定すれば、答えを記録することができます.
修正チームを持って延長します.一、修正操作もエンドポイントとして移動します.左右のエンドポイントが検索の左右のエンドポイントに対応する時に、時間の順序を調整して、時間的にも該当するようにします.そのため、s o r t sortの並び替えを調整する必要があります.ブロックサイズはn 2/3 n^｛2/3｝n 2/3です.できないと証明します①左の端のブロックを小さいから大きいまで並べ替えます.②左端点がブロック相であると同時に、右端点があるブロック(右端点でもかまいません.両者はほとんど区別がありません.)を小から大へ並べ替えます.③右エンドポイントのブロックも同じで、クエリの時間順に小さいものから順に並べ替えます.
if(bel[a.l] == bel[b.l]) return bel[a.r] == bel[b.r] ? a.time < b.time : a.r < b.r;
else return bel[a.l] < bel[b.l];
三、現在の時間を記録する変数t＿i m e timeが右(新しい時間)に近づいてきた時、まず自分で増加してから、答えを更新します.現在時刻を記録している変数t＿i m＿timeが左(古い時間)に近づいてきたら、まず答えを更新してから、自減します.初期値は0 0のため、現在の所在時間として記録されています.
例題コード:
#include
",ans[i]);
system("pause");
return 0;0000000
}
ノードをシーケンスに記録すると、ツリー上の問題はシーケンス問題になります.それで普通のチームの状況になりました.
どのように適切なシーケンスを見つけて、ツリーをシーケンスに変換しますか?普通のd f s dfs dfs順序では問題が解決できない場合、オラ順序の概念を導入する必要があります.オーラル・シーケンスは、ある点を巡回する前と後の両方において、現在のノードを記録する特殊なd f s dfs dfsシーケンスである.このように、シーケンス長は2∗n2＊n 2∗nである.各点は2回記録されます.f＿i r＿fir[]fir[]とl s t[]lst[]の2つの配列は、各ノードがシーケンスにおいて最初に出現し、最後に出現した位置をそれぞれ記録する.v's[]vis[]vis[]は、その時点までに訪問されたことがあるかどうかを示しています.
アルゴリズムプロセス:
ツリー上の2点u u uとv vのl c a lcaをwとし、f＿i r[u]<=f＿i r[v]fir[u]]<=fir[v]fir[u]]==fir[v]とする.
①w wがドットu uであれば(2点はチェーン上にある).経路u−−v−v−vが経験する点は、「f＿i r[u],f＿i r[v]」[fir]、[u],fir[v]、[u]とラベル付けされたサブストリングにある.このような点は経路u−−v−v−u−vが経験した点ではないので、2回の出現点は0 0 0に寄与する.②経路u−−v＞v−u−v上の点はサブストリングの中で一回だけ現れて、それぞれ計算に寄与します.
②w w wがドットu uでない場合(2点は同じチェーンにない).このとき取ったサブストリングの下付きは[l s t[u],f i r[v][lst[u],fir[v][lst[u],fir[v]]に対応します.この2つの点のl c a lcaを記憶します.2点の経路はl c a lca lcaだけがこの段の串内にないからです.左区間の端点はf＿i r＿fir[u]fir[u]を取る必要がないので、[f＿i r[u],l s t[u]−1]、[fir],lst[u]-1]、[fir],lst[u]−1]の区間は余分です.②類の質問に対しては、l c a lca lcaは追加的な添加が必要であり、答えを更新したらl c a lca lcaのv＿v i s visを元に戻す(l c a lcaは連続的なサブ串内にないため).
例題:Count on a tree II例題コード:
#include
",ans[i]);
system("pause");
return 0;
}