随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

RMQ

RMQ

       定义:
            A[0...n-1]                   目标数组                         Log2[1...n]                  2为底i的对数

      算法目的:

              给定海量询问区间,求解区间最值。
      算法核心思想:
            (只对最小值进行讨论,最大值的话可以通过原数组求相反数再求最小值获得)

              算法分两步:1、预处理          2、询问

              1) 预处理
                 f[i][j] 表示 [i, i + 2j - 1]这个区间内的最小值所在数的下标。

                     a) j = 0,显然f[i][0] = i;

                     b) j > 0, 由于这个区间长度必定是2的倍数,所以它一定能够拆成两个长度一样的子区间,即[i, i + 2j-1 - 1][i + 2j-1, i + 2j - 1],仔细观察可以发现:

                            f[i][j-1] 表示的区间是 [i, i + 2j-1 - 1]

                            f[i + 2j-1][j-1] 表示的区间是 [i, i + 2j-1 - 1]

                     为了方便阅读,令x = f[i][j-1],   y = f[i + 2j-1][j-1],所以f[i][j] = A[x] < A[y] ? x : y;

              2) 询问
                 询问的时候可以把原区间[l, r]拆成两个长度为2k的区间(区间之间允许有交),分别用f[l][k] f[r-2k+1][k]表示两个区间内最小值所在的下标。并且k取值要求能够使得 [l, l+2k-1] [r-2k+1,r] 的并集 [l, r]

                     于是 k为满足l+2k-1 <= r并且值最大,即2k <= r-l+1,则k <= log2(r-l+1), k为整数,所以klog2(r-l+1)的下取整,由于1 <= r-l+1 <= n

                     x = f[l][k],   y = f[r-2k+1][k],询问结果为:A[x] < A[y] ? x : y;

       算法复杂度:

              预处理:O( n log(n) )

              询问:O(1)

       给出我的模板:

 1 #define MAXN 50010
 2 #define MAXL 16
 3 #define MAXQ 200100
 4  
 5  
 6 // 该RMQ模板只用于求最小值,若要求最大值只需要将原数组取相反数,然后结果再取相反数即可
 7  
 8 class RMQData {
 9 public:
10        int index;
11        int val;
12 }rd[MAXN];
13  
14 int n;
15 int Log2[MAXN];         // Log2[i] = log2(i)
16 int f[MAXN][MAXL];    // f[i][j] 表示 [i, (i + 2^j) - 1]这个区间的最小值 对应数的下标
17                               // f[i][j] = min{ f[i][j-1] , f[ i + 2^(j-1) ][j-1] }
18  
19 void RMQ_Init() {
20        int i, j, p;
21  
22        // 计算log以2为底的i的对数 log2(i)
23        Log2[1] = 0;
24        for(i = 2; i < n; i++) {
25               Log2[i] = Log2[i-1];
26               if( 1<<(Log2[i] + 1) == i ) {
27                      Log2[i] ++;
28               }
29        }
30        for(j = 0; j < MAXL; j++) {
31               for(i = 0; i < n; i++) {
32                      if(j == 0) {
33                             f[i][0] = i;
34                      }else {
35                             f[i][j] = f[i][j-1];
36                             p = i + (1<<(j-1));
37                             if(p < n) {
38                                    if( rd[ f[p][j-1] ].val < rd[ f[i][j] ].val ) {
39                                           f[i][j] = f[p][j-1];
40                                    }
41                             }                         
42                      }
43               }
44        }
45 }
46  
47 // 询问的时候拆成两个长度为2^k的区间
48 // f[l][k] 和 f[r-2^k+1][k]
49 // 并且k的取值要求能够使得 [l,l+2^k-1] 和 [r-2^k+1,r] 的并集 为 [l, r]
50 // 于是 k为满足l+2^k-1 <= r并且值最大,即2^k <= r-l+1
51 // k <= log2(r-l+1), 又k为整数,所以k为log2(r-l+1)的下取整
52 int RMQ_Query(int l, int r) {
53        if(l > r) {
54               int tmp = l;
55               l = r;
56               r = tmp;
57        }
58        int k = Log2[r - l + 1];
59        return rd[ f[l][k] ].val < rd[ f[r-(1<<k)+1][k] ].val ? f[l][k] : f[r-(1<<k)+1][k];
60 }

 

PKU 3264 Balanced Lineup

       RMQ,求解区间最大最小值的差。


PKU 3368 Frequent values

       题意:给定一个长度为N(N <= 100000)的单调不降序列Si,然后是Q(Q <= 100000)条询问,问给定区间出现最多的数的次数。

       题解:离散化 + RMQ

    由于Q很大,询问的复杂度必须要log(n),这样一来就先确定下来是线段树了,这个题目有个限制条件,所有数都是单调不增的排列的,换言之,就是说如果两个数相同的话,他们之间的所有数必定也和它们相同。于是就有了O(Q log(n))(RMQ就是O(Q))的算法:

       对于所有的数均设定一个组号,也可以叫离散化吧,相同的数有相同的组号,然后将各个数的频率统计后记录在一个数组中,表示该类数的大小,对于输入的询问[x, y],直接查询它们在哪个组,分三种情况讨论:

       1) 如果xy在一个组,那么最长长度就是y - x + 1

       2) 如果组号相差1,那么找出两者的分界点z(假设z点和x点组号相同),那么答案就是Max{z - x + 1, y - z}

       3) 如果相差大于1,那么先将两头截掉,统计大的记录,再和中间那段的最大值比较大小,中间那段的最大值可以用线段树 或者 RMQ区间查询最值。

       本题还有线段树的解法,代码见:

       http://www.cppblog.com/menjitianya/archive/2011/03/29/142966.html

 

PKU 2452 Sticks Problem

      题意:给定一个长度为N(N <= 50000)的数列Si,要求找到SiSj(1 <= i < j <= N)使得所有的Sk(i < k < j)大于Si并且小于Sj。如果能找到这样的对数,输出最大的j-i,否则输出-1
      题解:二分 + RMQ(或线段树)

      首先考虑最暴力的情况,自然是枚举ij,然后判i+1j-1这些数是否满足条件,如果满足则更新j-i,这样的复杂度是O(n3)的,时间上显然说不过去。然后试着降掉一维,同样枚举ij,然后在判断是否满足条件时,利用RMQ求区间最值,这样的复杂度就降到了O(n2logn),然而N的数据量还是不允许我们这么做,于是只能试着寻找O(n logn)的算法。那么我们尝试枚举一个j,看看能不能通过它来确定i,这里有一条很明显的性质,就是如果SiSj-1都小于Sj那么Si+1Sj-1必然也都小于Sj,这条性质可以让我们二分枚举i的左边界t,采用二分找到最小的t使得St-1 >= Sj,也即St < Sj(t <= i < j),找的过程可以采用RMQ求出区间最大值进行比较,然后问题就转化成了在以下数列:St St+1 ... Sj-1 Sj 中找到最小的i(t <= i < j)使得Si+1Sj都大于Si,很明显,又是一个区间最值的问题,利用RMQ求出[t, j-1]最小值的下标,就是我们要求的i,如果有多个,必须选择最靠近j的,这是显然的。这样总的复杂度就降到O(n(logn)2)

       当然,求最值的时候可以采用线段树代替RMQ

       线段树的代码见:

       http://www.cppblog.com/menjitianya/archive/2011/03/29/142962.html


ZJU 2859 Matrix Searching

       题意:给定一个n*n(n <= 300)的矩阵,然后是(T <= 106)次询问,每次询问某个子矩阵中的最小值。

       题解:二维RMQ( 二维线段树)

      裸模板题。思想和一维RMQ一样,二维情况的f数组是四维的。

      线段树的代码见:

       http://www.cppblog.com/menjitianya/archive/2011/03/30/143010.html

 

PKU 2637 WorstWeather Ever

      题意:给定N(N <= 50000)条信息,表示第yi年的降水量是ri,然后给出M(M <= 10000)条询问,每条询问的格式是Y X,表示自从第Y年以来X这一年是最大的降水量,问这句话正确与否。

      正确的判断条件是:

            1.YX这些年的所有年份的降水量已知。

            2.Y的降水量 >= X的降水量。

            3.对于每个ZY < Z < XZ的降水量小于X的降水量。

      可能正确的判断条件是:

            其中有一年的降水量不知道。

      错误的判断条件是:

            其他情况。

       题解:二分 + RMQ

       逻辑强题。首先记录下每个信息所在的连续块,如果两个信息的连续块相同,说明它们之间的年份全部连续。年份的查找可以采用二分查找,然后就是分情况讨论了,对输入的两个年份YX,利用二分查找找到最大的小于等于给定年份的那条记录fYfX

       .如果两者查到的记录都在输入数据中出现过,然后判断他们是不是属于一个连续的块,只需要下标索引即可,然后是两种情况:

           1. 如果属于同一个连续块,说明中间的年份全部出现过,然后利用线段树查找fY的年份的最大降水量Yr[fY+1, fX-1]的最大降水量ZrfX的最大降水量Xr,如果满足以下条件:(Yr >= Xr && Zr < Xr)则说明条件属实,是true的情况,否则则是false

           2.如果不属于同一个连续块,说明中间的年份不是全部出现过,然后利用RMQ查找fY的年份的最大降水量Yr[fY+1, fX-1]的最大降水量ZrfX的最大降水量Xr,如果满足以下条件:(Yr >= Xr && Zr < Xr)则说明当前条件属实,但是也有可能没出现过的记录破坏这个条件,所以是maybe的情况,否则则是false

       .如果X能够查到,则利用线段树查找[fY+1, fX-1]的最大降水量ZrfX的最大降水量Xr,如果满足以下条件:Zr < Xr则说明条件有可能属实,是maybe的情况,否则则是false

       .如果Y能查到,这个条件就比较隐秘了,因为需要满足(Yr >= Xr && Zr < Xr),而ZrXr无从得知,但是我们可以知道Yr >= Xr > Zr,于是只要判断当前的Zr是否小于Yr

如果成立,则是maybe,否则就是false

       .最后一种情况就是XY的年份在先前的数据中都没有出现过,这肯定是maybe的情况。


PKU 2201 Cartesian Tree

       题意:给定N(N <= 50000)个整数对(key, a),要求将他们组织成一棵树二叉树,并且对于树的任意一个结点,满足如下两个性质:

       1) 当前结点的a值大于它父节点的a(小顶堆的性质)

       2) 当前结点的key值大于左子树的key值,并且小于右子树的key(排序二叉树的性质)

       题目保证所有的key值和a值都不同。

       题解:首先将所有整数对按key值递增排序,这样我们只需要对数组进行切分,如果第t个结点作为根结点,那么[1, t-1]必定是它的左子树集合,[t+1, N]必定是它的右子树集合,这样就能够保证第二个条件,而第一个条件需要满足父节点的a值小于左右子树的a值,所以第t个结点必定是所有数中a值最小的,于是可以规约出一个递归算法,对于当前区间[l, r],找到区间内a值最小的作为根结点,然后将它左边的区间和右边的区间进行相同的递归运算。初始区间为[1, N],当[l, r]满足 l > r即为递归出口。求区间最小值可以采用RMQ

       总的时间复杂度为排序的时间复杂度O(N log N)


posted on 2014-06-26 16:35 英雄哪里出来 阅读(3976) 评论(0)  编辑 收藏 引用 所属分类: 算法专辑


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理