Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

RMQ简洁的代码

Posted by makuiyu at 2013-12-24 10:55:44 on Problem 3264 and last updated at 2013-12-24 16:17:22
#include <algorithm>
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>

#define N 500010

using namespace std;

int cow[N], minc[N][20], maxc[N][20];
int n, q;

void RMQinit()
{
    int i, j, m;
    for(i=1; i<=n; ++i)
        minc[i][0] = maxc[i][0] = cow[i];
    m = int(log(n*1.0)/log(2.0));
    for(i=1; i<=m; ++i)
        for(j=n; j>=1; --j)
        {
            maxc[j][i] = maxc[j][i-1];
            if(j+(1<<(i-1)) <= n)
                maxc[j][i] = max(maxc[j][i], maxc[j+(1<<(i-1))][i-1]);

            minc[j][i] = minc[j][i-1];
            if(j+(1<<(i-1) <= n))
                minc[j][i] = min(minc[j][i], minc[j+(1<<(i-1))][i-1]);
        }
}

int RQMmin(int l, int r)
{
    int m = int(log(r-l+1.0)/log(2.0));
    return min(minc[l][m], minc[r-(1<<m)+1][m]);
}

int RQMmax(int l, int r)
{
    int m = int(log(r-l+1.0)/log(2.0));
    return max(maxc[l][m], maxc[r-(1<<m)+1][m]);
}

int main()
{
    int a, b;
    int i;
    scanf("%d %d", &n, &q);
    for(i=1; i<=n; ++i)
        scanf("%d", &cow[i]);
    RMQinit();
    while(q--)
    {
        scanf("%d %d", &a, &b);
        printf("%d\n", RQMmax(a, b)-RQMmin(a, b));
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator