同样,感谢yg大神对我的指导.
本来本蒟蒻是想来练一练RMQ的,没先到用树状数组过了....
本蒟蒻对这题数据也是无语的,树状数组和线段树居然不爆空间......
好了,看楼下两位大神分别用了RMQ和线段树,于是本蒟蒻决定发一波树状数组,其实树状数组应该跑的最快,线段树常数太大......
树状数组求区间最大值,应该算得上是模板题了吧,
在来看维护区间最大值的算法,我们先看一整段区间[1,n]都需要初始化的情况。(即 h[] 数组都为0,现在需要用 a[] 数组更新 h[] 数组)
- void updata(int i, int val)
- {
- while (i <= n)
- {
- h[i] = max(h[i], val);
- i += lowbit(i);
- }
- }
这样是也可行的,于是我们就有了一个O(n*logn)的维护方法,即当要更新一个数的时候,把 h[] 数组清零, 然后用数组 a[] 去更新 h[] 数组 但这个复杂度显然太高了。
但是,我们不难发现:对于x,可以转移到x的只有,x-2^0,x-2^1,x-2^2,.......,x-2^k (k满足2^k < lowbit(x)且2^(k+1)>=lowbit(x))
举例:
若 x = 1010000= 1001000 + lowbit(1001000) = 1001000 + 1000 = 1001000 + 2^3= 1001100 + lowbit(1001100) = 1001100 + 100
= 1001100 + 2^2= 1001110 + lowbit(1001110) = 1001110 + 10 = 1001110 + 2^1= 1001111 + lowbit(1001111) = 1001111 + 1
= 1001111 + 2^0
所以对于每一个h[i],在保证h[1...i-1]都正确的前提下,要重新计算h[i]值的时间复杂度是O(logn),具体方法如下:
- h[x] = a[x];
- lx = lowbit(x);
- for (i=1; i<lx; i<<=1)
- h[x] = max(h[x], h[x-i]);
- x += lowbit(x);
这样,我们就可以得到一个和树状数组维护区间合算法很像的算法
- void updata(int x)
- {
- int lx, i;
- while (x <= n)
- {
- h[x] = a[x];
- lx = lowbit(x);
- for (i=1; i<lx; i<<=1)
- h[x] = max(h[x], h[x-i]);
- x += lowbit(x);
- }
- }
这个算法的时间复杂度是O((logn)^2),所以现在就可以在O((logn)^2)的时间内完成最值的区间维护了。 本段文字引用:http://blog.csdn.net/u010598215/article/details/48206959
接着就很好办了,把输入的数据按序编号,然后输出找到的最大值的编号即可.
好了,闲话少叙,贴上代码:
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
/* P2311 loidc,想想看 题解
*/ const int N=1011000;//居然没有爆空间,数据太弱
long long n,m,i,a[N],t[N*4],k1,k2,j,f[N];//注意:此处树状数组要开到N*4
/* 接下来是树状数组求区间最大值模板,详情见上面的分析
*/
- long long lowbit(long long x){
- return x&(-x);
- }
- void tree(long long x){
- long long l;
- while(x<=n){
- t[x]=a[x];
- l=lowbit(x);
- for(long long h=1;h<l;h<<=1){
- t[x]=max(t[x],t[x-h]);
- }
- x+=lowbit(x);
- }
- return;
- }
- long long sum(long long l,long long r){
- long long ans=0;
- while(r>=l){
- ans=max(ans,a[r]);
- r--;
- for(;(r-lowbit(r))>=l;r-=lowbit(r)){
- ans=max(ans,t[r]);
- }
- }
- return ans;
- }
- //模板结束
- int main(){
- scanf("%lld",&n);
- for(i=1;i<=n;i++){
- scanf("%lld",&a[i]);
- f[a[i]]=i;//将输入数据编号
- tree(i);//初始化
- }
- scanf("%lld",&m);
- for(i=1;i<=m;i++){
- scanf("%lld%lld",&k1,&k2);
- printf("%lld\n",f[sum(k1,k2)]);//将找到的最大值的编号输出
- }
- system("pause");
- exit(0);
- }
接下来,我们来聊一聊RMQ的做法, 首先普及一下,什么是RMQ:
RMQ的主要运用是Sparse_Table算法(简称ST算法),它可以在O(nlogn)的预处理以后实现O(1)的查询效率,即整体时间复杂度为O(nlogn)-O(1)。
RMQ的主要原理就是dp,用 a[1..n]表示一组数,F[i,j]表示从a[i]到a[i+2^j-1]这个范围内的最大值,也就是以a[i]为起点连续2^j个数的最大值,由于元素个数为2^j个,所以从中间平均分成两部分,每一部分的元素个数刚好为2^(j-1)个.
很明显,整个区间的最大值一定是左右两部分最大值中的较大值,满足动态规划的最优性原理:
状态转移方程:F[i,j]=max(F[i,j-1],F[i+2^(j-1),j-1])
边界条件为:F[i,0]=a[i]
我们可以采用自底向上的算法递推出所有符合条件的f[i,j]的值,就可以在O(nlogn)的时间复杂度内预处理F数组。
例如:f[2,3]保存的是a[2],a[3],a[4],……,a[9]中的最小值,而f[2,3]=
min(f[2,2],f[6,2])=min((a[2],a[3],a[4],a[5]),(a[6],a[7],a[8],a[9]))
预处理F数组代码:
- for(i=1;i<=n;i++)f[i][0]=a[i]; //初始化
- for(j=1;j<=int(log(n)/log(2));j++) //递推
- for(i=1;i+(1<<j)-1<=n;i++)
- f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
对于询问[L,R],求出最大的x,满足2^x<=R-L+1,即x=int(log(R-L+1)/log(2)) [L,R]=[L,L+2^x-1] ∪[R+1-2^x,R],两个子区间元素个数都是2^x个,所以RMQ(L,R)=max(F[L,x],F[R+1-2^x,x])
询问操作代码:
- int Ask(int L,int R)
- { int k;
- k=int(log(R-L+1)/log(2));
- return max(f[L][k],f[R+1-(1<<k)][k]);
- }
该算法总时间复杂度为O(NlogN+M) 本段文字引用https://wenku.baidu.com/view/4e0e4778f111f18582d05a03.html?from=search
好了,后面的就好办了,跟树状数组一样,输出找到最大值的编号,
这又怎么做呢?其实很简单:
只需要将状态转移方程嵌在a数组利用即可:
f[i][j]=(a[f[i][j-1]]>a[f[i+(1<<(j-1))][j-1]])?f[i][j-1]:f[i+(1<<(j-1))][j-1]
询问时也一样:return a[f[l][k]]>a[f[r+1-(1< 是不是很简单呢?