首页 > 代码库 > Poj3264(ST算法)

Poj3264(ST算法)

2024-07-26 01:57:49   211人阅读

    以前也没怎么听过这个算法,网络赛中有个题好像是什么最近公共祖先,看了一下这个算法,是一个动态规划,核心思想是倍增.

    用途:解决rmq问题,例如给一个序列{an},询问是任意一个区间(l,r)中最小的数或者最大的数.

    时间复杂度:预处理的时间是O(nlogn) 查询:O(1)

    局限性:只能处理序列不变的情况,因为只能针对一个序列进行预处理.       

    状态定义:dp[i][j],表示一个序列中从第i个数长度为2^j的连续序列中的最大值(根据实际需要).

    状态转移方程(以最大值为例):dp[i][j]=max(dp[i][j-1],dp[i+1<<(j-1)][j-1]);     

    处理完后就可以在O(1)的时间内处理每一个询问了.

    对于一个查询(l,r) 定义int tp=(int)log2(r-l);答案ans=max(dp[l][tp],dp[r-(1<<tp)+1][tp]);查询的区间重合也对结果没有影响,满足区间加法.

    以Poj3264为例,AC代码:

 1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <stdlib.h> 5 #include <math.h> 6 using namespace std; 7 #define maxn 100005 8 #define maxl 20 //2^16ÊÇ65536 9 int num[maxn],f_max[maxn][maxl],f_min[maxn][maxl],n;10 void rmq_st()11 {12     for(int i=1;i<=n;i++)13     {14      f_max[i][0]=num[i];15      f_min[i][0]=num[i];16     }17     for(int j=1;j<=(int)log2(n);j++)18      for(int i=1;i<=n;i++)19      {20       f_max[i][j]=max(f_max[i][j-1],f_max[i+(1<<(j-1))][j-1]);21       f_min[i][j]=min(f_min[i][j-1],f_min[i+(1<<(j-1))][j-1]);22      }23 }24 int main()25 {26     int Q;27     while(~scanf("%d%d",&n,&Q))28     {29         for(int i=1;i<=n;i++)30          scanf("%d",&num[i]);31         rmq_st();32         int l,r,maxnum,minnum,m;33         for(int i=1;i<=Q;i++)34         {35             scanf("%d%d",&l,&r);36             m=(int)(trunc(log2(r-l+1)));37             maxnum=max(f_max[l][m],f_max[r-(1<<m)+1][m]);38             minnum=min(f_min[l][m],f_min[r-(1<<m)+1][m]);39             cout<<maxnum-minnum<<endl;40         }41     }42     return 0;43 }

 

Poj3264(ST算法)


联系
我们