RMQのSTアルゴリズムの使用【まとめ】【固定区間の長さを求める1次元テクニックを添付】

4079 ワード

RMQ問題:区間最小値問題(区間最大値問題も解決できます.)
解決アルゴリズム:ST(Sparse-Tableアルゴリズム、ダイナミック企画に基づいて区間の一番値を求めるアルゴリズム)
STアルゴリズムは前処理とクエリの二つの部分に分けられます.
まず配列を定義します.Amax[i][j]をiから始まり、長さは2^jの区間の中の最大値とします.Amin[i][j]はiから始まり、長さは2^jの区間の中の最小値です.
前処理は次の通りです.長さが2^jの区間を二つの区間に分けます.同じ区間です. 区間1は i...i+2^(j-1)-1 区間2は i+2^(j-1)….i+2^j-1 取得状態移行方程式(長さが増分されたもの)A max[i]=max(Amax[i]、[j-1],Amax[i+2^(j-1)]Amin[i]、[j]=max(Amin[i]、[j-1],Amin[i+2(j-1)[J-1]境界条件はF[i]=[i]= 二:クエリーは、MAX L Rが[L,R]区間の最大値MIN L Rを表しています.[L,R]区間の最小値を照会するためには、Lから始まる長さ2^kの区間と、Rで終わる長さ2^kの区間の両方が[L,R]k値全体を含めて計算されるようなk値を求める必要があります. 1,k=(int)log 2(R-L+1) 2,k値は0から2^kがR-L+1より大きいまでインクリメントされる. kが見つかったら、クエリ操作は、return max(Amax[L]、[k],Amax[R-(1<実際の問題
N個の数のシーケンスA[]とM回のクエリーを与え、MAX x yは区間[x,y]の最大値を求め、MIN x yは区間[x,y]の最小値を求める.
コード:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 10010
#define INF 1000000000
using namespace std;
int A[MAXN];
int N, M;
int Amax[MAXN][50];//Amax[i][j]   i   ，   2 j           
int Amin[MAXN][50];//Amin[i][j]   i   ，   2 j           
void RMQ_init()
{
    for(int i = 1; i <= N; i++)
        Amax[i][0] = Amin[i][0] = A[i];
    for(int j = 1; (1<<j) <= N; j++)
    {
        for(int i = 1; i + (1<<j)-1 <= N; i++)
        {
            Amax[i][j] = max(Amax[i][j-1], Amax[i+(1<<(j-1))][j-1]);
            Amin[i][j] = min(Amin[i][j-1], Amin[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(char *op, int L, int R)
{
    //k      
    int k = 0;
    while((1<<(k+1)) <= R-L+1) k++;
    //int k = (int)(log(double(R - L + 1))/log((double)2));
    if(strcmp(op, "MAX") == 0)
        return max(Amax[L][k], Amax[R-(1<<k)+1][k]);
    else
        return min(Amin[L][k], Amin[R-(1<<k)+1][k]);
}
int main()
{
    while(scanf("%d%d", &N, &M), N||M)
    {
        for(int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
        RMQ_init();
        char op[10];
        int x, y;
        while(M--)
        {
            scanf("%s%d%d", op, &x, &y);
            printf("%d
", query(op, x, y));
        }
    }
    return 0;
}

上記のRMQの使用について述べました.シーケンスの任意の区間の長さの最大値と最小値を求めます.
延長:N個の数のシーケンスを与え、固定区間長はkです.M回クエリーMAX x(MIN x)——クエリ[x,x+k-1]の最大値(最小値)
この時も私たちは上記の方法でやってもいいです.しかし、この問題に対しては、区間長がkの時の情報を使うだけです.
考えてみますどのように最適化しますか?区間長がkの場合の情報だけを使用してください.
つまり、すべての区間長の可能な値を二次元配列で記憶する必要はない.
私達はただこのように定義する必要があります.Amax[i]にはシーケンスA[i]から始まり、長さはkの区間の中の最大値が格納されています.Amin[i]も同じです.
このようにすれば、私達は長さの増加によって区間の長さがkの時を押し出すだけでいいです.
照会については、変更もなく変数lenを設定します.適切なlenが見つかりました.つまり、Lから始まる区間とRで終わる長さが2^lenまでの区間がクエリ区間をカバーすればいいです.
コードを詳しく見てください

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1000000+10
using namespace std;
int N, M, k;
int A[MAXN];
int Amax[MAXN];
int Amin[MAXN];
void RMQ_init()
{
    for(int i = 1; i <= N; i++)
        Amax[i] = Amin[i] = A[i];
    for(int j = 1; (1<<j) <= k; j++)
    {
        for(int i = 1; i + (1<<j) - 1 <= N; i++)
        {
            Amax[i] = max(Amax[i], Amax[i + (1<<(j-1))]);//  
            Amin[i] = min(Amin[i], Amin[i + (1<<(j-1))]);
        }
    }
}
int query(char *op, int L, int R)
{
    int len = 0;
    while(1<<(len+1) <= R-L+1) len++;// len 
    if(strcmp(op, "MAX") == 0)
        return max(Amax[L], Amax[R-(1<<len)+1]);
    else
        return min(Amin[L], Amin[R-(1<<len)+1]);
}
int main()
{
    while(scanf("%d%d%d", &N, &M, &k) != EOF)
    {
        for(int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
        RMQ_init();
        char op[10];
        int x;
        while(M--)
        {
            scanf("%s%d", op, &x);
            printf("%d
", query(op, x, x+k-1));
        }
    }
    return 0;
}

スタックとキューでBFSとDFSアルゴリズムを実現する.

アルゴリズム効果ABテストにおけるPV-UV非対称性