时间戳

首页 > 技术文章 > rmq模板

rmq模板

13224ACMer 2016-03-12 19:53 原文

/*
HDU 3183
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
const int MAXN=1010;
int a[MAXN];
int dp[MAXN][20];

void makeRMQIndex(int n,int b[])//形成最小值下标的RMQ
{
    for(int i=0;i<n;i++)
      dp[i][0]=i;
    for(int j=1;(1<<j)<=n;j++)
       for(int i=0;i+(1<<j)-1<n;i++)
          dp[i][j]=b[dp[i][j-1]]<=b[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
          //这里一定要加等号，就是相等的时候取下标小的
}
int rmqIndex(int s,int v,int b[])
{
    int k=(int)(log(v-s+1.0)/log(2.0));
    return b[dp[s][k]]<=b[dp[v-(1<<k)+1][k]]?dp[s][k]:dp[v-(1<<k)+1][k];
    //加等号，取小标小的
}
char str[MAXN];
int ans[MAXN];
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int m;
    while(scanf("%s%d",&str,&m)!=EOF)
    {
        int n=strlen(str);
        for(int i=0;i<n;i++)
               a[i]=str[i]-'0';
        makeRMQIndex(n,a);
        int t=0;
        int temp=0;
        for(int i=m;i<n;i++)//找n-m个数，每次从[t,i]中找最小的
        {
            t=rmqIndex(t,i,a);
            ans[temp++]=a[t++];
        }
        t=0;
        while(t<temp&&ans[t]==0)t++;
        if(t>=temp)printf("0\n");
        else
        {
            for(int i=t;i<temp;i++)printf("%d",ans[i]);
            printf("\n");
        }
    }
    return 0;
}

 

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
const int MAXN=50050;

int dpmax[MAXN][20];
int dpmin[MAXN][20];

void makeMaxRmq(int n,int b[])
{
    for(int i=0;i<n;i++)
       dpmax[i][0]=b[i];
    for(int j=1;(1<<j)<=n;j++)
      for(int i=0;i+(1<<j)-1<n;i++)
        dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
}
int getMax(int u,int v)
{
    int k=(int)(log(v-u+1.0)/log(2.0));
    return max(dpmax[u][k],dpmax[v-(1<<k)+1][k]);
}
void makeMinRmq(int n,int b[])
{
    for(int i=0;i<n;i++)
       dpmin[i][0]=b[i];
    for(int j=1;(1<<j)<=n;j++)
      for(int i=0;i+(1<<j)-1<n;i++)
        dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
}
int getMin(int u,int v)
{
    int k=(int)(log(v-u+1.0)/log(2.0));
    return min(dpmin[u][k],dpmin[v-(1<<k)+1][k]);
}

int a[MAXN];
int main()
{
    int n,Q;
    int u,v;
    while(scanf("%d%d",&n,&Q)!=EOF)
    {
        for(int i=0;i<n;i++)
           scanf("%d",&a[i]);
        makeMaxRmq(n,a);
        makeMinRmq(n,a);
        while(Q--)
        {
            scanf("%d%d",&u,&v);
            u--;
            v--;
            int t1=getMax(u,v);
            int t2=getMin(u,v);
            printf("%d\n",t1-t2);
        }
    }
    return 0;
}

 

推荐阅读