https://13331.org/26.html
http://en.wikipedia.org/wiki/Range_minimum_query
http://www.cnblogs.com/kuangbin/p/3227420.html

BIT

树状数组解决 RMQ，由于 RMQ 问题无法区间相减，因此只能询问前后缀以及单调的修改。

http://codeforces.com/gym/100460/problem/K

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;

VII A, B;
int a[N],b[N];
int n;

namespace BIT{
    int C1[N], C2[N];
    void Add(int C[], int x, int d){
        for (;x<=n;x+=low_bit(x)) checkMin(C[x], d);
    }
    int Sum(int C[], int x){
        int res = INF; for (;x;x^=low_bit(x)) checkMin(res, C[x]);
        return res;
    }

} using namespace BIT;


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    FLC(C1, C2, 0x3f);

    int m; RD(n); REP(i, n) A.PB(MP(RD(), i));
    REP(i, n) B.PB(MP(RD(), i));
    SRT(A); SRT(B);
    A.PB(MP(INF, INF)); B.PB(MP(INF, INF));

    DWN(i, n, 0){
        Add(C1, n-i, A[i].se);
        Add(C2, n-i, B[i].se);
    }

    RD(m);
    REP(i, m) RD(a[i]); REP(i, m) RD(b[i]);

    // 1..n

    REP(i, m){
        int aa = Sum(C1, n-UBD(A, MP(a[i], INF))  );
        int bb = Sum(C2, n-UBD(B, MP(b[i], INF))  );
//
  //      cout << aa << " " << bb << endl;

        if (aa == bb) puts("Draw");
        else puts( aa < bb ? "Mike" : "Constantine");
    }
}

Sparse Table

另一种区间分割方案，缺点是不能修改。
在 lca 问题和后缀数组求 lcp 问题中都经常使用。

int ST[LV][N];

int rmq(int l, int r){
    if (l > r) swap(l, r); ++r; int lv = lg2(r-l);
    return min(ST[0][lv][l], ST[0][lv][r-(1<<lv)]);
}

for ( int lv = 1 ; (1 << lv) <= n ; lv ++ ){
    for ( int i = 1 ; i + (1 << lv)  <= n + 1 ; i ++ ){
        ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + (1<<(lv-1))]);                
    }
}

HDU 2888 – Check Corners （矩形。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1778847

        REP(xx, lg2(n)+1) REP(yy, lg2(m)+1) if (xx+yy){
            REP(x, n-_1(xx)+1) REP(y, m-_1(yy)+1){
                if (xx){
                    ST[xx][yy][x][y] = max(ST[xx-1][yy][x][y], ST[xx-1][yy][x+_1(xx-1)][y]);
                }
                else{
                    ST[xx][yy][x][y] = max(ST[xx][yy-1][x][y], ST[xx][yy-1][x][y+_1(yy-1)]);
                }
            }
        }

POJ – 2019 Cornfields （正方形。。时空上降一个 log。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1778846

ZOJ – 3614 Choir （维护方差。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1778842

线段树

最大的好处是支持修改。
https://www.shuizilong.com/house/archives/spoj-3557-ioi04-hermes/

Posted by xiaodao
Category: 快晴