POJ 3264 RMQ問題STアルゴリズム
4846 ワード
以前は線分樹でRMQ問題を解決していたので、頭を省くことができましたが・・・(書きやすいので)...
しかしRMQはさすがに定数が大きいし、プログラムがSTよりも長いので・・・以前はSTアルゴリズムを書いていましたが、毎回最後まで+1なのか、-1なのか、境界問題処理の私の卵は何度も砕けていたので、今回はST(sparse table)計算法を改めて学び、これらの問題の理解をしっかりと処理しました.
STアルゴリズム:RMQ問題を解決する.RMQ問題:
区間最大値、最小値問題......
時間複雑度:nlogn,クエリO(1)を前処理する.前処理とクエリーの定数はいずれも極小です.セグメントツリーはnlognプリプロセッシングですが定数はやや大きく、クエリはlognです・・・もちろん、セグメントツリーには他にもサポートされている操作がありますので、ともかく.
STアルゴリズムの限界:静的RMQ問題を解決する.でも!RMQと接尾辞配列を組むと、とても使いやすい!
本題:
(この字はちょっと小さすぎますか?急いで大きい字に変えます)
こんな大きな字はずっと楽に見えますが、私の近眼にとっては.
こんな字は頼りになりますが・・・これでいいです.
st[i][j]表示,,r[i]r[i+1]r[i+2]....r[i+2^j-1]の一連で、配列の下にiからi+2^j-1までの区間内で、最も値がいくらであるかが示されている.△ここから、最値は最小値となり、最大値は同じです.
では明らかにst[i][0]=r[i];r[i]..r[i + 1] ... r[i+2^0-1]は実質的にr[i]からr[i]の区間である…つまりst[i][0]=r[i]を初期化すればよい.
次のポイントは、st[i][j]=min(s[i][j-1]、s[i+2^(j-1)][j-1]はどうやって来たのでしょうか?
例を挙げましょう.
i=3,j=3のときst[3][3]が示す区間が3 4 5 6である[78 9 10]
i=3,j=2のときst[3][2]が示す区間は明らかに3 4 5 6
このとき私たちは明らかに見ることができて、私たちは7の位置からつまりst[7][2]が示す区間7 8 9 10を必要とします.
ではst[3][3]=min(st[3][2],st[7][2]);
すると、構造過程が出てきます.
次のプログラムは,最大と最小の2つのケースをどのように構築するかを示す.
st[0][i]は[0][2][3]...[2^i-1]の区間です.[2^i-1]で表される下付き文字が現れ、すでにnを超えている場合は、明らかにこれ以上計算する必要はありません.
2^i-1すなわち(1<だいにそうサイクル
jは窮屈な区間起点位置(終点位置はj+2^i-1)として、彼の終点位置もnで考えなければならない.だから
値を取ると判断する場合は......
[j,j+2^i−1]区間全体を2つの同じ長さの区間に分割する.
[j,j+2^(i-1)-1,]区間と[j+2^(i-1),j+2^i-1の2つの区間であり,後者は実質的にst[j+2^(i-1)][i-1]である.
区間全体の最小値、すなわち
これにより初期化の問題が解決した.時間複雑度nlogn
===============
次に,O(1)のクエリをどのように実現するかである.
3 4 5 6 7 8という区間の最小値を調べると、実際には2つに分けてあげます.
クエリー3 4 4 5 6と5 6 7 8の最小値は、両方を最小にすればいいです.交差があり、並列セットが区間全体をカバーできる限り、彼の最小値は彼らの区間全体の最小値に違いないからだ.
次に、st[3][2]とst[5][2]の2つの場所から検索する方法を考えてみましょう.
いずれにしても、L+2^i-1(これがst[L][i]が示す区間の右端)はRよりも小さくなければならないか等しいか・・・区間:L,L+2^i-1
R-2^i+1は必ずLより大きいか等しい区間:R-2^I+1,R
同時に、彼らはまた合併しなければなりません!つまりR-2^i+1>=L+2^i-1
総合的に:最小のiを見つけて、満足します
L + 2 ^i - 1 >= R - 2 ^i + 1
簡略化後i=log(R-L+2)/log(2)-1の結果を上に上げます(それ自体が整数であれば動かない)
この式はC言語で表すのは複雑です.私は直接ddを使います.
i = int(log(r - l + 2)/log(2) + 0.99999) - 1; テストに合格できることを示します.
もちろん、この表現方法は科学的ではありません.私たちは多くの条件を利用していません.
この式も見てみましょう.
R - 2 ^i + 1 >= L + 2 ^i - 1
L+2^i-1>R-2^i+1と書くこともできます
化簡得i+1>(log(R-L+1)/log(2))
小さい番号の右の式は整数で、
一つの結論によると、小数点のある数字は、整数+1を取って、この数字自体より大きいに違いない.
このように見ると、iは右の小数点のある数字としてよい. i = (int) (log(R-L+1)/log(2))
もちろん、i=(int)(log(R-L+1)/log(2))の書き方は、区間長など、他の方法で説明することもできますが、思考量がやや大きく、考えたくないと思います
そうすると、プログラムが出てきます.flagは質問が大きいか小さいかを示します
すべての手順は次のとおりです.
しかしRMQはさすがに定数が大きいし、プログラムがSTよりも長いので・・・以前はSTアルゴリズムを書いていましたが、毎回最後まで+1なのか、-1なのか、境界問題処理の私の卵は何度も砕けていたので、今回はST(sparse table)計算法を改めて学び、これらの問題の理解をしっかりと処理しました.
STアルゴリズム:RMQ問題を解決する.RMQ問題:
区間最大値、最小値問題......
時間複雑度:nlogn,クエリO(1)を前処理する.前処理とクエリーの定数はいずれも極小です.セグメントツリーはnlognプリプロセッシングですが定数はやや大きく、クエリはlognです・・・もちろん、セグメントツリーには他にもサポートされている操作がありますので、ともかく.
STアルゴリズムの限界:静的RMQ問題を解決する.でも!RMQと接尾辞配列を組むと、とても使いやすい!
本題:
(この字はちょっと小さすぎますか?急いで大きい字に変えます)
こんな大きな字はずっと楽に見えますが、私の近眼にとっては.
こんな字は頼りになりますが・・・これでいいです.
st[i][j]表示,,r[i]r[i+1]r[i+2]....r[i+2^j-1]の一連で、配列の下にiからi+2^j-1までの区間内で、最も値がいくらであるかが示されている.△ここから、最値は最小値となり、最大値は同じです.
では明らかにst[i][0]=r[i];r[i]..r[i + 1] ... r[i+2^0-1]は実質的にr[i]からr[i]の区間である…つまりst[i][0]=r[i]を初期化すればよい.
次のポイントは、st[i][j]=min(s[i][j-1]、s[i+2^(j-1)][j-1]はどうやって来たのでしょうか?
例を挙げましょう.
i=3,j=3のときst[3][3]が示す区間が3 4 5 6である[78 9 10]
i=3,j=2のときst[3][2]が示す区間は明らかに3 4 5 6
このとき私たちは明らかに見ることができて、私たちは7の位置からつまりst[7][2]が示す区間7 8 9 10を必要とします.
ではst[3][3]=min(st[3][2],st[7][2]);
すると、構造過程が出てきます.
次のプログラムは,最大と最小の2つのケースをどのように構築するかを示す.
void makermq(int *r, int n)
{
for (int i = 0; i != n; ++ i) stmax[i][0] = stmin[i][0] = r[i];
for (int i = 1; (1 << i) <= n; ++ i)
for (int j = 0; j + (1 << i) - 1 < n; ++ j)
{
stmax[j][i] = max(stmax[j][i - 1], stmax[j + (1 << (i - 1))][i - 1]);
stmin[j][i] = min(stmin[j][i - 1], stmin[j + (1 << (i - 1))][i - 1]);
}
}
st[0][i]は[0][2][3]...[2^i-1]の区間です.[2^i-1]で表される下付き文字が現れ、すでにnを超えている場合は、明らかにこれ以上計算する必要はありません.
2^i-1すなわち(1<
jは窮屈な区間起点位置(終点位置はj+2^i-1)として、彼の終点位置もnで考えなければならない.だから
j + (1 << i) - 1 < n値を取ると判断する場合は......
[j,j+2^i−1]区間全体を2つの同じ長さの区間に分割する.
[j,j+2^(i-1)-1,]区間と[j+2^(i-1),j+2^i-1の2つの区間であり,後者は実質的にst[j+2^(i-1)][i-1]である.
区間全体の最小値、すなわち
stmin[j][i] = min(stmin[j][i - 1], stmin[j + (1 << (i - 1))][i - 1]);これにより初期化の問題が解決した.時間複雑度nlogn
===============
次に,O(1)のクエリをどのように実現するかである.
3 4 5 6 7 8という区間の最小値を調べると、実際には2つに分けてあげます.
クエリー3 4 4 5 6と5 6 7 8の最小値は、両方を最小にすればいいです.交差があり、並列セットが区間全体をカバーできる限り、彼の最小値は彼らの区間全体の最小値に違いないからだ.
次に、st[3][2]とst[5][2]の2つの場所から検索する方法を考えてみましょう.
いずれにしても、L+2^i-1(これがst[L][i]が示す区間の右端)はRよりも小さくなければならないか等しいか・・・区間:L,L+2^i-1
R-2^i+1は必ずLより大きいか等しい区間:R-2^I+1,R
同時に、彼らはまた合併しなければなりません!つまりR-2^i+1>=L+2^i-1
総合的に:最小のiを見つけて、満足します
L + 2 ^i - 1 >= R - 2 ^i + 1
簡略化後i=log(R-L+2)/log(2)-1の結果を上に上げます(それ自体が整数であれば動かない)
この式はC言語で表すのは複雑です.私は直接ddを使います.
i = int(log(r - l + 2)/log(2) + 0.99999) - 1; テストに合格できることを示します.
もちろん、この表現方法は科学的ではありません.私たちは多くの条件を利用していません.
この式も見てみましょう.
R - 2 ^i + 1 >= L + 2 ^i - 1
L+2^i-1>R-2^i+1と書くこともできます
化簡得i+1>(log(R-L+1)/log(2))
小さい番号の右の式は整数で、
一つの結論によると、小数点のある数字は、整数+1を取って、この数字自体より大きいに違いない.
このように見ると、iは右の小数点のある数字としてよい. i = (int) (log(R-L+1)/log(2))
もちろん、i=(int)(log(R-L+1)/log(2))の書き方は、区間長など、他の方法で説明することもできますが、思考量がやや大きく、考えたくないと思います
そうすると、プログラムが出てきます.flagは質問が大きいか小さいかを示します
int ask(int l, int r, int flag)
{
//int tmp = int(log(r - l + 2)/log(2) + 0.99999) - 1; // ，
int tmp = int(log(r - l + 1)/log(2));
if (!flag) return min(stmin[l][tmp], stmin[r - (1 << tmp) + 1][tmp]);
else return max(stmax[l][tmp], stmax[r - (1 << tmp) + 1][tmp]);
}
すべての手順は次のとおりです.
#include <cstdio>
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int max_n = 50000 + 10;
int n, questions;
int stmax[max_n][20], stmin[max_n][20];
int a[max_n];
void makermq(int *r, int n)
{
for (int i = 0; i != n; ++ i) stmax[i][0] = stmin[i][0] = r[i];
for (int i = 1; (1 << i) <= n; ++ i)
for (int j = 0; j + (1 << i) - 1 < n; ++ j)
{
stmax[j][i] = max(stmax[j][i - 1], stmax[j + (1 << (i - 1))][i - 1]);
stmin[j][i] = min(stmin[j][i - 1], stmin[j + (1 << (i - 1))][i - 1]);
}
}
int ask(int l, int r, int flag)
{
//int tmp = int(log(r - l + 2)/log(2) + 0.99999) - 1; // ，
int tmp = int(log(r - l + 1)/log(2));
if (!flag) return min(stmin[l][tmp], stmin[r - (1 << tmp) + 1][tmp]);
else return max(stmax[l][tmp], stmax[r - (1 << tmp) + 1][tmp]);
}
int main()
{
scanf("%d%d", &n, &questions);
for (int i = 0; i != n; ++ i) scanf("%d", &a[i]);
makermq(a, n);
while (questions -- )
{
int L ,R;
scanf("%d%d", &L, &R);
--L, --R;
int a = ask(L, R, 1);
int b = ask(L, R, 0);
printf("%d
", a - b);
}
return 0;
}