Dyd's Blog

He who has a strong enough why can bear almost any how.

四毛子

Posted on Edited on In
Symbols count in article: 6.2k Reading time ≈ 6 mins.

用分块平衡时间

四毛子

四毛子算法（ Method of Four Russians ），估计是四个俄罗斯人提出的？

它其实主要是一种平衡时间复杂度的思想

加一减一 ST 表的优化

先看一个简单问题，给定一个序列，满足其差分序列只有 $+1$ 和 $-1$ ，多次询问 RMQ

ST 表显然可以做到 $O(n \log n) - O(1)$ ，但这没有很好的利用好性质，四毛子是这样做的：

把序列按照 $B = \lceil \frac{\log n}{2} \rceil$ （经验值 $\lceil \frac{\log n}{2} \rceil \sim \lceil \frac{3 \log n}{2} \rceil$ ）分块，跨块直接 ST 表，预处理是 $O(\frac{n}{B} \log \frac{n}{B}) < O(n)$ ；对于块内，考虑到本质不同的块只有 $2^B$ 个，直接扫描每个不同块存下来，是 $O(B \times 2^B) < O(n)$ ；询问是 $O(1)$ ；如此，我们做到了 $O(n) - O(1)$ 解决问题

lca

上面的问题泛用性不强，考虑用四毛子解决更加普遍的问题： lca

记录欧拉环游序（不难发现它的长度为 $2m$ ，其中 $m$ 代表边数，是 $O(n)$ 级的），发现相邻两个的 $dep$ 正是一个一加一减 ST 表，直接维护即可，给出代码：

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define FF std::function
#define pb(x) push_back(x)
#define fi first
#define se second
using LL = long long;
using PII = std::pair<int, int>;
using std::cerr;
const int N = 5e5 + 100, L = N << 1, D = 32, INF = 0x3f3f3f3f;
int n, m, rt, cnt = 0, num, B;
int dfn[N], bid[L], bk[N];
PII dat[L];
std::vector<int> G[N];
struct Block{ int l, r, tp; } b[N];
template<class T>
bool cmn(T &x, T y){ return x > y ? x = y, true : false; }
namespace ST
{
    PII mn[L][D];
    int lg2[L];
    void init()
    {
        lg2[1] = 0;
        for (int i = 2; i <= num; ++i) lg2[i] = lg2[i >> 1] + 1;
        for (int i = 1; i <= num; ++i) mn[i][0] = dat[b[i].l + bk[b[i].tp] - 1];
        for (int j = 1, t = lg2[num]; j <= t; ++j)
            for (int i = 1; i <= num - (1 << j) + 1; ++i) mn[i][j] = std::min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);    
    }
    PII ask(int l, int r)
    {
        if (l > r) return {INF, INF};
        int t = lg2[r - l + 1];
        return std::min(mn[l][t], mn[r - (1 << t) + 1][t]);
    }
}
void build()
{
    B = log2(cnt) / 2 + 1;
    for (int i = 1; i <= cnt; i += B) b[++num].l = i, b[num].r = i + B - 1;
    for (int i = cnt + 1; i <= b[num].r; ++i) dat[i] = {INF, INF};
    for (int i = 1; i <= num; ++i)
        for (int j = b[i].l; j <= b[i].r; ++j) bid[j] = i;
    FF<void(int)> calc = [&](int x)
    {
        bk[x] = 1;
        for (int i = 2, sum = 0, mn = 0; i <= B; ++i)
        {
            if ((x >> (i - 1)) & 1) ++sum;
            else --sum;
            if (sum < mn) mn = std::min(mn, sum), bk[x] = i; 
        }
    } ;
    FF<int(Block)> get_tp = [&](Block x)
    {
        int res = 0;
        for (int i = x.l + 1; i <= x.r; ++i) res |= (dat[i].fi - dat[i - 1].fi >= 0 ? 1 : 0) << (i - x.l);
        return res;
    } ;
    for (int i = (1 << B) - 1; ~i; --i) calc(i);
    for (int i = 1; i <= num; ++i) b[i].tp = get_tp(b[i]);
    ST::init();
}
PII ask(int l, int r)
{
    if (l > r) return ask(r, l);
    FF<PII(int, int)> bask = [&](int l, int r)
    {
        int bb = bid[l], ll = l - b[bb].l + 1, rr = r - b[bb].l + 1;
        int t = b[bb].tp;
        t >>= ll - 1;
        t |= ((1 << (rr - ll + 1)) - 1) ^ ((1 << B) - 1);
        return dat[l + bk[t] - 1];
    } ;
    if (bid[l] == bid[r]) return bask(l, r);
    PII res = std::min(bask(l, b[bid[l]].r), bask(b[bid[r]].l, r));
    if (bid[r] - bid[l] > 1) cmn(res, ST::ask(bid[l] + 1, bid[r] - 1));
    return res;
}
int main()
{
    scanf("%d %d %d", &n, &m, &rt);
    for (int i = 1, u, v; i < n; ++i) scanf("%d %d", &u, &v), G[u].pb(v), G[v].pb(u);
    FF<void(int, int, int)> dfs = [&](int x, int fa, int dep)
    {
        dfn[x] = ++cnt;
        dat[cnt] = {dep, x};
        for (int y : G[x]) if (y != fa) dfs(y, x, dep + 1), dat[++cnt] = {dep, x};
    } ;
    dfs(rt, 0, 1), build();
    for (int i = 1, a, b; i <= m; ++i) scanf("%d %d", &a, &b), printf("%d\n", ask(dfn[a], dfn[b]).se);
    return 0;
}

真正的 ST

现在我们来看看一般的 RMQ 问题，考虑建出笛卡尔树，对于询问直接求 lca ，还是 $O(n) - O(1)$ 的（然而实际运行中没感觉比 ST 表快多少）

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#define FF std::function
#define fi first
#define se second
#define STC static
using PII = std::pair<int, int>;
const int N = 1e5 + 100, INF = 0x3f3f3f3f;
namespace FR //Four Russians
{
    const int L = N << 1;
    struct Tree{ int lc, rc, dat; } tr[N];
    struct Block{ int l, r, tp; } b[N];
    int dfn[N], bid[L], cnt = 0, rt, num = 0, B, bk[L];
    PII dat[L];
    template<class T>
    bool cmn(T &x, T y){ return y < x ? x = y, true : false; }
    namespace ST
    {
        const int D = 18;
        int lg2[L];
        PII mn[L][D];
        void init()
        {
            lg2[1] = 0;
            for (int i = 2; i <= num; ++i) lg2[i] = lg2[i >> 1] + 1;
            for (int i = 1; i <= num; ++i) mn[i][0] = dat[b[i].l + bk[b[i].tp] - 1];
            for (int j = 1, t = lg2[num]; j <= t; ++j)
                for (int i = 1; i <= num - (1 << j) + 1; ++i) mn[i][j] = std::min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
        }
        PII ask(int l, int r)
        {
            if (l > r) return {INF, INF};
            int t = lg2[r - l + 1];
            return std::min(mn[l][t], mn[r - (1 << t) + 1][t]);
        }
    }
    void init(int len, int x[])
    {
        FF<void(int, int[])> bct = [&](int len, int x[])
        {
            STC int stk[N];
            int top = 0;
            for (int i = 1; i <= len; ++i) tr[i].dat = x[i];
            for (int i = 1, k; i <= len; ++i)
            {
                for (k = top; k && tr[stk[k]].dat < tr[i].dat; --k);
                if (k) tr[stk[k]].rc = i;
                if (k < top) tr[i].lc = stk[k + 1];
                stk[top = k + 1] = i;
            }
            rt = stk[1];
        } ; 
        bct(len, x);
        FF<void(int, int)> dfs = [&](int x, int dep)
        {
            dfn[x] = ++cnt, dat[cnt] = {dep, x};
            if (tr[x].lc) dfs(tr[x].lc, dep + 1), dat[++cnt] = {dep, x};
            if (tr[x].rc) dfs(tr[x].rc, dep + 1), dat[++cnt] = {dep, x};
        } ;
        dfs(rt, 1);
        B = log2(cnt) / 2 + 1;
        for (int i = 1; i <= cnt; i += B) b[++num].l = i, b[num].r = i + B - 1;
        for (int i = cnt + 1; i <= b[num].r; ++i) dat[i] = {INF, INF};
        for (int i = 1; i <= num; ++i)
            for (int j = b[i].l; j <= b[i].r; ++j) bid[j] = i;
        FF<void(int)> calc = [&](int x)
        {
            bk[x] = 1;
            for (int i = 2, mn = 0, sum = 0; i <= B; ++i)
            {
                if ((x >> (i - 1)) & 1) ++sum;
                else --sum;
                if (cmn(mn, sum)) bk[x] = i; 
            }
        } ;
        FF<int(Block)> get_tp = [&](Block x)
        {
            int res = 0;
            for (int i = x.l + 1; i <= x.r; ++i) res |= (dat[i].fi - dat[i - 1].fi >= 0 ? 1 : 0) << (i - x.l);
            return res;
        } ; 
        for (int i = (1 << B) - 1; ~i; --i) calc(i);
        for (int i = 1; i <= num; ++i) b[i].tp = get_tp(b[i]);
        ST::init();
    }
    PII to_ask(int l, int r)
    {
        if (l > r) return to_ask(r, l);
        FF<PII(int, int)> bask = [&](int l, int r)
        {
            Block &x = b[bid[l]];
            int t = x.tp, ll = l - x.l + 1, rr = r - x.l + 1;
            t >>= ll - 1;
            t |= ((1 << (rr - ll + 1)) - 1) ^ ((1 << B) - 1);
            return dat[l + bk[t] - 1];
        } ;
        if (bid[l] == bid[r]) return bask(l, r); 
        PII res = std::min(bask(l, b[bid[l]].r), bask(b[bid[r]].l, r));
        if (bid[r] - bid[l] > 1) cmn(res, ST::ask(bid[l] + 1, bid[r] - 1));
        return res;
    }
    int ask(int l, int r){ return tr[to_ask(dfn[l], dfn[r]).se].dat; }
}
int n, m, a[N];
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    FR::init(n, a);
    for (int l, r; m--; ) scanf("%d %d", &l, &r), printf("%d\n", FR::ask(l, r));
    return 0;
}