RMQ算法区间最值

问题类型：是多次询问一个大区间里子区间的最值问题

dp + 位运算的思想处理

rmax[i][j]表示从i开始到i + 2^j - 1的区间里的最大值
dp[i][j] ==== (i,i + 2^j - 1)
分为

dp[i][j-1] === (i,i + 2^(j-1) - 1)
dp[i + 1 << (j-1))][j-1] === (i + 2^(j-1),i + 2^j - 1)

所以初始处理就比较明显了

int rmax[maxn][20];

int rmin[maxn][20];

int a[maxn];

int n,m;

void rmq(int flag)

{

    for(int i = 1;i <= n;i++)

    {

        rmax[i][0] = rmin[i][0] = a[i];

    }

    for(int j = 1;(1 << j) <= n;j++)

    {

        for(int i = 1;i + (1 << j) - 1 <= n;i++)

        {

            if(flag)

                rmax[i][j] = max(rmax[i][j-1],rmax[i + (1 << (j-1))][j-1]);

            else

                rmin[i][j] = min(rmin[i][j-1],rmin[i+(1<<(j-1))][j-1]);

        }

    }

}

外层循环是跨度，很明显，因为他是基础

查询算法，求出最小分割区间k，覆盖l，r

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        for(int i = 1;i <= n;i++)

            scanf("%d",&a[i]);

        rmq(1);

        rmq(0);

        int l,r;

        for(int i = 1;i <= m;i++)

        {

            scanf("%d%d",&l,&r);

            int k = 0;

            while(1 << (k + 1) <= r - l + 1)

                k++;

            int ansmax = max(rmax[l][k] , rmax[r - (1 << k) + 1][k]);

            int ansmin = min(rmin[l][k] , rmin[r - (1 << k) + 1][k]);

            printf("%d\n",ansmax - ansmin);

        }

    }

    return 0;

}

巴特西

RMQ算法区间最值

最新文章

热门文章