水厂日志

发表于 更新于 分类于 ， ，

题目

利姆露现在想知道一个奇怪魔法序列的含义，于是她把这个任务交给了大贤者。

这个魔法序列由 nn 个字符组成，仅包含 L，R，小写拉丁字母和括号（即 ‘(’ 和 ‘)’），表达对一个空白字符串的操作（因为是空白字符串，所以最初操作位置在哪里都一样），其中

  1. L 表示当前操作位置左移一位。
  2. R 表示当前操作位置右移一位。
  3. 其余任何小写拉丁字母或括号表示将当前操作位置修改为该字符。

大贤者知道这个操作产生的序列对应一个魔法，当序列中括号不合法时，魔法会失败；而括号序列合法时，括号的最大嵌套重数就是魔法的强度。

现在大贤者想知道这个过程中每一步产生的序列对应的魔法是一个失败的魔法还是一个成功的魔法，若是一个成功的魔法，则其威力是多少？你能够帮忙完成这件事吗？

（不知道怎么概括，直接复制粘贴了）

题解

参考出题人给的题解PPT。

主要是维护一个编辑器，同时能快速得到字符串中括号是否匹配，以及括号的嵌套层数。

我一开始看到括号匹配就想到栈，但是每次都遍历一次铁定超时。实际上我们只需要对字符串求一个前缀和，(加1，)减1，如果前缀和数组中有小于0的数或者最后一位不为0（即左右括号数量不相等）则非法，前缀和数组的最大值则是最大嵌套数。所以只需要维护一个前缀和数组，以及最大值和最小值即可，原数组的单点修改会导致前缀和数组的区间修改，用线段树可以实现复杂度$O(\log_2 n)$完成，查询最大值和最小值也是。所以总的复杂度是$O(n\log_2n)$。

因为光标可能会移动到左边，所以可以从数组中间开始。

代码

因为没有发生WA，而只有RE（数组越界），所以就没写暴力验证。

RE的原因是数组开小了，$n$最大是1e6，所以数组应该要开到2e6长度。

AC代码

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
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

using namespace std;
const long long MAX = 1e6 + 7;

char arr[MAX * 2];

struct Node {
    int left, right;
    int val, min, max, lazy;
};

Node tree[MAX * 8];

void build(int left, int right, int treeIndex = 1) {
    auto &node = tree[treeIndex];
    node.left = left;
    node.right = right;
    if (left != right) {
        int mid = (left + right) / 2;
        build(left, mid, treeIndex * 2);
        build(mid + 1, right, treeIndex * 2 + 1);
    }
}

void update(int left, int right, int val, int treeIndex = 1) {
    auto &node = tree[treeIndex];
    if (node.left == node.right) {
        node.val += val;
        node.max = node.val;
        node.min = node.val;
        return;
    }
    if (node.left >= left && node.right <= right) {
        // 子集
        node.lazy += val;
        node.max += val;
        node.min += val;
        return;
    }
    int mid = (node.left + node.right) / 2;
    if (mid >= left) {
        update(left, right, val, treeIndex * 2);
    }
    if (mid < right) {
        update(left, right, val, treeIndex * 2 + 1);
    }
    node.max = max(tree[treeIndex * 2].max, tree[treeIndex * 2 + 1].max) + node.lazy;
    node.min = min(tree[treeIndex * 2].min, tree[treeIndex * 2 + 1].min) + node.lazy;
}

int query(int pos, int treeIndex = 1) {
    auto &node = tree[treeIndex];
    if (node.left == node.right) {
        return node.val;
    }
    int mid = (node.left + node.right) / 2;
    // FIXME: 优化一波？
    if (pos <= mid) {
        return node.lazy + query(pos, treeIndex * 2);
    } else {
        return node.lazy + query(pos, treeIndex * 2 + 1);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    int arrCursor = MAX;
    cin >> n;
    char c;
    const int rMax = arrCursor + n + 5;
    const int lMin = arrCursor - n + 5;
    build(lMin, rMax);
    while (n--) {
        cin >> c;
        if (c == 'L') {
            arrCursor -= 1;
        } else if (c == 'R') {
            arrCursor += 1;
        } else {
            char origin = arr[arrCursor];
            arr[arrCursor] = c;
            if (c == '(') {
                if (origin == ')') {
                    // +2
                    update(arrCursor, rMax, 2);
                } else if (origin != '(') {
                    // +1
                    update(arrCursor, rMax, 1);
                }
            } else if (c == ')') {
                if (origin == '(') {
                    // -2
                    update(arrCursor, rMax, -2);
                } else if (origin != ')') {
                    update(arrCursor, rMax, -1);
                }
            } else {
                if (origin == '(') {
                    // -1
                    update(arrCursor, rMax, -1);
                } else if (origin == ')') {
                    // +1
                    update(arrCursor, rMax, 1);
                }
            }
        }
        if (tree[1].min >= 0 && query(rMax) == 0) {
            cout << tree[1].max << " ";
        } else {
            cout << -1 << " ";
        }
    }
    return 0;
}

测试例生成（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/bin/env python
import random


def d(n, filename='in'):
    n = int(n)
    arr = ['(', ')', 'L', 'R', 'a']
    random.shuffle(arr)
    a = [arr[random.randint(0, 4)] for i in range(n)]
    fi = open(filename, 'w')
    fi.write("{}\r\n{}\r\n".format(
        n, "".join(a)
    ))
    fi.close()

发表于 更新于 分类于 ， ，

题目

你带着大量佣兵回到城市，看到了大量的新赏金任务。你无视其他等级的任务，拿过最高等级的任务列表，发现其任务数量刚好和你的佣兵数量相同，便把它们都接到了自己手上。

每个佣兵都有自己的能力值，每个任务都有能力值要求，能力值大于要求即可完成任务。

你让佣兵们自行选择任务（每人一个），然而，一旦脱离你的命令，他们就无法做出恰当的决策：你看完他们的选择后，发现他们选择的任务既有重复，也有缺漏，还有不少佣兵选择了自己能力不够、无法完成的任务。但你既然已经下令，朝令夕改会影响你的威信。

因此，你决定让他们按照自己的选择从你的手中接任务，如果选择的任务已经被接，则按照任务列表接下一个任务，如果还是被接则继续往下直至接到任务，如果到了最后一个还需继续往下，则从列表的第一个任务开始。（可以把列表理解为环状。列表顺序是既定的，你不可以修改）

不过，还有一件你可以控制的事：你可以决定他们谁先接任务。你需要找到一个最优的顺序，让佣兵完成最多的任务。

请计算最优顺序下可完成的任务数量。

（不知道怎么概括，以上为直接复制粘贴）

题解

按照出题人的题解。

首先要保证所有任务都不会被放弃，选择合适的起点即可。首先将每个任务被选中的人数减1求前缀和，找到最小的位置，从该位置的下一个位置作为起点即可保证所有任务都会有人接。

然后遍历每一个任务，查找可以选的人中有没有刚好大于任务需求的，有就让他接，没有就让能力最低的接，二分查找即可。维护最小值可以用std::set，这个容器的第一个元素就是最小的。

代码

因为并没有发生WA，所以就懒得写暴力验证程序了。

顺便std::set有一个问题，就是容器为空的时候如果调用erase删除元素会发生死循环，而不是RE，到OJ上的表现就是TLE，搞得我老在查是不是常数太大了。

AC代码如下

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

using namespace std;
const long long MAX = 5e5 + 7;

int choice[MAX];
int abilities[MAX];
int missionSelectedSum[MAX];
int missions[MAX];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    cin >> n;
    set<int> ability;
    unordered_set<int> missionSelected[n + 1];
    int tmp;
    // 找起点
    for (int i = 1; i <= n; i++) {
        cin >> choice[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> missions[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        missionSelected[choice[i]].insert(tmp);
    }
    int minSum = n + 1;
    missionSelectedSum[0] = 0;
    for (int i = 1; i <= n; i++) {
        missionSelectedSum[i] = missionSelectedSum[i - 1] + missionSelected[i].size() - 1;
    }
    // find the min sum
    int start = 1;
    for (int i = 1; i <= n; i++) {
        if (minSum > missionSelectedSum[i]) {
            start = i;
            minSum = missionSelectedSum[i];
        }
    }
    start += 1;
    // 开始了
    int ans = 0;
    for (int i = start; i <= n; i++) {
        for (auto it:missionSelected[i]) {
            ability.insert(it);
        }
        if (ability.empty()) {
            continue;
        }
        auto it = ability.lower_bound(missions[i]);
        if (it != ability.end()) {
            ans += 1;
            ability.erase(it);
        } else {
            ability.erase(ability.begin());
        }
    }
    for (int i = 1; i < start; i++) {
        for (auto it:missionSelected[i]) {
            ability.insert(it);
        }
        if (ability.empty()) {
            continue;
        }
        auto it = ability.lower_bound(missions[i]);
        if (it != ability.end()) {
            ans += 1;
            ability.erase(it);
        } else {
            ability.erase(ability.begin());
        }
    }
    cout << ans << endl;
    return 0;
}

测试例生成（Python）

这个程序其实不是很优，当max比较大的时候生成会很慢，主要是因为会生成长度为max的数组。如果不用这个方法的话得手写一个能产生唯一数字的序列，懒得再改了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/bin/env python
import random


def f(n, max=1e9, filename='in'):
    n = int(n)
    max = int(max)
    choice = [str(random.randint(1, n)) for i in range(n)]
    mission = list(range(1, max))
    random.shuffle(mission)
    mission = list(map(lambda x: str(x), mission[: n]))
    ability = list(range(1, max))
    random.shuffle(ability)
    ability = list(map(lambda x: str(x), ability[: n]))
    fi = open(filename, 'w')
    fi.write("{}\r\n{}\r\n{}\r\n{}\r\n".format(
        n, " ".join(choice), " ".join(mission), " ".join(ability)
    ))
    fi.close()

发表于 更新于 分类于 ， ，

题目

给一个$n$行$m$列的数据，找出其中

  • 尽可能大
  • 边长为奇数
  • 中心元素能被其他元素整除

的正方形。

题解

出题人的PPT题解上写的挺清楚了，上述条件成立的情况下，则中心元素一定是正方形内所有元素中最小的，而且正方形内所有元素的最大公约数也是中心元素。

暴力枚举每个点就行。我们可以用二维ST表来实现复杂度$O(1)$求最小值，$O(\log_2 n)$求区域内的最大公约数（GCD）。下标从$0$开始的话，只需要从$(1,1)$枚举到$(n-1,m-1)$即可，因为边缘上的数不会有正方形。

对于每个枚举，首先确定忽略条件3时最大能取的正方形的边长是多少，比如$(i,j)$的话最大边长是

1
min(min(i, n - i - 1), min(j, m - j - 1))

然后通过二分查找确定条件3下的最大边长。

代码

WA AC代码

我真希望在这里写的是”AC代码”，可惜现在还是卡在第8个测试点。

5.4 20:35 update: 因为把第102行的i写成了j导致一直卡在第8个test case而自闭。关于错误的位置可以看暴力验证代码的第100行（也就是说那个暴力程序是错误的）。

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

using namespace std;
const long long MAX = 2e6 + 7;

long long a[500][500];
long long st[500][500][10];
long long stGCD[500][500][10];

#define qmin(a, b, c, d) min(min(a,b),min(c,d))

long long gcd(long long x, long long y) {
    if (x == 0) {
        return y;
    }
    return gcd(y % x, x);
}

#define qgcd(a, b, c, d) gcd(gcd(a, b), gcd(c, d))

int pow2[10];

long long queryMin(long long midX, long long midY, long long len) {
    int k = log2(len * 2 + 1);
    return qmin(st[midX - len][midY - len][k],
                st[midX - len][midY + len - pow2[k] + 1][k],
                st[midX + len - pow2[k] + 1][midY - len][k],
                st[midX + len - pow2[k] + 1][midY + len - pow2[k] + 1][k]);
}

long long queryGCD(long long midX, long long midY, long long len) {
    int k = log2(len * 2 + 1);
    return qmin(stGCD[midX - len][midY - len][k],
                stGCD[midX - len][midY + len - pow2[k] + 1][k],
                stGCD[midX + len - pow2[k] + 1][midY - len][k],
                stGCD[midX + len - pow2[k] + 1][midY + len - pow2[k] + 1][k]);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m;
    cin >> n >> m;
    // n行m列
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            st[i][j][0] = a[i][j];
            stGCD[i][j][0] = a[i][j];
        }
    }
    // 预处理
    int len = min(n, m);
    pow2[0] = 1;
    for (int k = 1; k < 10; k++) {
        pow2[k] = pow2[k - 1] * 2;
    }
    int log2len = log2(len) + 1;
    for (int k = 1; k <= log2len; k++) {
        for (int i = 0; i + pow2[k] <= n; i++) {
            for (int j = 0; j + pow2[k] <= m; j++) {
                st[i][j][k] = qmin(st[i][j][k - 1],
                                   st[i][j + pow2[k - 1]][k - 1],
                                   st[i + pow2[k - 1]][j][k - 1],
                                   st[i + pow2[k - 1]][j + pow2[k - 1]][k - 1]);
                stGCD[i][j][k] = qgcd(stGCD[i][j][k - 1],
                                      stGCD[i][j + pow2[k - 1]][k - 1],
                                      stGCD[i + pow2[k - 1]][j][k - 1],
                                      stGCD[i + pow2[k - 1]][j + pow2[k - 1]][k - 1]);
            }
        }
    }
    // 查询
    int ans = 0;
    int count = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            // 确定可以取的范围
            int maxLen = qmin(i, n - i - 1, j, m - j - 1);
            // 二分查找
            int l = 1, r = maxLen + 1;
            while (l < r) {
                int mid = (l + r) / 2;
                if (a[i][j] == queryMin(i, j, mid) && a[i][j] == queryGCD(i, j, mid)) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            if (l == 1) {
                continue;
            }
            if (ans == l - 1) {
                // cout << i << "\t" << j << "\t" << l - 1 << endl;
                count += 1;
            } else if (l - 1 > ans) {
                // cout << i << "\t" << j << "\t" << l - 1 << endl;
                ans = l - 1;
                count = 1;
            }
        }
    }
    if (ans == 0) {
        cout << 1 << endl << n * m << endl;
        return 0;
    }
    cout << (ans * 2 + 1) * (ans * 2 + 1) << endl;
    cout << count << endl;
    return 0;
}

测试例生成（Python）

1
2
3
4
5
6
7
8
9
10
11
12
#!/bin/env python
import random


def e(n, m, max=1e9, filename='in'):
    a = []
    for i in range(n):
        a.append("\t".join([str(random.randint(1, max)) for j in range(m)]))
    f = open(filename, 'w')
    f.write("{} {}\r\n{}\r\n".format(n, m, "\r\n".join(a)))
    f.close()

暴力验证

这个其实不能算完全暴力，因为还是用了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
113
114
115
116
117
118
119
120
121
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

using namespace std;
const long long MAX = 2e6 + 7;

int a[500][500];
int st[500][500][10];
int stGCD[500][500][10];

#define qmin(a, b, c, d) min(min(a,b),min(c,d))

int gcd(int x, int y) {
    if (x == 0) {
        return y;
    }
    return gcd(y % x, x);
}

#define qgcd(a, b, c, d) gcd(gcd(a, b), gcd(c, d))

int pow2[10];

int queryMin(int midX, int midY, int len) {
    int k = log2(len * 2 + 1);
    return qmin(st[midX - len][midY - len][k],
                st[midX - len][midY + len - pow2[k] + 1][k],
                st[midX + len - pow2[k] + 1][midY - len][k],
                st[midX + len - pow2[k] + 1][midY + len - pow2[k] + 1][k]);
}

int queryGCD(int midX, int midY, int len) {
    int k = log2(len * 2 + 1);
    return qmin(stGCD[midX - len][midY - len][k],
                stGCD[midX - len][midY + len - pow2[k] + 1][k],
                stGCD[midX + len - pow2[k] + 1][midY - len][k],
                stGCD[midX + len - pow2[k] + 1][midY + len - pow2[k] + 1][k]);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m;
    cin >> n >> m;
    // n行m列
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            st[i][j][0] = a[i][j];
            stGCD[i][j][0] = a[i][j];
        }
    }
    // 预处理
    int len = min(n, m);
    pow2[0] = 1;
    for (int k = 1; k < 10; k++) {
        pow2[k] = pow2[k - 1] * 2;
    }
    int log2len = log2(len) + 1;
    for (int k = 1; k <= log2len; k++) {
        for (int i = 0; i + pow2[k] <= n; i++) {
            for (int j = 0; j + pow2[k] <= m; j++) {
                st[i][j][k] = qmin(st[i][j][k - 1],
                                   st[i][j + pow2[k - 1]][k - 1],
                                   st[i + pow2[k - 1]][j][k - 1],
                                   st[i + pow2[k - 1]][j + pow2[k - 1]][k - 1]);
                stGCD[i][j][k] = qgcd(stGCD[i][j][k - 1],
                                      stGCD[i][j + pow2[k - 1]][k - 1],
                                      stGCD[i + pow2[k - 1]][j][k - 1],
                                      stGCD[i + pow2[k - 1]][j + pow2[k - 1]][k - 1]);
            }
        }
    }
    // 查询
    int ans = 0;
    int count = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            // 确定可以取的范围
            int maxLen = qmin(i, n - i - 1, j, m - j - 1);
            // 暴力查找
            for (int l = maxLen; l >= 1; l--) {
                if (a[i][j] == queryMin(i, j, l) && a[i][j] == queryGCD(j, j, l)) {
                    if (ans == l) {
                        // cout << i << "\t" << j << "\t" << l << endl;
                        count += 1;
                    } else if (l > ans) {
                        // cout << i << "\t" << j << "\t" << l << endl;
                        ans = l;
                        count = 1;
                    }
                    break;
                }
            }
        }
    }
    if (ans == 0) {
        cout << 1 << endl << n * m << endl;
        return 0;
    }
    cout << (ans * 2 + 1) * (ans * 2 + 1) << endl;
    cout << count << endl;
    return 0;
}

发表于 更新于 分类于 ， ，

题目

一个环，环上有点，查询从$s$点到最近的大于等于$t$的点的正向距离，没有则输出$-1$。每个点在被查询过后会消失，没消失的点的值每次查询都增加1。

题解

基本上还是用线段树。

首先用一个grow变量标记过了多少个晚上，长了多少，然后就是用线段树查找出距离$s$最近的大于等于$t-\mathrm{grow}$的点，输出距离完事。

因为有环，所以在查找的时候需要做一些处理来拆环。我的做法比较省事，数组长度为$n$，先查找从$s$到$n$有没有，如果没有就查找从$0$到$s-1$，如果也没有就输出$-1$，有就计算距离输出。

因为是线段树，所以查询复杂度$O(\log_2 n)$，因为有$m$次查询，所以总的时间复杂度是$O(m\log_2 n)$。

代码

因为基本上是一发入魂（手点快了交了十多发完全一样的代码，有些AC有些TLE），所以就没写样例生成程序和暴力验证。

AC代码

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

using namespace std;
const long long MAX = 2e6 + 7;

int h[MAX];

struct Node {
    int left, right;
    int max;
    bool empty;
    Node *leftSon;
    Node *rightSon;
    Node *father;
};

Node &buildTree(int left, int right, Node *father = nullptr) {
    auto &node = *(new Node[1]);
    node.left = left;
    node.right = right;
    node.father = father;
    node.empty = false;
    if (left == right) {
        // leaf
        node.max = h[left];
        return node;
    }
    // build son
    int mid = (left + right) / 2;
    node.leftSon = &buildTree(left, mid, &node);
    node.rightSon = &buildTree(mid + 1, right, &node);
    node.max = max(node.leftSon->max, node.rightSon->max);
    return node;
}

void updateFatherMax(Node &node) {
    int newMax = max(node.leftSon->max, node.rightSon->max);
    if (newMax != node.max) {
        node.max = newMax;
        if (node.father != nullptr) {
            updateFatherMax(*node.father);
        }
    }
}

int queryMax(int left, int right, int t, Node &node) {
    if (node.empty || node.max < t) {
        return -1;
    }
    if (node.left == node.right) {
        // get caught
        node.empty = true;
        // update to father
        updateFatherMax(*node.father);
        return node.left;
    }
    int leftAns = -1;
    if (left <= node.left && right >= node.right) {
        // sub set
        leftAns = queryMax(left, right, t, *node.leftSon);
        return leftAns != -1 ? leftAns : queryMax(left, right, t, *node.rightSon);
    }
    int mid = (node.left + node.right) / 2;
    if (left <= mid) {
        leftAns = queryMax(left, right, t, *node.leftSon);
        if (leftAns != -1) {
            return leftAns;
        }
    }
    if (right > mid) {
        return queryMax(left, right, t, *node.rightSon);
    }
    return -1;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    // build tree
    auto root = buildTree(1, n);
    cin >> m;
    int s, t;
    int grow = 0;
    while (m--) {
        cin >> s >> t;
        int ans = -1;
        ans = queryMax(s + 1, n, t - grow, root);
        if (ans != -1) {
            ans = ans - s - 1;
        } else if (s != 0) {
            ans = queryMax(1, s, t - grow, root);
            if (ans != -1) {
                ans = (n - s - 1) + ans;
            }
        }
        cout << ans << " ";
        grow += 1;
    }
    return 0;
}

发表于 更新于 分类于 ， ，

题目

可持久化线段树模板题。

给一段序列，完成两个操作

  • 从一个版本新建一个版本，然后单点修改
  • 查询某个版本中某个点的值

题解

其实模板题没什么好说的，看下可持久化线段树的工作方式就知道了。OI-WiKi真是个好东西。这里还是描述一下怎么做吧。

假如我们要更新原数组中的1号元素，可以从上往下也可以从下往上，我选择的是从上往下。如下图

img

可以发现，每次更新一个点，只需要将查询路径中所有的节点都拷贝一份就好了。假如要更新的位置x在当前节点区间的左边，那么新拷贝的节点右儿子不变，左儿子建立一个拷贝，然后递归下去。复杂度和一般线段树一样，查询和修改都是$O(\log_2n)$。

代码

AC代码

居然一发入魂，懒得写测试例生成程序和暴力验证了。

个人觉得不是很优雅，在类中要使用自身的引用会有的麻烦，直接指针了。

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

using namespace std;
const long long MAX = 1e6 + 7;

//节点，包含区间左、区间右、当前值
struct Node {
    int left = 1, right = 1;
    bool init = false;
    int value = 0;
    Node *leftSon;
    Node *rightSon;
};

int a[MAX];

Node &buildTree(int left, int right) {
    auto &node = *(new Node[1]);
    node.left = left;
    node.right = right;
    node.init = true;
    if (left == right) {
        node.value = a[left];
        return node;
    }
    int mid = (left + right) / 2;
    node.leftSon = &buildTree(left, mid);
    node.rightSon = &buildTree(mid + 1, right);
    return node;
}

Node &update(int x, int y, Node &node) {
    auto &newNode = *(new Node[1]);
    memcpy(&newNode, &node, sizeof(Node));
    if (node.left == node.right) {
        newNode.value = y;
        return newNode;
    }
    // 更新并生成新版本
    int mid = (node.left + node.right) / 2;
    if (x <= mid) {
        // left
        newNode.leftSon = &update(x, y, *node.leftSon);
    } else {
        newNode.rightSon = &update(x, y, *node.rightSon);
    }
    return newNode;
}

int query(int x, Node &node) {
    if (node.left == node.right) {
        return node.value;
    }
    int mid = (node.left + node.right) / 2;
    if (x <= mid) {
        return query(x, *node.leftSon);
    } else {
        return query(x, *node.rightSon);
    }
}

Node root[100000];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m;
    char c;
    int v, x, y;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // build tree
    int version = 0;
    root[version] = buildTree(1, n);
    for (int i = 1; i <= m; i++) {
        cin >> c >> v >> x;
        if (c == '1') {
            // update
            cin >> y;
            version += 1;
            root[version] = update(x, y, root[v]);
        } else {
            // query
            cout << query(x, root[v]) << endl;
        }
    }
    return 0;
}

发表于 更新于 分类于 ， ，

题目

查找长度为$n$的序列中第一个大于等于$k$的元素的位置，并将这个位置的值减去$k$，重复$m$次。

题解

直接线段树。

首先建立线段树，每个节点保存区间内的最大值，从根节点递归下去即可，复杂度$O(n\log_2n)$。因为只需要单点更新，其实zkw线段树可能更适合，不过这里普通线段树就能过，就没必要了。

查找的过程也很简单，从根节点开始，如果当前节点的max小于$k$直接返回$-1$，如果当前节点是叶子节点就返回自己的索引，否则先找左儿子，左儿子如果是$-1$就返回右儿子，每次查询的复杂度是$O(\log_2n)$。我在自己笔记本上测试，$T=1,n=10^6,m=10^6$情况下的随机数据，基本压着1秒的线，太极限了。

代码

AC代码

有学长说这是主席树（持久化线段树），我也不知道是不是，照着OI-WiKi写的。

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

using namespace std;
const long long MAX = 1e6 + 7;

#define TREE_SUM 0
#define TREE_MAX 1
#define TREE_MIN 0

//节点，包含区间和、最大值、最小值、区间左、区间右
struct Node {
#if TREE_SUM
    int sum;
#endif
#if TREE_MAX
    long long max;
#endif
#if TREE_MIN
    int min;
#endif
    int left, right;
};
Node tree[MAX * 4];

long long a[MAX];

class SegmentTree {
private:
    int n;
public:
    SegmentTree(int _n) : n(_n * 4)/*, tree(_n * 4 + 1)*/ {}

    SegmentTree(int _n, long long *a) : n(_n + 1)/*, tree(_n * 4 + 3)*/ {
        build(1, _n, 1, a);
    }

    void build(int left, int right, int index, const long long *a) {
        auto &node = tree[index];
        if (left == right) {
            // 当前值
#if TREE_SUM
            tree[index].sum = a[left];
#endif
#if TREE_MAX
            node.max = a[left];
#endif
#if TREE_MIN
            tree[index].min = a[left];
#endif
            node.left = left;
            node.right = left;
            return;
        }
        int mid = (left + right) / 2;
        build(left, mid, index * 2, a);
        build(mid + 1, right, index * 2 + 1, a);
#if TREE_SUM
        tree[index].sum = tree[index * 2].sum + tree[index * 2 + 1].sum;
#endif
#if TREE_MAX
        node.max = max(tree[index * 2].max, tree[index * 2 + 1].max);
#endif
#if TREE_MIN
        tree[index].min = min(tree[index * 2].min, tree[index * 2 + 1].min);
#endif
        node.left = left;
        node.right = right;
    }

#if TREE_SUM
    // 求区间和
    int querySum(int left, int right, int index = 1) {
        if (left <= tree[index].left && right >= tree[index].right) {
            // 子集
            return tree[index].sum;
        }
        int ans = 0;
        int mid = (tree[index].left + tree[index].right) / 2;
        if (left <= mid) {
            // [left,mid]与询问区间有交集，递归查询左儿子
            ans += querySum(left, right, index * 2);
        }
        if (right > mid) {
            // [mid+1,right]与询问区间有交集，递归查询左儿子
            ans += querySum(left, right, index * 2 + 1);
        }
        return ans;
    }
#endif
#if TREE_MAX

    // 求区间最大值
    int queryMax(int left, int right, int index = 1) {
        if (left <= tree[index].left && right >= tree[index].right) {
            // 子集
            return tree[index].max;
        }
        int leftAns = INT_MIN;
        int rightAns = INT_MIN;
        int mid = (tree[index].left + tree[index].right) / 2;
        if (left <= mid) {
            leftAns = queryMax(left, right, index * 2);
        }
        if (right > mid) {
            rightAns += queryMax(left, right, index * 2 + 1);
        }
        return max(leftAns, rightAns);
    }

#endif
#if TREE_MIN
    // 求区间最小值
    int queryMin(int left, int right, int index = 1) {
        if (left <= tree[index].left && right >= tree[index].right) {
            // 子集
            return tree[index].min;
        }
        int leftAns = INT_MAX;
        int rightAns = INT_MAX;
        int mid = (tree[index].left + tree[index].right) / 2;
        if (left <= mid) {
            leftAns = queryMin(left, right, index * 2);
        }
        if (right > mid) {
            rightAns = queryMin(left, right, index * 2 + 1);
        }
        return min(leftAns, rightAns);
    }
#endif
#if TREE_SUM
    // 更新父节点的区间和
    void updateFatherSum(int treeIndex) {
        tree[treeIndex].sum = tree[treeIndex * 2].sum + tree[treeIndex * 2 + 1].sum;
        if (treeIndex != 1) {
            updateFatherSum(treeIndex / 2);
        }
    }
#endif

#if TREE_MAX

    void updateFatherMax(int treeIndex) {
        auto &node = tree[treeIndex];
        auto newMax = max(tree[treeIndex * 2].max, tree[treeIndex * 2 + 1].max);
        if (newMax != node.max && treeIndex != 1) {
            node.max = newMax;
            updateFatherMax(treeIndex / 2);
        }
    }

#endif

    // 单点更新
    void update(int index, long long value, int treeIndex = 1) {
        auto node = &tree[treeIndex];
        if (node->left == node->right) {
            //当前节点，更新
#if TREE_SUM
            tree[treeIndex].sum = value;
            updateFatherSum(treeIndex);
#endif
#if TREE_MAX
            node->max = value;
            updateFatherMax(treeIndex / 2);
#endif
#if TREE_MIN
            tree[treeIndex].min = value;
#endif
            return;
        }
#if TREE_MAX
        // 逐渐变小，应该不需要
        // node->max = max(node->max, value);
#endif
#if TREE_MIN
        tree[treeIndex].min = min(tree[treeIndex].min, value);
#endif
        int mid = (node->left + node->right) / 2;
        if (index <= mid) {
            update(index, value, treeIndex * 2);
        } else {
            update(index, value, treeIndex * 2 + 1);
        }
    }

    // 查询第一个大于等于k的元素，通过max>=k确定
    int getAns(int left, int right, long long k, int treeIndex = 1) {
        auto &node = tree[treeIndex];
        if (node.max < k) {
            // 别找了，就没有
            return -1;
        }
        if (node.left == node.right) {
            // 叶子，返回索引
            a[node.left] -= k;
            node.max -= k;
            updateFatherMax(treeIndex / 2);
            return node.left;
        }
        int leftAns = -1, rightAns = -1;
        if (node.left >= left && node.right <= right) {
            // 此节点被包含在区间中
            // 先找左边，是否有大于等于k的
            leftAns = getAns(left, right, k, treeIndex * 2);
            if (leftAns != -1) {
                return leftAns;
            }
            return getAns(left, right, k, treeIndex * 2 + 1);
        }
        // 有交集
        int mid = (node.left + node.right) / 2;
        if (left <= mid) {
            leftAns = getAns(left, right, k, treeIndex * 2);
            if (leftAns != -1) {
                return leftAns;
            }
        }
        if (right > mid) {
            return getAns(left, right, k, treeIndex * 2 + 1);
        }
        return -1;
    }
};

auto st = SegmentTree(MAX);

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t, n, m;
    int l, r, k;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        // build tree
        st.build(1, n, 1, a);
        for (int i = 1; i <= m; i++) {
            int idx = -1;
            cin >> l >> r >> k;
            idx = st.getAns(l, r, k);
            cout << idx << " ";
        }
    }
    return 0;
}

测试例生成（Python）

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
#!/bin/env python
import random


def v(t, n, m, max=1e9, filename='in'):
    t = int(t)
    n = int(n)
    m = int(m)
    max = int(max)
    step = t // 10
    f = open(filename, 'w')
    f.write("{}\r\n".format(t))
    for i in range(t):
        a = [str(random.randint(1, max)) for i in range(n)]
        q = [" ".join([
            str(random.randint(1, n // 2)),
            str(random.randint(n // 2, n)),
            str(random.randint(1, max))]) for i in range(m)]
        f.write("{} {}\r\n{}\r\n{}\r\n".format(
            n, m, " ".join(a), "\r\n".join(q)
        ))
        if i % step == 0:
            print(i)
    f.close()

暴力验证

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;
const long long MAX = 1e6 + 7;
long long a[MAX];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t, n, m;
    int l, r;
    long long k;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        while (m--) {
            cin >> l >> r >> k;
            // 暴力
            for (; l <= r; l++) {
                if (a[l] >= k) {
                    break;
                }
            }
            if (l <= r) {
                cout << l << " ";
                a[l] -= k;
            } else {
                cout << -1 << " ";
            }
        }
    }
    return 0;
}

发表于 更新于 分类于 ， ，

关键字：前缀和；逆序对；树状数组；

这题实属有丶东西。

首先确定分母，显然$l$和$r$共有$\frac{n(n+1)}{2}$种取值，所以分母就是那么多。

这题需要算法的部分主要在分子，即有多少个$(l,r)$对使得平均值小于等于$k$。

首先为了方便，我们将输入的每个元素全部减去$k$，这样只需要判断$[l,r]$区间上的和是否小于等于0即可即可，于是很自然地，我们可以算一下前缀和，这里用$S_i$表示。

那么对于$[l,r]$区间上的和，我们可以很方便地用$A=S_r-S_{l-1}$求出来，显然我们知道，$r\ge l$，而$l$和$r$都是整数，所以有$r>l-1$，现在联立一下，得到
$$
\cases{
S_r-S_{l-1}\le0 \
r>l-1
}
$$
这不就是妥妥的逆序对吗？也就是说，只要求出$S_i$的逆序对即可。

一般求逆序对可以暴力（时间复杂度$O(n^2)$）、归并排序（时间复杂度$O(n\log_2n)$）、树状数组（时间复杂度$O(n\log_2n)$），因为是数据结构专题，很自然地就选树状数组了。

求逆序对的思路参照leetcode 面试题51，首先对输入的序列，可以从后向前遍历，设当前遍历的元素是$a_i$，那么我们只需要找到在$a_i$之后且小于等于$a_i$的元素个数。具体来说，我们可以用一个桶，并求出桶中$1$到$a_i$的区间和，然后另第$a_i$个元素自增即可，因为桶需要更新，所以可以用树状数组或者线段树来完成，查询和更新的复杂度都是$O(\log n)$。

另外要注意，$a_i$的值可能很大，在题目中范围是1e9，然而我们并没有那么大的内存去开1e9长度的数组作为桶。实际上我们只要求逆序对的个数，对逆序对的具体值并不关心，只要他们的大小关系没问题就行，所以我们可以使用离散化算法，使得$a_i$的值缩小到$n$，具体做法是先拷贝到另一个数组，然后排序，再二分查找回来，就可以将原数组映射到大小为$n$的值域内。离散化算法的复杂度是$O(n\log n)$。

最后的输出就没啥了，gcd求最大公约数，分子分母都除以最法公约数，加个斜杠输出。

细节

  • int会溢出。
  • 答案为0单独判断，输出0/1。
  • 在求逆序对的时候如果$l-1$从1开始，那么$l$就得从0开始，所以得注意前缀和数组第一个元素，要么在前缀和数组头部添一个0，要么单独遍历$l=0$的情况。

代码

AC代码

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;
const long long MAX = 2e5 + 7;

long long gcd(long long a, long long b) {
    return a == 0 ? b : gcd(b % a, a);
}

class BIT {
private:
    vector<long long> tree;
    long long n;

public:
    BIT(long long _n) : n(_n), tree(_n + 1) {}

    static long long lowbit(long long x) {
        return x & (-x);
    }

    // 查询前缀和
    long long query(long long x) {
        long long ret = 0;
        while (x) {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    // 自增1
    void update(long long x) {
        while (x <= n) {
            tree[x]++;
            x += lowbit(x);
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    long long n, k;
    cin >> n >> k;
    vector<long long> sum(n + 1), arr(n + 1);
    long long ans = 0;
    long long tmp;
    for (long long i = 1; i <= n; i++) {
        cin >> tmp;
        arr[i] = tmp - k;
    }
    // prefix sum
    for (long long i = 1; i <= n; i++) {
        sum[i] = arr[i] + sum[i - 1];
    }
    // 求逆序对
    // 离散化
    vector<long long> tmpArr = sum;
    // for l=1
    sort(tmpArr.begin(), tmpArr.end());
    for (long long i = 0; i <= n; i++) {
        sum[i] = lower_bound(tmpArr.begin(), tmpArr.end(), sum[i]) - tmpArr.begin() + 1;
    }
    // 树状数组统计逆序对
    BIT bit(n + 1);
    for (long long i = n; i >= 0; i--) {
        ans += bit.query(sum[i]);
        bit.update(sum[i]);
    }
    // cout << ans << endl;
    // return 0;
    if (ans == 0) {
        cout << "0/1" << endl;
    } else {
        long long g = gcd(ans, n * (n + 1) / 2);
        cout << ans / g << "/" << n * (n + 1) / 2 / g;
    }
    return 0;
}

测试例生成（Python）

1
2
3
4
5
def c(n, k):
     a = [str(random.randint(1,2 * k)) for i in range(n)]
     f = open('in', 'w')
     f.write("{} {}\r\n{}\r\n".format(n, k, " ".join(a)))
     f.close()

暴力法（用于验证）

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;
const long long MAX = 2e5 + 7;

long long gcd(long long a, long long b) {
    return a == 0 ? b : gcd(b % a, a);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    long long n, k;
    cin >> n >> k;
    vector<long long> sum(n + 1), arr(n + 1);
    long long ans = 0;
    long long tmp;
    for (long long i = 1; i <= n; i++) {
        cin >> tmp;
        arr[i] = tmp - k;
        if (arr[i] <= 0) {
            ans += 1;
        }
    }
    // prefix sum
    for (long long i = 1; i <= n; i++) {
        sum[i] = arr[i] + sum[i - 1];
    }
    // 暴力
    for (long long l = 1; l < n; l++) {
        for (long long r = l + 1; r <= n; r++) {
            if (sum[r] - sum[l - 1] <= 0) {
                ans += 1;
            }
        }
    }
    // cout << ans << endl;
    // return 0;
    if (ans == 0) {
        cout << "0/1" << endl;
    } else {
        long long g = gcd(ans, n * (n + 1) / 2);
        cout << ans / g << "/" << n * (n + 1) / 2 / g;
    }
    return 0;
}

发表于 更新于 分类于 ， ，

关键字：栈；贪心；

leetcode 1081差不多，但是有一点区别。这题直接给出了元素的种类，也就是$k$，而leetcode上那题并不直接给出元素种类，但最多是26（小写字母），而这题的$k$高达1e6…

leetcode社区中的题解主要有两种方法：

  • 栈+贪心
  • 寻找第一个元素的位置+贪心

我在写本题的时候用的第一个方法，第二个应该也可以，但是有点麻烦，它需要$o(1)$的复杂度确定从$i$到最后共有多少种元素，leetcode那题因为最多26种，所以直接位运算就完事，而本题的$k$高达1e6，位运算显然不现实，也可以用前缀和去判断，但是我懒得写，直接第一种完事。

题解

参照这个题解。

上面链接的那个幻灯片就很直观了。首先从输入读取一个数字，如果栈是空的则入栈，如果非空则判断能否进入，首先先确定栈内是否存在这个数字，我的做法是用一个marked数组保存已经入栈的数字，如果存在则不处理，不存在则进行下一步，判断栈顶元素是否大于输入的数，如果大于而且栈顶元素还存在于之后的输入中，则出栈并重复这一步骤，直到栈为空或者栈顶小于输入的数，然后入栈，此时就能保证字典序是最小的。

要判断栈顶元素是否还存在于之后的输入中，我的做法是保存每个数字最后出现的位置，这样直接判断当前位置是否小于最后的位置即可。

代码

AC代码

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;
const int MAX = 1e6 + 5;
int lastPos[MAX];
int seq[MAX];
int origin[MAX];
bool marked[MAX];

int main() {
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(0);
    int n;
    int k;
    int tmp;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        // cin >> tmp;
        scanf("%d", &tmp);
        origin[i] = tmp;
        lastPos[tmp] = i;
    }
    // stack
    int stackIter = 1;
    for (int i = 1; i <= n; i++) {
        if (stackIter == 1) {
            // insert anyway
            seq[stackIter] = origin[i];
            marked[origin[i]] = true;
            stackIter += 1;
        } else {
            if (seq[stackIter - 1] == origin[i] || marked[origin[i]]) {
                continue;
            }
            while (true) {
                if (stackIter != 1 && seq[stackIter - 1] >= origin[i] && i < lastPos[seq[stackIter - 1]]) {
                    // pop
                    marked[seq[stackIter - 1]] = false;
                    stackIter -= 1;
                } else {
                    // insert
                    seq[stackIter] = origin[i];
                    marked[origin[i]] = true;
                    stackIter += 1;
                    break;
                }
            }
        }
    }
    if (stackIter <= k) {
        cout << "Kanade";
        return 0;
    }
    for (int i = 1; i < stackIter; i++) {
        //cout << seq[i] << " ";
        printf("%d ", seq[i]);
    }
    return 0;
}

测试例生成（Python3）

1
2
3
4
5
6
import random
def k(n,k):
     a = [str(random.randint(1, k)) for i in range(n)]
     f = open('in', 'w')
     f.write("{} {}\r\n{}\r\n".format(n, k, " ".join(a)))
     f.close()

彩蛋

吐个槽，我在本机上测试1e6的数据量，默认编译器是clang++ 11.0.3 with LLVM，跑了两秒多，换成g++9瞬间提升到0.08秒，绝了。

破案了，macOS上的clang++默认使用libc++，这个库无法通过一般方法关闭流同步，而g++使用的是libstdc++，就没有这个问题。

发表于 更新于 分类于 ， ，

关键字：并查集；

快慢指针法

这个方法来自于判断链表中是否存在环，原理很直观，就是加入一个移动较慢的指针（一般是快指针速度的一半），如果链表中有环的话，就会导致两个指针出发了一段时间后“撞”在一起。所以只要在出发后判断两个指针是否相等即可确定链表中是否有环。

题解

并查集模板题，快慢指针法判断是否成环，再加个路径压缩就完事。复杂度$o(n)$，这题限时是200ms，太极限了。

代码

AC代码

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;

int a[1000000];
int isLoop = 0;

int findSet(int fast, int slow, bool moveSlow = false, int step = 0) {
    if (fast == a[fast]) {
        isLoop = 0;
        return fast;
    } else {
        fast = a[fast];
        if (moveSlow) {
            slow = a[slow];
        } else {
            if (step && fast == slow) {
                // loop
                isLoop = 1;
                return fast;
            }
        }
        return findSet(fast, slow, !moveSlow, step + 1);
    }
}

void mergeSet(int x) {
    if (x == a[x]) {
        return;
    }
    int t = a[x];
    a[x] = x;
    mergeSet(t);
}

int main() {
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        //cin >> a[i];
        scanf("%d", a + i);
        if (a[i] == i) {
            ans += 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == i) {
            continue;
        }
        findSet(i, i);
        if (isLoop) {
            // new loop
            ans += 1;
        }
        // compress
        mergeSet(i);
    }
    cout << ans;
    return 0;
}

其中的findSet函数用于查找根结点，成环的话会返回环上某一点，具体是哪个这里不展开说，同时会标记isLoop变量。

mergeSet用于路径压缩，如果我们只关心一个结点的根结点，在findSet完成之后直接把根结点设为它的父结点，这样如果以后还有结点在findSet过程中路过这个结点就可以快速找到根结点了，再引申一下，如果将路径上所有的结点都重新设置父亲结点，就可以加快经过那些结点的findSet。再优化一下，ans+=1之后，这个结点的根结点其实也不重要了，它的子结点必然不需要ans+=1，所以直接把路径上每个结点都设为根节点，速度又能提升一些。

发表于 更新于 分类于 ，

废话不多说，直接上代码：

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
class BIT {
private:
    vector<int> tree;
    int n;
public:
    BIT(int _n) : n(_n), tree(_n + 1) {}

    static int lowbit(int x) {
        return x & (-x);
    }

    // 查询前缀和
    int query(int x) {
        int ret = 0;
        while (x) {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    // 更新
    void update(int x, int v) {
        while (x <= n) {
            tree[x] = v;
            x += lowbit(x);
        }
    }
};

从leetcode的一个题解里面抄的，构造函数接受一个参数_n表示数组长度，并初始化（为0），做了一些改动，感觉非常舒适。

TODO

  • 从数组或者迭代器中初始化
  • 使用模板，不局限于int类型