RMQ
题意是，有长度最多50,000的正整数序列，最多200,000次询问，对于每次询问(l, r)，需要输出下标[l, r]范围内序列最大值和最小值的差。
最近啃的是郭华阳的《RMQ与LCA问题》，敲了下基于倍增思想的ST算法。O(nlgn)预处理后，可以O(1)回答每次询问。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define M 100000 int n,q,mx[M][20],mn[M][20]; void init() { memset(mn,127,sizeof mn); memset(mx,0,sizeof mx); int i,j,k,l; for(i=0;i<n;i++) { scanf("%d",&j); mx[i][0]=mn[i][0]=j; } for(k=l=1;l<n;k++,l<<=1) { for(i=0;i<n;i++) { mx[i][k]=max(mx[i][k-1],mx[i+l][k-1]); mn[i][k]=min(mn[i][k-1],mn[i+l][k-1]); } } } void solve() { int i,j,k,l; while(q--) { scanf("%d%d",&i,&j); if(--i==--j) { puts("0"); continue; } for(k=0,l=1;i+l<=j+1;k++,l<<=1); k--; l>>=1; printf("%d\n",max(mx[i][k],mx[j+1-l][k]) -min(mn[i][k],mn[j+1-l][k])); } } int main() { while(~scanf("%d%d",&n,&q)) { init(); solve(); } return 0; } |
之前做这题用的是O(qlgn)的线段树：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<cstdio> int n,q,ml,h[50000],mx,mn; struct node { int mx,mn; node *l,*r; }mem[100000],*root; void init(int L,int R,node *p) { int m=L+R>>1; if(L==R) { p->mx=p->mn=h[m]; return; } p->l=&mem[ml++]; init(L,m,p->l); p->r=&mem[ml++]; init(m+1,R,p->r); p->mx=p->l->mx>p->r->mx?p->l->mx:p->r->mx; p->mn=p->l->mn<p->r->mn?p->l->mn:p->r->mn; } void ins(int l,int r,int L,int R,node *p) { int m=L+R>>1; if(l==L&&r==R) { mx=mx>p->mx?mx:p->mx; mn=mn<p->mn?mn:p->mn; return; } if(r<=m) ins(l,r,L,m,p->l); else if(l>m) ins(l,r,m+1,R,p->r); else { ins(l,m,L,m,p->l); ins(m+1,r,m+1,R,p->r); } } int main() { int i,j,k; while(~scanf("%d%d",&n,&q)) { ml=0; root=&mem[ml++]; for(i=0;i<n;i++) scanf("%d",&h[i]); init(0,n-1,root); while(q--) { scanf("%d%d",&i,&j); mn=1000001; mx=0; ins(i-1,j-1,0,n-1,root); printf("%d\n",mx-mn); } } return 0; } |