发表了博客
2018/12/23 21:59

倍增RMQ算法浅谈

题目: 求某一区间的最大值。 f[a][b]中a代表的是当前的位置,b代表的是以a为起点往后移动的区间长度2^b。 1 void bz(int n) 2 { 3 for(int i=1;i<=n;i++) 4 f[i][0]=a[i];//先定义长度1为自己本身。 5 for(int j=1;(1<<j)<=n;j++)//以区间逐步移长。//tip1 6 { 7 for(int i=1;i+(1<<j)-1<=n;i++)//点的位置逐步往后移。//tip2 8   f[i][j]=max(f[i][j-1],f[i+(1<<(j-1)...

0
0
发表了博客
2019/02/15 07:47

RMQ问题--范围最小值问题

范围最小值问题(Range Minium Query,RMQ)---RMQ问题 一、一维问题 给出一个n个元素的数组A1,A2,...,An, 设计一个数据结构, 支持查询操作Query(L,R):计算min(AL,AL+1,...AR) 显然, 用一个循环来计算最小值 显然不够快, 即使是前缀和的思想也不能提高效率! 那么, 实践中最常用的是Tarjan的Sparse-Table算法(就是ST表) 预处理时间:O(nlogn) 查询时间:O(1) (这个算法非常好写,而且还不容易出错) (其实:RMQ...

0
0
发表了博客
2018/03/05 09:56

【bzoj1067】[SCOI2007]降雨量 倍增RMQ

题目描述 我们常常会说这样的话:“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年,且对于任意Y<Z<X,Z年的降雨量严格小于X年。例如2002,2003,2004和2005年的降雨量分别为4920,5901,2832和3890,则可以说“2005年是自2003年以来最多的”,但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知,有的说法是可能正确也可以不正确的。 输入 输入仅一行包含一个正整数n,为已知的数据。以下n行每...

0
0
发表了博客
2020/06/16 13:21

st表、RMQ和LCA

int lca(int x,int y) { if(de[x]<de[y]) swap(x,y); int d=de[x]-de[y]; for(int i=log2(d);i>=0;i--) { if(d&(l<<i)) { x=fa[x][i]; } } for(int i=log2(n);i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } if(x!=y) { return fa[x][0]; } else { ...

0
0
发表了博客
2020/06/16 13:18

st表、RMQ和LCA

int lca(int x,int y) { if(de[x]<de[y]) swap(x,y); int d=de[x]-de[y]; for(int i=log2(d);i>=0;i--) { if(d&(l<<i)) { x=fa[x][i]; } } for(int i=log2(n);i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } if(x!=y) { return fa[x][0]; } else { ...

0
0
发表了博客
2020/06/16 13:23

st表、RMQ和LCA

int lca(int x,int y) { if(de[x]<de[y]) swap(x,y); int d=de[x]-de[y]; for(int i=log2(d);i>=0;i--) { if(d&(l<<i)) { x=fa[x][i]; } } for(int i=log2(n);i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } if(x!=y) { return fa[x][0]; } else { ...

0
0
发表了博客
2016/06/13 13:26

HDU2888二维RMQ

HDU2888二维RMQ dp[row][col][i][j] 表示[row,row+2^i-1]x[col,col+2^j-1] 二维区间内的最小值 这是RMQ-ST算法的核心: 倍增思想 == min( [row,row+ 2^(i-1)-1]x[col,col+2^j-1], [row+2^(i-1),row+2^i-1]x[col,col+2^j-1] ) = min(dp[row][col][i-1][j], dp[row+(1<<(i-1))][col][i-1][j] ) //y轴不变,x轴二分 (i!=0) 或 == min( [row,row+2^i-1]x[col,col+2^(j-1)-1], [row,row+2^i-1]x[col+2^(i-1),col+2^j-1] ) = min(dp[...

0
0
发表了博客
2019/02/02 17:11

UVA - 1618 Weak Key(RMQ算法)

题目: 给出k个互不相同的证书组成的序列Ni,判断是否存在4个证书Np、Nq、Nr、Ns(1≤p<q<r<s≤k)使得Nq>Ns>Np>Nr或者Nq<Ns<Np<Nr。 思路: 有两种情况<小、最大、最小、大>、<大、最小、最大、小>,枚举第1个和第4个数,用RMQ查询这两个数之间的最大值和最小值,然后根据给出的条件判断一下就可以了。 看到好多大佬不用RMQ也写出来了,还需要在研究一下。 代码: #include <bits/stdc++.h> #define inf 0x3f3f3f3f #define MA...

0
0
发表了博客
2018/07/29 19:54

【HDOJ6305】RMQ Similar Sequence(笛卡尔树)

题意: 给定一个数组a,现在存在一个数组b,其元素值在[0,1]随机生成 若对于a,b,任意rmq问题的最值出现在同一个数组中的位置,则数组b的价值为∑b[i],否则为0,求数组b的期望价值 n<=1e6 思路: 1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 usi...

0
0
发表了博客
2019/02/13 19:40

ST算法(倍增)(用于解决RMQ)

ST算法 在RMQ(区间最值问题)问题中,我了解到一个叫ST的算法,实质是二进制的倍增。 ST算法能在O(nlogn)的时间预处理后,用O(1)的时间在线回答区间最值。 f[i][j]表示从i位起的2^j个数中的最大(最小)数,即[i,i+2^j-1]中的最大(最小)值,从其定义中可以看出来。 下面的实现代码以最大值为例: 预处理: void preST(int len){ for(int i=1;i<=len;i++) f[i][0]=i; int m=log(len)/log(2)+1; for(int j=1;j<m;j...

0
0
没有更多内容
加载失败,请刷新页面
点击加载更多
加载中
下一页