### Brief description:

… RMQ 模板題。。（無修改。。多詢問。。。

### Analysis:

… （線段樹直接 T 不解釋。。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; inline int _1(int x){return 1 << x;} inline void RD(int &x){scanf("%d", &x);} /*----*/ const int L = 19, N = 250000; float ST[L][N]; int n, m, i, j, a, b, lv, up; int main(){ freopen("in.txt", "r", stdin); RD(n); for(i=0;i<n;++i) scanf("%f", &ST[0][i]); for (up = log2(n), lv = 1; lv <= up; ++ lv) for (i = 0; i <= n - _1(lv); ++i) ST[lv][i] = min(ST[lv - 1][i], ST[lv - 1][i + _1(lv - 1)]); RD(m); while (m--){ RD(a), RD(b), lv = log2(b - a); printf("%.6f\n", min(ST[lv][a], ST[lv][b - _1(lv)])); } }

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;} template<class T> inline T low_bit(T x) {return x & -x;} inline void RD(int &x){scanf("%d", &x);} /*----*/ const int N = 250001; float A[N], C[N], res; int n, m, i, j, a, b; int main(){ //freopen("in.txt", "r", stdin); RD(n); for(i=1;i<=n;++i) scanf("%f", &A[i]), C[i] = A[i]; for (i=1;i<=n;++i) for (j=1;j<low_bit(i);j<<=1) checkMin(C[i], C[i-j]); RD(m); while (m--){ RD(a), RD(b), ++a, res = A[b]; while (b!=a){ for (--b;b-a>=low_bit(b);b-=low_bit(b)) checkMin(res, C[b]); checkMin(res, A[b]); } printf("%.6f\n", res); } }

(正常向。。。

(2.10s +- 。。

(3.35s +- 。。。

#include<iostream> #include<cmath> float a[19][250000]; int n,i,j,t;main(){ for(scanf("%d",&n),i=0;i<n;++i)scanf("%f",a[0]+i); for(t=log2(n),i=1;i<=t;++i)for(j=0;j<=n-(1<<i);++j)a[i][j]=std::min(a[i-1][j],a[i-1][j+(1<<i-1)]); for(scanf("%d",&n);n--;)scanf("%d%d",&i,&j),t=log2(j-i),printf("%.6f\n",std::min(a[t][i],a[t][j-(1<<t)])); }

#include <cstdio> #define M(a,b) if (b<a) a=b; #define B(x) (x&-x) const int N = 250001; float A[N], C[N], r; int n, i, j; main(){ for(scanf("%d", &n), i=1;i<=n;++i) scanf("%f", &A[i]), C[i] = A[i]; for (i=1;i<=n;++i) for (j=1;j<B(i);j<<=1) M(C[i], C[i-j]); for(scanf("%d",&n);n--;){ scanf("%d%d",&i,&j),++i,r=A[j]; while (i!=j){ for (--j;j-i>=B(j);j-=B(j)) M(r, C[j]); M(r, A[j]); } printf("%.6f\n",r); } }

( 鬼畜縮碼版。。。

(174cm 。。。

(。206cm 。。這尼瑪詢問過程也太長了。。實在是縮不動啊。。。

### External link:

http://acm.mipt.ru/judge/problems.pl?problem=105

http://richardxx.yo2.cn/articles/bit_rmq.html

http://www.cnblogs.com/ambition/archive/2011/04/06/bit_rmq.html

http://www.cppblog.com/MatoNo1/archive/2011/03/19/142238.html