某岛

… : "…アッカリ～ン . .. . " .. .

July 23, 2010

MIPT 105. RMQ problem

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 。。这尼玛询问过程也太长了。。实在是缩不动啊。。。