RMQ算法题目-白红宇

RMQ算法题目

阅读量：4552 次

发布时间：2019-06-08

本文共 1295 字，大约阅读时间需要 4 分钟。

pku 3264

题意：

给定n个奶牛的高度，求区间[s,e]中最高与最低高度的差值。

rmq模板题目：

求出最高最低然后求差。

注意这里f[i][j]表示从j开始的2^i次方个数的最值。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define maxn 50007#define N 22using namespace std;int fMin[N][maxn],fMax[N][maxn];int pow2[N],a[maxn];void init_rmq(int len){    int i,j;    for (i = 0; i < N; ++i) pow2[i] = 1<

pku Frequent values

题意：

给定长度为n的不降序列，求询问区间[s,e]内出现频率最高的频率；

思路：

本题可用线段树的区间合并来做：

rmq做法，首先将其离散化相同的点映射到一个点上，并记录该点能够达到的最左端点最有端点；

分三种情况讨论[s,e]

hash[i]位i离散化后对应的新序号，R[hash[i]]表示i离散化后的点能够到达的最右端，L[hash[i]]表示i离散化后的点能够到达的最左端，

1：如果s与e对应的离散化后的点为同一点则频率为 e - s + 1;(1,1,1,1)

2：如果s与e所对应的离散化后的点相差1则频率为 Li = R[hash[l]] - l + 1; Ri = r - L[hash[r]] + 1; max(Li,Ri); (1 1 3 3)

3：如果s与e所对应的离散化后的点相差大于1则频率为

Li = R[hash[l]] - l + 1;

Ri = r - L[hash[r]] + 1;

Li = max(Li,Ri);

Ri = rmq(hash[l] + 1,hash[r] - 1);

max(Li,Ri)；

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define maxn 100007using namespace std;int hash[maxn],L[maxn],R[maxn];int a[maxn],f[maxn][22],pow2[22];void init_rmq(int len){    int i,j;    for (i = 0; i < 22; ++i) pow2[i] = 1<