The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2:Hong Kong)

A. TreeScript

先跑较小的子树，但是要留下 $p_i$，最后跑 $dp$ 值最大的子树 $v1$。

$dp_{u} = \max {dp_{v_1}, dp_{v_2}+1}$。

B. BigPicture

被染色的必然是一个连通块。

对于每个没有被染色的连通块，恰好有一个格子的右边和下面都被染色。

所以前缀和计算即可，复杂度 $O(nm)$

C. PaintingGrid

如果 NM 都是奇数，那么无解。

如果 $N > 2^M$ 或者 $M > 2^N$，那么无解（鸽笼原理）。

如果存在一个解。

首先可以先构造前 $\log m$ 行，$a_{i,j}$ 表示 $j$ 有没有 $2^i$ 这一位，然后放入一个取反列，这样可以满足黑白 1/2。

这样就可以保证每列不同，后面随意构造（也要放入取反列）就可以了。（只要满足行不相同）

如果 $n$ 是偶数，那么显然可以。

如果 $n$ 是奇数，$m$ 必定是偶数，所以在第 $\log m$ 行的时候一定是黑白 1/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
#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    if (n * m % 2 == 1) {
        std::cout << "NO\n";
        return;
    }
    if (m <= 30 && (1 << m) < n) {
        std::cout << "NO\n";
        return;
    }
    if (n <= 30 && (1 << n) < m) {
        std::cout << "NO\n";
        return;
    }
    
    std::cout << "YES\n";
    
    bool swap = false;
    if (n < m) {
        swap = true;
        std::swap(n, m);
    }
    
    std::vector<std::vector<int>> a;
    int lg = std::__lg(m);
    if ((1 << lg) < m) {
        lg++;
    }
    for (int i = lg - 1; i >= 0; i--) {
        std::vector<int> x(m), y(m);
        for (int j = 0; j < m; j++) {
            x[j] = j >> i & 1;
            y[j] = !x[j];
        }
        a.push_back(x);
        a.push_back(y);
    }
    if (n % 2 == 1) {
        a.pop_back();
    }
    std::sort(a.begin(), a.end());
    
    int cur = 0, p = 0, q = a.size() - 1;
    int t = a.size();
    while (a.size() < n) {
        std::vector<int> x(m), y(m);
        for (int j = 0; j < m; j++) {
            if (j < 30 && (cur >> j & 1)) {
                x[m - 1 - j] = 1;
            }
            y[m - 1 - j] = !x[m - 1 - j];
        }
        cur++;
        while (p < t && a[p] < x) {
            p++;
        }
        if (p < t && a[p] == x) {
            continue;
        }
        while (q >= 0 && a[q] > y) {
            q--;
        }
        if (q >= 0 && a[q] == y) {
            continue;
        }
        a.push_back(x);
        a.push_back(y);
    }
    
    if (!swap) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                std::cout << a[i][j];
            }
            std::cout << "\n";
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                std::cout << a[j][i];
            }
            std::cout << "\n";
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

E. Goose, goose, Duck?

有多少个区间满足没有元素出现 k 次。

扫描线，考虑枚举左端点，然后加上合法的点的个数。

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
std::vector<std::vector<int>> pos(m);
for (int i = 0; i < n; i++) {
    pos[a[i]].push_back(i);
}
std::vector<std::vector<std::tuple<int, int, int>>> f(n);
for (int i = 0; i < m; i++) {
    for (int j = 0; j + k - 1 < pos[i].size(); j++) {
        int xl = 0, xr = pos[i][j];
        int yl = pos[i][j + k - 1], yr = n - 1;
        if (j > 0) {
            xl = pos[i][j - 1] + 1;
        }
        if (j + k < pos[i].size()) {
            yr = pos[i][j + k] - 1;
        }
        f[xl].emplace_back(yl, yr, 1);
        if (xr < n - 1) {
            f[xr + 1].emplace_back(yl, yr, -1);
        }
    }
}

Info init;
init.min = 0;
init.cnt = 1;
LazySegmentTree<Info, Tag> seg(std::vector(n, init));

i64 ans = 0;

for (int i = 0; i < n; i++) {
    for (auto [l, r, t] : f[i]) {
        seg.rangeApply(l, r + 1, t);
    }
    auto info = seg.rangeQuery(0, n);
    if (info.min == 0) {
        ans += info.cnt - i;
    }
}

std::cout << ans << "\n";

F. SumofNumbers

尽量均分，余数小于等于 $k$，然后 dp 一下就可以了。

H. AnotherGooseGooseDuckProblem

1
2
3
4
5
void solve() {
  int l, r, b, k;
  cin >> l >> r >> b >> k;
  cout << 1ll * (b * ((l + b - 1) / b)) * k << "\n";
}

I. Range Closest Pair of Points Query

https://www.luogu.com.cn/problem/P9062

可以转到题解区。

以下方法没有经过任何测试：

回忆全局平面最近点对的办法：可以多次随机旋转一个角度，按照 x*y 排序，前后找 C 个更新。

对于区间，我们可以处理出 $ans_{L,R}$ 表示 $[L,R]$ 块的答案，散块拿出来当全局处理，剩下的是散块和整块之间的答案更新。

具体的：对于一个点 $i$，记录 $tmp_{i, j}$ 表示 $i$ 点在 $j$ 块内的最近距离。

$res1_{j,k,i}$ 表示 $k$ 的前 $i$ 个点和 $j$ 的最短距离，可以通过 $tmp_{i,j}$ 做前缀最小值处理出来，同样 $res2$ 处理后缀最小值。

复杂度是 $C \times N \sqrt N$，不知道能不能过。

K. Maximum GCD

一个数字如果取模，那么可以取到的范围是 $[1, \lfloor \frac{x}{2} \rfloor]$。

不取模就是 $x$。

L. Permutation Compression

首先肯定是从大到小删除数字，然后用尽可能大的长度删。

具体的：找到一个数字可以掌控的区间（用单调栈加二分就可以），然后看一下这个区间里面存在的数字个数是多少，用尽可能大的 $l_i$ 去删掉这个数字。

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
#include <bits/stdc++.h>

using i64 = long long;
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n = 0) {
        init(n);
    }
    
    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }
    
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    
    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int kth(T k) {
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    
    std::vector<int> a(n), b(m), pos(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i]--;
        pos[a[i]] = i;
    }
    for (int i = 0; i < m; i++) {
        std::cin >> b[i];
        b[i]--;
    }
    
    std::vector<int> len(k);
    for (int i = 0; i < k; i++) {
        std::cin >> len[i];
    }
    std::sort(len.begin(), len.end());
    
    std::multiset s(len.begin(), len.end());
    
    std::vector<int> del, l(n), r(n);
    std::vector<bool> isdel(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (j < m && a[i] == b[j]) {
            j++;
        } else {
            isdel[i] = true;
            del.push_back(a[i]);
        }
    }
    
    if (del.size() != n - m) {
        std::cout << "NO\n";
        return;
    }
    
    std::vector<int> stk{-1};
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = stk.size() - 1;
        while (lo < hi) {
            int x = (lo + hi + 1) / 2;
            if (a[i] > a[stk[x]]) {
                hi = x - 1;
            } else {
                lo = x;
            }
        }
        l[i] = stk[lo];
        
        if (!isdel[i]) {
            stk.resize(lo + 1);
            stk.push_back(i);
        }
    }
    
    stk = {n};
    for (int i = n - 1; i >= 0; i--) {
        int lo = 0, hi = stk.size() - 1;
        while (lo < hi) {
            int x = (lo + hi + 1) / 2;
            if (a[i] > a[stk[x]]) {
                hi = x - 1;
            } else {
                lo = x;
            }
        }
        r[i] = stk[lo];
        
        if (!isdel[i]) {
            stk.resize(lo + 1);
            stk.push_back(i);
        }
    }
    
    std::sort(del.begin(), del.end());
    
    Fenwick<int> fen(n);
    for (int i = 0; i < n; i++) {
        fen.add(i, 1);
    }
    
    for (int i = int(del.size()) - 1; i >= 0; i--) {
        int j = pos[del[i]];
        int cnt = fen.rangeSum(l[j] + 1, r[j]);
        
        auto it = s.upper_bound(cnt);
        if (it == s.begin()) {
            std::cout << "NO\n";
            return;
        }
        s.erase(std::prev(it));
        fen.add(j, -1);
    }
    
    std::cout << "YES\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}