解題區/解題區 - Zerojudge

b494. 史蒂芙的修羅道

contents

  1. 1. Problem
    1. 1.1. 背景
    2. 1.2. 題目描述
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. morris traversal
    2. 4.2. stack

Problem

背景

史蒂芙被王國政務工作忙昏頭，每次都要求效率的極限，即使不會玩遊戲，只要把政務工作處理到極致，想必這就是另一種人生價值。

題目描述

回顧一個經典問題區間極大極小值詢問 RMQ，她收到下面這一份代碼

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
#include <bits/stdc++.h>
using namespace std;
unsigned int seed = 0;
unsigned int p_random() {return seed = (seed*9301+49297);}
unsigned int A[5000005];
int main() {
    int N, M, S, x, y;
    unsigned int hash = 0;
    scanf("%d %d %d", &N, &M, &S);
    seed = S;
    for (int i = 1; i <= N; i++)
        A[i] = p_random();
    for (int i = 0; i < M; i++) {
        x = p_random()%N+1, y = p_random()%N+1;
        if (x > y)	swap(x, y);
        unsigned int max_val = A[x];
        for (int j = x; j <= y; j++)
            max_val = max(max_val, A[j]);
        hash ^= max_val; 
    }
    printf("%lu\n", hash);
    return 0;
}

「給定 $N$ 個整數、$M$ 個詢問操作、$S$ 為亂數種子，接著產生 $N$ 個數字，對於接下來 $M$ 個詢問，每一個詢問兩個整數，輸出區間內的最大值。」這對曾經的史蒂芙而言，用過 Segment Tree、Sparse Table、Unrolled Linked List 解決過，時間、空間複雜度都非常優秀。

現在的工作就是加速這一份代碼。

Sample Input

1
8 5 10

Sample Output

1
4049919279

Solution

經典 RMQ 問題，主要有以下四種，最後一種只支持離線不帶修改的操作。

  • sqrt-decomposition $O(N)$ - $O(\sqrt{N})$
  • sparse table $O(N \log N)$ - $O(1)$
  • segment tree $O(N)$ - $O(\log N)$
  • cartesian tree + tarjan LCA algorithm + morris traversal $O(N + Q)$

於是出了這一題 b494. 史蒂芙的修羅道，把第一種算法卡時間、第二種算法卡空間、第三種算法卡常數。

實作起來非常變態，速度一不小心就會輸非遞迴的 segment tree (zkw 線段樹或者稱做 non-recursive segment tree 的實作技巧，詳見 codeforce - Efficient and easy segment trees )，儘管如此還是卡不住這類的實作，但時間上把遞迴實作的版本卡 TLE，速度略贏 prefect tree 的 segment tree 的實作，但使用空間多了兩倍。

  • 不開 std::vector，否則記憶體會預保留一倍。
  • 使用 tarjan LCA algorithm 在笛卡爾樹二元樹上時要特化操作。
  • 無法使用遞迴，實作非遞迴的二元搜尋樹走訪常數要注意。

通常 tarjan LCA algorithm 會把一個詢問拆成兩個詢問，常數會多 1。在笛卡爾樹上有一個性質，每一個節點的狀態為 <key, value> 看 key 仍然是一個二元搜尋樹，看 value 是一個 heap，在完成 tarjan LCA algorithm 需要的是後序走訪，能保證回答 LCA(x, y) 的順序。假設詢問 LCA(x, y) && x < y 只需要在 y 節點準備詢問 x 即可。

若要降空間複雜度常數，利用 morris traversal 在空間複雜度 $O(1)$ 完成。若使用 stack<> 模擬 tarjan LCA algorithm，最慘的空間複雜度是 $O(N)$。

morris traversal

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000005, MAXQ = 5000005;
struct Node {
    int idx;
    Node *ch[2], *fa;
    Node() {
        idx = 0;
        ch[0] = ch[1] = fa = NULL;
    }
} nodes[MAXN];
struct QEdge {
    int u;
    QEdge *next;
};
QEdge qedge[MAXQ], *qadj[MAXN] = {};
unsigned int A[MAXN], eq, ret;
int parent[MAXN];
void init(int n) {
    eq = 0;
    for (int i = 0; i <= n; i++)
        parent[i] = i /*, qadj[i] = NULL */;
}
void insert(Node *u, Node *p) {
    while (A[p->idx] < A[u->idx])	p = p->fa;
    u->ch[0] = p->ch[1];
    if (p->ch[1])	p->ch[1]->fa = u;
    p->ch[1] = u;
    u->fa = p;
}
void build(int N) {
    nodes[0] = Node(), A[0] = UINT_MAX;
    for (int i = 1; i <= N; i++) {
        nodes[i] = Node(), nodes[i].idx = i;
        insert(&nodes[i], &nodes[i-1]);
    }
}
int findp(int x) {
    return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
void tree_reverse(Node *from, Node *to) {
    if (from == to)	return ;
    Node *x = from, *y = from->ch[1], *z;
    while (true) {
        z = y->ch[1];
        y->ch[1] = x;
        x = y, y = z;
        if (x == to)
            return ;
    }
}
void print_reverse(Node *from, Node *to) {
    tree_reverse(from, to);
    Node *p = to;
    while (true) {
        int u = p->idx;
        for (QEdge *e = qadj[u]; e; e = e->next)
            ret ^= A[findp(e->u)];
        if (p->fa != NULL)	parent[findp(u)] = p->fa->idx;
        if (p == from)	break;
        p = p->ch[1];
    }		
    tree_reverse(to, from);
}
void tarjan(Node *root) {	
    Node *cur, *prev, tmp;
    tmp.ch[0] = root;
    cur = &tmp, prev = NULL;
    while (cur != NULL) {
        if (cur->ch[0] == NULL) {
            cur = cur->ch[1];
        } else {
            prev = cur->ch[0];
            while (prev->ch[1] != NULL && prev->ch[1] != cur)
                prev = prev->ch[1];
            if (prev->ch[1] == NULL) {
                prev->ch[1] = cur, cur = cur->ch[0];
            } else {
                print_reverse(cur->ch[0], prev);
                prev->ch[1] = NULL, cur = cur->ch[1];
            }
        }
    }
}
void add(int x, int y, int qid) {
    if (x < y)	swap(x, y);
    qedge[eq].u = y, qedge[eq].next = qadj[x], qadj[x] = &qedge[eq++];
}
unsigned int seed = 0;
unsigned int gen() {return seed = (seed*9301+49297);}
int N, M, S, x, y;
int main() {
    scanf("%d %d %d", &N, &M, &S);
    seed = S, init(N);
    for (int i = 1; i <= N; i++)
        x = gen(), A[i] = x;
    for (int i = 0; i < M; i++) {
        x = gen()%N+1, y = gen()%N+1;
        add(x, y, i);
    }
    ret = 0;
    build(N), tarjan(nodes[0].ch[1]);
    printf("%lu\n", ret);
    return 0;
}

stack

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000005, MAXQ = 5000005;
struct Node {
    int idx;
    Node *ch[2], *fa;
    Node() {
        idx = 0;
        ch[0] = ch[1] = fa = NULL;
    }
} nodes[MAXN];
struct QEdge {
    int u;
    QEdge *next;
};
QEdge qedge[MAXQ], *qadj[MAXN] = {};
unsigned int A[MAXN], eq, ret;
int parent[MAXN];
void init(int n) {
    eq = 0;
    for (int i = 0; i <= n; i++)
        parent[i] = i /*, qadj[i] = NULL */;
}
void insert(Node *u, Node *p) {
    while (A[p->idx] < A[u->idx])	p = p->fa;
    u->ch[0] = p->ch[1];
    if (p->ch[1])	p->ch[1]->fa = u;
    p->ch[1] = u;
    u->fa = p;
}
void build(int N) {
    nodes[0] = Node(), A[0] = UINT_MAX;
    for (int i = 1; i <= N; i++) {
        nodes[i] = Node(), nodes[i].idx = i;
        insert(&nodes[i], &nodes[i-1]);
    }
}
int findp(int x) {
    return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
pair<Node*, int> stk[MAXN];
void tarjan(Node *root) {
    int top = -1, u;
    Node *p;
    stk[++top] = {root, 0};
    while (top >= 0) {
        pair<Node*, int> &x = stk[top];
        x.second++;
        if (x.second == 1) {
            if (x.first->ch[0])
                stk[++top] = {x.first->ch[0], 0};
        } else if (x.second == 2) {
            if (x.first->ch[1])
                stk[++top] = {x.first->ch[1], 0};
        } else {
            top--;
            p = x.first, u = p->idx;
            for (QEdge *e = qadj[u]; e; e = e->next)
                ret ^= A[findp(e->u)];
            parent[findp(u)] = p->fa->idx;
        }
    }
}
void add(int x, int y, int qid) {
    if (x < y)	swap(x, y);
    qedge[eq].u = y, qedge[eq].next = qadj[x], qadj[x] = &qedge[eq++];
}
unsigned int seed = 0;
unsigned int gen() {return seed = (seed*9301+49297);}
int N, M, S, x, y;
int main() {
    scanf("%d %d %d", &N, &M, &S);
    seed = S, init(N);
    for (int i = 1; i <= N; i++)
        A[i] = gen();
    for (int i = 0; i < M; i++) {
        x = gen()%N+1, y = gen()%N+1;
        add(x, y, i);
    }
    ret = 0;
    build(N), tarjan(nodes[0].ch[1]);
    printf("%lu\n", ret);
    return 0;
}