我在GYH神牛的论文里看到对于RMQ问题有一种很方便的离线算法。。于是写了个程序去AMIPT105这道标准的RMQ题。。
论文在这里：cid-47648079f9d741d1.skydrive.live.com/self.aspx/OI/RMQ%e9%97%ae%e9%a2%98%e7%9a%84%e7%a6%bb%e7%ba%bf%e8%bf%91%e7%ba%bf%e6%80%a7%e7%ae%97%e6%b3%95.doc
Code:
#include<cstdio>
#include<utility>
using namespace std;
typedef pair<int,int> pi;
const int maxn=250000,maxm=2*maxn;
int stack[maxn],top=0,n,cnt=0,m;
int F[maxn];
float A[maxn],Ans[maxm];
inline void makeset(int x){F[x]=x;}
int find(int x){if(F[x]==F[F[x]])return F[x];return F[x]=find(F[x]);}
inline void Union(int x,int y){F[y]=x;}
int first[maxn],next[maxm],qnt=0;
pi data[maxm];
void add_query(int l,int r)
{
data[qnt]=pi(l,cnt++);
next[qnt]=first[r];
first[r]=qnt++;
}
void init()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%f",A+i),first[i]=-1;
scanf("%d",&m);int l,r;
for(int i=0;i<m;i++) scanf("%d %d",&l,&r),add_query(l,r-1);
}
void solve()
{
for(int i=0;i<n;i++)
{
makeset(i);
while(top&&A[stack[top-1]]>=A[i])
{Union(i,stack[–top]);}
stack[top++]=i;pi*tmp;
for(int j=first[i];j!=-1;j=next[j])
{
tmp=data+j;
Ans[tmp->second]=A[find(tmp->first)];
}
}
for(int i=0;i<m;i++)
printf("%fn",Ans[i]);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
solve();
}