{"id":92,"date":"2010-02-07T23:46:00","date_gmt":"2010-02-07T15:46:00","guid":{"rendered":"http:\/\/localhost\/?p=92"},"modified":"2010-02-07T23:46:00","modified_gmt":"2010-02-07T15:46:00","slug":"the_mipt_105_a_o_n_rmq_offline_algorithm","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=92","title":{"rendered":"MIPT 105 \u4e00\u79cdO\uff08n\uff09\u7684RMQ\u79bb\u7ebf\u7b97\u6cd5"},"content":{"rendered":"

\u6211\u5728GYH\u795e\u725b\u7684\u8bba\u6587\u91cc\u770b\u5230\u5bf9\u4e8eRMQ\u95ee\u9898\u6709\u4e00\u79cd\u5f88\u65b9\u4fbf\u7684\u79bb\u7ebf\u7b97\u6cd5\u3002\u3002\u4e8e\u662f\u5199\u4e86\u4e2a\u7a0b\u5e8f\u53bbAMIPT105\u8fd9\u9053\u6807\u51c6\u7684RMQ\u9898\u3002\u3002
\u8bba\u6587\u5728\u8fd9\u91cc\uff1acid-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<\/a>
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<\/a>("%fn",Ans[i]);
}
int main()
{
\/\/freopen("in","r",stdin);
\/\/freopen("out","w",stdout);
init();
solve();
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u6211\u5728GYH\u795e\u725b\u7684\u8bba\u6587\u91cc\u770b\u5230\u5bf9\u4e8eRMQ\u95ee\u9898\u6709\u4e00\u79cd\u5f88\u65b9\u4fbf\u7684\u79bb\u7ebf\u7b97\u6cd5\u3002\u3002\u4e8e\u662f\u5199\u4e86\u4e2a\u7a0b\u5e8f\u53bbAMIPT105\u8fd9\u9053\u6807\u51c6\u7684RMQ\u9898\u3002\u3002\u8bba\u6587\u5728\u8fd9\u91cc\uff1acid-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.docCode:#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)]; } } […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/92"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=92"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/92\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=92"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=92"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=92"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}