线性时间区间最值(RMQ)算法

Posted by EtaoinWu on 周日 30 四月 2017

大概思路是这样的 :

  • 利用 笛卡尔树 将序列的 RMQ 转化为笛卡尔树上的 LCA

  • 利用 Euler Tour Technique 将 LCA 转化为 +1/-1 RMQ

  • 利用 Method of Four Russians 将 RMQ 以 \(\frac{\log{n}}{2}\) 为大小分块 ( 这边钦定了块大小为 \(8\)), 最多只有 \(O(\sqrt{n})\) 块 , 然后预处理 。

  • 块外使用 ST 表来进行查询

实际查询效率与只使用 ST 表差不多 。

quite complicated and not applicable in practice

#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
template<typename T>
inline void gi(T &dx)
{
    dx = 0;
    int cc = getchar();
    bool nega = false;
    while (cc < '0' || cc > '9') { nega = (cc == '-' ? true : nega); cc = getchar(); }
    while (cc >= '0' && cc <= '9') { dx = (T)(dx * 10 + cc - '0'); cc = getchar(); }
    if (nega) { dx = -dx; }
}
#if __cplusplus >= 201103L || (defined(_MSVC_LANG) && _MSVC_LANG >= 201103L)
template<typename T, typename ...Args> inline void gi(T &a, Args &...args)
{ gi(a); gi(args...); }
#else
template<typename T1, typename T2> inline void gi(T1 &a, T2 &b) { gi(a); gi(b); }
template<typename T1, typename T2, typename T3> inline void gi(T1 &a, T2 &b, T3 &c) { gi(a); gi(b); gi(c); }
template<typename T1, typename T2, typename T3, typename T4> inline void gi(T1 &a, T2 &b, T3 &c, T4 &d) { gi(a); gi(b); gi(c); gi(d); }
template<typename T1, typename T2, typename T3, typename T4, typename T5> inline void gi(T1 &a, T2 &b, T3 &c, T4 &d, T5 &e) { gi(a); gi(b); gi(c); gi(d); gi(e); }
#endif
#ifdef _MSVC_LANG
#define __attribute__(x)
#else
#define log2(x) (31-__builtin_clz(x))
#endif
namespace io
{
#define BUF_SIZE 5000010
    char buf[BUF_SIZE];
    int at = BUF_SIZE;
    FILE *in = stdin;
    __attribute__((optimize("Ofast"), target("no-ieee-fp,arch=amdfam10")))inline char gc()
    {
        if (at == BUF_SIZE) { fread(buf, BUF_SIZE, 1, in); at = 0; }
        return buf[at++];
    }
    template<typename T>
    __attribute__((optimize("Ofast"), target("no-ieee-fp,arch=amdfam10")))inline void gi(T&n)
    {
        n = 0; char c = gc();
        while (c<'0')c = gc();
        while (c >= '0') { n = n * 10 - 48 + c; c = gc(); }
    }
#if __cplusplus >= 201103L || (defined(_MSVC_LANG) && _MSVC_LANG >= 201103L)
    template<typename T, typename ...Args> inline void gi(T &a, Args &...args)
    { gi(a); gi(args...); }
#else
    template<typename T1, typename T2> inline void gi(T1 &a, T2 &b) { gi(a); gi(b); }
    template<typename T1, typename T2, typename T3> inline void gi(T1 &a, T2 &b, T3 &c) { gi(a); gi(b); gi(c); }
    template<typename T1, typename T2, typename T3, typename T4> inline void gi(T1 &a, T2 &b, T3 &c, T4 &d) { gi(a); gi(b); gi(c); gi(d); }
    template<typename T1, typename T2, typename T3, typename T4, typename T5> inline void gi(T1 &a, T2 &b, T3 &c, T4 &d, T5 &e) { gi(a); gi(b); gi(c); gi(d); gi(e); }
#endif
    char str[BUF_SIZE * 10]; int len, out[100], num;
    template<typename T>
    __attribute__((optimize("Ofast"), target("no-ieee-fp,arch=amdfam10")))inline void wi(T k)
    { num = 0; do { out[++num] = k % 10, k /= 10; } while (k); for (int i = num; i >= 1; --i)str[len++] = '0' + out[i]; str[len++] = '\n'; }
#undef BUF_SIZE
};
const int maxn = 111111;
int n, m;
struct graph
{
    int beg[maxn], nxt[maxn * 2], to[maxn * 2];
    int e;
    void ae(int x, int y)
    {
        ++e;
        to[e] = y;
        nxt[e] = beg[x];
        beg[x] = e;
    }
} g;
int fa[maxn];
int dep[maxn];
int rt;
int eu[maxn * 2], ec = 0;
int rv[maxn * 2];
int any[maxn * 2];
const int lay = 18;
int st[33333][lay + 2];
int rm[33333][9][9];
int pre[33333][9];
int suf[33333][9];
int inn[33333];
int typ[33333];
int tv[33333];
const int bs = 8;
int gn;
#define bel(x) ((((x)-1)>>3)+1)
inline void build_rmq(int nn)
{
    static int a[233];
    while ((nn & 7) != 0) ++nn;
    for (int i = 0; i < (1 << (bs - 1)); ++i) { // 0:-1, 1:+1
        a[1] = 0;
        for (int j = 0; j < bs - 1; ++j) {
            if (i & (1 << j)) {
                a[j + 2] = a[j + 1] + 1;
            } else {
                a[j + 2] = a[j + 1] - 1;
            }
        }
        for (int j = 1; j <= bs; ++j) {
            rm[i][j][j] = j;
            for (int k = j + 1; k <= bs; ++k) {
                rm[i][j][k] = a[k] < a[rm[i][j][k - 1]] ? k : rm[i][j][k - 1];
            }
        }
        for (int j = 1; j <= bs; ++j) {
            pre[i][j] = rm[i][1][j];
            suf[i][j] = rm[i][j][bs];
        }
        inn[i] = rm[i][1][bs];
    }
    gn = nn >> 3;
    for (int i = 1; i <= gn; ++i) {
        // i * bs - bs + 1 -> i * bs
        typ[i] = 0;
        int upl = i << 3;
        for (int j = upl - bs + 2, cc = 0; j <= upl; ++j, ++cc) {
            if (rv[j] - rv[j - 1] >= 0) {
                typ[i] |= (1 << cc);
            }
        }
        tv[i] = rv[inn[typ[i]] + ((i - 1) << 3)];
    }
    int lly = log2(gn) + 1;
    for (int i = 1; i <= gn; ++i) { st[i][0] = i; }
    for (int j = 1; j <= lly; ++j) {
        // i + 2^j - 1 <= n
        // i <= n - 2^j + 1
        int upl = gn - (1 << j) + 1;
        //cerr << upl << endl;
        for (int i = 1; i <= upl; ++i) {
            int k = i + (1 << (j - 1));
            st[i][j] = tv[st[k][j - 1]] < tv[st[i][j - 1]] ? st[k][j - 1] : st[i][j - 1];
        }
    }
}
inline int stq(int l, int r)
{
    ++r;
    int dis = r - l;
    int p = log2(dis);
    r -= 1 << p;
    return tv[st[l][p]] < tv[st[r][p]] ? st[l][p] : st[r][p];
}
inline int rmq(int l, int r)
{
    if (l > r) swap(l, r);
    int ll = bel(l), rr = bel(r);
    if (ll == rr) {
        int bas = (ll - 1) << 3;
        int dl = l - bas, dr = r - bas;
        return bas + rm[typ[ll]][dl][dr];
    } else if (ll + 1 == rr) {
        int lb = (ll - 1) << 3, rb = (rr - 1) << 3;
        int i1 = suf[typ[ll]][l - lb] + lb;
        int i2 = pre[typ[rr]][r - rb] + rb;
        return rv[i1] < rv[i2] ? i1 : i2;
    } else {
        int tt = stq(ll + 1, rr - 1);
        tt = ((tt - 1) << 3) + inn[typ[tt]];
        int lb = (ll - 1) << 3, rb = (rr - 1) << 3;
        int i1 = suf[typ[ll]][l - lb] + lb;
        int i2 = pre[typ[rr]][r - rb] + rb;
        int ii = rv[i1] < rv[i2] ? i1 : i2;
        return rv[ii] < rv[tt] ? ii : tt;
    }
}
void dfs(int x)
{
    eu[++ec] = x;
    any[x] = ec;
    for (int i = g.beg[x]; i; i = g.nxt[i]) {
        int y = g.to[i];
        dep[y] = dep[x] + 1;
        dfs(y);
        eu[++ec] = x;
    }
}
inline int lca(int x, int y)
{
    return eu[rmq(any[x], any[y])];
}
int dr[maxn];
int stk[maxn], tp;
struct node
{
    int k, l, r;
} t[maxn];
inline int build_dkrtree()
{
    tp = 0;
    for (int i = 1; i <= n; i++) {
        t[i].k = dr[i], stk[tp+1] = 0;
        while (tp && t[stk[tp]].k < t[i].k) --tp;
        t[i].l = stk[tp + 1];
        if (tp) t[stk[tp]].r = i;
        stk[++tp] = i;
    }
    while (tp) --tp;
    return stk[1];
}

int main()
{
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    io::gi(n);
    for (int i = 1; i <= n; ++i) {
        io::gi(dr[i]);
        dr[i] = dr[i];
    }
    rt = build_dkrtree();
    for (int i = 1; i <= n; ++i) {
        if (t[i].l) g.ae(i, t[i].l);
        if (t[i].r) g.ae(i, t[i].r);
    }
    dfs(rt);
    for (int i = 1; i <= ec; ++i) { rv[i] = dep[eu[i]]; }
    build_rmq(ec);
    io::gi(m);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        io::gi(x, y);
        io::wi(dr[lca(x, y)]);
    }
    fwrite(io::str, io::len, 1, stdout);
    return 0;
}

comments powered by HyperComments