四毛子算法(The Method of Four Russians)

数据结构
2.6k 词

0 前言

说实话这东西看了一天也没有看懂，只能先贴模板了，以后再来填坑. 咕咕咕警告

1 算法原理

四毛子算法

以上内容引用自 CSP-S 2021 第一轮 的最后一题.

2 例题&代码实现

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <cmath>

using namespace std;

const int MAXN = 100000, MAXT = MAXN << 1;
const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB;

struct node
{
    int val;
    int dep, dfn, end;
    node *son[2];
} T[MAXN];

int n, t, b, c, Log2[MAXC + 1];
int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1];
node *root, *A[MAXT], *Min[MAXL][MAXC];

void build()
{
    static node *S[MAXN + 1];
    int top = 0;
    for (int i = 0; i < n; i++)
    {
        node *p = &T[i];
        while (top && S[top]->val < p->val)
            p->son[0] = S[top--];
        if (top)
            S[top]->son[1] = p;
        S[++top] = p;
    }
    root = S[1];
}

void DFS(node *p)
{
    A[p->dfn = t++] = p;
    for (int i = 0; i < 2; i++)
        if (p->son[i])
        {
            p->son[i]->dep = p->dep + 1;
            DFS(p->son[i]);
            A[t++] = p;
        }
    p->end = t - 1;
}

node *min(node *x, node *y)
{
    return x->dep < y->dep ? x : y;
}

void ST_init()
{
    b = (int)(ceil(log2(t) / 2));
    c = t / b;
    Log2[1] = 0;
    for (int i = 2; i <= c; i++)
        Log2[i] = Log2[i >> 1] + 1;
    for (int i = 0; i < c; i++)
    {
        Min[0][i] = A[i * b];
        for (int j = 1; j < b; j++)
            Min[0][i] = min(Min[0][i], A[i * b + j]);
    }
    for (int i = 1, l = 2; l <= c; i++, l <<= 1)
        for (int j = 0; j + l <= c; j++)
            Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]);
}

void small_init()
{
    for (int i = 0; i <= c; i++)
        for (int j = 1; j < b && i * b + j < t; j++)
            if (A[i * b + j]->dep < A[i * b + j - 1]->dep)
                Dif[i] |= 1 << (j - 1);
    for (int S = 0; S < (1 << (b - 1)); S++)
    {
        int mx = 0, v = 0;
        for (int i = 1; i < b; i++)
        {
            v += (S >> (i - 1) & 1) ? -1 : 1;
            if (v < mx)
            {
                mx = v;
                Pos[S] = i;
            }
        }
    }
}

node *ST_query(int l, int r)
{
    int g = Log2[r - l + 1];
    return min(Min[g][l], Min[g][r - (1 << g) + 1]);
}

node *small_query(int l, int r)
{
    int p = l / b;
    int S = (Dif[p] >> (l - p * b)) & ((1 << (r - l)) - 1);
    return A[l + Pos[S]];
}

node *query(int l, int r)
{
    if (l > r)
        return query(r, l);
    int pl = l / b, pr = r / b;
    if (pl == pr)
    {
        return small_query(l, r);
    }
    else
    {
        node *s = min(small_query(l, pl * b + b - 1), small_query(pr * b, r));
        if (pl + 1 <= pr - 1)
            s = min(s, ST_query(pl + 1, pr - 1));
        return s;
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> T[i].val;
    }
    build();
    DFS(root);
    ST_init();
    small_init();
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        cout << query(Max.T[l].dfn, Max.T[r].dfn)->val << endl;
    }
    return 0;
}