注，你需要将Codeforces右上角处的语言设置切换成俄语，才能看到完整版的题单，推荐配合 Codeforces Better 翻译插件刷
Z-Function
注意参考代码中的zFunction定义，有的z[0]=n，有的z[0]=n
Step 1
A. Наидлиннейший палиндромный префикс - 1（The Idnaean Palindry Prefix - 1）
题意
给你一个字符串，要求你找出最长回文前缀的长度，$n \le 2000$。
参考思路
直接将原字符串反转，拼接到原字符串后面，跑一遍 Z-Function，再从 $i = n$ 向 $i < 2n$ 遍历，判断第一次出现 $z[i] \ge 2n - i$ 的下标位置即可，复杂度 $O(n)$。
参考代码
auto zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s;
std::cin >> s;
std::string t(s.rbegin(), s.rend());
int n = s.size();
s += t;
auto z = zFunction(s);
int ans = 1;
for (int i = 1; i <= n; i++) {
if (z[2 * n - i] == i) ans = i;
}
std::cout << ans << "\n";
}
B. Префиксный и суффиксные подстроки - 1(Prefix and suffix substrates - 1)
题意
给你一个字符串，求该字符串有多少子串，要么是前缀，要么是后缀（同时满足前缀后缀则不统计）。
参考思路
考虑 $n^2$ 枚举子串左右端点，可以用 Z-Function 实现 $O(1)$ 判断前缀（即 $z[i] \ge len$）；同理，将字符串反转后跑 Z-Function 可以 $O(1)$ 判断子串是否是字符串的后缀。
参考代码
auto zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
auto z = zFunction(s);
auto rz = zFunction(std::string(s.rbegin(), s.rend()));
int cnt = 0;
for (int i = 0; i < n; i++) {//枚举左端点
for (int j = i; j < n; j++) {//枚举右端点
int len = (j - i + 1);
if ((z[i] >= len) ^ (rz[n - 1 - j] >= len)) {
cnt++;
}
}
}
std::cout << cnt << "\n";
}
C. Поиск подстроки в строке с джокерами в образце(Search for substrings in a string with jokers in sample)
题意
给定文本 $t$（$|t| \le 50000$） 和模式 $p$（$|p| \le 100$）。文本由小写拉丁字母组成。模式由小写拉丁字母组成，并且可能包含 $0$ 个或更多个特殊字符 ‘?’(通配符)。通配符是模式中的一个特殊字符，它可以被视为与文本中的任何字符相等。
在文本中输出所有模式的出现位置。找出文本中所有这样的索引 $i$ ，使得从文本索引 $i$ 开始存在模式的出现位置。
参考思路
考虑用直觉爆改 Z-Function，将 Z-Function 判断字符相等的条件改成：
(s[i + z[i]] == s[z[i]] || s[z[i]] == '?')
再将模式串拼到文本串前面，跑 Z-Funciton 后，$O(n)$ 在文本串枚举 $i$ 判断 $z[i] == |p|$ 即可
这种爆改Z-Function的复杂度，疑似是 O(nm) 的，如果原文本和模式串都有通配符，可以这样改：（经 Luogu P4173 验证，喜提 TLE）
(s[i + z[i]] == s[z[i]] || (z[i] < n_ && s[z[i]] == '*') || (i + z[i] >= n_ && s[i + z[i]] == '*'))
参考代码
auto zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && (s[i + z[i]] == s[z[i]] || s[z[i]] == '?'))
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s, t;
std::cin >> s >> t;
int n = s.size();
int m = t.size();
s = t + s;
auto z = zFunction(s);
std::vector<int> ans;
for (int i = m; i < n + m; i++) {
if (z[i] >= m) ans.push_back(i - m);
}
std::cout << ans.size() << "\n";
for (auto &i : ans) std::cout << i << " ";
std::cout << "\n";
}
D. Количество хороших подстрок - 1(Number of good substrates - 1)
题意
给定两个字符串 $s$ 和 $t$ 。如果字符串 $s[i \dots j]$ 的一个子字符串不包含字符串 $t$ 作为子字符串，则称该子字符串为“好”子字符串。即使内容相同，但位置不同的子字符串在 $s$ 中也应被视为不同的子字符串。换句话说，你需要找到满足以下条件的索引对 $(i,j)$ ( $i \le j$ ) 的数量：子字符串 $s[i \dots j]$ 不包含 $t$ 。
参考思路
算贡献题，用字符串拼接跑 Z-Function 的方法预处理出所有 t 在 s 中的匹配位置，然后统计贡献即可。
初始化答案为 $ans = n(n - 1) / 2$ 考虑每个匹配位置对答案的贡献，设匹配位置的左右端点为 $l, r$，则对答案的贡献为 $ans -= l * (n - r)$，然后画图理解一下不同匹配位置之间是否会互相影响，以及如何抵消掉改影响即可。
时间复杂度：$O(n)$
参考代码
auto zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s, t;
std::cin >> s >> t;
int n = s.size();
int m = t.size();
auto z = zFunction(t + s);
std::vector<int> match;
for (int i = m; i + m - 1 < n + m; i++) {
if (z[i] >= m) match.push_back(i - m);
}
i64 ans = 1ll * n * (n + 1) / 2;
std::vector<i64> r(match.size());
//重点是这里的贡献处理，可以自己画个图理解一下怎么抵消的贡献
for (int i = 0; i < match.size(); i++) {
int r_ = n - (match[i] + m - 1);
for (int j = i; j >= std::max(0, i - 1); j--) {
ans -= (match[j] + 1) * r_;
r_ = -r_;
}
}
std::cout << ans << "\n";
}
Step 2
A. Z-функция (простая версия)(Z-function (simple version))
n 方实现 Z-Function， 板子题，不讲
B. Z-функция строки Грея(Z-function line of Gray)
题意
格雷码字符串序列 $g_1, g_2, \dots$ 如下所示：
- $g_1$ = “a”
- $g_2$ = “aba”
- $g_3$ = “abacaba”
- $g_4$ = “abacabadabacaba”
- …
- $g_i$ = $g_{i-1} + c_i + g_{i-1}$ , 其中 $c_i$ 是字母表中的第 $i$ 个字符
- …
需要注意的是，格雷码的长度增长非常快(第 $i$ 行的长度为 $2^i - 1$)，但它们具有规律的分形结构。
格雷码经常被用来分析字符串算法的运作。
在这个任务中，你需要根据给定的格雷码字符串索引 $k$ 和数字 $j$ ，输出 $z_j$ - 在索引 $j$ 处的字符串 $g_k$ 的 z 函数值。
参考思路
打表找规律，然后写个递归即可。
当 $k = 4$ 时，Z-Function打表结果如下：
0 1 0 3 0 1 0 7 0 1 0 3 0 1 0
结论是，区间长度按照 $1, 3, 7, …$ 的形式递增，递归向下搜，如果 $j$ 位于区间中点，那么搜索结束，直接输出区间长度除2，否则将区间切成两块更新 j 为到区间左端点的距离，继续往下递归即可。
参考代码
int dfs(int n, int i) {
if ((n + 1) / 2 == i) return n / 2;
return dfs(n / 2, i % ((n + 1) / 2));
}
void solve() {
int k, j;
std::cin >> k >> j;
if (j == 0) {
std::cout << 0 << "\n";
return;
}
std::cout << dfs((1 << k) - 1, j) << "\n";
}
C. Строка по z-функции(Line by z-function)
题意
给定一个长度为 $n$ ( $1 \le n \le 50$ ) 的整数数组 $z$ ，数组中的元素取值范围为 $0$ 到 $50$ 。请判断是否存在一个字符串 $s$ ，其 z 函数值为 $z$ 。如果存在，请输出任意一个这样的字符串。字符串 $s$ 可以使用大小写英文字母。
参考思路
先做点特判，比如 $z[0] == 0$ 且 $z[i] \le (n - i)$。
然后暴力初始化原串为 $n$ 个不同的字符，最后按照 Z-Function 定义暴力 $O(n^2)$ 更新原字符串。对处理出的字符串跑一遍 Z Function 验证一下即可。
参考代码
//预处理
std::vector<char> mp;
for (char c = 'a'; c <= 'z'; c++) {
mp.push_back(c);
}
for (char c = 'A'; c <= 'Z'; c++) {
mp.push_back(c);
}
void solve() {
int n;
std::cin >> n;
std::vector<int> z(n);
for (auto &i : z) std::cin >> i;
if (z[0] != 0) {
std::cout << "!\n";
return;
}
for (int i = 1; i < n; i++) {
if (z[i] > (n - i)) {
std::cout << "!\n";
return;
}
}
std::string ans(n, 'a');
for (int i = 0; i < n; i++) {
ans[i] = mp[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < z[i]; j++) {
ans[i + j] = ans[j];
}
}
auto z_ = zFunction(ans);
if (z == z_) {
std::cout << ans << "\n";
} else {
std::cout << "!\n";
}
}
Step 3
A. Z-функция(Z-function)
Z-Function 板子题，不讲
Step 4
A. Минимальный период строки(Minimum line period)
题意
用字符串的 z 函数来解决这个问题。有很多方法可以解决这个问题，但作为使用 z 函数的练习，请尝试提出并实现这样一个解决方案。
在这个问题中，如果重复无数次的字符串 $p$ 的前缀是 $s$ ，那么字符串 $p$ 就叫做字符串 $s$ 的周期。换句话说，如果 $pp \dots p \dots$ 以 $s$ 开头。
您的任务是找到这样一个字符串 $p$ ，它是给定字符串 $s$ 的最短周期。例如， $s$ =abcab 的最短周期是 $p$ =abc。
参考思路
z-Function 板子题，跑一遍 zFunction 后，从前往后枚举 $i$，找到第一次出现 $z[i] == n - i$ 的位置，截断并输出字符串即可，如果均找不到，输出整个字符串。
参考代码
std::vector<int> zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s;
std::cin >> s;
auto z = zFunction(s);
int n = s.size();
for (int i = 1; i < n; i++) {
if (z[i] == n - i) {
std::cout << s.substr(0, i) << "\n";
return;
}
}
std::cout << s << "\n";
}
B. Циклические сдвиги(Cyclical shifts)
题意
用字符串的 z 函数来解决这个问题。有很多方法可以解决这个问题，但作为使用 z 函数的练习，请尝试提出并实现这样一个解决方案。
给出长度为 $n$ 的字符串 $s$ 。它的循环左移值 $k$ ( $0 \le k < n$ ) 称为形式为 $s_{k}s_{k+1} \dots s_{n-1}s_{0}s_{1} \dots s_{k-1}$ 的字符串 $t$ 。
下面给出两个长度相同的字符串 $s$ 和 $t$ 。我们需要检查 $t$ 是否是 $s$ 的循环移位。如果是，请根据上述定义打印相应的 $k$ 。
参考思路
考虑字符串拼接：$s + t + t$，然后对拼接后的字符串跑一遍 z-Function，最后暴力从 $n$ 到 $2 * n$ 枚举 $i$，判断 是否出现过 $z[i] \ge n$ 即可。复杂度 $O(n)$
参考代码
std::vector<int> zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s, t;
std::cin >> s >> t;
int n = s.size();
t = s + t + t;
auto z = zFunction(t);
for (int i = n; i < n + n; i++) {
if (z[i] >= n) {
std::cout << (2 * n - i) % n << "\n";
return;
}
}
std::cout << -1 << "\n";
}
C. Вхождения префиксов(Entry of prefixes)
题意
用字符串的 z 函数来解决这个问题。有很多方法可以解决这个问题，但作为使用 z 函数的练习，请尝试提出并实现这样一个解决方案。
给出字符串 s。从 1 到 |s| 的每个 i 求其长度为 i 的前缀在字符串中出现的次数。
参考思路
对原字符串跑一遍 z Function，然后枚举 $z[i]$，维护一个差分数组 pre[0]++，pre[z[i]]–，最后前缀和计数即可。复杂度 $O(n)$
参考代码
std::vector<int> zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
std::vector<int> pre(n + 1);
for (auto &i : zFunction(s)) {
pre[0]++; pre[i]--;
}
std::partial_sum(pre.begin(), pre.end(), pre.begin());
for (int i = 0; i < n; i++) std::cout << pre[i] << " ";
std::cout << "\n";
}
D. Палиндромный префикс(Palinthic prefix)
题意
用字符串的 z 函数来解决这个问题。有很多方法可以解决这个问题，但作为使用 z 函数的练习，请尝试提出并实现这样一个解决方案。
给出字符串 $s$ 。求其最长前缀的长度，它是一个回文。
参考思路
考虑如下字符串拼接：s 和 自身反串拼接，然后跑一遍 zFunction，枚举下标更新最长答案即可。
参考代码
auto zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s;
std::cin >> s;
std::string t(s.rbegin(), s.rend());
int n = s.size();
s += t;
auto z = zFunction(s);
int ans = 1;
for (int i = 1; i <= n; i++) {
if (z[2 * n - i] == i) ans = i;
}
std::cout << ans << "\n";
}
E. Странная операция(Strange operation)
题意
对于给定的字符串 $s = s_{1} s_{2} \dots s_{n}$ 来说，有效的操作包括以下步骤：
- 从 $0$ 到 $n$ 之间(包括首尾)选择一个整数 $k$ ；
- 删除前 $k$ 个字符，但以相反的顺序将它们添加到字符串的末尾：即 $s$ 的形式为 $s_{k+1}\dots s_{n}~s_{k}~s_{k-1}~\dots s_{1}$ 。
有两个字符串 $s$ 和 $t$ 。检查是否有一种操作能使 $s$ 等于 $t$ 。操作只能进行一次。
参考思路
先预处理判断字符串长度是否相等。
考虑字符串拼接：r = t + s，然后跑一遍 Z-Function，从中间开始向后枚举下标，在第一次出现 $r[n + i] != r[n - 1 - i]$ 前 判断是否存在匹配：$z[n + i] == n - i$ 即可。
参考代码
auto zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s, t;
std::cin >> s >> t;
if (s.size() != t.size()) {
std::cout << "No";
return;
}
int n = s.size();
auto r = t + s;
auto z = zFunction(r);
for (int i = 0; i < n; i++) {
if (z[n + i] == n - i) {
std::cout << "Yes\n" << i;
return;
}
if (r[n + i] != r[n - 1 - i]) {
std::cout << "No";
return;
}
}
}
F. Кратчайшая надстрока(The shortest superstructure)
题意
用字符串的 z 函数来解决这个问题。有很多方法可以解决这个问题，但作为使用 z 函数的练习，请尝试提出并实现这样一个解决方案。
给出两个字符串 $s$ 和 $t$ 。输出包含 $s$ 和 $t$ 两个子串的最短字符串 $r$ 。
参考思路
分别考虑 s + t 和 t + s，分别跑一遍 zFunction，由于正反操作一样，不妨先考虑 s + t，先判断 s 是否 直接出现在 t串中，若出现，则直接返回 t；否则从拼接位置开始向后遍历，判断第一次出现 $z[i] == n + m - i$ 时，直接返回 $t + s.substr(z[i])$ 即可；否则直接返回 t + s。对t + s，操作相同，所以封装一个函数，分便对两种拼接跑一遍答案，比较长度并输出即可。
直接看代码可能好理解一点
参考代码
auto zFunction(const std::string &s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s, t;
std::cin >> s >> t;
auto work = [&](std::string a, std::string b) -> std::string {
int n = a.size();
int m = b.size();
auto s = a + b;
auto z = zFunction(s);
for (int i = n; i < n + m; i++) {
if (z[i] >= n) {
return b;
}
}
for (int i = n; i < n + m; i++) {
if (z[i] == n + m - i) {
return b + a.substr(z[i]);
}
}
return b + a;
};
auto ans1 = work(s, t);
auto ans2 = work(t, s);
std::cout << (ans1.size() < ans2.size() ? ans1 : ans2) << "\n";
}
G. Кубики(Cubequets)
题意
用字符串的 z 函数来解决这个问题。有很多方法可以解决这个问题，但作为使用 z 函数的练习，请尝试提出并实现这样一个解决方案。
幽灵 Petya 喜欢玩他的方块。他喜欢把它们摆成一排，看着自己的作品。不过，最近他的朋友们决定和 Petya 开个玩笑，在他的游戏室里放了一面镜子。毕竟，每个人都知道镜子里是照不出鬼的！但是立方体可以。
现在，彼佳看到了 $n$ 个彩色方块，但他不知道哪些是真的，哪些只是镜子里的倒影。帮助彼佳！找出 Petya 可以拥有多少个立方体。Petya 看到了镜子中所有立方体的倒影，以及立方体在他面前的部分。有些立方体可能在 Petya 的后面，但他看不到。
参考思路
研究一下样例会发现，这题实际上等价于求所有偶数长度的前缀回文串。考虑字符串拼接：s + 自身反串，然后跑一遍 Z-Function，最后枚举下标找回文串即可
参考代码
auto zFunction(const auto& s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
auto a_ = a;
a_.reserve(2 * n);
std::reverse(a.begin(), a.end());
for (auto &i : a) a_.push_back(i);
std::vector<int> ans;
ans.reserve(n);
auto z = zFunction(a_);
for (int i = n; i < 2 * n; i++) {
if (z[i] % 2 == 0 && z[i] == 2 * n - i) {
ans.push_back(n - z[i] / 2);
}
}
ans.push_back(n);
for (auto &i : ans) std::cout << i << " ";
}
H. Сумма длин различных подстрок(The amount of lengths of different substrings)
题意
用字符串的 z 函数来解决这个问题。有很多方法可以解决这个问题，但作为使用 z 函数的练习，请尝试提出并实现这样一个解决方案。
给出字符串 $s$。输出该字符串所有可能的不同子串的总长度。
参考思路
先考虑所有位置的字符均不相等的字符串的贡献是多少：$ans = \sum_{i = 1}^n\sum_{j = i}^nj - i = \sum_{i = 1}^{n} \frac{i(i + 1)}{2}$
再考虑如果出现子串相同的情况，那么如何抵消重复的贡献。
不难发现，我们可以利用 SA数组 的思想，先将字符串所有的后缀提出来，排序后暴力求字典序相邻后缀的lcp，最后令 $ans = ans - \sum|lcp_i|(|lcp_i| + 1) / 2$ 即可。
（感觉，似乎用不上 Z-Function，如果直接上 SA数组，可以做到$O(n)$ 的复杂度）
复杂度：$O(n^2)$
参考代码
auto zFunction(const auto& s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
//z[0] = n;
return z;
}
i64 sum(i64 x) {
return x * (x + 1) / 2;
}
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
std::vector<i64> pre(n + 1);
for (int i = 1; i <= n; i++) {
pre[i] = sum(i);
}
std::partial_sum(pre.begin(), pre.end(), pre.begin());
i64 ans = pre[n];
std::vector<std::string> t;
for (int i = 0; i < n; i++) {
t.push_back(s.substr(i));
}
std::sort(t.begin(), t.end());
for (int i = 1; i < n; i++) {
auto z = zFunction(t[i - 1] + t[i]);
ans -= sum(std::min<int>(t[i - 1].size(), z[t[i - 1].size()]));
}
std::cout << ans;
}
I. Неточный поиск(Inaccurate search)
题意
使用字符串的z函数来解决这个问题。有很多方法可以解决这个问题，但作为z函数的练习，请尝试设计并实现这样的解决方案。
给出文本 $t = t_{1}~t_{2}~\dots~t_{|t|}$ 和样本 $p = p_{1}~p_{2}~\dots~p_{|p|}$ 。此外，还设置了参数 $k$ 。
如果 $t[d~\dots~d + |p| - 1] = p$ 对 $d$ 是正确的，那么 $t$ 和 $d$ 有一个精确的条目 $p$ 。
对于索引 $d$ ，在 $t[d~\dots~d + |p| - 1]$ 子字符串中有一个 $f$ 字符的窗口，在这个窗口中可以更改 $0$ 或更多字符，这样(但窗口长度保持不变)子字符串 $t[d~\dots~d + |p| - 1]$ 等于 $p$ ，同时 $f \le k$ ，在这种情况下，样本输入不准确。很明显，确切的输入是一个不准确的私人案例。
例如，如果 $k = 3$ ， $t$ = " abacabadabacaba “和 $p$ = ” baxayad “，那么索引 $2$ 就有一个不准确的条目(注意，在这个问题中，所有的索引都是从 $1$ 开始编号的)。
您的任务是查找文本 $t$ 中样本 $p$ 的所有不准确输入。
参考思路
先特判字符串长度，$|s| < |t|$ 则无解；再特判 $k > |t|$，则任意位置均可匹配。
考虑字符串拼接 : t + s 和 t反转 + s反转，分别跑一遍 Z-Function 得到 z 和 rz 数组，最后双指针匹配即可。复杂度 $O(n + m)$
直接看代码实现更好理解一点
参考代码
auto zFunction(const auto& s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
//z[0] = n;
return z;
}
void solve() {
std::string s, t;
std::cin >> s >> t;
int k;
std::cin >> k;
if (s.size() < t.size()) {
std::cout << 0 << "\n";
return;
}
if (k >= t.size()) {
std::cout << s.size() - t.size() + 1 << "\n";
for (int i = 0; i <= s.size() - t.size(); i++) {
std::cout << i + 1 << " ";
}
return;
}
std::vector<int> ans;
auto z = zFunction(t + s);
auto rz = zFunction(std::string(t.rbegin(), t.rend()) + std::string(s.rbegin(), s.rend()));
int i = 0, j = s.size() - t.size();
while (t.size() + i <= s.size()) {
if (z[t.size() + i] + rz[t.size() + j] + k >= t.size()) {
ans.push_back(i + 1);
}
i++; j--;
}
std::cout << ans.size() << "\n";
for (auto &i : ans) std::cout << i << " ";
}
J. Циклические суффиксы(Cyclical suffixes)
题意
用字符串的 z 函数来解决这个问题。有很多方法可以解决这个问题，但作为使用 z 函数的练习，请尝试提出并实现这样一个解决方案。
考虑字母表 $\Sigma$ 上的字符串 $s = s_1 s_2 s_3 \dots s_{n - 1} s_n$ 。让我们把 $s$ 字符串的 $m$ 阶循环扩展称为由 $m$ 个字符组成的 $s_1 s_2 s_3 … s_{n - 1} s_n s_1 s_2 …$ 形式的字符串；这意味着我们将 $s$ 字符串追加到自身，直到得到所需的长度，然后取长度前缀 $m$ 。
我们将循环字符串 $\tilde s$ 称为字符串 $s$ 的无限循环扩展。
让我们考虑循环字符串 $\tilde s$ 的后缀。显然，最多有 $|s|$ 个不同的后缀： $(n + 1)$ (第一个后缀匹配第一个后缀)， $(n + 2)$ (第二个后缀匹配第二个后缀)，以此类推。此外，不同的后缀可能更少。例如，如果 $S = {abab}$ ，循环字符串 $\tilde s$ 的前四个后缀是：
- $\tilde s_1 = {ababababab} …$
- $\tilde s_2 = {bababababa} …$
- $\tilde s_3 = {ababababab} …$
- $\tilde s_4 = {bababababa} …$
这里只有两个不同的后缀，而 $|s| = 4$ .
让我们对 $\tilde s$ 的前 $|s|$ 个后缀按词性排序。如果两个后缀相匹配，我们将把索引较小的后缀放在前面。现在，我们对以下问题感兴趣：字符串 $\tilde s$ 本身在这个列表中处于什么位置？
例如，考虑字符串 $S = {cabcab}$ ：
- $\tilde s_2 = {abcabcabca} …$
- $\tilde s_5 = {abcabcabca} …$
- $\tilde s_3 = {bcabcabcab} …$
- $\tilde s_6 = {bcabcabcab} …$
- $\tilde s_1 = {cabcabcabc} …$
- $\tilde s_4 = {cabcabcabc} …$
这里循环字符串 $\tilde s = \tilde S_1$ 位于第五位。
给您的是字符串 $s$ 。您的任务是找出循环字符串 $\tilde s$ 在所述顺序中的位置。
参考思路
先对原串求一遍Z-Function，然后枚举z[i]，跳lcp（即z[i]，也就是后缀 i 和后缀 0的lcp）做字符比较即可，复杂度 $O(n)$。
直接看代码可能会更好理解
参考代码
auto zFunction(const auto& s) {
int n = s.size();
std::vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r)
z[i] = std::min(z[i - l], r - i);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] > r)
l = i, r = i + z[i];
}
z[0] = n;
return z;
}
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
s += s;
auto z = zFunction(s);
int cnt = 1;
for (int i = 0; i < n; i++) {
cnt += (z[i] == 2 * n - i ? false : (s[z[i]] > s[i + z[i]]));
}
std::cout << cnt;
}
Suffix array
Step 1
A. Suffix Array - 1
SA数组 板子题，不讲
但由于 SA 码量略大，为不影响阅读，我先放个板子在这吧，后面的代码中的 SA 均指此板子。
struct SA {
int n;
std::vector<int> sa, rk, lc;
std::vector<std::vector<int>> st;
SA(std::string s) : n(s.size()), sa(n), rk(n), lc(n), st(std::__lg(n) + 1, std::vector<int>(n + 1)) {
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(),
[&](int a, int b) {
return s[a] < s[b];
});
rk[sa[0]] = 0;
for (int i = 1; i < n; i++) {
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
}
int k = 1;
std::vector<int> tmp, cnt(n);
tmp.reserve(n);
while (rk[sa[n - 1]] < n - 1) {
tmp.clear();
for (int i = 0; i < k; i++) {
tmp.push_back(n - k + i);
}
for (auto i : sa) {
if (i >= k) {
tmp.push_back(i - k);
}
}
std::fill(cnt.begin(), cnt.end(), 0);
for (int i = 0; i < n; i++) {
cnt[rk[i]]++;
}
for (int i = 1; i < n; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
sa[--cnt[rk[tmp[i]]]] = tmp[i];
}
std::swap(rk, tmp);
rk[sa[0]] = 0;
for (int i = 1; i < n; i++) {
rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
}
k *= 2;
}
for (int i = 0, j = 0; i < n; i++) {
if (rk[i] == 0) {
j = 0;
} else {
for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j]; ) {
j++;
}
lc[rk[i]] = j;
}
}
st[0] = lc;
for (int j = 0; j < std::__lg(n); j++) {
for (int i = 0, m = n - (1 << j + 1); i <= m; i++) {
st[j + 1][i] = std::min(st[j][i], st[j][i + (1 << j)]);
}
}
}
int lcp(int x, int y) {
if (x == y) return n - x;
x = rk[x]; y = rk[y];
if (x > y) std::swap(x, y);
++x;
int z = std::__lg(y - x + 1);
return std::min(st[z][x], st[z][y - (1 << z) + 1]);
}
};
Step 2
A. Suffix Array - 2
SA数组板子题，不讲
Step 3
A. Substring Search
题意
给定一个字符串 $t$ 和 $n$ 查询，每个查询都是一个字符串 $s_i$ 。对于每个请求，你都需要确定字符串 $s_i$ 是否作为子串出现在 $t$ 中。
参考思路
对原始串 t 求SA数组，然后每次询问在sa数组上二分出询问串的 rank，最后判断询问串是否存在即可。复杂度 $O(\sum|s|\log|t|)$
参考代码
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
SA sa(s);
int q;
std::cin >> q;
while (q--) {
std::string p;
std::cin >> p;
if (p.size() > s.size()) {
std::cout << "No\n";
continue;
}
auto check_low = [&](int j) -> bool {
for (int i = 0; i < std::min<int>(n - j, p.size()); i++) {
if (p[i] != s[j + i]) {
return s[j + i] < p[i];
}
}
return n - j <= p.size();
};
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (mid >= n || mid < 0) break;
if (check_low(sa.sa[mid])) {//s.substr(sa.sa[mid]) <= p
l = mid + 1;
} else {
r = mid - 1;
}
}
auto ck = [&](int i) -> bool {
if (i >= n || i < 0) {
return 0;
}
auto t = s.substr(sa.sa[i]);
if (t.size() < p.size() || t.substr(0, p.size()) != p) {
return 0;
} else {
return 1;
}
};
bool ans = 0;
for (int i = l - 1; i <= l; i++) ans |= ck(i);
std::cout << (ans ? "Yes" : "No") << "\n";
}
}
B. Counting Substrings
题意
给定一个字符串 $t$ 和 $n$ 查询，每个查询都是一个字符串 $s_i$ 。对于每个查询，你需要计算字符串 $s_i$ 作为子串出现在 $t$ 中的次数。
参考思路
我们直接在sa数组上分别二分出，第一个字典序大于询问串的位置 $i$，以及第一个字典序小于等于询问串的位置 $j$，那么答案就是 $i - j + 1$（差不多这个思路，具体细节自己品）
参考代码
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
SA sa(s);
int q;
std::cin >> q;
while (q--) {
std::string p;
std::cin >> p;
if (p.size() > s.size()) {
std::cout << "0\n";
continue;
}
auto check_lower = [&](int j) -> bool {
for (int i = 0; i < std::min<int>(n - j, p.size()); i++) {
if (p[i] != s[j + i]) {
return s[j + i] > p[i];
}
}
return n - j >= p.size();
};
auto check_upper = [&](int j) -> bool {
for (int i = 0; i < std::min<int>(n - j, p.size()); i++) {
if (p[i] != s[j + i]) {
return s[j + i] < p[i];
}
}
return n - j < p.size();
};
auto get_lower = [&]() -> int {
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (mid >= n || mid < 0) break;
if (check_lower(sa.sa[mid])) {//s.substr(sa.sa[mid]) >= p
r = mid - 1;
} else {
l = mid + 1;
}
}
return r + 1;
};
auto get_upper = [&]() -> int {
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (mid >= n || mid < 0) break;
if (check_upper(sa.sa[mid])) {//s.substr(sa.sa[mid]) <= p
l = mid + 1;
} else {
r = mid - 1;
}
}
return l - 1;
};
p.back()++;
int up = get_upper();
p.back()--;
int lo = get_lower();
std::cout << up - lo + 1 << "\n";
}
}
Step 4
A. Suffix Array and LCP
题意
为给定的字符串 $s$ 建立一个后缀数组，为每两个相邻的后缀找出最长公共前缀的长度。
参考思路
SA数组板子题，前面的板子里面的 lc 数组即为所求（下标从 1 开始）。
Step 5
A. Number of Different Substrings
题意
计算给定字符串 $s$ 的不同子串的个数。
参考思路
考虑求出SA数组中的lc数组。然后枚举 i，统计 $(n - sa[i]) - lc[i]$ 即可。
参考代码
void solve() {
std::string s;
std::cin >> s;
SA sa(s);
int n = s.size();
i64 ans = 0;
for (int i = 0; i < n; i++) {
ans += (n - sa.sa[i]) - sa.lc[i];
}
std::cout << ans;
}
B. Longest Common Substring
题意
找出两个给定字符串 $s$ 和 $t$ 的最长公共子串。
参考思路
考虑字符串拼接：$r = s + ‘#’ + t$，对拼接后的字符串求 SA数组，初始化 $ans$ 为空，最后从 $1$ 到 $n + m + 1$ 枚举下标，当 $lc[i] > |ans|$ ，且 $sa[i - 1]$ 和 $sa[i]$ 分别属于不同串时（即一个属于 s，一个属于 t）更新答案即可。复杂度 $O(n + m)$
参考代码
void solve() {
std::string s, t;
std::cin >> s >> t;
int n = s.size();
int m = t.size();
auto z = s;
z += '#';
z += t;
SA sa(z);
int mx = 0;
std::string ans;
auto get_len = [&](int i) -> int {
return n + 1 + m - sa.sa[i];
};
for (int i = 1; i <= n + m; i++) {
if (sa.lc[i] > ans.size() &&
(get_len(i) > m && get_len(i - 1) <= m ||
get_len(i) <= m && get_len(i - 1) > m)
) {
ans = z.substr(sa.sa[i], sa.lc[i]);
}
}
std::cout << ans;
}
C. Sorting Substrings
题意
给定字符串 $s$ 及其一组子串。子串由一对数字 $l_i,r_i$ 定义，即子串左端的位置和右端的位置。您需要按词典顺序对子串进行排序。如果子串等同于单词，则使用词对本身作为额外的排序键（即首先按 $l$ 进行比较，然后按 $r$ ）。
参考思路
考虑利用 SA数组 重载 sort 的 cmp 函数，利用 SA数组 快速求两后缀的 lcp的功能，快速跳过两后缀相同的部分，直接比较两后缀第一次出现不同的位置，即可实现 $O(1)$ 比较两子串字典序。复杂度 $O(|s|\log|s|)$
参考代码
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
SA sa(s);
int m;
std::cin >> m;
std::vector<std::pair<int, int>> a(m);
for (auto &[l, r] : a) {
std::cin >> l >> r;
l--; r--;
}
std::sort(a.begin(), a.end(), [&](const auto& i, const auto& j) {
int lcp = sa.lcp(i.first, j.first);
if (lcp >= std::min(i.second - i.first + 1, j.second - j.first + 1)
) {
if (i.second - i.first + 1 < j.second - j.first + 1) return true;
if (i.second - i.first + 1 == j.second - j.first + 1) {
return i.first < j.first;
}
return false;
}
return s[i.first + lcp] < s[j.first + lcp];
});
for (auto &[l, r] : a) {
std::cout << l + 1 << " " << r + 1 << "\n";
}
}
D. Borders
题意
如果字符串 $t$ 同时是字符串 $s$ 的后缀和前缀，那么它就是字符串 $s$ 的 border。例如，字符串 $abbabba$ 有三个 border： $abba$ 、 $a$ 和空字符串。
给定字符串 $s$ ，计算其所有子串的 border 总数。
参考思路
不难发现，任取两不同后缀 $i$，$j$，求出 $lcp$ 后，可以得到 $|lcp|$ 个不同子串，分别以 $s.substr(i, 1)，s.substr(i, 2)，…，s.substr(i, |lcp|)$ 为border，而不重地枚举出所有 $i$，$j$ 对（$i < j$），求 $lcp$，所求得的所有 border 恰好能遍历 s 的所有子串的所有 border。所以答案就是，$\sum_{i = 1}^{n - 1}\sum_{j = i + 1}^nlcp(i, j) = \sum_{i = 1}^{n - 1}\sum_{j = i + 1}^n\min(lc[i + 1], lc[i + 2],…,lc[j])$
考虑如何降低复杂度，由于区间min具有单调性，我们可以根据 lc 的值，构建小根堆的笛卡尔树，然后在笛卡尔树上 dfs 时，维护左右区间大小，累加贡献 $lsiz[now] * rsiz[now] * lc[now]$ 即可，时间复杂度 $O(n)$。
参考代码
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
SA sa(s);
std::vector<int> a;
for (int i = 1; i < n; i++) a.push_back(sa.lc[i]);
std::vector<int> lc(n - 1, -1), rc(n - 1, -1);
std::vector<int> stk;
for (int i = 0; i < n - 1; i++) {
while (stk.size() && a[i] < a[stk.back()]) {
rc[stk.back()] = lc[i];
lc[i] = stk.back();
stk.pop_back();
}
stk.push_back(i);
}
while (stk.size() > 1) {
int x = stk.back();
stk.pop_back();
rc[stk.back()] = x;
}
i64 ans = 1ll * n * (n + 1) / 2;
std::vector<int> lm(n - 1), rm(n - 1);
auto dfs = [&](auto&& self, int now) -> void {
lm[now] = rm[now] = now;
if (lc[now] != -1) {
self(self, lc[now]);
lm[now] = std::min(lm[now], lm[lc[now]]);
rm[now] = std::max(rm[now], rm[lc[now]]);
}
if (rc[now] != -1) {
self(self, rc[now]);
lm[now] = std::min(lm[now], lm[rc[now]]);
rm[now] = std::max(rm[now], rm[rc[now]]);
}
ans += 1ll * (now - lm[now] + 1) * (rm[now] - now + 1) * a[now];
};
if (n - 1) dfs(dfs, stk.back());
std::cout << ans;
}
E. Refrain
题意
考虑一个由 $n$ 个整数组成的数组，从 $1$ 到 $m$ 。如果数组中连续元素的长度与出现次数的乘积为最大值，则称该数组的一个子序列为反演。
给定一个数组，你的任务是找出它的反演。
参考思路
考虑将原数组当成字符串，求出原数组的 SA数组，不难发现，对sa数组中任意两不同后缀 $i$，$j$，从 $i$ 到 $j$ 的每个“子串”，前 $min(lc[i + 1], lc[i + 2], …, lc[j])$ 个元素均一一对应相等。
于是，我们可以求原数组的 SA数组，然后对 lc数组构建小根堆的笛卡尔树。最后在笛卡尔树上跑 dfs，当 $|ans| < (lsiz[now] + rsiz[now] + 1) * lc[now]$ 时更新答案即可，时间复杂度：$O(n)$。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
SA sa(a);
i64 ans = n;
int beg = 0, lcp = n;
std::vector<int> b;
for (int i = 1; i < n; i++) b.push_back(sa.lc[i]);
std::vector<int> lc(n - 1, -1), rc(n - 1, -1);
std::vector<int> stk;
for (int i = 0; i < n - 1; i++) {
while (stk.size() && b[i] < b[stk.back()]) {
rc[stk.back()] = lc[i];
lc[i] = stk.back();
stk.pop_back();
}
stk.push_back(i);
}
while (stk.size() > 1) {
int x = stk.back();
stk.pop_back();
rc[stk.back()] = x;
}
std::vector<int> lm(n - 1), rm(n - 1);
auto dfs = [&](auto&& self, int now) -> void {
lm[now] = rm[now] = now;
if (lc[now] != -1) {
self(self, lc[now]);
lm[now] = std::min(lm[now], lm[lc[now]]);
rm[now] = std::max(rm[now], rm[lc[now]]);
}
if (rc[now] != -1) {
self(self, rc[now]);
lm[now] = std::min(lm[now], lm[rc[now]]);
rm[now] = std::max(rm[now], rm[rc[now]]);
}
if (ans < 1ll * b[now] * (rm[now] - lm[now] + 2)) {
ans = 1ll * b[now] * (rm[now] - lm[now] + 2);
beg = sa.sa[now];
lcp = b[now];
}
};
if (n - 1) dfs(dfs, stk.back());
std::cout << ans << "\n";
std::cout << lcp << "\n";
for (int i = beg; i < beg + lcp; i++) {
std::cout << a[i] << " ";
}
}
F. Periodic Substring
题意
给定字符串 $s$ 。求最大整数 $k$ ，使得字符串 $s$ 中有一个非空子串是 $k$ 个相同字符串的拼接。
参考思路
先考虑暴力怎么做，自然我们可以想到枚举周期起点，枚举周期长度暴力check，但时间复杂度是 $O(n^3)$ 的。
对着样例具体分析，比方说 $aabaaabaaabaaabaab$，答案是 $4$，可以发现，$i = 0$ 号下标开始的后缀和 $j = 4$ 号下标开始的后缀，其 $lcp$ 长度是 $12$，而 $|lcp| / (j - i) + 1$ 就是答案 $4$。若我们枚举下标为 $i = 2$ 和 $j = 3$，算出来的为 $1$，比真正答案小。
由上述分析可知，答案即为 $\max_{i = 1}^{n - 1}\max_{j = i + 1}^n\min(lc[i + 1], lc[i + 2], …, lc[j]) / (j - i) + 1$。
考虑对 lc数组 构建笛卡尔树，我们知道，为了使得答案最大化， $i$ 和 $j$ 间的距离要尽可能小，所以在笛卡尔树上跑dfs时，可以进行启发式合并，维护每个节点左右子树的下标集合，然后在合并时更新答案 $ans = max(ans, lc[now] / (now - 左子树中离 now 最近的下标 + 1)，lc[now] / (右子树中离 now 最近的下标 - now + 1))$ 即可。
时间复杂度：$O(|s|\log|s|)$
参考代码
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
if (n == 1) {
std::cout << 1;
return;
}
SA sa(s);
int ans = 1;
std::vector<int> b;
for (int i = 1; i < n; i++) b.push_back(sa.lc[i]);
std::vector<int> lc(n - 1, -1), rc(n - 1, -1);
std::vector<int> stk;
for (int i = 0; i < n - 1; i++) {
while (stk.size() && b[i] < b[stk.back()]) {
rc[stk.back()] = lc[i];
lc[i] = stk.back();
stk.pop_back();
}
stk.push_back(i);
}
while (stk.size() > 1) {
int x = stk.back();
stk.pop_back();
rc[stk.back()] = x;
}
std::vector<std::set<int>> idx(n - 1);
auto insert = [&](int i, int index, int val) {
if (idx[i].size() == 0) idx[i].insert(index);
else {
auto [it, ok] = idx[i].insert(index);
if (ok) {
if (*it != *idx[i].begin()) {
ans = std::max(ans, val / (*it - *std::prev(it)) + 1);
}
if (*it != *idx[i].rbegin()) {
ans = std::max(ans, val / (*std::next(it) - *it) + 1);
}
}
}
};
auto dfs = [&](auto&& self, int now) -> void {//维护所有出现过的下标，如果出现过，那么跳过
if (lc[now] != -1) self(self, lc[now]);
if (rc[now] != -1) self(self, rc[now]);
if (lc[now] != -1 && rc[now] != -1) {
if (idx[lc[now]].size() > idx[rc[now]].size()) {
std::swap(idx[lc[now]], idx[rc[now]]);
}
std::swap(idx[now], idx[rc[now]]);
for (auto &index : idx[lc[now]]) {
insert(now, index, b[now]);
}
} else if (lc[now] != -1) {
std::swap(idx[now], idx[lc[now]]);
} else if (rc[now] != -1) {
std::swap(idx[now], idx[rc[now]]);
}
insert(now, sa.sa[now], b[now]);
insert(now, sa.sa[now + 1], b[now]);
};
dfs(dfs, stk[0]);
std::cout << ans << "\n";
}
Segment Tree, part 1
Step 1
A. Segment Tree for the Sum
题意
维护单点修改，区间求和的线段树。
参考思路
板子题，没有思路可言。
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
};
struct Info {
i64 sum = 0;
};
Info operator+(const Info &a, const Info &b) {
return Info{(a.sum + b.sum)};
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (auto &i : a) std::cin >> i.sum;
SGT<Info> sgt(a);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int p, x;
std::cin >> p >> x;
sgt.modify(p, Info{x});
} else {
int l, r;
std::cin >> l >> r;
std::cout << sgt.rangeQuery(l, r).sum << "\n";
}
}
}
B. Segment Tree for the Minimum
题意
维护单点修改，区间查询最小值的线段树。
参考思路
将线段树默认值初始化为无穷大，然后区间合并的函数改成 $\min(a, b)$即可。
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
};
struct Info {
i64 sum = 1e9;
};
Info operator+(const Info &a, const Info &b) {
return Info{std::min(a.sum, b.sum)};
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (auto &i : a) std::cin >> i.sum;
SGT<Info> sgt(a);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int p, x;
std::cin >> p >> x;
sgt.modify(p, Info{x});
} else {
int l, r;
std::cin >> l >> r;
std::cout << sgt.rangeQuery(l, r).sum << "\n";
}
}
}
C. Number of Minimums on a Segment
题意
维护单点修改，区间查询最小数，以及最小数的数量的线段树。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {
i64 mi = 1e9;//初始化区间min为inf
i64 cnt = 0;//初始化min的数量为空
};
Info operator+(const Info &a, const Info &b) {
Info c;
if (a.mi < b.mi) return a;
if (a.mi > b.mi) return b;
return Info{a.mi, a.cnt + b.cnt};
}
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
};
struct Info {
i64 mi = 1e9;
i64 cnt = 0;
};
Info operator+(const Info &a, const Info &b) {
Info c;
if (a.mi < b.mi) return a;
if (a.mi > b.mi) return b;
return Info{a.mi, a.cnt + b.cnt};
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (auto &i : a) (std::cin >> i.mi), i.cnt = 1;
SGT<Info> sgt(a);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int p, x;
std::cin >> p >> x;
sgt.modify(p, Info{x, 1});
} else {
int l, r;
std::cin >> l >> r;
auto z = sgt.rangeQuery(l, r);
std::cout << z.mi << " " << z.cnt << "\n";
}
}
}
Step 2
A. Segment with the Maximum Sum
题意
询问区间最大子段和。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {
i64 L = 0;
i64 R = 0;
i64 mx = 0;
i64 sum = 0;
};
Info operator+(const Info &a, const Info &b) {
Info c;
c.mx = std::max({a.mx, b.mx, a.R + b.L});
c.L = std::max(a.L, a.sum + b.L);
c.R = std::max(b.R, b.sum + a.R);
c.sum = a.sum + b.sum;
return c;
}
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
};
struct Info {
i64 L = 0;
i64 R = 0;
i64 mx = 0;
i64 sum = 0;
};
Info operator+(const Info &a, const Info &b) {
Info c;
c.mx = std::max({a.mx, b.mx, a.R + b.L});
c.L = std::max(a.L, a.sum + b.L);
c.R = std::max(b.R, b.sum + a.R);
c.sum = a.sum + b.sum;
return c;
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (auto &i : a) {
std::cin >> i.sum;
i.L = i.R = i.mx = std::max(0ll, i.sum);
}
SGT<Info> sgt(a);
std::cout << sgt.rangeQuery(0, n).mx << "\n";
while (m--) {
int p, x;
std::cin >> p >> x;
Info z;
z.sum = x;
z.L = z.R = z.mx = std::max(0, x);
sgt.modify(p, z);
std::cout << sgt.rangeQuery(0, n).mx << "\n";
}
}
B. K-th one
题意
给定一个01数组，实现单点值取反，区间查询第 k个1的下标的数据结构。
参考思路
考虑维护一个单点修改，区间求和的线段树，对于每次查询，二分出最小的下标 $p$，使得 $\sum_{i = 0}^p a[i] = k$ 即可。复杂度 $O(nlog^2n)$
参考代码
偷懒没写线段树，用的树状数组，知道怎么做就行。
template<typename T>
struct BIT {
std::vector<T> a;
int n;
BIT(int n_) {//下标从1开始
a.clear();
a.resize(n_ + 1);
n = n_;
}
BIT() {}
BIT(const BIT& bit) {//[可选] 复制bit（很少用）
n = bit.n;
a = bit.a;
}
T getsum(int x) {//获取[1, x]的和 O(logn)
T s = T();
while (x) {
s = s + a[x];
x -= (x &- x);
}
return s;
}
void modify(int x, T val) {//单点增加x处的值 O(logn)
while (x <= n) {
a[x] = a[x] + val;
x += (x &- x);
}
}
};
void solve() {
int n, m;
std::cin >> n >> m;
BIT<int> bit(n);
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
bit.modify(i + 1, x);
a[i] = x;
}
while (m--) {
int op, p;
std::cin >> op >> p;
if (op == 1) {
bit.modify(p + 1, -a[p]);
a[p] = 1 - a[p];
bit.modify(p + 1, a[p]);
} else {
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (bit.getsum(mid) >= p + 1) r = mid - 1;
else l = mid + 1;
}
std::cout << r << "\n";
}
}
}
C. First element at least X
题意
维护单点修改，查询最小的，使得 $a[j] \ge x$ 的下标 $j$。
参考思路
考虑维护区间max，然后进行线段树上二分即可。
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {// [original] range find first
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {// [practice] range find first
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F &&pred) {// [original] range find last
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F &&pred) {// [practice] range find last
return findLast(1, 0, n, l, r, pred);
}
};
struct Info {
int mx = -1;
};
Info operator+(const Info &a, const Info &b) {
return Info{std::max(a.mx, b.mx)};
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (auto &i : a) std::cin >> i.mx;
SGT<Info> sgt(a);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int p, x;
std::cin >> p >> x;
sgt.modify(p, Info{x});
} else {
int v;
std::cin >> v;
int z = sgt.findFirst(0, n,
[&](auto p) {
return p.mx >= v;
}
);
std::cout << z << "\n";
}
}
}
D. First element at least X - 2
题意
维护单点修改，区间查询最小的，使得 $a[j] \ge x$ 的下标 $j$。
参考思路
和上题没区别，维护区间max，进行线段树上二分即可。
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {// [original] range find first
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {// [practice] range find first
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F &&pred) {// [original] range find last
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F &&pred) {// [practice] range find last
return findLast(1, 0, n, l, r, pred);
}
};
struct Info {
int mx = -1;
};
Info operator+(const Info &a, const Info &b) {
return Info{std::max(a.mx, b.mx)};
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (auto &i : a) std::cin >> i.mx;
SGT<Info> sgt(a);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int p, x;
std::cin >> p >> x;
sgt.modify(p, Info{x});
} else {
int v, l;
std::cin >> v >> l;
int z = sgt.findFirst(l, n,
[&](auto p) {
return p.mx >= v;
}
);
std::cout << z << "\n";
}
}
}
Step 3
A. Inversions
题意
给定由 $n$ 个元素组成的排列 $p_i$ ，求每个 $i$，使得 $j < i$ 和 $p_j > p_i$ 的 $j$ 的个数.
参考思路
维护一个单点修改，区间查询和的数据结构，然后从小到大枚举每个数在原数组中的出现位置，询问 $[1, i]$ 的和，再修改 $a[i] = 1$ 即可，时间复杂度 $O(n\logn)$
参考代码
用的树状数组，用线段树也能实现相同的操作。
template<typename T>
struct BIT {
std::vector<T> a;
int n;
BIT(int n_) {//下标从1开始
a.clear();
a.resize(n_ + 1);
n = n_;
}
BIT() {}
BIT(const BIT& bit) {//[可选] 复制bit（很少用）
n = bit.n;
a = bit.a;
}
T getsum(int x) {//获取[1, x]的和 O(logn)
T s = 0;
while (x) {
s += a[x];
x -= (x &- x);
}
return s;
}
void modify(int x, T val) {//单点增加x处的值 O(logn)
while (x <= n) {
a[x] += val;
x += (x &- x);
}
}
};
void solve() {
int n;
std::cin >> n;
BIT<int> bit(n);
for (int i = 1; i <= n; i++) {
int x;
std::cin >> x;
std::cout << bit.getsum(n) - bit.getsum(x) << " ";
bit.modify(x, 1);
}
}
B. Inversions 2
题意
这道题是上一道题的反转版。有一个由 $n$ 个元素组成的排列 $p_i$ ，我们写下了每个 $i$ 的数字 $a_i$ 、 $j < i$ 和 $p_j > p_i$ 的数字 $j$ 。恢复给定的 $a_i$ 的原始排列。
参考思路
线段树维护一个01数组，实现单点修改，区间求和的操作。初始化数组全为 1，然后倒着遍历数组 a，每次查询 区间 $[1, n]$ 中，第一个使得 $\sum_{j = 1}^p = a[i]$ 的下标 p，保存到ans数组里（倒序保存），并更新 $a[p] = 0$。最后输出 ans 即可。
参考代码
这里我没写线段树 / 树状数组，用 pbds 偷鸡过了，想练线段树可以自己按相同逻辑实现。
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
namespace pb = __gnu_pbds;
template <class T, class Cmp = std::less<T>>
using RBT =
pb::tree<T, pb::null_type, Cmp, pb::rb_tree_tag,
pb::tree_order_statistics_node_update>;
/**
* order_of_key(x) -> 查询有多少元素比x小
* find_by_order(x) -> 查询第x个元素的迭代器
*/
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
std::vector<int> ans;
RBT<int, std::greater<int>> s;
for (int i = 1; i <= n; i++) {
s.insert(i);
}
for (int i = n - 1; i >= 0; i--) {
int x = *s.find_by_order(a[i]);
s.erase(x);
ans.push_back(x);
}
for (int i = n - 1; i >= 0; i--) {
std::cout << ans[i] << " ";
}
}
C. Nested Segments
题意
给定一个由 $2n$ 个数字组成的数组，其中从 1 到 $n$ 的每个数字都正好出现两次。如果数字 $y$ 的出现次数都在数字 $x$ 的出现次数之间，我们就说 $y$ 嵌套在 $x$ 中。求每个线段 $i$ 内部嵌套了多少个线段。
参考思路
考虑将所有相同的数字对提取出来，按照 {第一次出现的下标，第二次出现的下标，具体数字} 保存。再按照第一次出现的下标排序。维护一个单点修改，区间求和的数据结构，初始化数组a为0。从大到小枚举 {l, r, p}，查询 $[l, r]$ 作为 $ans[p]$ 的答案，并更新 $a[p]$ 为 $1$。最后输出答案即可。
参考代码
没用线段树，想用自己写。
template<typename T>
struct BIT {
std::vector<T> a;
int n;
BIT(int n_) {//下标从1开始
a.clear();
a.resize(n_ + 1);
n = n_;
}
BIT() {}
BIT(const BIT& bit) {//[可选] 复制bit（很少用）
n = bit.n;
a = bit.a;
}
T getsum(int x) {//获取[1, x]的和 O(logn)
T s = 0;
while (x) {
s += a[x];
x -= (x &- x);
}
return s;
}
void modify(int x, T val) {//单点增加x处的值 O(logn)
while (x <= n) {
a[x] += val;
x += (x &- x);
}
}
};
void solve() {
int n;
std::cin >> n;
std::map<int, std::vector<int>> pos;
for (int i = 1; i <= 2 * n; i++) {
int x;
std::cin >> x;
pos[x].push_back(i);
}
BIT<int> bit(2 * n);
std::vector<int> ans(n);
std::vector<std::array<int, 3>> p;
for (auto &[k, v] : pos) {
p.push_back({v[0], v[1], k});
}
std::sort(p.begin(), p.end());
for (int i = n - 1; i >= 0; i--) {
ans[p[i][2] - 1] = (bit.getsum(p[i][1]) - bit.getsum(p[i][0]));
bit.modify(p[i][1], 1);
}
for (auto &i : ans) std::cout << i << " ";
}
D. Intersecting Segments
题意
给定一个由 $2n$ 个数字组成的数组，其中从 1 到 $n$ 的每个数字都恰好出现两次。如果数字 $y$ 在数字 $x$ 出现的次数之间恰好出现一次，我们就说线段 $y$ 与线段 $x$ 相交。求每条线段 $i$ 与多少条线段相交。
参考思路
和上题类似，采用合适的顺序枚举，分别维护每个线段的左相交和右相交线段数量即可。具体看代码吧。
参考代码
template<typename T>
struct BIT {
std::vector<T> a;
int n;
BIT(int n_) {//下标从1开始
a.clear();
a.resize(n_ + 1);
n = n_;
}
BIT() {}
BIT(const BIT& bit) {//[可选] 复制bit（很少用）
n = bit.n;
a = bit.a;
}
T getsum(int x) {//获取[1, x]的和 O(logn)
T s = 0;
while (x) {
s += a[x];
x -= (x &- x);
}
return s;
}
void modify(int x, T val) {//单点增加x处的值 O(logn)
while (x <= n) {
a[x] += val;
x += (x &- x);
}
}
};
void solve() {
int n;
std::cin >> n;
std::map<int, std::vector<int>> pos;
for (int i = 1; i <= 2 * n; i++) {
int x;
std::cin >> x;
pos[x].push_back(i);
}
BIT<int> bit(2 * n);
std::vector<int> lin(n), rin(n);//相含数组
std::vector<std::array<int, 3>> p;
for (auto &[k, v] : pos) {
p.push_back({v[0], v[1], k});
}
std::sort(p.begin(), p.end());
for (int i = 0; i < n; i++) {
lin[p[i][2] - 1] = (bit.getsum(p[i][1]) - bit.getsum(p[i][0]));
bit.modify(p[i][1], 1);
}
bit = BIT<int>(2 * n);
std::sort(p.begin(), p.end(), [](auto a, auto b) {
return a[1] < b[1];
});
for (int i = n - 1; i >= 0; i--) {
rin[p[i][2] - 1] = (bit.getsum(p[i][1]) - bit.getsum(p[i][0]));
bit.modify(p[i][0], 1);
}
for (int i = 0; i < n; i++) {
std::cout << lin[i] + rin[i] << " ";
}
}
E. Addition to Segment
题意
维护区间加，单点查询的数据结构。
参考思路
考虑用单点修改，区间求和的数据结构，维护一个差分数组，每次修改时，只需要修改区间端点即可，查询时直接查询 $[1, p]$ 的和，即为答案。
参考代码
没写线段树，想练线段树自己写
template<typename T>
struct BIT {
std::vector<T> a;
int n;
BIT(int n_) {//下标从1开始
a.clear();
a.resize(n_ + 1);
n = n_;
}
BIT() {}
BIT(const BIT& bit) {//[可选] 复制bit（很少用）
n = bit.n;
a = bit.a;
}
T getsum(int x) {//获取[1, x]的和 O(logn)
T s = 0;
while (x) {
s += a[x];
x -= (x &- x);
}
return s;
}
void modify(int x, T val) {//单点增加x处的值 O(logn)
while (x <= n) {
a[x] += val;
x += (x &- x);
}
}
};
void solve() {
int n, m;
std::cin >> n >> m;
BIT<i64> bit(n + 1);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r, v;
std::cin >> l >> r >> v;
bit.modify(l + 1, v);
bit.modify(r + 1, -v);
} else {
int p;
std::cin >> p;
std::cout << bit.getsum(p + 1) << "\n";
}
}
}
Step 4
A. Sign alternation
题意
执行由 $n$ 元素 $a_1, a_2 … a_n$ 组成的数据结构，并进行以下操作：
- 为元素 $a_i$ 赋值 $j$ ；
- 在 $l$ 到 $r$ （含）（ $a_l - a_{l+1} + a_{l + 2} - … \pm a_{r}$ ）的范围内查找交替符号和。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {
i64 sum = 0;
int siz = 0;
};
Info operator+(const Info &a, const Info &b) {
Info c;
if (a.siz & 1) {
c.sum = a.sum - b.sum;
} else {
c.sum = a.sum + b.sum;
}
c.siz = a.siz + b.siz;
return c;
}
当然，还有一种方法是，开两个线段树，分别对奇偶位置维护区间和。
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
};
struct Info {
i64 sum = 0;
int siz = 0;
};
Info operator+(const Info &a, const Info &b) {
Info c;
if (a.siz & 1) {
c.sum = a.sum - b.sum;
} else {
c.sum = a.sum + b.sum;
}
c.siz = a.siz + b.siz;
return c;
}
void solve() {
int n;
std::cin >> n;
std::vector<Info> a(n);
for (auto &i : a) (std::cin >> i.sum), i.siz = 1;
SGT<Info> sgt(a);
int q;
std::cin >> q;
while (q--) {
int op;
std::cin >> op;
if (op == 0) {
int i, j;
std::cin >> i >> j;
sgt.modify(i - 1, Info{j, 1});
} else {
int l, r;
std::cin >> l >> r;
std::cout << sgt.rangeQuery(l - 1, r).sum << "\n";
}
}
}
B. Cryptography
题意
给定 $n$ 个大小为 $2\times 2$ 的矩阵 $A_1, A_2, …, A_n$ 。你需要计算几个查询的矩阵 $A_i, A_{i+1}, …, A_j$ 的乘积。所有计算均以 $r$ 为模来进行。
参考思路
矩阵乘积也具有结合律，所以可以用线段树维护。考虑如下维护的信息与信息间的合并设计：
struct Info {
i64 a[2][2] = {0};
Info() {
for (int i = 0; i < 2; i++) {
a[i][i] = 1;
}
}
};
Info operator+(const Info &a, const Info &b) {
Info c;
for (int i = 0; i < 2; i++) c.a[i][i] = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
(c.a[i][j] += (a.a[i][k] * b.a[k][j]) % M) %= M;
}
}
}
return c;
}
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
};
int M;
struct Info {
i64 a[2][2] = {0};
Info() {
for (int i = 0; i < 2; i++) {
a[i][i] = 1;
}
}
};
Info operator+(const Info &a, const Info &b) {
Info c;
for (int i = 0; i < 2; i++) c.a[i][i] = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
(c.a[i][j] += (a.a[i][k] * b.a[k][j]) % M) %= M;
}
}
}
return c;
}
void solve() {
int n, m;
std::cin >> M >> n >> m;
std::vector<Info> a(n);
for (auto &v : a) {
std::cin >> v.a[0][0] >> v.a[0][1] >> v.a[1][0] >> v.a[1][1];
v.a[0][0] %= M;
v.a[0][1] %= M;
v.a[1][0] %= M;
v.a[1][1] %= M;
}
SGT<Info> sgt(a);
while (m--) {
int l, r;
std::cin >> l >> r;
auto z = sgt.rangeQuery(l - 1, r);
std::cout << z.a[0][0] << " " << z.a[0][1] << "\n";
std::cout << z.a[1][0] << " " << z.a[1][1] << "\n";
std::cout << "\n";
}
}
C. Number of Inversions on Segment
题意
给定一个由小整数（ $1 \leq a_i \leq 40$ ）组成的数组 $a$ 。你需要建立一个数据结构来处理两种类型的查询：
- 查找段上的逆序对数。
- 修改数组元素。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {
std::vector<int> cnt, pre;
i64 inv = 0;
Info() : cnt(41), pre(41) {}
Info(std::vector<int> &cnt, std::vector<int> &pre, i64 inv) : cnt(cnt), pre(pre), inv(inv) {}
Info(int x) : cnt(41), pre(41) {
cnt[x]++;
for (int i = 1; i <= 40; i++) {
pre[i] = pre[i - 1] + cnt[i];
}
}
};
Info operator+(const Info &a, const Info &b) {
Info c;
c.inv = a.inv + b.inv;
for (int i = 1; i <= 40; i++) {
c.inv += 1ll * (a.pre[40] - a.pre[i]) * b.cnt[i];
}
c.cnt = a.cnt;
for (int i = 1; i <= 40; i++) {
c.cnt[i] += b.cnt[i];
c.pre[i] = c.pre[i - 1] + c.cnt[i];
}
return c;
}
时间复杂度：$O(40 n \log n)$
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
};
struct Info {
std::vector<int> cnt, pre;
i64 inv = 0;
Info() : cnt(41), pre(41) {}
Info(std::vector<int> &cnt, std::vector<int> &pre, i64 inv) : cnt(cnt), pre(pre), inv(inv) {}
Info(int x) : cnt(41), pre(41) {
cnt[x]++;
for (int i = 1; i <= 40; i++) {
pre[i] = pre[i - 1] + cnt[i];
}
}
};
Info operator+(const Info &a, const Info &b) {
Info c;
c.inv = a.inv + b.inv;
for (int i = 1; i <= 40; i++) {
c.inv += 1ll * (a.pre[40] - a.pre[i]) * b.cnt[i];
}
c.cnt = a.cnt;
for (int i = 1; i <= 40; i++) {
c.cnt[i] += b.cnt[i];
c.pre[i] = c.pre[i - 1] + c.cnt[i];
}
return c;
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (auto &i : a) {
int x;
std::cin >> x;
i = Info(x);
}
SGT<Info> sgt(a);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r;
std::cin >> l >> r;
std::cout << sgt.rangeQuery(l - 1, r).inv << "\n";
} else {
int p, x;
std::cin >> p >> x;
sgt.modify(p - 1, Info(x));
}
}
}
D. Number of Different on Segment
题意
给定一个由小整数（ $1 \leq a_i \leq 40$ ）组成的数组 $a$ 。你需要建立一个数据结构来处理两种类型的查询：
- 查找段上不同元素的数量、
- 更改数组中的元素。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {
int cnt[41] = {0};
int sum = 0;
};
Info operator+(const Info &a, const Info &b) {
Info c;
for (int i = 1; i <= 40; i++) {
c.cnt[i] = (a.cnt[i] | b.cnt[i]);
c.sum += c.cnt[i];
}
return c;
}
时间复杂度：$O(40 n \log n)$
参考代码
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
};
struct Info {
int cnt[41] = {0};
int sum = 0;
};
Info operator+(const Info &a, const Info &b) {
Info c;
for (int i = 1; i <= 40; i++) {
c.cnt[i] = (a.cnt[i] | b.cnt[i]);
c.sum += c.cnt[i];
}
return c;
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (auto &i : a) {
int x;
std::cin >> x;
i.cnt[x]++;
i.sum++;
}
SGT<Info> sgt(a);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r;
std::cin >> l >> r;
std::cout << sgt.rangeQuery(l - 1, r).sum << "\n";
} else {
int p, x;
std::cin >> p >> x;
Info z;
z.cnt[x]++;
z.sum++;
sgt.modify(p - 1, z);
}
}
}
E. Earthquakes
题意
一个城市是由 $n$ 个单元组成的序列，编号从 0 到 $n-1$ 。最初，所有单元格都是空的。然后，两种类型中的 $m$ 个事件依次发生：
- 在单元格 $i$ 中正在建造强度为 $h$ 的建筑物（如果该单元格中已有建筑物，则该建筑物将被拆除并被新建筑物取代）、
- 在 $l$ 到 $r-1$ 的区间内发生了威力为 $p$ 的地震，摧毁了所有强度不超过 $p$ 的建筑物。
你的任务是针对每次地震说出它将摧毁多少座建筑物。
参考思路
考虑维护一个单点修改，区间查询最小值的线段树。初始化 a 为 inf。每次查询时，不断查询区间中第一个最小值的位置，判断其是否小于等于 $p$，修改为 inf，并计数即可。时间复杂度 $O(n\log n)$
参考代码
constexpr int inf = 1e9 + 1;
//单点修改，区间查询。（可选功能：区间查找满足条件的第一个元素，区间查找满足条件的最后一个元素
template<class Info>// SGT template (from jiangly)
struct SGT {
int n;// size
std::vector<Info> info;// the info vector
SGT() : n(0) {}// default initialize
SGT(int n_, Info v_ = Info()) {// initialize with v
init(n_, v_);
}
template<class T>
SGT(std::vector<T> init_) {// initialize with a vector
init(init_);
}
void init(int n_, Info v_ = Info()) {// initialize with v
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {// initialize with a vector
n = init_.size();
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {// pull up the way of update
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {// [original] SGT point modify
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {// [practice] SGT point modify
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {// [original] SGT range query
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {// [practice] SGT range query
return rangeQuery(1, 0, n, l, r);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {// [original] range find first
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {// [practice] range find first
return findFirst(1, 0, n, l, r, pred);
}
//暴力删 min
int calc(int l, int r, int p) {
int sum = 0;
while (rangeQuery(l, r).mi <= p) {
int i = findFirst(l, r,
[&](Info &z) {
return z.mi <= p;
}
);
modify(i, Info{inf});
sum++;
}
return sum;
}
};
struct Info {
int mi = inf;
};
Info operator+(const Info &a, const Info &b) {
return Info{std::min(a.mi, b.mi)};
}
void solve() {
int n, m;
std::cin >> n >> m;
SGT<Info> sgt(n);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int p, x;
std::cin >> p >> x;
sgt.modify(p, Info{x});
} else {
int l, r, p;
std::cin >> l >> r >> p;
std::cout << sgt.calc(l, r, p) << "\n";
}
}
}
Segment Tree, part 2
Step 1
A. Addition to Segment
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 在从 $l$ 到 $r-1$ 的数段中添加数字 $v$ 、
- 查找元素 $i$ 的当前值。
参考思路
维护一个区间修改，单点查询的线段树即可。
参考代码
用的数组数组，想练线段树自己写。
template<typename T>
struct BIT {
std::vector<T> a;
int n;
BIT(int n_) {//下标从1开始
a.clear();
a.resize(n_ + 1);
n = n_;
}
BIT() {}
BIT(const BIT& bit) {//[可选] 复制bit（很少用）
n = bit.n;
a = bit.a;
}
T getsum(int x) {//获取[1, x]的和 O(logn)
T s = 0;
while (x) {
s += a[x];
x -= (x &- x);
}
return s;
}
void modify(int x, T val) {//单点增加x处的值 O(logn)
while (x <= n) {
a[x] += val;
x += (x &- x);
}
}
};
void solve() {
int n, m;
std::cin >> n >> m;
BIT<i64> bit(n + 1);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r, v;
std::cin >> l >> r >> v;
bit.modify(l + 1, v);
bit.modify(r + 1, -v);
} else {
int p;
std::cin >> p;
std::cout << bit.getsum(p + 1) << "\n";
}
}
}
B. Applying MAX to Segment
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 对于从 $l$ 到 $r-1$ 的所有 $i$ 执行 $a_i = \max(a_i, v)$ 操作、
- 查找元素 $i$ 的当前值。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
int mx;
Info(int mx = 0) : mx(mx) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(std::max(mx, b.mx));
}
};
struct Tag {//Tag信息
int v = 0;
Tag(int v = 0) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(std::max(v, b.v));
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
return Info(std::max(a.mx, b.v));
}
参考代码
template<typename Info, typename Tag>
struct SGT {
#define lson (p<<1)
#define rson (p<<1|1)
std::vector<Info> ans;
std::vector<Tag> tag;
int n;
SGT() : n(0) {}
SGT(int n, Info v = Info()) {
init(std::vector<Info>(n, v));
}
SGT(std::vector<Info> a) {
init(a);
}
void init(std::vector<Info> a) {
n = a.size();
ans.resize(4 << std::__lg(n));
tag.resize(4 << std::__lg(n));
auto build = [&](auto&& self, int p, int l, int r) -> void {
if (r - l == 1) {
ans[p] = a[l];
return;
}
int m = (l + r) >> 1;
self(self, lson, l, m);
self(self, rson, m, r);
pushup(p);
};
build(build, 1, 0, n);
}
void pushup(int p) {
ans[p] = ans[lson] + ans[rson];
}
void pushdown(int p, int l, int r) {
int m = (l + r) / 2;
ans[lson] = ans[lson] + tag[p];
tag[lson] = tag[lson] + tag[p];
ans[rson] = ans[rson] + tag[p];
tag[rson] = tag[rson] + tag[p];
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, int y, Tag k) {//区间修改
if (x <= l && r <= y) {
ans[p] = ans[p] + k;
tag[p] = tag[p] + k;
return;
}
pushdown(p, l, r);
int m = (l + r) >> 1;
if (x < m) modify(lson, l, m, x, y, k);
if (y > m) modify(rson, m, r, x, y, k);
pushup(p);
}
void modify(int l, int r, Tag k) {// [可选]
if (l == r) return;//
assert(l < r && l >= 0 && r <= n);
modify(1, 0, n, l, r, k);
}
Info query(int p, int l, int r, int x, int y) {//区间查询
if (x <= l && r <= y) return ans[p];
Info res;
pushdown(p, l, r);
int m = (l + r) >> 1;
if (x < m) res = res + query(lson, l, m, x, y);
if (y > m) res = res + query(rson, m, r, x, y);
return res;
}
Info query(int l, int r) { // [可选]
if (l == r) return Info();//
assert(l < r && l >= 0 && r <= n);
return query(1, 0, n, l, r);
}
#undef lson
#undef rson
};
struct Info {//信息
int mx;
Info(int mx = 0) : mx(mx) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(std::max(mx, b.mx));
}
};
struct Tag {//Tag信息
int v = 0;
Tag(int v = 0) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(std::max(v, b.v));
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
return Info(std::max(a.mx, b.v));
}
void solve() {
int n, m;
std::cin >> n >> m;
SGT<Info, Tag> sgt(n);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r, v;
std::cin >> l >> r >> v;
sgt.modify(l, r, Tag(v));
} else {
int p;
std::cin >> p;
std::cout << sgt.query(p, p + 1).mx << "\n";
}
}
}
C. Assignment to Segment
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 为从 $l$ 到 $r-1$ 段上的所有元素赋值 $v$ 、
- 查找元素 $i$ 的当前值。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
int v;
Info(int v = 0) : v(v) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(v + b.v);
}
};
struct Tag {//Tag信息
int v = -1;
Tag(int v = -1) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
if (b.v == -1) return Tag(v);
return b;
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
if (b.v == -1) return a;
return Info(b.v);
}
参考代码
template<typename Info, typename Tag>
struct SGT {
#define lson (p<<1)
#define rson (p<<1|1)
std::vector<Info> ans;
std::vector<Tag> tag;
int n;
SGT() : n(0) {}
SGT(int n, Info v = Info()) {
init(std::vector<Info>(n, v));
}
SGT(std::vector<Info> a) {
init(a);
}
void init(std::vector<Info> a) {
n = a.size();
ans.resize(4 << std::__lg(n));
tag.resize(4 << std::__lg(n));
auto build = [&](auto&& self, int p, int l, int r) -> void {
if (r - l == 1) {
ans[p] = a[l];
return;
}
int m = (l + r) >> 1;
self(self, lson, l, m);
self(self, rson, m, r);
pushup(p);
};
build(build, 1, 0, n);
}
void pushup(int p) {
ans[p] = ans[lson] + ans[rson];
}
void pushdown(int p, int l, int r) {
int m = (l + r) / 2;
ans[lson] = ans[lson] + tag[p];
tag[lson] = tag[lson] + tag[p];
ans[rson] = ans[rson] + tag[p];
tag[rson] = tag[rson] + tag[p];
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, int y, Tag k) {//区间修改
if (x <= l && r <= y) {
ans[p] = ans[p] + k;
tag[p] = tag[p] + k;
return;
}
pushdown(p, l, r);
int m = (l + r) >> 1;
if (x < m) modify(lson, l, m, x, y, k);
if (y > m) modify(rson, m, r, x, y, k);
pushup(p);
}
void modify(int l, int r, Tag k) {// [可选]
if (l == r) return;//
//assert(l < r && l >= 0 && r <= n);//可选
modify(1, 0, n, l, r, k);
}
Info query(int p, int l, int r, int x, int y) {//区间查询
if (x <= l && r <= y) return ans[p];
Info res;
pushdown(p, l, r);
int m = (l + r) >> 1;
if (x < m) res = res + query(lson, l, m, x, y);
if (y > m) res = res + query(rson, m, r, x, y);
return res;
}
Info query(int l, int r) { // [可选]
if (l == r) return Info();//
//assert(l < r && l >= 0 && r <= n);//可选
return query(1, 0, n, l, r);
}
#undef lson
#undef rson
void show() {
std::cout << "=======================\n";
for (int i = 0; i < n; i++) {
std::cout << query(i, i + 1).v << " ";
}
std::cout << "\n";
}
};
struct Info {//信息
int v;
Info(int v = 0) : v(v) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(v + b.v);
}
};
struct Tag {//Tag信息
int v = -1;
Tag(int v = -1) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
if (b.v == -1) return Tag(v);
return b;
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
if (b.v == -1) return a;
return Info(b.v);
}
void solve() {
int n, m;
std::cin >> n >> m;
SGT<Info, Tag> sgt(n);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r, v;
std::cin >> l >> r >> v;
sgt.modify(l, r, Tag(v));
} else {
int p;
std::cin >> p ;
std::cout << sgt.query(p, p + 1).v << "\n";
}
}
}
Step 2
出于码量考虑，该节只给出 Info 和 Tag 的设计，具体实现请自己补充完整。
A. Addition and Minimum
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 将 $v$ 添加到从 $l$ 到 $r-1$ 的线段上、
- 查找从 $l$ 到 $r-1$ 的线段上的最小值。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
i64 mi;
Info(i64 mi = 2e18) : mi(mi) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(std::min(mi, b.mi));
}
};
struct Tag {//Tag信息
i64 v;
Tag(i64 v = 0) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(v + b.v);
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {
return Info(a.mi + b.v);
}
B. Multiplication and Sum
题意
有一个由 $n$ 个元素组成的数组，最初填的是 1。你需要编写一个数据结构来处理两种类型的查询：
- 用数字 $v$ 乘从 $l$ 到 $r-1$ 部分的所有元素、
- 求从 $l$ 到 $r-1$ 的线段上的总和。
这两个运算都以 $10^9+7$ 为模来进行。
参考思路
考虑如下维护的信息与信息间的合并设计：
constexpr int M = 1e9 + 7;
struct Info {//信息
int sum;
Info(int sum = 0) : sum(sum) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info((sum + b.sum) % M);
}
};
struct Tag {//Tag信息
int v;
Tag(int v = 1) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(1ll * v * b.v % M);
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {
return Info((1ll * a.sum * b.v) % M);
}
C. Bitwise OR and AND
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 对从 $l$ 到 $r-1$ 的所有元素执行 $a_i = a_i | v$ （按位 OR）操作
- 查找从 $l$ 到 $r-1$ 范围内元素的位操作 AND。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
int sum;
Info(int sum = (1 << 30) - 1) : sum(sum) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(sum & b.sum);
}
};
struct Tag {//Tag信息
int v;
Tag(int v = 0) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(v | b.v);
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {
return Info(a.sum | b.v);
}
D. Addition and Sum
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 将 $v$ 添加到从 $l$ 到 $r-1$ 的数据段中、
- 求从 $l$ 到 $r-1$ 的线段上的和。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
i64 sum;
int siz;
Info(i64 sum = 0, int siz = 0) : sum(sum), siz(siz) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(sum + b.sum, siz + b.siz);
}
};
struct Tag {//Tag信息
i64 v;
Tag(i64 v = 0) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(v + b.v);
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {
return Info(a.sum + a.siz * b.v, a.siz);
}
E. Assignment and Minimum
题意
有一个由 $n$ 元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 为从 $l$ 到 $r-1$ 的线段上的所有元素赋值 $v$ 、
- 查找从 $l$ 到 $r-1$ 的线段上的最小值。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
i64 mi;
Info(i64 mi = 1e9 + 1) : mi(mi) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(std::min(mi, b.mi));
}
};
struct Tag {//Tag信息
i64 v;
Tag(i64 v = -1) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
if (b.v == -1) return Tag(v);
return b;
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
if (b.v == -1) return a;
return Info(b.v);
}
F. Assignment and Sum
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 为从 $l$ 到 $r-1$ 段的所有元素赋值 $v$ 、
- 求从 $l$ 到 $r-1$ 的线段上的总和。
参考思路
struct Info {//信息
i64 sum;
int siz;
Info(i64 sum = 0, int siz = 0) : sum(sum), siz(siz) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(sum + b.sum, siz + b.siz);
}
};
struct Tag {//Tag信息
i64 v;
Tag(i64 v = -1) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
if (b.v == -1) return Tag(v);
return b;
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
if (b.v == -1) return a;
return Info(b.v * a.siz, a.siz);
}
Step 3
A. Assignment and Maximal Segment
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 为从 $l$ 到 $r-1$ 的线段上的所有元素赋值 $v$ 、
- 找出总和最大的线段。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
i64 ans;
i64 L, R;
i64 sum;
int siz;
Info(i64 ans = 0, i64 L = 0, i64 R = 0, i64 sum = 0, int siz = 0)
: ans(ans), L(L), R(R), sum(sum), siz(siz) {}
Info operator+(const Info& b) const {//信息直接合并方式
Info c;
c.ans = std::max({ans, b.ans, R + b.L});
c.R = std::max(b.R, R + b.sum);
c.L = std::max(L, sum + b.L);
c.sum = sum + b.sum;
c.siz = siz + b.siz;
return c;
}
};
struct Tag {//Tag信息
i64 active;
int v;
Tag(i64 active = 0, int v = 0) : active(active), v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
if (b.active == 0) return Tag(active, v);
return b;
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
if (b.active == 0) return a;
Info c;
c.sum = 1ll * a.siz * b.v;
c.ans = c.L = c.R = std::max(0ll, c.sum);
c.siz = a.siz;
return c;
}
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
SGT<Info, Tag> sgt(n, Info(0 ,0 ,0 ,0, 1));
while (m--) {
int l, r, v;
std::cin >> l >> r >> v;
sgt.modify(l, r, Tag(1, v));
std::cout << sgt.query(0, n).ans << "\n";
}
}
B. Inverse and K-th one
题意
有一个 $n$ 布尔数组，初始值为零。您需要编写一个数据结构来处理两种类型的查询：
- 将 $l$ 至 $r-1$ 段中所有元素的值改为相反值、
- 找到 $k$ /-1的索引。
参考思路
维护区间反转，区间求和的数据结构，然后二分区间端点即可。
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
int one;
int zer;
Info(int one = 0, int zer = 0) : one(one), zer(zer) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(one + b.one, zer + b.zer);
}
};
struct Tag {//Tag信息
int rev;
Tag(int rev = 0) : rev(rev) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(rev ^ b.rev);
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {
if (!b.rev) return a;
return Info(a.zer, a.one);
}
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
SGT<Info, Tag> sgt(n, Info(0, 1));
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r;
std::cin >> l >> r;
sgt.modify(l, r, Tag(1));
} else {
int k;
std::cin >> k;
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (sgt.query(0, mid + 1).one >= k + 1) r = mid - 1;
else l = mid + 1;
}
std::cout << r + 1 << "\n";
}
}
}
C. Addition and First element at least X
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理两种类型的查询：
- 将 $v$ 添加到从 $l$ 到 $r-1$ 的线段上的所有元素、
- 找出最小索引 $j$ ，使得 $j \ge l$ 和 $a[j] \ge x$ .
参考思路
维护区间加，区间求最大值的线段树，询问时进行线段树上二分即可。
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
i64 mx;
Info(i64 mx = 0) : mx(mx) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(std::max(mx, b.mx));
}
};
struct Tag {//Tag信息
i64 v;
Tag(i64 v = 0) : v(v) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(v + b.v);
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {
return Info(a.mx + b.v);
}
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
SGT<Info, Tag> sgt(n, Info(0));
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r, v;
std::cin >> l >> r >> v;
sgt.modify(l, r, Tag(v));
} else {
int x, l;
std::cin >> x >> l;
std::cout << sgt.findFirst(l, n,
[&](Info &p) {
return p.mx >= x;
}
) << "\n";
}
}
}
Step 4
A. Assignment, Addition, and Sum
题意
有一个由 $n$ 个元素组成的数组，初始填充为零。你需要编写一个数据结构来处理三种类型的查询：
- 为从 $l$ 到 $r-1$ 段上的所有元素赋值 $v$ 、
- 将 $v$ 添加到从 $l$ 到 $r-1$ 线段上的所有元素、
- 求从 $l$ 到 $r-1$ 的线段上的和。
参考思路
维护多个Tag的线段树。
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
i64 sum;
int siz;
Info(i64 sum = 0, int siz = 0) : sum(sum), siz(siz) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(sum + b.sum, siz + b.siz);
}
};
struct Tag {//Tag信息
i64 add;
i64 chg;
Tag(i64 add = 0, i64 chg = -1) : add(add), chg(chg) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
if (b.chg != -1) return b;
if (chg == -1) return Tag(add + b.add, -1);
return Tag(0, chg + b.add);
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
if (b.chg == -1) return Info(a.sum + a.siz * b.add, a.siz);
return Info(a.siz * b.chg, a.siz);
}
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
SGT<Info, Tag> sgt(n, Info(0, 1));
while (m--) {
int op, l, r;
std::cin >> op >> l >> r;
if (op == 1) {
int v;
std::cin >> v;
sgt.modify(l, r, Tag(0, v));
} else if (op == 2) {
int v;
std::cin >> v;
sgt.modify(l, r, Tag(v, -1));
} else {
std::cout << sgt.query(l, r).sum << "\n";
}
}
}
B. Add Arithmetic Progression On Segment
题意
给你一个数组 $x$ ，由等于 $0$ 的 $n$ 个元素和两种类型的 $m$ 个查询组成：
- 为一个数段添加算术级数：查询用四个整数 $l, r, a, d$ 来描述–每个 $l \le i \le r$ 都要执行 $x_i += a + d \cdot (i - l)$ ；
- 打印给定元素的当前值。
参考思路
没法用高度封装性的线段树了，考虑如下信息维护，与 pushdown 和 modify 函数设计：
std::vector<i64> sum, k, d;
void pushdown(int p, int l, int r) {
int m = (l + r) / 2;
//左儿子下传lazy
sum[lson] += k[p] * (m - l) + d[p] * (m - l) * (m - l - 1) / 2;
k[lson] += k[p];
d[lson] += d[p];
i64 k_ = k[p] + (m - l) * d[p];//首项
sum[rson] += (k_ + k_ + d[p] * (r - m - 1)) * (r - m) / 2;
k[rson] += k_;
d[rson] += d[p];
k[p] = d[p] = 0;
}
void modify(int p, int l, int r, int x, int y, i64 k_, i64 d_) {//区间修改
if (x <= l && r <= y) {
i64 k__ = k_ + (l - x) * d_;
sum[p] += k__ * (r - l) + d_ * (r - l) * (r - l - 1) / 2;
k[p] += k__;
d[p] += d_;
return;
}
pushdown(p, l, r);
int m = (l + r) >> 1;
if (x < m) modify(lson, l, m, x, y, k_, d_);
if (y > m) modify(rson, m, r, x, y, k_, d_);
pushup(p);
}
参考代码
#define lson (p<<1)
#define rson (p<<1|1)
std::vector<i64> sum, k, d;
int n;
void pushup(int p) {
sum[p] = sum[lson] + sum[rson];
}
template<typename T>
void init(std::vector<T> a) {
n = a.size();
sum.resize(4 << std::__lg(n));
k.resize(4 << std::__lg(n));
d.resize(4 << std::__lg(n));
}
void pushdown(int p, int l, int r) {
int m = (l + r) / 2;
//左儿子下传lazy
sum[lson] += k[p] * (m - l) + d[p] * (m - l) * (m - l - 1) / 2;
k[lson] += k[p];
d[lson] += d[p];
i64 k_ = k[p] + (m - l) * d[p];//首项
sum[rson] += (k_ + k_ + d[p] * (r - m - 1)) * (r - m) / 2;
k[rson] += k_;
d[rson] += d[p];
k[p] = d[p] = 0;
}
void modify(int p, int l, int r, int x, int y, i64 k_, i64 d_) {//区间修改
if (x <= l && r <= y) {
i64 k__ = k_ + (l - x) * d_;
sum[p] += k__ * (r - l) + d_ * (r - l) * (r - l - 1) / 2;
k[p] += k__;
d[p] += d_;
return;
}
pushdown(p, l, r);
int m = (l + r) >> 1;
if (x < m) modify(lson, l, m, x, y, k_, d_);
if (y > m) modify(rson, m, r, x, y, k_, d_);
pushup(p);
}
void modify(int l, int r, i64 k, i64 d) {// [可选]
if (l == r) return;//
assert(l < r && l >= 0 && r <= n);
modify(1, 0, n, l, r, k, d);
}
i64 query(int p, int l, int r, int x, int y) {//区间查询
if (x <= l && r <= y) return sum[p];
i64 res = 0;
pushdown(p, l, r);
int m = (l + r) >> 1;
if (x < m) res = res + query(lson, l, m, x, y);
if (y > m) res = res + query(rson, m, r, x, y);
return res;
}
i64 query(int l, int r) { // [可选]
if (l == r) return 0;//
assert(l < r && l >= 0 && r <= n);
return query(1, 0, n, l, r);
}
#undef lson
#undef rson
void show() {
std::cout << "=======================\n";
for (int i = 0; i < n; i++) {
std::cout << query(i, i + 1) << " ";
}
std::cout << "\n";
}
void solve() {
int n, m;
std::cin >> n >> m;
init(std::vector<int>(n, 0));
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r, a, d;
std::cin >> l >> r >> a >> d;
modify(l - 1, r, a, d);
} else {
int p;
std::cin >> p;
std::cout << query(p - 1, p) << "\n";
}
}
}
C. Painter
题意
意大利抽象艺术家 F. Mandarino 开始对绘制一维黑白画感兴趣。他试图找到画面中黑色部分的最佳位置和数量。为此，他在线条上花费了白段和黑段，在每次操作之后，他都想知道最终画面中黑色段的数量及其总长度。
最初，线条是白色的。您的任务是编写一个程序，在每次操作后输出艺术家感兴趣的数据。
参考思路
struct Info {//信息
int cnt, sum, siz;
bool L, R;//黑色段是否挨着左边和右边
Info(int cnt = 0, int sum = 0, int siz = 0, bool L = 0, bool R = 0) : cnt(cnt), sum(sum), siz(siz), L(L), R(R) {}
Info operator+(const Info& b) const {//信息直接合并方式
Info c;
c.L = L;
c.R = b.R;
c.cnt = cnt + b.cnt - (R & b.L);
c.siz = siz + b.siz;
c.sum = sum + b.sum;
return c;
}
};
struct Tag {//Tag信息
int chg;
Tag(int chg = -1) : chg(chg) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
if (b.chg != -1) return b;
return Tag(chg);
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
if (b.chg == -1) return a;
return Info(b.chg, a.siz * b.chg, a.siz, b.chg, b.chg);
}
参考代码
void solve() {
int n;
std::cin >> n;
SGT<Info, Tag> sgt(1e6, Info(0, 0, 1, 0, 0));
while (n--) {
char c;
int x, l;
std::cin >> c >> x >> l;
x += 5e5;
sgt.modify(x, x + l, Tag(c == 'B'));
auto z = sgt.query(0, 1e6);
std::cout << z.cnt << " " << z.sum << "\n";
}
}
这里提供一种不用线段树的做法（据说就是珂朵莉树？）
void solve0() {
int n;
std::cin >> n;
auto cmp = [](const auto& a, const auto& b) -> auto {
return a.second < b.first;
};
std::set<std::pair<int, int>, decltype(cmp)> s(cmp);
i64 cnt = 0;
auto insert = [&](int l, int r) {
if (l > r) return;
auto it = s.find({l - 1, r + 1});
while (it != s.end()) {
if (it->first > r + 1) break;
auto [ll, rr] = *it;
it++; s.erase(std::prev(it));
cnt -= rr - ll + 1;
l = std::min(l, ll);
r = std::max(r, rr);
}
s.insert({l, r});
cnt += r - l + 1;
};
auto erase = [&](int l, int r) {
if (l > r) return;
auto it = s.find({l, r});
while (it != s.end()) {
if (it->first > r) break;
auto [ll, rr] = *it;
it++; s.erase(std::prev(it));
cnt -= rr - ll + 1;
insert(ll, l - 1);
insert(r + 1, rr);
}
};
while (n--) {
char op;
int l, x;
std::cin >> op >> l >> x;
int r = l + x - 1;
if (op == 'W') {
erase(l, r);
} else {
insert(l, r);
}
std::cout << s.size() << " " << cnt << "\n";
}
}
D. Problem About Weighted Sum
题意
在这个问题中，你要回答关于给定数组的加权和的查询。从形式上看，你将得到一个长度为 $n$ 的数组 $a[1 \dots n]$ 。你要回答两种类型的查询：
- 分段变化：给定三个整数 $l, r, d$ ，将 $d$ 添加到数组的每个元素 $i$ 中，使得 $l \le i \le r$ 、
- 计算加权和：给定两个整数 $l, r$ ，计算并打印 $a[l] \cdot 1 + a[l + 1] \cdot 2 + \dots \ a[r] \cdot (r - l + 1)$ 。
参考思路
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
i64 sum, wsum;
int siz;
Info(i64 sum = 0, i64 wsum = 0, int siz = 0)
: sum(sum), wsum(wsum), siz(siz) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(
sum + b.sum,
wsum + siz * b.sum + b.wsum,
siz + b.siz
);
}
};
struct Tag {//Tag信息
int d = 0;
Tag(int d = 0) : d(d) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(d + b.d);
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {
return Info(
a.sum + a.siz * b.d,
a.wsum + 1ll * a.siz * (a.siz + 1) / 2 * b.d,
a.siz
);
}
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (auto &v : a) {
std::cin >> v.sum;
v.wsum = v.sum;
v.siz = 1;
}
SGT<Info, Tag> sgt(a);
while (m--) {
int op, l, r;
std::cin >> op >> l >> r;
if (op == 1) {
int d;
std::cin >> d;
sgt.modify(l - 1, r, Tag(d));
} else {
std::cout << sgt.query(l - 1, r).wsum << "\n";
}
}
}
E. Wall
题意
这是 2014 年国际信息学奥林匹克竞赛（IOI）中的一道难题。尝试使用线段树来解决它！
建嘉正在用大小相同的砖块堆砌一堵墙。这堵墙由 $n$ 列砖组成，从左到右编号为 $0$ 至 $(n - 1)$ 。这些砖柱可能有不同的高度。柱子的高度就是其中砖块的数量。
建甲砌墙的过程如下。一开始，任何一列都没有砖块。然后，“健嘉 “会经历 $k$ 个添加或移除砖块的阶段。当所有 $k$ 个阶段都完成后，建造过程结束。在每个阶段中，“佳佳 “都会得到一系列连续的砖柱和高度 $h$ ，并执行以下步骤：
- 在加砖阶段，“佳佳 “会在给定范围内的砖块少于 $h$ 的柱子上加砖块，这样这些柱子就正好有 $h$ 块砖块。他不对拥有 $h$ 或更多砖块的列做任何操作。
- 在删除阶段，贾健从给定范围内有多于 $h$ 块砖的列中删除砖块，使它们正好有 $h$ 块砖。而对于砖块数少于或等于 $h$ 的列，他什么也不做。
你的任务是确定墙的最终形状。
参考思路
考虑维护一个线段树，Tag 维护区间合法的最小最大值，Info 维护每个点的高度值，如果 Info 代表的值小于 Tag 维护的最小值，那么直接将 Info 代表的值设置为这个最小值；如果 Info 代表的值大于 Tag 维护的最大值，那么直接将 Info 代表的值设置为这个最大值；否则不做操作。
而 Tag 对 Tag 的更新也类似，指需要对原 Tag 的两端分别用新 Tag，按照上述方式，分别“夹”一下即可。
考虑如下维护的信息与信息间的合并设计：
struct Info {//信息
i64 v;
Info(i64 v = 0) : v(v) {}
Info operator+(const Info& b) const {//信息直接合并方式
return b;
}
};
struct Tag {//Tag信息
i64 L, R;
Tag(i64 L = -1e9, i64 R = 1e9) : L(L), R(R) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
return Tag(std::clamp(L, b.L, b.R), std::clamp(R, b.L, b.R));
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {
return Info(std::clamp(a.v, b.L, b.R));
}
其中 clamp 恰好就能实现上述 “夹” 的操作。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n, Info(0));
SGT<Info, Tag> sgt(a);
while (m--) {
int op, l, r, h;
std::cin >> op >> l >> r >> h;
if (op == 1) {//add，将低于 h 的置为 h
sgt.modify(l, r + 1, Tag(h, 1e9));
} else {
sgt.modify(l, r + 1, Tag(-1e9, h));
}
}
for (int i = 0; i < n; i++) {
std::cout << sgt.query(i, i + 1).v << "\n";
}
}
F. Mountain
题意
这是 IOI 2005 中的一个问题，也是用线段树解决的
山地游乐园开设了一个全新的模拟过山车。模拟轨道由 $n$ 根端对端连接的轨道组成，第一根轨道的起点固定在高程 0 处。操作员 Byteman 可以通过调整若干连续轨道的高程变化来随意重新配置轨道。其他轨道的高程变化不受影响。每次调整轨道时，后面的轨道都会根据需要升高或降低，以连接轨道，同时将起点保持在标高 0 处。
每次启动时，都会以足够的能量将轿厢发射至高度 $h$ 。也就是说，只要轨道的高度不超过 $h$ ，只要没有到达轨道的终点，小车就会继续行驶。
给定当天所有的乘车记录和轨道配置变化，计算每次乘车时小车停止前所经过的轨道数。
模拟器内部将轨道表示为 $n$ 升高变化 $d_i$ 的序列。最初轨道是水平的，即所有 $i$ 都是 $d_i = 0$ 。
在一天中，运行和重新配置是交错进行的。每次重新配置由三个数字组成： $a$ 、 $b$ 和 $D$ 。需要调整的区段包括 $a$ 至 $b$ （含）的轨道。区段中每条轨道的高程变化设置为 $D$ 。
每个轨道都由一个数字 $h$ 指定，即轨道车可以达到的最大高度。
参考思路
细节非常多的题，整理完题意后，其实就是让你维护一个差分数组，实现对差分数组进行区间修改，查询第一次 $[1, p]$ 大于 $h$ 的下标 $p$，那么我们按照题意设计 Info 和 Tag 即可。
注意，题目的 $n$ 高达 $10^9$，但是只有最多 $10^5$ 次操作。所以要先进行离散化分块，询问时在检查出的块内二分，这点比较麻烦。
参考代码
#define int i64
constexpr int inf = 1e9 + 1;
struct Info {//信息
int sum, presummax;
int siz;
Info(int sum = 0, int presummax = 0, int siz = 0)
: sum(sum), presummax(presummax), siz(siz) {}
Info operator+(const Info& b) const {//信息直接合并方式
return Info(sum + b.sum, std::max(presummax, sum + b.presummax), siz + b.siz);
}
};
struct Tag {//Tag信息
int chg;
Tag(int chg = -inf) : chg(chg) {}
Tag operator+(const Tag& b) const {//Tag之间合并关系
if (b.chg == -inf) return Tag(chg);
return b;
}
};
//Tag与Info之间的合并关系
Info operator+(const Info& a, const Tag& b) {//赋值型Tag
if (b.chg == -inf) return a;
return Info(a.siz * b.chg, std::max<int>(0, a.siz * b.chg), a.siz);
}
struct OP {
char op;
int l, r, d;
int h;
};
void solve() {
int n;
std::cin >> n;
std::vector<OP> ops;
std::vector<int> b;
auto get = [&](int x) -> int {
return std::lower_bound(b.begin(), b.end(), x) - b.begin();
};
char op;
while (std::cin >> op) {
if (op == 'E') break;
if (op == 'I') {
int l, r, d;
std::cin >> l >> r >> d;
b.push_back(l - 1);
b.push_back(l);
b.push_back(r);
b.push_back(r + 1);
ops.push_back(OP{op, l, r, d, 0});
} else {
int h;
std::cin >> h;
ops.push_back(OP{op, 0, 0, 0, h});
}
}
b.push_back(0);
b.push_back(1);
b.push_back(n + 1);
std::sort(b.begin(), b.end());
b.erase(std::unique(b.begin(), b.end()), b.end());
int m = b.size();
std::vector<Info> a(m);
a[m - 1].siz = 1;
for (int i = 1; i < m - 1; i++) {
a[i].siz = b[i + 1] - b[i];
}
SGT<Info, Tag> sgt(a);
sgt.modify(m - 1, m, Tag(1e9 + 1));
for (auto &[op, l, r, v, h] : ops) {
if (op == 'I') {
sgt.modify(get(l), get(r + 1), Tag(v));
} else {
int l = 1, r = m - 1, ans = m - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (sgt.query(0, mid + 1).presummax > h) r = mid - 1, ans = mid;
else l = mid + 1;
}
auto z = sgt.query(ans, ans + 1);
int diff = z.sum / z.siz;
int t = (h - sgt.query(0, ans).sum) / diff;
int real_ans = sgt.query(0, ans).siz + t;
std::cout << real_ans << "\n";
}
}
}
Binary Search
Step 1
A. Binary Search
题意
实现二分算法。
输入的第一行包含整数 $n$ 和 $k$ （ $1 \le n$ , $k \le 10^5$ ），即数组的长度和查询次数。第二行包含数组中的 $n$ 个元素，按非递减顺序排序。第三行包含 $k$ 个查询。所有数组元素和查询次数都是整数，每个元素的绝对值都不超过 $10^9$ 。
参考思路
板子题。
参考代码
想练自己写实现。
void solve() {
int n, m;
std::cin >> n >> m;
std::set<int> s;
while (n--) {
int x;
std::cin >> x;
s.insert(x);
}
while (m--) {
int x;
std::cin >> x;
std::cout << (s.count(x) ? "YES" : "NO") << "\n";
}
}
B. Closest to the Left
题意
给定一个由 $n$ 个数字（按非递减顺序排列）和 $k$ 个查询组成的数组。请为每个查询打印不大于给定值的数组元素的最大索引。
参考思路
二分即可，自己写实现去
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::set<std::pair<int, int>> s;
for (int i = 1; i <= n; i++) {
int x;
std::cin >> x;
s.insert({x, i});
}
while (m--) {
int x;
std::cin >> x;
auto it = s.lower_bound({x, n + 1});
if (it == s.begin()) std::cout << 0 << "\n";
else {
it--;
std::cout << it->second << "\n";
}
}
}
C. Closest to the Right
题意
给定一个由 $n$ 个数字（按非递减顺序排列）和 $k$ 个查询组成的数组。请为每个查询打印不小于给定数组元素的最小索引。
参考思路
同理，二分即可
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::set<std::pair<int, int>> s;
for (int i = 1; i <= n; i++) {
int x;
std::cin >> x;
s.insert({x, i});
}
while (m--) {
int x;
std::cin >> x;
auto it = s.lower_bound({x, 0});
if (it == s.end()) std::cout << n + 1 << "\n";
else std::cout << it->second << "\n";
}
}
D. Fast search
题意
给你一个由 $n$ 个整数 $a_1, a_2, …, a_n$ 组成的数组 $a$ 。
你的任务是回答 “有多少个数字的值在 $l$ 和 $r$ 之间？
参考思路
排序后离散化，前缀和预处理贡献，最后二分左右端点即可。
参考代码
void solve() {
int n;
std::cin >> n;
std::map<int, int> cnt;
while (n--) {
int x;
std::cin >> x;
cnt[x]++;
}
std::vector<int> b;
for (auto &[k, v] : cnt) {
b.push_back(k);
}
auto get = [&](int x) -> int {
return std::lower_bound(b.begin(), b.end(), x) - b.begin();
};
std::vector<int> pre(b.size() + 1);
for (int i = 0; i < b.size(); i++) {
pre[i + 1] = pre[i] + cnt[b[i]];
}
int q;
std::cin >> q;
while (q--) {
int l, r;
std::cin >> l >> r;
std::cout << pre[get(r + 1)] - pre[get(l)] << " ";
}
}
Step 2
A. Packing Rectangles
题意
有 $n$ 个大小相同的长方形：宽为 $w$ ，长为 $h$ 。要求找出一个最小的正方形，将这些矩形填入其中。矩形不能旋转。
参考思路
考虑二分答案，check函数中计算给定边长的正方形，最多能装多少矩形。
参考代码
void solve() {
i64 w, h, n;
std::cin >> w >> h >> n;
if (h > w) std::swap(w, h);
auto ck = [&](i64 x) -> bool {
//最密堆积，有没有不用 int128 的代码？不清楚
return i128((x / w) + (x % h) / w) * (x / h) >= n;
};
i64 l = h, r = n * w, ans = n * w;
while (l <= r) {
i64 mid = (l + r) / 2;
if (ck(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
std::cout << ans;
}
B. Ropes
题意
有 $n$ 根绳子，你需要从中剪出 $k$ 段同样长的绳子。求最大长度。
参考思路
考虑二分答案，check函数中枚举所有绳子，累计所有绳子提供的总贡献。
时间复杂度：$O(50n)$ 实数二分，最多二分50次就能保证精度了
参考代码
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
auto ck = [&](ld x) -> bool {
int cnt = 0;
for (auto &i : a) cnt += int(i / x);
return cnt >= k;
};
ld l = 0, r = 1e7;
for (int _ = 0; _ < 50; _++) {
ld mid = (l + r) / 2;
if (ck(mid)) l = mid;
else r = mid;
}
std::cout << std::setprecision(7) << std::fixed << l;
}
C. Very Easy Task
题意
今天上午，评委会决定在奥林匹克竞赛题库中再增加一个 “非常简单的问题”。组委会执行秘书已经打印了一份声明，现在他们需要在奥林匹克竞赛开始前再复印 $n$ 份。他手头有两台复印机，其中一台复印一张需时 $x$ 秒，另一台复印一张需时 $y$ 秒。(可以使用一台复印机，也可以同时使用两台复印机。不仅可以复印原件，还可以复印复印件）。帮助他们找出复印 $n$ 份声明所需的最短时间。
参考思路
考虑二分答案，二分函数中判断给定时间内是否能够满足要求即可。注意原件不计入复印件数量。
参考代码
void solve() {
i64 n, x ,y;
std::cin >> n >> x >> y;
if (x > y) std::swap(x, y);
auto ck = [&](i64 m) -> bool {
if (m < x) return 0;
return 1 + (m - x) / x + (m - x) / y >= n;
};
i64 l = 1, r = n * y;
while (l <= r) {
i64 mid = (l + r) / 2;
if (ck(mid)) r = mid - 1;
else l = mid + 1;
}
std::cout << r + 1;
}
D. Children Holiday
题意
儿童节的组织者正在计划为它充气 $$$m$$$ 气球。他们邀请了 $$$n$$$ 助手， $$$i$$$ 助手在 $$$t _ i$$$ 分钟内给气球充气，但是每次在 $$$z _ i$$$ 气球充气后，他就会感到疲劳并休息 $$$y _ i$$$ 分钟。现在这个节日的组织者想知道什么时候之后所有的气球都会被充气，这是助手们最优化的工作，以及每个气球会充多少气。(如果助理已经给气球充气，需要休息，但是他不需要再给气球充气，那么就认为他在最后一个气球充气结束后立即完成了工作，而不是在休息之后)。
参考思路
考虑二分答案，二分用时 $T$ 内是否能够完成任务。最后输出答案时注意要控制所有人充气的气球数之和，要刚好等于 $m$。
参考代码
void solve() {
int m, n;
std::cin >> m >> n;
std::vector<std::array<int, 3>> a(n);//t, z, y
for (auto &[t, z, y] : a) std::cin >> t >> z >> y;
auto ck = [&](int x) -> bool {
int cnt = 0;
for (auto &[t, z, y] : a) {
cnt += (x / (t * z + y)) * z + std::min(z, (x % (t * z + y)) / t);
}
return cnt >= m;
};
int l = 0, r = 2e9, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (ck(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
assert(ans != -1);
std::cout << ans << "\n";
i64 sum = m;
int x = ans;
for (auto &[t, z, y] : a) {
int tmp = (x / (t * z + y)) * z + std::min(z, (x % (t * z + y)) / t);
tmp = std::min(tmp, sum);
sum -= tmp;
std::cout << tmp << " ";
}
}
E. Equation
题意
求一个数 $x$ ，使得 $x^2+\sqrt{x}=c$ .
参考思路
一眼函数在定义域上单调递增，直接跑实数二分即可。
参考代码
ld f(ld x) {
return x * x + std::sqrt(x);
}
void solve() {
ld c;
std::cin >> c;
ld l = 0, r = 1e6;
for (int _ = 0; _ < 50; _++) {
ld mid = (l + r) / 2;
if (f(mid) >= c) r = mid;
else l = mid;
}
std::cout << std::setprecision(7) << std::fixed << l;
}
F. String Game
题意
Petya 有一个单词 $t$ ，他想用这个单词组成单词 $p$ 。Petya 开始按照一定的顺序删除字母，这被描述为单词 $t$ 中字母指数的排列组合： $a_1 … a_{|t|}$ .请注意，删除字母后，编号不会改变。
他的哥哥瓦夏担心彼佳会删除过多的字母，因此最终无法得到单词 $p$ 。瓦夏的任务是在某一时刻阻止哥哥，并以这样的方式完成自己的删除，这样得到的单词就是 $p$ 。由于 Petya 喜欢这项活动，Vasya 希望尽可能晚地阻止他。您的任务是在 Vasya 阻止他之前，告诉他 Petya 可以删除多少个字母。
从 $t$ 中删除字母可以得到单词 $p$ 。
参考思路
二分答案，二分函数中判断未删除的字符是否能组合出 $p$。
时间复杂度：$O(n\logn)$
参考代码
void solve() {
std::string s, t;
std::cin >> s >> t;
int n = s.size();
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
std::vector<int> rmp(n);
for (int i = 0; i < n; i++) {
rmp[a[i] - 1] = i;
}
auto ck = [&](int x) -> bool {
int j = 0;
for (int i = 0; i < n && j < t.size(); i++) {
if (rmp[i] < x || t[j] != s[i]) continue;
j++;
}
return j == t.size();
};
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (ck(mid)) l = mid + 1;
else r = mid - 1;
}
std::cout << l - 1;
}
G. Student Councils
题意
给定数字 $k$ 。每个学生会必须由 $k$ 名学生组成。重要规则：每个学生会应由来自不同小组的学生组成。也就是说，不能有两个来自同一小组的学生参加同一个学生会。
当然，每个学生参加的理事会不得超过一个（有些学生可能不参加任何理事会）。
给定数组 $a[1..n]$ ，其中 $a[i]$ 是 $i$ -th 组的学生人数。最多可以成立多少个理事会？
参考思路
套路题，先 sort 一下，保留前 $k$ 个不选，剩下的都能选，可以证明存在某种贪心策略，保证和前面 $k$ 组拼起来后每行选择了恰好 $k$ 个不同的元素。
然后由于答案具有单调性，可以直接二分答案，判断是否可以成立 $x$ 组即可。
参考代码
void solve() {
i64 k, n;
std::cin >> k >> n;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
std::sort(a.rbegin(), a.rend());
i64 cnt = 0;
for (i64 i = k; i < n; i++) {
cnt += a[i];
}
auto ck = [&](i64 x) -> bool {
i64 sum = 0;
for (i64 i = 0; i < k; i++) {
sum += std::min(a[i], x);
}
return sum + cnt >= x * k;
};
i64 l = 0, r = 2e16;
while (l <= r) {
i64 mid = (l + r) / 2;
if (ck(mid)) l = mid + 1;
else r = mid - 1;
}
std::cout << l - 1;
}
H. Hamburgers
题意
波利卡普斯非常喜欢吃汉堡包。他尤其喜欢自己亲手做的汉堡包。波利卡普认为，制作汉堡包只需要三种像样的材料：面包、香肠和奶酪。他把自己最喜欢的 “波利卡普汉堡包 “的配方写成一串字母 “B”（面包）、“S”（香肠）和 “C”（奶酪）。食谱中的配料从下到上依次排列，例如，食谱 “BSCBS “代表汉堡包，其中的配料从下到上依次为面包、香肠、奶酪、面包和香肠。
波利卡普斯厨房里有 $n_b$ 块面包、 $n_s$ 块香肠和 $n_c$ 块奶酪。此外，附近的商店也有这三种食材，价格分别为 $p_b$ 卢布一个面包、 $p_s$ 个香肠和 $p_c$ 块奶酪。
波利卡普斯有 $r$ 卢布，他准备用它们来购物。他最多可以做多少个汉堡包？你可以假设波利卡普不能掰开或切碎任何一块面包、香肠或奶酪。此外，店里每种材料的数量都是无限的。
参考思路
直接二分答案，二分是否能够做 $x$ 个汉堡，二分函数中统计需要花费的价钱，与 $r$ 比较即可。
参考代码
void solve() {
std::string s;
std::cin >> s;
std::map<char, int> cnt, cost, need;
std::cin >> cnt['B'] >> cnt['S'] >> cnt['C'];
std::cin >> cost['B'] >> cost['S'] >> cost['C'];
for (auto &c : s) need[c]++;
i64 p;
std::cin >> p;
auto ck = [&](i64 x) -> bool {
i64 cost_ = 0;
for (auto &[k, v] : cnt) {
if (v < x * need[k]) {
cost_ += (x * need[k] - v) * cost[k];
}
}
return cost_ <= p;
};
i64 l = 0, r = 1e15;
while (l <= r) {
i64 mid = (l + r) / 2;
if (ck(mid)) l = mid + 1;
else r = mid - 1;
}
std::cout << l - 1;
}
Step 3
A. Get together
题意
有 $n$ 人在一条直线上，他们需要聚集在一点。每个人都知道自己当前的位置 $x_i$ 和速度 $v_i$ 。请帮助他们找出最少能在多长时间内聚集到一点。
参考思路
考虑二分答案，二分最少用时，二分函数中检查 $n$ 个人所能抵达的区间交集是否非空即可。
参考代码
constexpr ld eps = 1e-6;
void solve() {
int n;
std::cin >> n;
std::vector<std::pair<i64, i64>> a(n);
for (auto &[x, v] : a) std::cin >> x >> v;
auto cmp = [](const auto& a, const auto& b) -> auto {
return a.second < b.first;
};
auto ck = [&](ld t) -> bool {
std::set<std::pair<ld, ld>, decltype(cmp)> s(cmp);
auto insert = [&](ld l, ld r) {
if (l + eps >= r) return;
s.insert({l, r});
};
s.insert({a[0].first - a[0].second * t, a[0].first + a[0].second * t});
for (auto &[x, v] : a) {//restrict
ld L = x - v * t, R = x + v * t;
auto it = s.begin();
while (it != s.end()) {
auto [l, r] = *it;
it++;
s.erase(std::prev(it));
insert(std::clamp(l, L, R), std::clamp(r, L, R));
}
}
return s.size() > 0;
};
ld l = 0, r = 2e10;
for (int _ = 0; _ < 60; _++) {
ld mid = (l + r) / 2;
if (ck(mid)) r = mid;
else l = mid;
}
std::cout << std::setprecision(7) << std::fixed << r;
}
B. Splitting an Array
题意
给定一个由 $n$ 个正整数组成的数组。你的任务是将数组分成 $k$ 段，使各段的最大和尽可能小。
参考思路
考虑二分答案，二分判断函数中，将当最大和为 $x$ 时，最多能划分的段数与 $k$ 比较即可。
参考代码
void solve() {
int n, k;
std::cin >> n >> k;
int mx = 0;
std::vector<int> a(n);
for (auto &i : a) (std::cin >> i), mx = std::max(mx, i);
auto ck = [&](i64 x) -> bool {
int cnt = 1;
i64 sum = 0;
for (auto &i : a) {
if (sum + i > x) {
cnt++;
sum = 0;
}
sum += i;
}
return cnt <= k;
};
i64 l = mx, r = 2e18;
while (l <= r) {
i64 mid = (l + r) / 2;
if (ck(mid)) r = mid - 1;
else l = mid + 1;
}
std::cout << r + 1;
}
C. Cows in Stalls
题意
牛栏位于一条直线上，您的任务是将奶牛安排到牛栏中，使奶牛之间的距离尽可能小。
参考思路
考虑直接二分答案，二分最小距离 $x$，在二分函数中用 lowerbound 二分向后跳，统计满足最小距离大于 $x$ 时，可用的栅栏数。
参考代码
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
auto ck = [&](int x) -> bool {
int cnt = 0;
auto it = a.begin();
while (it != a.end()) {
cnt++;
if (cnt >= k) return 1;
it = std::lower_bound(a.begin(), a.end(), *it + x);
}
return 0;
};
int l = 0, r = 1e9;
while (l <= r) {
int mid = (l + r) / 2;
if (ck(mid)) l = mid + 1;
else r = mid - 1;
}
std::cout << l - 1;
}
D. Minimum maximum on the Path
题意
道路网由 $n$ 个路口和 $m$ 条单行道组成，每条道路都从编号较低的路口通向编号较高的路口。每条路都有一个编号。你的任务是找到一条从路口 1 到路口 $n$ 的路径，它最多由 $d$ 条边组成，在这条路径上，各条边对应的数字的最大值都可能是最小值。
参考思路
先二分目标路径中最长的边的最小值，在二分函数中跑 01BFS，以边权为 1 跑最短路。再以跑出来的最小值跑一遍最短路，记录转移路径，最后输出记录的路径即可。
参考代码
void solve() {
int n, m, d;
std::cin >> n >> m >> d;
std::vector edg(n, std::vector<std::pair<int, int>>());
while (m--) {
int x, y, w;
std::cin >> x >> y >> w;
x--; y--;
edg[x].push_back({y, w});
//edg[y].push_back({x, w});
}
auto ck = [&](int r) -> bool {
std::vector<int> dis(n, 1e9);
std::queue<int> q;
q.push(0);
dis[0] = 0;
while (q.size()) {
auto now = q.front(); q.pop();
for (auto &[nxt, w] : edg[now]) {
if (w > r) continue;//超限
if (dis[nxt] > dis[now] + 1) {
dis[nxt] = dis[now] + 1;
q.push(nxt);
}
}
}
return dis[n - 1] <= d;
};
int l = 0, r = 1e9;
while (l <= r) {
int mid = (l + r) / 2;
if (ck(mid)) r = mid - 1;
else l = mid + 1;
}
if (r + 1 == 1e9 + 1) {
std::cout << -1;
return;
}
r++;
std::vector<int> dis(n, 1e9), fa(n);
std::queue<int> q;
q.push(0);
dis[0] = 0;
while (q.size()) {
auto now = q.front(); q.pop();
for (auto &[nxt, w] : edg[now]) {
if (w > r) continue;//超限
if (dis[nxt] > dis[now] + 1) {
dis[nxt] = dis[now] + 1;
fa[nxt] = now;
q.push(nxt);
}
}
}
std::vector<int> ans;
int now = n - 1;
while (now) {
ans.push_back(now);
now = fa[now];
}
ans.push_back(0);
std::reverse(ans.begin(), ans.end());
std::cout << ans.size() - 1 << "\n";
for (auto &i : ans) std::cout << i + 1 << " ";
}
Step 4
A. Maximum Average Segment
题意
给定一个数组 $n$ 和一个数字 $d$ 。你的任务是找出一个长度至少为 $d$ 的数段，在这个数段上，各元素的算术平均数尽可能最大。
参考思路
考虑二分答案 $x$，于是我们只需要判断是否存在一个长度大于 $d$ 的区间，使得 $\sum_{i = l}^ra[i] >= (r - l)x$，即 $\sum_{i = l}^ra[i] - x >= 0$，问题转化为，在 $a[i] - x$ 数组中找一段长度大于 $d$ 的区间，使得区间贡献和为正。
具体实现可以利用前缀和维护 $pre[j] = \sum_{i = 0}^ja[i] - x$，然后再对前缀和数组 $pre$ 维护前缀 $min$ 数组。
二分出具体答案后，直接构造即可。
参考代码
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
auto ck = [&](ld x) -> bool {
std::vector<ld> b(n);
for (int i = 0; i < n; i++) {
b[i] = a[i] - x;
}
std::vector<ld> pre(n);
pre[0] = b[0];
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1] + b[i];
}
std::vector<ld> g(n);
g[0] = std::min(0.0l, pre[0]);
for (int i = 1; i < n; i++) {
g[i] = std::min(g[i - 1], pre[i]);
}
for (int i = k - 1; i < n; i++) {
if (pre[i] >= (i >= k ? g[i - k] : 0)) {
return 1;
}
}
return 0;
};
ld l = 0, r = 100;
for (int _ = 0; _ <= 100; _++) {
ld mid = (l + r) / 2;
if (ck(mid)) l = mid;
else r = mid;
}
std::vector<ld> b(n);
for (int i = 0; i < n; i++) {
b[i] = a[i] - l;
}
std::vector<ld> pre(n);
pre[0] = b[0];
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1] + b[i];
}
std::vector<ld> g(n);
g[0] = std::min(0.0l, pre[0]);
for (int i = 1; i < n; i++) {
g[i] = std::min(g[i - 1], pre[i]);
}
for (int i = k - 1; i < n; i++) {
if (pre[i] >= (i >= k ? g[i - k] : 0)) {
if (i == k - 1) {
std::cout << 1 << " " << k;
return;
} else {
for (int j = 0; j <= i - k; j++) {
if (pre[j] == g[i - k]) {
std::cout << j + 2 << " " << i + 1;
return;
}
}
std::cout << 1 << " " << i + 1;
return;
}
}
}
//std::cout << l;
}
B. Minimum Average Path
题意
道路网由 $n$ 个路口和 $m$ 条单行道组成，每条道路都从编号较低的路口通向编号较高的路口。每条路都有一个编号。你的任务是找到一条从路口 1 到路口 $n$ 的路径，在这条路径上，边缘对应的数字的算术平均值尽可能小。
参考思路
和上题类似，考虑二分答案 $r$，二分答案时将边权修改为 $a[i] = w - r$，用树 dp 跑最长路，判 $dis[n - 1] <= 0$ 即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector redg(n, std::vector<std::pair<int, int>>());
while (m--) {
int x, y, w;
std::cin >> x >> y >> w;
x--; y--;
redg[y].push_back({x, w});
}
auto ck = [&](ld r) -> bool {
std::vector<ld> dp(n, 1e9);
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (auto &[from, w] : redg[i]) {
dp[i] = std::min(dp[i], dp[from] + w - r);
}
}
//std::cout << r << ": " << dp[n - 1] << "]\n";
return dp[n - 1] <= 0;
};
ld l = 0, r = 100;
for (int i = 0; i < 50; i++) {
ld mid = (l + r) / 2;
if (ck(mid)) r = mid;
else l = mid;
}
//std::cout << l;
std::vector<int> fa(n);
std::vector<ld> dp(n, 1e9);
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (auto &[from, w] : redg[i]) {
if (dp[i] > dp[from] + w - r) {
dp[i] = dp[from] + w - r;
fa[i] = from;
}
}
}
std::vector<int> ans;
int now = n - 1;
while (now) {
ans.push_back(now);
now = fa[now];
}
ans.push_back(0);
std::reverse(ans.begin(), ans.end());
std::cout << ans.size() - 1 << "\n";
for (auto &i : ans) std::cout << i + 1 << " ";
}
C. Pair Selection;
题意
给定 $n$ 对正整数 $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$ 。请选择其中的 $k$ ( $1 \le k \le n$ ) $i_1, i_2, \dots, i_k$ 使比例 $\frac{a_{i1} + a_{i2} + \dots + a_{ik}}{b_{i1} + b_{i2} + \dots + b_{ik}}$ 最大。
参考思路
01分数规划板子题，设 $\frac{a_{i1} + a_{i2} + \dots + a_{ik}}{b_{i1} + b_{i2} + \dots + b_{ik}} = x$，则有 $a_{i1} + a_{i2} + \dots + a_{ik} = (b_{i1} + b_{i2} + \dots + b_{ik})x$，即 $\sum (a_{ij} - b_{ij} x) = 0$。
考虑二分答案，在二分函数中构造数组 $c[i] = a[i] - b[i] * x$，然后排序后选前 $k$ 大，判断和与 $0$ 的大小即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::pair<int, int>> p(n);
for (auto &[a, b] : p) std::cin >> a >> b;
auto ck = [&](ld x) -> bool {
std::vector<ld> z(n);
for (int i = 0; i < n; i++) {
z[i] = p[i].first - x * p[i].second;
}
std::sort(z.rbegin(), z.rend());
ld sum = 0;
for (int i = 0; i < m; i++) {
sum += z[i];
}
return sum >= 0;
};
ld l = 0, r = 1e5;
for (int i = 0; i < 50; i++) {
ld mid = (l + r) / 2;
if (ck(mid)) l = mid;
else r = mid;
}
std::cout << std::setprecision(7) << std::fixed << l;
}
Step 5
A. K-th Number in the Union of Segments
题意
给定 $n$ 段整数[ $l_1,r_1$ ], [ $l_2,r_2$ ],…, [ $l_n,r_n$ ]。
让我们把这些数段中的所有数字写成一个数组。如果某个数字包含在一个以上的数段中，那么它在数组中出现的次数一定是它包含的数段的数量。也就是说，数组的长度等于所有数段中数字的总和。
之后，数组被排序。你的任务是找出数组中位于 $k$ 位置（编号从 0 开始）的数字。
参考思路
考虑二分答案 $x$，二分函数中遍历数组，收集小于等于 $x$ 的数的数量，将其与 $k$ 比较即可。
参考代码
void solve() {
i64 n, k;
std::cin >> n >> k;
std::vector<std::pair<i64, i64>> a(n);
for (auto &[l, r] : a) std::cin >> l >> r;
auto ck = [&](i64 x) -> bool {
i64 sum = 0;
for (auto &[l, r] : a) {
if (l > x) continue;
sum += (std::min(r, x) - l + 1);
}
return sum >= k + 1;
};
i64 l = -2e9, r = 2e9;
while (l <= r) {
i64 mid = (l + r) / 2;
if (ck(mid)) r = mid - 1;
else l = mid + 1;
}
std::cout << r + 1;
}
B. Multiplication Table
题意
彼得编制了一张大小为 $n\times n$ 的乘法表。在 $i$ ÷th行和 $j$ ÷th列中的单元格包含值 $i\cdot j$ 。彼得感兴趣的问题是：表格中哪个数字的升序是 $k$ -th？请帮助彼得回答这个问题。
参考思路
和上一题类似，考虑二分答案 $x$，在二分函数中遍历 $n$ 行，收集小于等于 $x$ 的数的数量，与 $k$ 比较即可。
参考代码
void solve() {
i64 n, k;
std::cin >> n >> k;
auto ck = [&](i64 x) -> bool {
i64 sum = 0;
for (int i = 1; i <= n; i++) {
if (i > x) continue;
sum += (std::min(n, x / i));
}
return sum >= k;
};
i64 l = 1, r = n * n;
while (l <= r) {
i64 mid = (l + r) / 2;
if (ck(mid)) r = mid - 1;
else l = mid + 1;
}
std::cout << r + 1;
}
C. K-th Sum
题意
有两个数组 $a$ 和 $b$ ，每个数组都由 $n$ 个整数组成。对于每一对数字 $(i, j): 1\le i, j\le n$ ，写出和 $a_i + b_j$ 。在得到的一组和中，按升序找出 $k$ 个。
参考思路
二分套二分，考虑二分答案 $x$，对两个数组排序后，在二分函数中枚举第一个数组，二分第二个数组中有多少个数满足 $a[i] + b[j] \le x$，收集数量后与 $k$ 作比较即可。
参考代码
void solve() {
i64 n, k;
std::cin >> n >> k;
std::vector<i64> a(n), b = a;
for (auto &i : a) std::cin >> i; std::sort(a.begin(), a.end());
for (auto &i : b) std::cin >> i; std::sort(b.begin(), b.end());
auto ck = [&](i64 x) -> bool {
i64 sum = 0;
for (int i = 0; i < n; i++) {
if (a[i] + b[0] > x) break;
sum += *std::ranges::partition_point(std::ranges::iota_view(0, n),
[&](int j) {
return a[i] + b[j] <= x;
}
);
}
return sum >= k;
};
i64 l = 1, r = 2e9;
while (l <= r) {
i64 mid = (l + r) / 2;
if (ck(mid)) r = mid - 1;
else l = mid + 1;
}
std::cout << r + 1;
}
Disjoint Sets Union
Step 1
A. Disjoint Sets Union
题意
实现并查集数据结构。您必须执行两种类型的查询：
- union $u$ - 联合分别包含 $u$ 和 $v$ 的两个集合 $v$ - 联合分别包含 $u$ 和 $v$ 的两个集合；
- 获取 $u$ $v$ - 检查两个元素 $u$ 和 $v$ 是否属于同一个集合。
参考思路
并查集板子题，不讲思路。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
F[find(x)] = find(y);
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
DSU dsu(n + 1);
while (m--) {
std::string s;
int x, y;
std::cin >> s >> x >> y;
if (s[0] == 'u') {
dsu.join(x, y);
} else {
if (dsu.find(x) == dsu.find(y)) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
}
}
}
B. Disjoint Sets Union 2
题意
实现并查集数据结构。您必须执行两种类型的查询：
- union $u$ - 将分别包含 $u$ 和 $v$ 的两个集合联合起来 $v$ - 将分别包含 $u$ 和 $v$ 的两个集合联合起来；
- get $v$ - 查找 $v$ 所属的集合，找出该集合的最小元素和最大元素，以及其中元素的总数。
参考思路
带权并查集板子题，在合并时转移权值即可。
参考代码
struct DSU {
std::vector<int> F, mi, mx, siz;
DSU(int n) : F(n), mi(n), mx(n), siz(n, 1) {
std::iota(F.begin(), F.end(), 0);
mi = mx = F;
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int Fx = find(x);
int Fy = find(y);
if (Fx != Fy) {
F[Fx] = Fy;
mi[Fy] = std::min(mi[Fy], mi[Fx]);
mx[Fy] = std::max(mx[Fy], mx[Fx]);
siz[Fy] += siz[Fx];
}
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
DSU dsu(n + 1);
while (m--) {
std::string op;
std::cin >> op;
if (op[0] == 'u') {
int x, y;
std::cin >> x >> y;
dsu.join(x, y);
} else {
int p;
std::cin >> p;
p = dsu.find(p);
std::cout << dsu.mi[p] << " ";
std::cout << dsu.mx[p] << " ";
std::cout << dsu.siz[p] << "\n";
}
}
}
C. Experience
题意
在新颖的网络游戏中，玩家像往常一样与怪物战斗并获得经验。为了与怪物战斗，玩家要组成突击队。消灭怪物后，队伍中的所有玩家都会获得相同数量的经验值。游戏的特点是不能拆散队伍，也不能离开队伍。唯一支持的操作是将两个队伍联合在一起。
由于已经有很多人在玩游戏，因此要求您保持玩家的经验值。
输入的第一行包含两个整数 $n$ 和 $m$ ($1\le n,m\le 2·10^5$) ー玩家数量和查询数量。
接下来的 $m$ 行包含查询描述，每行一个。查询可以有三种类型：
join $X$ $Y$ ーー加入球员 X 和 Y 所属的两个队 (如果他们已经在同一个队，没有任何变化)。
add $X$ $V$ ー将 $V$ ($1 \le V \le 100$) 经验点添加到玩家 $X$ 所属的团队中的每个玩家。
get $X$ ーー输出玩家当前的经验点数 $X$ 。最初，每个玩家都有 $0$ 经验值，并且每个玩家都在自己的 $1$ 号队伍中。
参考思路
带权并查集，维护权值加，合并时维护权值转移即可。
参考代码
struct DSU {
std::vector<int> F, bonus;//diff
std::vector<int> val;//与bonus无关的val
std::vector<std::set<int>> s;//启发式合并
DSU(int n) : F(n), bonus(n, 0), val(n, 0), s(n) {
std::iota(F.begin(), F.end(), 0);
for (int i = 0; i < n; i++) {
s[i].insert(i);
}
}
void add(int x, int v) {
bonus[find(x)] += v;
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int Fx = find(x);
int Fy = find(y);
if (Fx != Fy) {
if (s[Fx].size() > s[Fy].size()) std::swap(Fx, Fy);
F[Fx] = Fy;
for (auto &i : s[Fx]) {
val[i] += bonus[Fx];
val[i] -= bonus[Fy];
s[Fy].insert(i);
}
}
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
DSU dsu(n + 1);
while (m--) {
std::string op;
std::cin >> op;
if (op[0] == 'a') {
int p, v;
std::cin >> p >> v;
dsu.add(p, v);
} else if (op[0] == 'j') {
int x, y;
std::cin >> x >> y;
dsu.join(x, y);
} else {
int x;
std::cin >> x;
std::cout << dsu.val[x] + dsu.bonus[dsu.find(x)] << "\n";
}
}
}
D. Cutting a graph
题意
有一个无向图和两种类型的操作序列，其格式如下：
cut $u$ $v$ ーー从图中删除边 $u$ - $v$ ;
ask $u$ $v$ ーー检查顶点 $u$ 和 $v$ 是否在同一个连接元件 (图论)。在应用了所有的操作之后，该图不包含任何边。请查找类型 ask 的每个操作的结果。
参考思路
考虑将输入离线下来，反转输入，将 cut 改成 add，先预处理一遍，将原图中，不出现在操作序列中的所有边，全部加入并查集中，再倒着处理询问即可。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int Fx = find(x);
int Fy = find(y);
F[Fx] = Fy;
return !ok;
}
};
void solve() {
int n, m, q;
std::cin >> n >> m >> q;
std::set<std::pair<int, int>> edgs, res;
while (m--) {
int x, y;
std::cin >> x >> y;
if (x > y) std::swap(x, y);
edgs.insert({x, y});
}
std::vector<std::array<int, 3>> ask(q);
for (auto &[t, x, y] : ask) {
std::string op;
std::cin >> op >> x >> y;
if (x > y) std::swap(x, y);
if (op[0] == 'a') {
t = 0;
} else {
t = 1;
edgs.erase({x, y});
res.insert({x, y});
}
}
DSU dsu(n + 1);
for (auto &[x, y] : edgs) {
dsu.join(x, y);
}
std::vector<int> ans;
for (int i = q - 1; i >= 0; i--) {
auto &[t, x, y] = ask[i];
if (t) {
dsu.join(x, y);
} else {
ans.push_back(dsu.find(x) == dsu.find(y));
}
}
std::reverse(ans.begin(), ans.end());
for (auto &i : ans) std::cout << (i ? "YES" : "NO") << "\n";
}
E. Monkeys
题意
有 $n$ 猴子挂在一棵很高的树上。猴子的数量从 $1$ 到 $n$ 。第一只猴子 (领头的) 用尾巴吊在一根结实的树枝上。每只猴子都可以用自己的手抓住另一只猴子的尾巴，或者用自己的尾巴挂住另一只猴子。现在所有的猴子都直接或间接地挂在领头的猴子身上，而且没有倒下。猴子的一只手最多只能抓住一条尾巴 (或挂在一条尾巴上) ，但是任意数量的手可以抓住或挂在一条尾巴上。
每一秒，从零开始，其中一只猴子放开一只手，结构就会改变。此外，还可能发生一只或多只猴子开始跌倒的情况。这棵树非常高，所以需要一段时间才能倒下，猴子们在这段时间里继续松开双手。
您被给予初始配置和手释放的时间表。你要写一个程序，计算每只猴子开始倒下的时间。
参考思路
题意很迷，实际上手和尾巴可以等价，每个节点最多有 $3$ 条边，我们只需要维护每只猴子与 0 号猴子不在同一连通块（断开连接）的时间点即可。
建完图后，按时间顺序跑一遍生成树，最后倒着跑并查集加边即可，每只猴子第一次与 0 号猴子所处的联通块连通的时间，即为断开连接的时间。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int Fx = find(x);
int Fy = find(y);
if (Fx != Fy) {
if (Fx < Fy) std::swap(Fx, Fy);//让下标大的合并到小的
F[Fx] = Fy;
}
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> L(n + 1), R(n + 1);
std::multiset<std::pair<int, int>> edgs;
auto add = [&](int x, int y) {
if (x > y) edgs.insert({y, x});
else edgs.insert({x, y});
};
auto remove = [&](int x, int y) {
if (x == -1 || y == -1) return;
if (x > y) edgs.extract({y, x});
else edgs.extract({x, y});
};
for (int i = 1; i <= n; i++) {
std::cin >> L[i] >> R[i];
if (L[i] != -1) add(L[i], i);
if (R[i] != -1) add(R[i], i);
}
std::vector<std::pair<int, int>> event(m);
for (auto &[x, y] : event) {
int p, t;
std::cin >> p >> t;
if (t == 1) {
if (p > L[p]) x = L[p], y = p;
else x = p, y = L[p];
remove(p, L[p]);
} else {
if (p > R[p]) x = R[p], y = p;
else x = p, y = R[p];
remove(p, R[p]);
}
}
//时间顺序生成树
std::vector edg(n + 1, std::vector<int>());
std::vector<int> fall(n + 1, -1);
DSU dsu(n + 1);
dsu.join(0, 1);
auto JOIN = [&](int x, int y, int t) {
int fx = dsu.find(x);
int fy = dsu.find(y);
if (fx != fy) {
dsu.join(fx, fy);
if (fx > fy) std::swap(fx, fy);
edg[fx].push_back(fy);
if (fx == 0) {
fall[fy] = t;
}
}
};
edg[0].push_back(1);
for (auto &[x, y] : edgs) {
JOIN(x, y, -1);
}
for (int i = m - 1; i >= 0; i--) {
JOIN(event[i].first, event[i].second, i);
}
auto dfs = [&](auto&& self, int now, int from) -> void {
for (auto &nxt : edg[now]) {
if (nxt == from) continue;
fall[nxt] = std::max(fall[nxt], fall[now]);
self(self, nxt, now);
}
};
dfs(dfs, 0, -1);
for (int i = 1; i <= n; i++) std::cout << fall[i] << "\n";
}
Step 2
A. People are leaving
题意
$n$ 人站在 $1$ 至 $n$ 位置。您必须执行两种类型的查询：
- “- $x$ " - 位于 $x$ 位置的人离开；
- “? $x$ “–找到右边最近的还站着的人。
参考思路
考虑建立一个 n + 1 大小的并查集，每次进行第一个操作时，直接合并 $x$ 和 $x + 1$（注意让下标大的当联通块的祖先）；查询时查询 $x$ 处的祖先即可。
当然你用 set 维护也行，不过有点慢
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int Fx = find(x);
int Fy = find(y);
if (Fx != Fy) {
if (Fx > Fy) std::swap(Fx, Fy);//让下标小的合并到大的
F[Fx] = Fy;
}
return !ok;
}
};
void solve() {//312ms
int n, m;
std::cin >> n >> m;
DSU dsu(n + 2);
while (m--) {
char op;
int x;
std::cin >> op >> x;
if (op == '?') {
int z = dsu.find(x);
std::cout << (z == n + 1 ? -1 : z) << "\n";
} else {
dsu.join(x, x + 1);
}
}
}
B. Parking
题意
从 $1$ 到 $n$ 的环形停车场上有 $n$ 个车位。有 $n$ 辆车想按自然顺序停放。 $i$ 辆汽车想停在 $p_i$ 个车位上。如果汽车开到一个车位，而她的车位已被占用，那么它就会循环行驶，停在第一个空车位上。
参考思路
和上题类似，用并查集维护右边第一个没有被占用的车位，输入的同时查询结果，输出后再合并。注意要将 $n$ 号位置连接到 $1$ 号位置上。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {//x -> y
bool ok = (find(x) == find(y));
int Fx = find(x);
int Fy = find(y);
if (Fx != Fy) {
F[Fx] = Fy;
}
return !ok;
}
};
void solve() {
int n;
std::cin >> n;
DSU dsu(n);
for (int i = 0; i < n; i++) {
int p;
std::cin >> p;
p--;
int z = dsu.find(p);
std::cout << z + 1 << " ";
dsu.join(z, (z + 1) % n);
}
}
C. Restructuring Company
题意
即使是最成功的公司也会经历危机时期，这时你必须做出艰难的决定一一重组、废弃和合并部门、解雇员工以及做其他令人不快的事情。让我们来看看下面的公司模式。
大型软件公司有 $n$ 名员工。每个人都隶属于某个部门。最初，每个人都在自己的部门负责自己的项目(因此，每个公司最初由 $n$ 个部门组成，每个部门有一个人)。
然而，严酷的时代已经来临，公司管理层不得不聘请一位危机管理者来重建工作流程，以提高效率。让我们用 $team(person)$ 代表一个团队， $person$ 在其中工作。危机管理者可以做出两种决策：
将部门 $team(x)$ 和 $team(y)$ 合并为一个大部门，其中包含 $team(x)$ 和 $team(y)$ 的所有员工，其中 $x$ 和 $y$ ($1 \le x, y \le n$)--是公司某些员工中两个人的编号。如果 $team(x)$ 与 $team(y)$ 匹配，则不会发生任何操作。
合并部门 $team(x), team(x + 1), ..., team(y)$ ，其中 $x$ 和 $y$ ($1 \le x \le y \le n$) - 是公司两名员工的编号。
危机管理者有时会怀疑员工 $x$ 和 $y$ ($1 \le x, y \le n$) 是否在同一部门工作。
请帮助危机处理经理并回答他的所有疑问。
参考思路
用两个并查集，一个处理单点修改，一个处理区间修改。处理区间修改时，暴力向后跳，次数最多是 $n$ 次，跳的同时合并单点修改的并查集中对应的联通块。查询时查询单点修改所管理的联通块即可。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {//x -> y
bool ok = (find(x) == find(y));
int Fx = find(x);
int Fy = find(y);
if (Fx != Fy) {
F[Fx] = Fy;
}
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
DSU dsua(n + 1), dsub(n + 1);
while (m--) {
int op, x, y;
std::cin >> op >> x >> y;
if (op == 1) {
dsua.join(x, y);
} else if (op == 2) {
int now = dsub.find(x);
while (now <= y) {
dsub.join(now, y);
dsua.join(now, y);
now++;
if (now > n) break;
now = dsub.find(now);
}
} else {
int fx = dsua.find(x);
int fy = dsua.find(y);
std::cout << (fx == fy ? "YES" : "NO") << "\n";
}
}
}
D. Bosses
题意
一家公司有 $n$ 名员工，在当前时刻，没有人是其他人的下属。也就是说，每个员工都是自己的老板。如果一个人不是其他人的下属，我们就称他为老板。
您需要处理两类查询：
老板 $a$ 成为老板 $b$ 的下属(不再是老板)，
给定员工 $c$ ，我们应该通过他的多少个上级才能找到老板？
在第二种类型的查询中，如果 $c$ 是老板，则答案为 $0$，否则答案为某个正整数–员工的 “深度”。
请编写一个处理查询的程序。
参考思路
带权并查集，维护到祖先的路径长度，路径压缩时记得更新新的路径长度。
参考代码
struct DSU {
std::vector<int> F;
std::vector<int> val;
DSU(int n) : F(n), val(n, 0) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
if (F[x] == x) return x;
int fx = F[x];//暂存父节点，同时处理好父节点的权值更新
F[x] = find(fx);
val[x] += val[fx];
return F[x];
}
bool join(int x, int y) {//x -> y
int fx = find(x);
int fy = find(y);
if (fx != fy) {
F[fx] = fy;
val[fx]++;
}
return !(fx == fy);
}
};
void solve() {
int n, m;
std::cin >> n >> m;
DSU dsu(n + 1);
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int x, y;
std::cin >> x >> y;
dsu.join(x, y);
} else {
int p;
std::cin >> p;
dsu.find(p);
std::cout << dsu.val[p] << "\n";
}
}
}
E. Spanning Tree
题意
对于给定的连通无向加权图，找出权重最小的生成树。
参考思路
最小生成树板子，不讲思路。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
F[find(x)] = find(y);
return !ok;
}
};
i64 kruskal(std::vector<std::array<int, 3>> edgs, int n) {
std::sort(edgs.begin(), edgs.end());
DSU dsu(n);
i64 sum = 0;
//std::vector<std::vector<std::pair<int, int>>> edg(n);//连边
for (auto &[w, u, v] : edgs) {
int fu = dsu.find(u);
int fv = dsu.find(v);
if (fu != fv) {
//edg[u].push_back({v, w});
//edg[v].push_back({u, w});
dsu.join(u, v);
sum += w;
}
}
return sum;
}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::array<int, 3>> edgs(m);
for (auto &[w, x, y] : edgs) (std::cin >> x >> y >> w), x--, y--;
std::cout << kruskal(edgs, n);
}
F. Dense spanning tree
题意
您需要在图中找到一棵生成树，使最大边和最小边之间的差值最小。
参考思路
将边按权值排序后，双指针从小到大判断给定区间的边权是否存在生成树，双指针过程中记录答案，时间复杂度 $O(mlogm + nm)$。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
F[find(x)] = find(y);
return !ok;
}
};
bool kruskal(std::vector<std::array<int, 3>> &edgs, int n, int l, int r) {
//std::sort(edgs.begin(), edgs.end());
DSU dsu(n);
int cnt = n;
//std::vector<std::vector<std::pair<int, int>>> edg(n);//连边
//for (auto &[w, u, v] : edgs) {
for (int i = l; i < std::min<int>(edgs.size(), r + 1); i++) {
auto &[w, u, v] = edgs[i];
int fu = dsu.find(u);
int fv = dsu.find(v);
if (fu != fv) {
//edg[u].push_back({v, w});
//edg[v].push_back({u, w});
dsu.join(u, v);
cnt--;
}
}
return (cnt == 1);
}
void solve() {
int ans = 2e9 + 1;
int n, m;
std::cin >> n >> m;
std::vector<std::array<int, 3>> edgs(m);
for (auto &[w, x, y] : edgs) (std::cin >> x >> y >> w), x--, y--;
std::sort(edgs.begin(), edgs.end());
bool ok = 0;
int l = 0, r = n - 2;
do {
ok = 0;
while (r + 1 < m && (edgs[r][0] == edgs[r + 1][0] || r - l + 1 < n - 1)) r++, ok = 1;
if (kruskal(edgs, n, l, r)) {
ans = std::min(ans, edgs[r][0] - edgs[l][0]);
while (l + 1 < m && edgs[l][0] == edgs[l + 1][0]) l++, ok = 1;
if (l + 1 < m) l++, ok = 1;
} else {
while (r + 1 < m && edgs[r][0] == edgs[r + 1][0]) r++, ok = 1;
if (r + 1 < m) r++, ok = 1;
}
} while (ok);
if (ans == 2e9 + 1) {
std::cout << "NO";
} else {
std::cout << "YES\n";
std::cout << ans;
}
}
G. No refuel
题意
城市之间有多条道路 $1, 2, …, n$ 。每条道路的长度已知。道路网络是连通的，即任何一对城市之间都有一条道路。加油站只位于城市中。你必须计算出汽车要在城市间顺利行驶所能通过的最大距离。
参考思路
跑最小生成树，求最大边权即可。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
F[find(x)] = find(y);
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::array<int, 3>> edgs(m);
for (auto &[w, x, y] : edgs) std::cin >> x >> y >> w;
std::sort(edgs.begin(), edgs.end());
DSU dsu(n + 1);
int cnt = n;
for (auto &[w, x, y] : edgs) {
if (dsu.join(x, y)) cnt--;
if (cnt == 1) {
std::cout << w;
return;
}
}
}
H. Oil business
题意
给你一个无向连通图，图中有 $n$ 个顶点和 $m$ 条边。您知道每条边的删除成本。您希望删除尽可能多的边，使图形保持连通，且删除边的总成本不超过 $s$。
参考思路
考虑最大生成树，筛选出剩下未删的边，然后按权值从小到大选，一直选到第一次不满足总删除成本小于 $s$ 为止。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
F[find(x)] = find(y);
return !ok;
}
};
void solve() {
int n, m;
i64 s;
std::cin >> n >> m >> s;
std::vector<std::array<int, 4>> edgs(m);
for (auto &[w, x, y, id] : edgs) (std::cin >> x >> y >> w), x--, y--;
for (int i = 0; i < m; i++) {
edgs[i][3] = i + 1;
}
std::sort(edgs.rbegin(), edgs.rend());
DSU dsu(n);
std::vector<std::pair<int, int>> res, ans;
for (auto &[w, x, y, id] : edgs) {
if (!dsu.join(x, y)) {
res.push_back({w, id});
}
}
std::sort(res.begin(), res.end());
i64 sum = 0;
for (auto &[w, i] : res) {
if (sum + w <= s) {
sum += w;
ans.push_back({i, w});
} else {
break;
}
}
std::cout << ans.size() << "\n";
for (auto &[i, w] : ans) std::cout << i << " ";
}
I. Bipartite Graph
题意
给你一个由 $n$ 个顶点组成的空无向图。每个顶点在任何时刻都有 $0$ 或 $1$ 两种颜色，因此每条边都连接着不同颜色的顶点。
查询有两种类型：
- 给您来自不同连接组件的两个顶点 $x$ 和 $y$ ：在图中添加一条边 $(x, y)$ ，并改变颜色以满足条件。
- 给您来自一个相连组件的两个顶点 $x$ 和 $y$ ：回答它们的颜色是否相同。
最初的图形是空的。
参考思路
考虑扩展域并查集，维护两点间颜色是否不能相同。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
F[find(x)] = find(y);
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
int shift = 0;
DSU dsu(2 * n);
while (m--) {
int op, a, b;
std::cin >> op >> a >> b;
a = (a + shift) % n;
b = (b + shift) % n;
if (op) {//
bool ok = !(dsu.find(a) == dsu.find(b + n) || dsu.find(a + n) == dsu.find(b));
std::cout << (ok ? "YES" : "NO") << "\n";
if (ok) shift = (shift + 1) % n;
} else {
assert(dsu.find(a) != dsu.find(b));
dsu.join(a, b + n);
dsu.join(a + n, b);
}
}
}
J. First Non-Bipartite Edge
题意
双向图是一种无向图，可以将其顶点分成两部分，这样，边只能连接不同部分的顶点。
在本题中，$m$ 条边被逐一添加到最初的空图中，该图有 $n$ 个顶点。您的任务是确定第一条边的索引，使得添加后的图形不是二方图。
由 $n$ 个顶点组成的空图是一个包含 $n$ 个顶点且没有边的图。
参考思路
和上题类似，扩展域并查集维护两点间颜色是否能够相同，找到第一次发生冲突的位置即可。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
F[find(x)] = find(y);
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
DSU dsu(2 * n), part(n);
for (int i = 1; i <= m; i++) {
int a, b;
std::cin >> a >> b;
a--; b--;
if (part.find(a) == part.find(b) && !(dsu.find(a) == dsu.find(b + n) || dsu.find(a + n) == dsu.find(b))) {
std::cout << i;
return;
} else {
dsu.join(a, b + n);
dsu.join(a + n, b);
part.join(a, b);
}
}
std::cout << -1;
}
Step 3
A. DSU with rollback
题意
在这个问题中，你必须实现带有回滚功能的 DSU。该数据结构应支持三种操作：
- 联合 $u$ $v$ " - 将包含 $u$ 和 $v$ 的两个集合联合起来，并输出当前不相交集合的数量。
- persist” - 创建一个检查点，结构体可以回滚到该检查点。
- 回滚”–回滚到最新的检查点，删除该点，并输出当前不相交集合的个数。
参考思路
回滚并查集板子，在普通并查集中添加一个栈来记录历史信息即可。
参考代码
struct DSU_maintain {
std::vector<int> F, siz;
int cnt;
std::stack<std::vector<std::pair<int, int>>> stk;//有效操作
// fx，fy
DSU(int n) : F(n), cnt(n), siz(n, 1) {
std::iota(F.begin(), F.end(), 0);
stk.push(std::vector<std::pair<int, int>>());
}
int find(int x) {
while (x != F[x]) {
x = F[x];
}
return x;
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int fx = find(x);
int fy = find(y);
if (siz[fx] > siz[fy]) {//siz 小的连到 siz 大的上
std::swap(fx, fy);
}
if (!ok) {
cnt--;
stk.top().push_back({fx, fy});
F[fx] = fy;
siz[fy] += siz[fx];
}
return !ok;
}
void maintain() {
stk.push(std::vector<std::pair<int, int>>());
}
void rollback() {
assert(stk.size());
for (auto &[x, y] : stk.top()) {
cnt++;
siz[y] -= siz[x];
F[x] = x; F[y] = y;
}
stk.pop();
}
};
void solve() {
int n, m;
std::cin >> n >> m;
DSU_maintain dsu(n);
while (m--) {
std::string s;
std::cin >> s;
if (s[0] == 'p') {
dsu.maintain();
} else if (s[0] == 'u') {
int x, y;
std::cin >> x >> y;
x--; y--;
dsu.join(x, y);
std::cout << dsu.cnt << "\n";
} else {
dsu.rollback();
std::cout << dsu.cnt << "\n";
}
}
}
B. Number of Connected Components on Segments
题意
给你一个有 $n$ 个顶点和 $m$ 条不定向边的图。请编写一个程序来处理形式为 $(l_j, r_j)$ 的 $k$ 查询： $j$ -th 查询的答案是，如果我们删除图中所有的边，但不包括索引为 $l_j$ 至 $r_j$ 的边，则连通部分的数量为多少。
这些查询应独立回答。换句话说，要回答 $j$ -th 查询，应该考虑一个有 $n$ 个顶点和 $r_j-l_j+1$ 条边的图。
参考思路
考虑莫队分块，将询问离线下来，以左端点为准划分到 $\sqrt m$ 个块中，对于每个块的询问，按右端点排序后，用可持久化并查集维护。
设当前块的左右下标 id 为 $[Block_l_i, Block_r_i)$
如果询问的左右端点都在当前块内，那么并查集设置检查点后暴力加边再统计，最后直接回滚，复杂度是 $O(\sqrt m)$ 的。
如果询问的右端点不在当前块内，那么我们先将 $[Block_r_i, r_j)$ （如果该询问是这个块的第一个，右端点不在当前块的询问）或 $[r_{j - 1}, r_j)$ （如果该询问不是当前块的第一个，右端点不在当前块的询问）中的边全部补充到并查集中，然后设置检查点，暴力添加完 $[l_j, Block_l_i)$ 中的边并统计后再回滚，复杂度也是 $O(\sqrt m)$ 的。
每个块内，排序，处理查询的总时间复杂度为 $O(n_i\log n_i + \sqrt m + n)$，总时间复杂度即为 $O(n\log n + m + n\sqrt m)$。
参考代码
struct DSU {
std::vector<int> F, siz, rnk;
int cnt;
std::stack<std::vector<std::array<int, 6>>> stk;//有效操作
// fx，fy，siz[fx]，siz[fy], rnk[fx], rnk[fy]
DSU(int n) : F(n), cnt(n), siz(n, 1), rnk(n, 0) {
std::iota(F.begin(), F.end(), 0);
stk.push(std::vector<std::array<int, 6>>());
}
int find(int x) {
while (x != F[x]) {
x = F[x];
}
return x;
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int fx = find(x);
int fy = find(y);
if (siz[fx] > siz[fy]) {//siz 小的连到 siz 大的上
std::swap(fx, fy);
}
// if (rnk[fx] > rnk[fy]) {//按rank合并
// std::swap(fx, fy);
// }
if (!ok) {
cnt--;
stk.top().push_back({fx, fy, siz[fx], siz[fy], rnk[fx], rnk[fy]});
F[fx] = fy;
siz[fy] += siz[fx];
if (rnk[fx] == rnk[fy]) rnk[fy]++;
}
return !ok;
}
void check() {
stk.push(std::vector<std::array<int, 6>>());
}
void rollback() {//回滚要逆序回滚
assert(stk.size());
std::reverse(stk.top().begin(), stk.top().end());
for (auto &[x, y, sizx, sizy, rnkx, rnky] : stk.top()) {
cnt++;
F[x] = x; F[y] = y;
siz[x] = sizx; siz[y] = sizy;
rnk[x] = rnkx; rnk[y] = rnky;
}
stk.pop();
}
};
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::pair<int, int>> edg(m);
for (auto &[x, y] : edg) (std::cin >> x >> y), x--, y--;
int m_ = std::sqrt(m);
// [l, r, idx]
std::vector<std::vector<std::array<int, 3>>> qry(m / m_);
int q;
std::cin >> q;
for (int i = 0; i < q; i++) {
int l, r;
std::cin >> l >> r;
l--; r--;
while (l / m_ >= qry.size()) qry.push_back(std::vector<std::array<int, 3>>());
qry[l / m_].push_back({l, r, i});
}
std::vector<int> ans(q, -1);
for (int blk = 0; blk < qry.size(); blk++) {
DSU dsu(n);
std::sort(qry[blk].begin(), qry[blk].end(), [&](const auto& a, const auto& b) {
return a[1] < b[1];
});
int R = (blk + 1) * m_ - 1;
for (auto &[l, r, idx] : qry[blk]) {
if (r < (blk + 1) * m_) {//暴力算完，直接回滚
dsu.check();
for (int i = l; i <= r; i++) dsu.join(edg[i].first, edg[i].second);
ans[idx] = dsu.cnt;
dsu.rollback();
} else {//一直从blk * m_ 开始向右push，直到 R = r
while (R < r) R++, dsu.join(edg[R].first, edg[R].second);
dsu.check();
int L = (blk + 1) * m_;
while (L > l) L--, dsu.join(edg[L].first, edg[L].second);
ans[idx] = dsu.cnt;
dsu.rollback();
}
}
}
for (auto &i : ans) {
assert(i != -1);
std::cout << i << "\n";
}
}
C. Dynamic Connectivity Offline
题意
给您一个空无向图，其中有 n 个顶点。您必须回答三种类型的查询：
"+ $u$" -- 在图中添加一条无向边 $u$ - $v$。
"- $u$ $v$" -- 从图形中删除一条无向边 $u$ - $v$。
"?" - 计算图中相连组件的数量。
参考思路
考虑将所有询问离线下来，对于每条边，以时间段的形式记录其在整个时间轴上出现的时间。然后用线段树分治处理每个时间点处的联通性，处理询问即可。
参考代码
struct DSU_maintain {
std::vector<int> F, siz, rnk;
int cnt;
std::stack<std::vector<std::array<int, 6>>> stk;//有效操作
// fx，fy，siz[fx]，siz[fy], rnk[fx], rnk[fy]
DSU_maintain() {}
DSU_maintain(int n) : F(n), siz(n, 1), rnk(n, 0), cnt(n) {
std::iota(F.begin(), F.end(), 0);
stk.push(std::vector<std::array<int, 6>>());
}
int find(int x) {
while (x != F[x]) {
x = F[x];
}
return x;
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int fx = find(x);
int fy = find(y);
// if (siz[fx] > siz[fy]) {//siz 小的连到 siz 大的上
// std::swap(fx, fy);
// }
if (rnk[fx] > rnk[fy]) {//按rank合并
std::swap(fx, fy);
}
if (!ok) {
cnt--;
stk.top().push_back({fx, fy, siz[fx], siz[fy], rnk[fx], rnk[fy]});
F[fx] = fy;
siz[fy] += siz[fx];
if (rnk[fx] == rnk[fy]) rnk[fy]++;
}
return !ok;
}
void maintain() {
stk.push(std::vector<std::array<int, 6>>());
}
void rollback() {//回滚要逆序回滚
if (stk.size() == 0) {
1 / stk.size();
}
//assert(stk.size());
std::reverse(stk.top().begin(), stk.top().end());
for (auto &[x, y, sizx, sizy, rnkx, rnky] : stk.top()) {
cnt++;
F[x] = x; F[y] = y;
siz[x] = sizx; siz[y] = sizy;
rnk[x] = rnkx; rnk[y] = rnky;
}
stk.pop();
}
};
struct SGT_conquer {
#define lson (p<<1)
#define rson (p<<1|1)
std::vector<std::vector<std::pair<int, int>>> edg;
std::set<int> qry;
std::vector<int> ans;
int n, m;
DSU_maintain dsu;
SGT_conquer(int n, int m) : n(n), m(m), dsu(m) {//时间为n，节点有m个
edg.resize(4 << std::__lg(n));
}
//在时间点处添加询问
void modify_qry(int p, int l, int r, int x) {
if (x < l || x >= r) return;
if (r - l == 1) {
qry.insert(p);
return;
}
int m = (l + r) >> 1;
if (x < m) modify_qry(lson, l, m, x);
else modify_qry(rson, m, r, x);
}
//在时间段中添加边
void modify_edg(int p, int l, int r, int x, int y, std::pair<int, int> k) {
if (x >= y) return;
if (l >= y || r <= x) return;
if (x <= l && r <= y) {
edg[p].push_back(k);
return;
}
int m = (l + r) >> 1;
if (x < m) modify_edg(lson, l, m, x, y, k);
if (y > m) modify_edg(rson, m, r, x, y, k);
}
void conquer(int p, int l, int r) {
if (l >= r) return;
if (r - l == 1) {
dsu.maintain();
for (auto &[x, y] : edg[p]) {
dsu.join(x, y);
}
if (qry.count(p)) {
ans.push_back(dsu.cnt);
}
dsu.rollback();
return;
}
dsu.maintain();
for (auto &[x, y] : edg[p]) {
dsu.join(x, y);
}
int m = (l + r) >> 1;
conquer(lson, l, m);
conquer(rson, m, r);
dsu.rollback();
}
};
void solve() {
int n, m;
std::cin >> n >> m;
//if (m == 0) return;
std::map<std::pair<int, int>, int> mpL;//记录起始时间
std::set<std::array<int, 5>> qry;//[l, r, op, x, y]，实际上存的是 [l, r)
for (int i = 0; i < m; i++) {
char op;
std::cin >> op;
if (op == '?') {
qry.insert({i, i + 1, 0, -10, -10});
} else if (op == '+') {
int x, y; std::cin >> x >> y; x--; y--; if (x > y) std::swap(x, y);
mpL[{x, y}] = i;
} else {
int x, y; std::cin >> x >> y; x--; y--; if (x > y) std::swap(x, y);
qry.insert({mpL[{x, y}], i + 1, 1, x, y});
mpL.erase({x, y});
}
}
for (auto &[p, t] : mpL) {
auto &[x, y] = p;
qry.insert({t, m, 1, x, y});
}
SGT_conquer sgt(m, n);//时间，点集大小
for (auto &[l, r, op, x, y] : qry) {
if (op == 1) {
sgt.modify_edg(1, 0, m, l, r, std::make_pair(x, y));
} else {
sgt.modify_qry(1, 0, m, l);
}
}
sgt.conquer(1, 0, m);
for (auto &i : sgt.ans) std::cout << i << "\n";
}
Introduction to Graphic Theory
Step 1
A. Undirected Graph?
题意
给你两个数字 $n$ 和 $m$ 以及一个由 $m$ 对整数组成的列表（一对整数中的两个元素都在 $1$ 和 $n$ 之间）。检查给定的整数对列表是否是某个无向图的正确边列表（图中不应有循环或多条边）。
参考思路
直接将所有非自环边全部按小标号在前的顺序存到 set 中，再判断 set 大小是否等于 $m$ 即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::set<std::pair<int, int>> s;
for (int i = 0; i < m; i++) {
int x, y;
std::cin >> x >> y;
if (x != y) {
if (x > y) std::swap(x, y);
s.insert({x, y});
}
}
std::cout << (s.size() == m ? "YES" : "NO") << "\n";
}
B. Vertex Degrees
题意
给你一个无向图，并列出了它的边。请找出图中所有顶点的度数。
参考思路
直接开一个度数数组，然后每次加边，直接将对应节点的度数加一即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> d(n);
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
d[x]++; d[y]++;
}
for (auto &i : d) std::cout << i << " "; std::cout << "\n";
}
C. Type of Subsequence
题意
给你一个无向图和一系列顶点。该图由其边的列表给出。请判断给定的顶点序列是否是：
- 一个简单循环、
- 一个循环
- 简单路径
- 一条路径
- 或都不是。
参考思路
很无聊的定义题，注意特判只有一个点的图是 “none”。
参考代码
void solve() {
int n, m, k;
std::cin >> n >> m >> k;
std::vector<int> seq(k);
for (auto &i : seq) (std::cin >> i), i--;
std::vector edg(n, std::set<int>());
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
edg[x].insert(y);
edg[y].insert(x);
}
if (k == 2 && (seq.front() == seq.back())) {
//assert(0);
std::cout << "none\n";
return;
}
for (int i = 0; i < k - 1; i++) {//如果不连通
if (!edg[seq[i]].contains(seq[i + 1])) {
std::cout << "none\n";
return;
}
}
std::set<int> d;
for (auto &i : seq) d.insert(i);
if (seq.front() == seq.back()) {//是环
if (d.size() == k - 1) std::cout << "simple ";
std::cout << "cycle\n";
} else {
if (d.size() == k) std::cout << "simple ";
std::cout << "path\n";
}
}
D. Connectivity Components?
题意
给你一个无向图，图中有一个边列表和一组顶点。请检查给定的顶点是否正好构成给定图形的一个或多个连通部分。换句话说，给定的顶点必须是某个连接部分子集的顶点。
参考思路
问你，给定点集是否恰好是 原始图的几个联通分量的并集。
考虑用带权并查集维护联通块大小，然后将点集涉及的联通分量全存入 set 中去重，最后判断 set 中的联通分量大小和是否为 $k$即可。
参考代码
struct DSU {
std::vector<int> F, siz;
DSU(int n) : F(n), siz(n, 1) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int fx = find(x);
int fy = find(y);
if (fx ^ fy) {
F[fx] = fy;
siz[fy] += siz[fx];
}
return !ok;
}
};
void solve() {
int n, m, k;
std::cin >> n >> m >> k;
DSU dsu(n + 1);
std::vector<int> a(k);
for (auto &i : a) std::cin >> i;
while (m--) {
int x, y;
std::cin >> x >> y;
dsu.join(x, y);
}
std::set<int> s;
for (auto &i : a) s.insert(dsu.find(i));
int cnt = 0;
for (auto &i : s) cnt += dsu.siz[i];
std::cout << (cnt == k ? "YES" : "NO") << "\n";
}
E. Tree Degrees
题意
给你一个由 $n$ 个元素组成的数组 $d$ 。请检查是否存在一棵树，它的度数数组与数组 $d$ 匹配。
度数数组 - 这样的数组 $d$ ，其中每个顶点 $u$ 的 $d_u$ 值等于顶点 $u$ 的度数。
参考思路
分类讨论
- 当 $n = 1$ 时，判断 $d[0] == 0$ 即可；
- 当 $n \ne 1$ 时，先判断度数和是否等于， $2(n - 1)$ 再判断度数序列中是否存在 0 度数节点即可。
参考代码
void solve() {
int n;
std::cin >> n;
std::vector<int> d(n);
for (auto &i : d) std::cin >> i;
if (n == 1) {
std::cout << (d[0] == 0 ? "YES" : "NO") << "\n";
return;
}
if (std::accumulate(d.begin(), d.end(), 0ll) != 2 * (n - 1)) {
std::cout << "NO\n";
return;
}
for (auto &i : d) if (!i) {
std::cout << "NO\n";
return;
}
std::cout << "YES\n";
}
F. Graph by Array of Degrees
题意
给您一个数组，其中包含某个无向图的度数。用给定数组构建任意无向图。
图中不能有循环或多条边。
图中的顶点从 $1$ 开始编号。
参考思路
暴力模拟，将度数从大到小排序放入优先队列中，每次取出一个节点后，暴力向后取出 $d[i]$ 个节点，并连边，连完边后将 $d[j] > 0$ 的点加回队列中。时间复杂度 $O(n^2)$
参考代码
void solve() {
int n;
std::cin >> n;
std::vector<int> d(n);
for (auto &i : d) std::cin >> i;
std::priority_queue<std::pair<int, int>> q;
std::cout << std::accumulate(d.begin(), d.end(), 0ll) / 2 << "\n";
for (int i = 0; i < n; i++) {
if (d[i]) q.push({d[i], i + 1});
}
while (q.size()) {
auto [d_, now] = q.top(); q.pop();
std::vector<Z> res;
while (d_--) {
auto [d__, nxt] = q.top(); q.pop();
std::cout << now << " " << nxt << "\n";
if (--d__) {
res.push_back({d__, nxt});
}
}
for (auto &p : res) q.push(p);
}
}
G. Graph by Set of Degrees
题意
给出了一个无向图的度集。从给定的集合构造一个顶点数最少的无向图。
图表中不能有循环或多边
图的顶点从一开始编号
参考思路
考虑先想办法构造一个合法度数序列，不难发现一定有解，比如说由 $n$ 个完全图取并集，但是题目要求点数最少，所以不能直接这样构造。
手玩样例后我们不难发现，最少的点数似乎就是最大数字加一。考虑下面这种构造方式：
将度数序列从大到小排序后，设三个指针，一个（$i$）指向原度数集数组的头元素，一个（$j$）指向尾元素，再设一个初始值均为 $0$ 的，长为 $\max a_i + 1$ 的度数数组，用一个指针（$k$）指向数组的头元素。
当左指针指向 $x$，右指针指向 $y$ 时，将度数数组中，$[k, k + y - 1]$ 区间的元素均加上 $x$，将 $[k + y, k + x]$ 区间的元素均加上 $y$，然后 $i$ 指针右移一位，$j$ 指针左移一位，$k$ 指针右移 $y$ 位，知道 $i > j$ 时停止构造。
此时构造出来的度数序列就是一个合法的，点数最小的度数序列。接着再利用这个度数序列直接暴力 $O(n^2\log n)$ 构造相应的图即可。
时间复杂度：$O(n^2\log n)$
参考代码
using Z = std::pair<int, int>;
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
std::sort(a.rbegin(), a.rend());
std::vector<int> d(a[0] + 1);
int i = 0, j = n - 1, k = 0;
while (i <= j) {
while (a[j]) {
for (int l = k + 1; l <= k + a[i]; l++) d[l]++;
for (int l = i + 1; l <= j; l++) a[l]--;
d[k++] += a[i];
a[i]--;
}
a[i] = 0;
while (i < n && !a[i]) i++;
while (j >= 0 && !a[j]) j--;
//for (auto &i : d) std::cout << i << ' '; std::cout << '\n';
}
//for (auto &i : d) std::cout << i << ' ';
n = d.size();// F 题代码照搬即可
std::priority_queue<Z> q;
std::cout << n << ' ' << std::accumulate(d.begin(), d.end(), 0ll) / 2 << "\n";
for (int i = 0; i < n; i++) {
if (d[i]) q.push({d[i], i + 1});
}
while (q.size()) {
auto [d_, now] = q.top(); q.pop();
std::vector<Z> res;
while (d_--) {
auto [d__, nxt] = q.top(); q.pop();
std::cout << now << " " << nxt << "\n";
if (--d__) {
res.push_back({d__, nxt});
}
}
for (auto &p : res) q.push(p);
}
}
Step 2
A. Number of Vertices
题意
您将获得一个非负整数 $m$ 。打印无向图中具有精确 $m$ 边的最小顶点数。
参考思路
定义题，用完全图贪心二分即可。
参考代码
void solve() {
int n;
std::cin >> n;
i64 l = 0, r = n + 1;
while (l <= r) {
i64 mid = (l + r) / 2;
if (mid * (mid - 1) / 2 >= n) r = mid - 1;
else l = mid + 1;
}
std::cout << r + 1 << "\n";
}
B. Regular Graph
题意
给定两个整数 $n$ 和 $k$ 。构建一个具有 $n$ 顶点的 $k$ - 正则无向图，或者说它不存在。
参考思路
定义题，$k$-正则图，即每个点度数均为 $k$ 的图，先特判 $nk$ 是否为偶数，以及 $n$ 是否大于 $k$。（定义）
如果均满足以上条件，那么一定存在 $k$-正则图。
当 $k = 1$ 时，直接构造 $n$ 元环并输出即可。
当 $k \ne 1$ 时，分奇偶两类构造即可。当 $k$ 为偶数时，考虑类似 $n$ 元环的构造，每隔 $0$ 个节点连一次边，每隔 $1$ 个节点连一次边，…，每隔 $\frac{k}{2} - 1$ 个节点连一次边，即可保证最终每个点的度数均为 $k$；当 $k$ 为 奇数时，$n$ 必为偶数，在上述构造方法中，添加一种 每隔 $\frac{n}{2} - 1$ 个节点连一次边（对位连边）的连边方式即可。
参考代码
void solve() {
int n, k;
std::cin >> n >> k;
if (n * k & 1 || k >= n) {
std::cout << "NO\n";
return;
}
std::set<std::pair<int, int>> edg;
auto insert = [&](int x, int y) {
if (x > y) std::swap(x, y);
edg.insert({x, y});
};
if (k == 1) {
for (int i = 0; i < n; i += 2) {
insert(i, i + 1);
}
} else {
if (k & 1) {
for (int i = 1; i <= k / 2; i++) {
for (int j = 0; j < n; j++) {
insert(j, (j + i) % n);
}
}
for (int i = 0; i < n; i++) {
insert(i, (i + n / 2) % n);
}
} else {//偶数
for (int i = 1; i <= k / 2; i++) {
for (int j = 0; j < n; j++) {
insert(j, (j + i) % n);
}
}
}
}
std::vector<int> d(n);
for (auto &[x, y] : edg) {
d[x]++; d[y]++;
}
std::set<int> ds;
for (auto &i : d) ds.insert(i);
assert(ds.size() == 1 && *ds.begin() == k);
std::cout << "YES\n";
std::cout << edg.size() << "\n";
for (auto &[x, y] : edg) {
std::cout << x + 1 << " " << y + 1 << "\n";
}
}
C. Empty and Complete
题意
通过给出一个无向图的边列表，可以得到一个无向图。检查给定的图是最多一个空图和最多一个完整图的并。
参考思路
非常抽象的定义题，在此题中，空图的定义为，不包含任何边的图，所以只给一个点集也是空图。
因此，我们只需要判断原图中联通块大小不为 1 的数量是否小于等于 1，等于 1 时，通过那个联通块中的边数和点数，判断是否是一个完全图即可。
参考代码
struct DSU {
std::vector<int> F, siz, val;
int cnt;
DSU(int n) : F(n), siz(n, 1), val(n, 0), cnt(n) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
int fx = find(x), fy = find(y);
if (fx ^ fy) {
F[fx] = fy;
siz[fy] += siz[fx];
val[fy] += val[fx];
cnt--;
}
val[fy]++;
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
DSU dsu(n);
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
dsu.join(x, y);
}
int cnt = 0;//计数空点
for (int i = 0; i < n; i++) {
cnt += (dsu.siz[dsu.find(i)] == 1);
}
if (dsu.cnt - cnt > 1) {
std::cout << "NO\n";
} else if (dsu.cnt - cnt == 0) {
std::cout << "YES\n";
} else {
bool ok = 0;
for (int i = 0; i < n; i++) {
int u = dsu.find(i);
if (dsu.siz[u] != 1) {
ok = (dsu.val[u] == (1ll * dsu.siz[u] * (dsu.siz[u] - 1) / 2));
break;
}
}
std::cout << (ok ? "YES" : "NO") << "\n";
}
}
D. Complete Components
题意
给出一个由 $n$ 个顶点和 $m$ 个边组成的无向图。给定图的每个连接元件 (图论) 都是一个完整的子图。在给定的图中查找连接组件的数目。
参考思路
并查集直接做即可。
参考代码
struct DSU {
std::vector<int> F;
DSU(int n) : F(n + 1) {
std::iota(F.begin(), F.end(), 0);
}
int find(int x) {
return F[x] == x ? F[x] : F[x] = find(F[x]);
}
bool join(int x, int y) {
bool ok = (find(x) == find(y));
F[find(x)] = find(y);
return !ok;
}
};
void solve() {
int n, m;
std::cin >> n >> m;
DSU dsu(n);
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
n -= dsu.join(x, y);
}
std::cout << n << "\n";
}
Step 3
A. Sources and Sinks
题意
通过弧列表给出一个有向图。
有向图的源是一个顶点 $u$ ，其中没有顶点 $v$ ，因此 $v$ 与 $u$ 相邻 (在 $u$ 中没有进入的弧)。
有向图的汇是一个顶点 $u$ ，该顶点没有顶点 $v$ ，因此 $u$ 与 $v$ 相邻 (从 $u$ 出没有弧)。
计算给定图的源和汇的数目。
参考思路
按照题意统计出度和入度，统计出度为 0 的点以及入度为 0 的点数即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> in(n), out(n);
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
out[x]++; in[y]++;
}
int sou = 0, sin = 0;
for (auto &i : in) sou += (i == 0);
for (auto &i : out) sin += (i == 0);
std::cout << sou << " " << sin << "\n";
}
B. Functional Graph
题意
通过弧列表给出一个有向图。在一个步骤中，您可以在图表中添加或删除任何弧。
如果每个顶点的输出度为 $1$ ，则图称为泛函图。
找出从给定的图中得到一个函数图所需的最小移动次数。
参考思路
按照题意记录点出度，贪心删边即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> out(n);
int cnt = n;
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
if (out[x]) cnt++;
else out[x] = 1, cnt--;
}
std::cout << cnt << "\n";
}
C. Equal Degrees
题意
给定两个整数 $d_1$ 和 $d_2$ 。根据弧的个数，构造一个最小的非空有向图，使得每个顶点的传出度为 $d_1$ ，传入度为 $d_2$ 。
参考思路
直接贪心构造一个邻接矩阵全 1 的有向图即可。
参考代码
void solve() {
int a, b;
std::cin >> a >> b;
if (a ^ b) {
std::cout << "NO\n";
return;
}
std::cout << "YES\n";
std::cout << a << " " << a * a << "\n";
for (int i = 1; i <= a; i++) {
for (int j = 1; j <= a; j++) {
std::cout << i << " " << j << "\n";
}
}
}
D. Second Neighbors
题意
通过弧列表给出一个有向图。对于每个顶点 $v$ 按升序输出与至少一个与 $v$ 相邻的顶点相邻的所有顶点。
参考思路
复杂度够，直接按题意模拟即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector edg(n, std::vector<int>());
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
edg[x].push_back(y);
}
for (int i = 0; i < n; i++) {
std::set<int> s;
for (auto &nxt : edg[i]) {
for (auto &nnxt : edg[nxt]) {
//if (nnxt == i) continue;
s.insert(nnxt);
}
}
for (auto &j : s) std::cout << j + 1 << " ";
std::cout << "\n";
}
}
Step 4
A. Adjacency Matrix
题意
你通过一个无向图的边列表得到一个无向图，构造给定图的邻接矩阵。
参考思路
直接按题意模拟即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector edg(n, std::vector<int>(n));
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
edg[x][y] = edg[y][x] = 1;
}
for (auto &v : edg) {
for (auto &i : v) {
std::cout << i << " ";
}
std::cout << "\n";
}
}
B. Adjacency Matrix?
题意
您将得到一个数字 $n$ 和一个大小为 $n \times n$ 的二进制 (由零和一组成) 矩阵。检查给定的矩阵是否是某个无向图的邻接矩阵，如果是，输出这个图的顶点度数。
参考思路
判断矩阵是否对称，且主对角线均为 0 即可。输出度数时，输出矩阵每行的和即可。
参考代码
void solve() {
int n;
std::cin >> n;
std::vector edg(n, std::vector<int>(n));
for (auto &v : edg) {
for (auto &i : v) {
std::cin >> i;
}
}
bool ok = 1;
for (int i = 0; i < n; i++) {
ok &= (!edg[i][i]);
for (int j = i + 1; j < n; j++) {
ok &= (edg[i][j] == edg[j][i]);
}
}
if (!ok) {
std::cout << "NO\n";
return;
}
std::cout << "YES\n";
for (auto &v : edg) std::cout << std::accumulate(v.begin(), v.end(), 0) << " ";
std::cout << "\n";
}
C. Adjacency Lists
题意
给你一个无向图的邻接矩阵，根据给定的矩阵建立邻接列表。
参考思路
按照题意模拟即可。
参考代码
void solve() {
int n;
std::cin >> n;
std::vector edg(n, std::vector<int>(n));
for (auto &v : edg) {
for (auto &i : v) {
std::cin >> i;
}
}
for (auto &v : edg) {
for (int i = 0; i < n; i++) {
if (v[i]) std::cout << i + 1 << " ";
}
std::cout << "\n";
}
}
D. Two Edges
题意
通过给出一个无向图的边列表，可以得到一个无向图。查找图中具有一个共同端点的边对数，并且其他两个端点之间的距离正好为 $2$ 。
如果在第一个选项中存在一个边，但在第二个选项中没有，则认为两个选项是不同的。
参考思路
考虑每个点，如果不限制与其相邻的两点间是否有连边，那么以每个点为中心，共有 $ans = \sum \frac{d_i(d_i - 1)}{2}$ 种方案。不难发现需要剔除的不合法方案是三元环，所以只需再跑一遍无向图三元环计数，算出三元环数量 $cnt$ 后，$ans - 3cnt$ 即为所求答案。
时间复杂度：$O(m\sqrt m)$
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> d(n);
std::vector edg(n, std::vector<int>());
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
edg[x].push_back(y);
edg[y].push_back(x);
d[x]++; d[y]++;
}
i64 ans = 0;
for (auto &i : d) {
ans += 1ll * i * (i - 1) / 2;
}
std::vector redg(n, std::vector<int>());
for (int i = 0; i < n; i++) {
for (auto &nxt : edg[i]) {
if (d[i] > d[nxt]) {
redg[i].push_back(nxt);
} else if (d[i] < d[nxt]) {
redg[nxt].push_back(i);
} else if (i > nxt) {
redg[i].push_back(nxt);
} else {
redg[nxt].push_back(i);
}
}
}
for (auto &v : redg) {
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
}
int cnt = 0;
std::vector<int> vis(n, -1);
for (int u = 0; u < n; u++) {
for (auto &v : redg[u]) {
vis[v] = u;
}
for (auto &v : redg[u]) {
for (auto &w : redg[v]) {
cnt += (vis[w] == u);
}
}
}
std::cout << ans - 3 * cnt << "\n";
}
E. Complete Subgraphs
题意
通过给出一个无向图的边列表，可以得到一个无向图。查找选择形成 $K_4$ 的四个顶点的方法数。
如果有这样一个顶点存在于第一种方式中，但不存在于第二种方式中，则有两种方式被认为是不同的。
参考思路
直接无向图三元环计数，在找到三元环后，通过 bitset 暴力统计与当前三个点间均有连边的点数即可。
时间复杂度：$O(\frac{nm\sqrt m}{64})$
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
if (m < 6) {
while (m--) {
int x, y;
std::cin >> x >> y;
}
std::cout << 0 << "\n";
return;
}
std::vector<int> d(n);
std::vector<std::bitset<4000>> adj(n);
std::vector edg(n, std::vector<int>());
while (m--) {
int x, y;
std::cin >> x >> y;
x--; y--;
edg[x].push_back(y);
adj[x][y] = adj[y][x] = 1;
d[x]++; d[y]++;
}
std::vector redg(n, std::vector<int>());
for (int i = 0; i < n; i++) {
for (auto &nxt : edg[i]) {
if (d[i] > d[nxt]) {
redg[i].push_back(nxt);
} else if (d[i] < d[nxt]) {
redg[nxt].push_back(i);
} else if (i > nxt) {
redg[i].push_back(nxt);
} else {
redg[nxt].push_back(i);
}
}
}
i64 cnt = 0;
std::vector<int> vis(n, -1);
for (int u = 0; u < n; u++) {
for (auto &v : redg[u]) {
vis[v] = u;
}
for (auto &v : redg[u]) {
for (auto &w : redg[v]) {
if (vis[w] == u) {
cnt += (adj[u] & adj[v] & adj[w]).count();
}
}
}
}
std::cout << cnt / 4 << "\n";
}
Two Pointers Method
Step 1
A. Merging Arrays
题意
给你两个数组，按非递减顺序排序。将它们合并成一个排序的数组。
参考思路
双指针，当两边指针均未到达数组尾部时，对比两个指针所指向的数的大小，选择输出最小的数即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n), b(m);
for (auto &i : a) std::cin >> i;
for (auto &i : b) std::cin >> i;
int i = 0, j = 0;
while (i != n || j != m) {
if (i == n || j == m) {
if (i == n) std::cout << b[j++] << " ";
else std::cout << a[i++] << " ";
} else {
if (a[i] < b[j]) std::cout << a[i++] << " ";
else std::cout << b[j++] << " ";
}
}
}
B. Number of Smaller
题意
给您两个数组，按非递减顺序排序。对于第二个数组中的每个元素，找到第一个数组中严格小于它的元素数。
参考思路
双指针维护，对于第二个数组中的每个元素，找到第一个大于等于其的数的下标，输出即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n), b(m);
for (auto &i : a) std::cin >> i;
for (auto &i : b) std::cin >> i;
int i = 0, j = 0;
while (j < m) {
while (i < n && a[i] < b[j]) i++;
std::cout << i << " ";
j++;
}
}
C. Number of Equal
题意
给您两个数组 $a$ 和 $b$ ，按非递减顺序排序。查找其中 $a_i = b_j$ 的对 $(i, j)$ 的数目。
参考思路
双指针维护统计，具体实现细节看代码吧。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n), b(m);
for (auto &i : a) std::cin >> i;
for (auto &i : b) std::cin >> i;
i64 sum = 0;
int i = 0, j = 0;
while (i < n && j < m) {
while (i < n && j < m && a[i] != b[j]) {
while (j < m && i < n && a[i] < b[j]) i++;
while (i < n && j < m && a[i] > b[j]) j++;
}
if (!(i < n && j < m)) break;
int res = a[i];
int cnta = 0, cntb = 0;
while (i < n && a[i] == res) cnta++, i++;
while (j < m && b[j] == res) cntb++, j++;
sum += 1ll * cnta * cntb;
}
std::cout << sum;
}
Step 2
A. Segment with Small Sum
题意
给定一个由 $n$ 个整数 $a_i$ 组成的数组。如果数组中 $a[l..r]$ ( $1\le l\le r\le n$ )段的元素之和最多为 $s$ ，那么这段数组就是好数组。你的任务是找出最长的良好线段。
参考思路
直接双指针滑动窗口，维护区间和小于 $s$ 的最长段即可。
参考代码
void solve() {
i64 n, s;
std::cin >> n >> s;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
int i = 0;
i64 sum = 0, ans = 0;
for (int j = 0; j < n; j++) {
sum += a[j];
while (sum > s) sum -= a[i++];
ans = std::max<int>(ans, j - i + 1);
}
std::cout << ans;
}
B. Segment with Big Sum
题意
给定一个由 $n$ 个整数 $a_i$ 组成的数组。假设该数组的 $a[l..r]$ 段（ $1\le l\le r\le n$ ）中的元素之和至少为 $s$ ，那么该段就是好数组。( $1\le l\le r\le n$ )，如果这段上的元素之和至少为 $s$ ，那么这段就是好的。你的任务是找出最短的良好线段。
参考思路
和上题类似，双指针滑动窗口，维护区间和大于等于 $s$ 的最小段长度即可。
参考代码
void solve() {
i64 n, s;
std::cin >> n >> s;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
int i = 0, ans = n + 1;
i64 sum = 0;
for (int j = 0; j < n; j++) {
sum += a[j];
while (sum - a[i] >= s) sum -= a[i++];
if (sum >= s) ans = std::min(ans, j - i + 1);
}
std::cout << (ans == n + 1 ? -1 : ans);
}
C. Number of Segments with Small Sum
题意
给定一个由 $n$ 个整数 $a_i$ 组成的数组。假设数组 $a[l..r]$ ( $1\le l\le r\le n$ )中的元素之和最多为 $s$ ，那么这个数组中的 $a[l..r]$ ( $1\le l\le r\le n$ )就是好数组。你的任务是找出好线段的数量。
参考思路
和上题类似，双指针滑动窗口，维护区间和小于等于 $s$，每新增一个元素，维护完左端点后，直接在答案中增加区间长度即可（可以理解为，以当前元素为右端点，向左共有 $r - l + 1$ 个区间，均满足要求）
参考代码
void solve() {
i64 n, s;
std::cin >> n >> s;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
i64 cnt = 0;
i64 sum = 0;
int i = 0;
for (int j = 0; j < n; j++) {
sum += a[j];
while (sum > s) sum -= a[i++];
cnt += (j - i + 1);
}
std::cout << cnt;
}
D. Number of Segments with Big Sum
题意
给定一个由 $n$ 个整数 $a_i$ 组成的数组。假设数组 $a[l..r]$ ( $1\le l\le r\le n$ )的元素之和至少为 $s$ ，那么这个数组的 $a[l..r]$ ( $1\le l\le r\le n$ ) 段就是好数段。你的任务是找出好线段的数量。
参考思路
和上题类似，只不过统计答案时，修改的贡献变成 左端点的下标（即，以当前位置为右端点，区间左端点以前的任何点作为右端点均可行）。
参考代码
void solve() {
i64 n, s;
std::cin >> n >> s;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
i64 cnt = 0;
i64 sum = 0;
int i = 0;
for (int j = 0; j < n; j++) {
sum += a[j];
while (sum >= s) sum -= a[i++];
cnt += i;
}
std::cout << cnt;
}
E. Segments with Small Set
题意
给定一个由 $n$ 个整数 $a_i$ 组成的数组。我们假设，如果数组 $a[l..r]$ ( $1\le l\le r\le n$ ) 的某一段上的唯一元素不超过 $k$ ，那么这段就是好数组。你的任务是找出不同的好线段的数量。
参考思路
双指针滑动窗口，开个map维护统计区间本质不同数的数量即可。
参考代码
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
std::map<int, int> cnt;
i64 ans = 0;
int i = 0;
for (int j = 0; j < n; j++) {
cnt[a[j]]++;
while (cnt.size() > k) if (--cnt[a[i++]] == 0) cnt.erase(a[i - 1]);
ans += (j - i + 1);
}
std::cout << ans;
}
F. Segments with Small Spread
题意
给定一个由 $n$ 个整数 $a_i$ 组成的数组。假设数组 $a[l..r]$ 中的一段（ $1\le l\le r\le n$ ）是好的。( $1\le l\le r\le n$ )，如果这段数组中最大元素和最小元素的差最多为 $k$ ，那么这段数组就是好数组。你的任务是找出不同良好线段的数量。
参考思路
和上题类似，用map维护区间极差小于等于 $k$ 即可。
参考代码
void solve() {
i64 n, k;
std::cin >> n >> k;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
i64 ans = 0;
int i = 0;
std::multiset<i64> s;
for (int j = 0; j < n; j++) {
s.insert(a[j]);
while (*s.rbegin() - *s.begin() > k) s.extract(a[i++]);
ans += (j - i + 1);
}
std::cout << ans;
}
G. Coprime Segment
题意
给定一个由 $n$ 个整数 $a_i$ 组成的数组。如果数组 $a[l..r]$ ( $1\le l\le r\le n$ )中所有数字的 GCD 都是 $1$ ，那么这个数组中的一段 $a[l..r]$ ( $1\le l\le r\le n$ ) 就是好数组。你的任务是找出最短的良好数段。
参考思路
和上题类似，用ST表维护区间gcd即可。
参考代码
struct ST {//静态RMQ
int n;
std::vector<std::vector<i64>> f;
void load(std::vector<i64> &a) {
n = a.size();
f = std::vector<std::vector<i64>>(n, std::vector<i64>(std::log2(n) + 2));
for (int i = 0; i < n; i++) f[i][0] = a[i];
}
void work() {
for (int j = 1; j < std::log2(n) + 1; j++) {
for (int i = 0; i < n - (1 << j) + 1; i++) {
f[i][j] = std::gcd(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}
i64 query(int l, int r) {//左闭右开
r--;
if (l > r) return 0;//一般用不到
int s = std::log2(r - l + 1);
return std::gcd(f[l][s], f[r - (1 << s) + 1][s]);
}
};
void solve() {
int n;
std::cin >> n;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
ST st;
st.load(a);
st.work();
int ans = n + 1;
int i = 0;
for (int j = 0; j < n; j++) {
while (st.query(i + 1, j + 1) == 1) i++;
if (st.query(i, j + 1) == 1) ans = std::min(ans, j - i + 1);
}
std::cout << (ans == n + 1 ? -1 : ans);
}
Step 3
A. Looped Playlist
题意
米沙通过播放器听音乐，他的播放列表由 $n$ 首歌组成，这些歌曲按照特定顺序播放。最后一首歌结束后，第一首歌开始播放。每首歌都有自己的特点，积极性 $a_i$ ，由整数给出。听完 $i_th$ 歌曲后，米莎的情绪上升了 $a_i$ 。
米沙可以开始聆听任意一首歌曲，也可以连续聆听任意数量的歌曲，同时他可以多次聆听某些歌曲。
如果米沙听完歌曲后心情至少增加了 $p$ ，他就会感到开心。他希望听的歌曲越少越好。帮助他选择要开始听的歌和要听的歌曲数量，让他感到快乐。
参考思路
考虑到可能存在，即使全部听完，也不可能达到 $p$ 的情况，即答案可能需要经过多次循环播放，我们需要预处理权值总和，判断至少需要循环几次。然后再将权值数组复制一份，拼接到原数组后面求一遍前缀和，最后跑一遍 $n^2$ 的双指针暴力统计最短的剩余所需区间长度，更新答案即可。
参考代码
void solve() {
i64 n, s;
std::cin >> n >> s;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
std::vector<i64> pre(2 * n + 1);
i64 sum = std::accumulate(a.begin(), a.end(), 0ll);
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + a[i - 1];
}
for (int i = 1; i <= n; i++) {
pre[i + n] = pre[i - 1 + n] + a[i - 1];
}
i64 ans = s / sum * n;
s %= sum;
if (s == 0) {
std::cout << 1 << " " << ans;
return;
}
int mi = 2 * n;
int idx = 1;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= 2 * n; j++) {
if (pre[j] - pre[i - 1] >= s) {
if (mi > j - i + 1) {
mi = j - i + 1;
idx = i;
}
break;
}
}
}
std::cout << idx << " " << ans + mi;
}
B. Total Length
题意
给定一个由 $n$ 个整数 $a_i$ 组成的数组。如果数组 $a[l..r]$ ( $1\le l\le r\le n$ )中的元素之和最多为 $s$ ，那么这个数组的 $a[l..r]$ ( $1\le l\le r\le n$ )段就是好数段。你的任务是找出所有好线段的长度之和。
参考思路
和前面某题类似，不过要求长度和，所以我们只需在双指针滑动窗口的维护过程中，将答案更新方式改成，加上 $\frac{(r - l + 1)(r - l)}{2}$ 即可。
参考代码
i64 calc(int x) {
return 1ll * x * (x + 1) / 2;
}
void solve() {
i64 n, s;
std::cin >> n >> s;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
i64 ans = 0;
i64 sum = 0;
int i = 0;
for (int j = 0; j < n; j++) {
sum += a[j];
while (sum > s) sum -= a[i++];
//std::cout << i << "<->" << j << "] : " << j - i + 1 << "\n";
ans += calc(j - i + 1);
}
std::cout << ans;
}
C. Che city
题意
这是 2013 年俄罗斯高中团队编程竞赛中的一个问题
在车城市中心有一条步行街，是城市居民最喜欢散步的地方之一。这条街非常适合散步，因为沿街都是 $n$ 有趣的纪念碑。
车城的女孩玛莎喜欢学校里的两个男孩，她无法在他们之间做出选择。为了做出最后的决定，她决定同时和两个男孩约会。玛莎想在步行街上选择两个纪念碑，男孩们会在附近等她。同时，她还想选择这样的纪念碑，这样男孩子们就不会看到彼此了。玛莎知道，由于有雾，男孩们只有在距离不超过 $r$ 米的地方才能看到对方。玛莎感兴趣的是，有多少种方法可以选择两个不同的纪念碑来组织约会。
参考思路
考虑双指针滑动窗口维护所有 “能够互相看到对方” 的方案数 $cnt$，答案即为 $\frac{n(n - 1)}{2} - cnt$。
参考代码
void solve() {
i64 n, s;
std::cin >> n >> s;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
i64 ans = 0;
int i = 0;
for (int j = 0; j < n; j++) {
while (a[j] - a[i] > s) i++;
//ans += 1ll * i * (n - j);
ans += j - i + 1;
}
std::cout << n * (n + 1) / 2 - ans;
}
D. Stylish clothes
题意
格列布喜欢购物。有一次，他想出了一个主意，那就是选择帽子、衬衫、裤子和鞋子，使它们看起来尽可能时尚。在格列布的理解中，当衣服各元素的颜色差异很小时，衣服就会更时尚。
有 $n_1$ 顶帽子、 $n_2$ 件衬衫、 $n_3$ 条裤子和 $n_4$ 双鞋子($1 \le n_i \le 100,000$)。每个衣服元素都有自己的颜色(从 $1$ 到 $100, 000$ 的整数)。一组衣服包括一顶帽子、一件衬衫、一条裤子和一双靴子。每套衣服的特征是任意两个元素之间的最大差异。请帮助格列布选择最时尚的套装，即色差最小的套装。
参考思路
将四种数据均输入，排序后，四指针动态维护答案即可。具体实现细节看代码吧。
参考代码
using Z = std::array<int, 3>;
void solve() {
std::vector a(4, std::vector<int>());
for (int i = 0; i < 4; i++) {
int n;
std::cin >> n;
a[i].resize(n);
for (auto &j : a[i]) std::cin >> j;
std::sort(a[i].begin(), a[i].end());
}
std::set<Z> s;
std::vector<int> i(4);
std::priority_queue<Z, std::vector<Z>, std::greater<Z>> q;
for (int j = 0; j < 4; j++) {
if (i[j] != a[j].size() - 1) q.push({a[j][i[j]], i[j], j});
s.insert({a[j][i[j]], i[j], j});
}
int midiff = (*s.rbegin())[0] - (*s.begin())[0];
std::vector<int> ans(4);
for (auto &[v, idx, i_] : s) {
ans[i_] = v;
}
while (q.size()) {
auto [_, idx, i_] = q.top(); q.pop();
s.erase({_, idx, i_});
idx++;
s.insert({a[i_][idx], idx, i_});
if (idx != a[i_].size() - 1) {
q.push({a[i_][idx], idx, i_});
}
if ((*s.rbegin())[0] - (*s.begin())[0] < midiff) {
midiff = (*s.rbegin())[0] - (*s.begin())[0];
for (auto &[v, idx, i_] : s) {
ans[i_] = v;
}
}
}
for (auto &j : ans) std::cout << j << " ";
}
E. Knapsack on a Segment
题意
给定一个由 $n$ 项组成的数组，每个项的权重为 $w_i$ ，成本为 $c_i$ 。您需要选择此数组的 一连续段 ，该数组的总权重不大于 $s$ ，并且总成本为最大值。
参考思路
考虑双指针滑动窗口，维护区间对权重求和小于等于 $s$，同时动态更新成本和的最大值即可。
参考代码
void solve() {
i64 n, s;
std::cin >> n >> s;
std::vector<i64> w(n), c(n);
for (auto &i : w) std::cin >> i;
for (auto &i : c) std::cin >> i;
int i = 0;
i64 sum_w = 0, sum_c = 0;
i64 ans = 0;
for (int j = 0; j < n; j++) {
sum_w += w[j];
sum_c += c[j];
while (sum_w > s) sum_w -= w[i], sum_c -= c[i++];
ans = std::max(ans, sum_c);
}
std::cout << ans;
}
F. Card Substrings
题意
给定字符串 $s$ 和 $m$ 带字母的卡片。您的任务是计算字符串 $s$ 的子字符串的数量，这些字符串可以由这些卡片生成。
例如，如果 $s = $ “aaab”，并且有三张卡片上有字母 “a”、“a” 和 “b”，那么您可以创建三个子字符串 “a”、子字符串 “b”、两个子字符串 “aa”、子字符串 “ab” 和 “aab”。您不能使子字符串为 “aaa” 和 “aaab”，因为只有两张卡片带有字母 “a”。
参考思路
双指针维护区间各种元素数量和不超指定限制即可。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::string s, t;
std::cin >> s >> t;
std::vector<int> cnt(26), zcnt(26);
for (auto &c : t) cnt[c - 'a']++;
int i = 0;
i64 ans = 0;
for (int j = 0; j < n; j++) {
zcnt[s[j] - 'a']++;
while (zcnt[s[j] - 'a'] > cnt[s[j] - 'a']) zcnt[s[i++] - 'a']--;
ans += j - i + 1;
}
std::cout << ans;
}
G. Not Very Rude Substring
题意
您收到一个字符串 $s$ ，由 $n$ 小写英文字母组成。
长度为 $k$ 的字符串 $t$ 的粗糙度是 $(i, j)$ 的整数对数，其中 $1 \le i < j \le k$ ，其中 $t_i = $ “a” 和 $t_j = $ “b”。换句话说，字符串的粗鲁之处在于除了两个字符以外删除所有字符的方法的数量，以便字符串 “ab” 保留下来。
您的任务是查找最大长度的子字符串 $s_l s_{l + 1} \dots s_r$ ，其粗鲁程度不超过 $c$ 。
参考思路
根据题目定义，双指针维护区间子串的 rude 不超 $c$ 时更新答案即可。具体实现细节看代码吧。
参考代码
void solve() {
i64 n, c;
std::cin >> n >> c;
std::string s;
std::cin >> s;
int i = 0;
int ans = 0;
i64 r = 0;
std::vector<int> cnt(2);
for (int j = 0; j < n; j++) {
int k = s[j] - 'a';
if (k <= 1) {
if (k == 1) r += cnt[0];
cnt[k]++;
while (r > c) {
int k_ = s[i++] - 'a';
if (k_ > 1) continue;
if (k_ == 0) r -= cnt[1];
cnt[k_]--;
}
}
ans = std::max(ans, j - i + 1);
}
std::cout << ans;
}
H. A-B Knapsack
题意
给定 $n$ 件，重量为 $A$ ，成本为 $a_1, …, a_n$ ； $m$ 件，重量为 $B$ ，成本为 $b_1, …, b_m$ 。
这些物品装满了一个背包，该背包可承受的重量不超过 $s$ 。求背包中物品的最大总成本。
参考思路
一看是背包问题，但实际上权值是固定的，我们先把重量大的物品装满背包，然后一个个取出物品时，双指针添加另一个重量较小，权值较大的物品，动态更新答案即可。
参考代码
void solve() {
int n, m;
i64 s, A, B;
std::cin >> n >> m >> s >> A >> B;
std::vector<i64> a(n), b(m);
for (auto &i : a) std::cin >> i;
for (auto &i : b) std::cin >> i;
std::sort(a.rbegin(), a.rend());
std::sort(b.rbegin(), b.rend());
if (A > B) {
std::swap(A, B);
std::swap(a, b);
std::swap(n, m);
}
i64 sum = 0;
i64 sum_w = 0;
int i = 0;
for (; i < n; i++) {
if (sum_w + A > s) break;
sum += a[i];
sum_w += A;
}
i64 ans = sum;
for (int j = 0; j < m; j++) {
sum += b[j];
sum_w += B;
while (i && sum_w > s) sum_w -= A, sum -= a[--i];
if (sum_w > s) break;
//std::cout << i << ", " << j << ": " << sum << "]\n";
ans = std::max(ans, sum);
}
std::cout << ans;
}
I. Segment with the Required Subset
题意
给定一个由 $n$ 个整数 $a_i$ 组成的数组。如果在这个数组的某一段 $a[l..r]$ 上可以选择一组和等于 $s$ 的数，那么这个数组的某一段 $a[l..r]$ 就是好数组。你的任务是找出最短的好线段。
参考思路
考虑 dp，设 dp[i][j] 表示 到 i 位置为止，使得能够选一些数，让 sum 为 j，的最近的最大下标。
这跟双指针有关嘛？
参考代码
void solve() {
int n, s;
std::cin >> n >> s;
std::vector dp(n, std::vector<int>(s + 1, -1));
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
for (int i = 0; i < n; i++) {
dp[i][a[i]] = i;
}
int ans = n + 1;
if (a[0] == s) ans = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j <= s; j++) {
dp[i][j] = std::max(dp[i][j], dp[i - 1][j]);
}
for (int j = a[i]; j <= s; j++) {
dp[i][j] = std::max(dp[i][j], dp[i - 1][j - a[i]]);
}
//std::cout << i << ": " << ans << "]\n";
if (dp[i][s] != -1) {
ans = std::min(ans, i - dp[i][s] + 1);
}
}
std::cout << (ans == n + 1 ? -1 : ans);
}