不会的东西越来越多了
B. K-Set Tree
https://www.luogu.com.cn/problem/CF1691F
令 \(F_i\) 表示以 \(1\) 为根时，\(S\) 在 \(i\) 子树内的答案。则：
\[ F_u=\left(C_{siz_u}^k-\sum C_{siz_v}^k\right)\cdot siz_u+\sum F_v\\ \]
直接换根是很复杂的；把 \(\sum C_{siz_v}^k\) 记作 \(dp_u\)，把 \(\sum F_v\) 记作 \(f_u\)，那么：
\[ res=\sum(C_n^k-dp_u)\cdot n+f_u\\ \]
这样做是为了把两个和 \(v\) 有关的乘项拆开来换根，实际换根的时候就只用分别换 \(f,dp\) 两个值，不用考虑二次项等问题，计算量会少很多
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, k;
std::cin >> n >> k;
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<long long> fac(n + 1), inv(n + 1);
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i - 1] * i % mod;
auto qkp = [](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
if (m > n)
return 0ll;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
};
auto res(0ll);
std::vector<int> siz(n + 1), ss(n + 1);
std::vector<long long> f(n + 1), dp(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
siz[x] = 1;
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
(f[x] += (C(siz[i], k) - dp[i]) * siz[i] + f[i]) %= mod;
(dp[x] += C(siz[i], k)) %= mod;
siz[x] += siz[i];
}
return;
};
DFS(1, -1);
DFS = [&](int x, int fa) {
(res += (C(n, k) - dp[x]) * n + f[x]) %= mod;
for (auto i : g[x])
if (i != fa) {
(f[i] += (C(n - siz[i], k) - (dp[x] - C(siz[i], k))) * (n - siz[i]) + f[x] - f[i] - (C(siz[i], k) - dp[i]) * siz[i]) %= mod;
(dp[i] += C(n - siz[i], k)) %= mod;
DFS(i, x);
}
return;
};
DFS(1, -1);
std::cout << (res + mod) % mod << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C. Li Hua and Path
https://www.luogu.com.cn/problem/CF1797F
考虑容斥，分别求解满足 1、满足 2、满足 12（注意要减两倍）就能计算答案
发现题目所求点对形式很符合 Kruskal 重构树的要求，考虑以对应点权为边权，分别建立 min，max Kruskal 点权多叉重构树。
点权多叉重构树？
在点权上做 Kruskal 重构树时，发现边的虚点是不必要的，可以直接将更优点作为父亲。
写的时候有点难想清楚…… 可以画画图，仔细确定一下 Kruskal 重构树的具体性质
这样做的优势是没有虚点，一些问题会方便一些；但同时放弃了二叉树的结构，一些题可能没那么好做。
这道题只用经典 Kruskal 重构树也可以解决。
发现 1 2 均可以转化成两棵树在两棵树上的祖孙关系要求，可以轻松地分别统计满足 1、满足 2 的点对数量
考虑怎么处理同时满足 12 的，发现要求在两棵树上二者应该都具有祖孙关系，且是相反的。可以考虑在一棵树上 DFS 的同时用主席树存储祖先，在另一颗树上 ask
考虑从更容易用 dfn 表示的子树问题思考，在 min 树上分配 dfn 后，在 max 树上用 DFS + 回溯得到每个点实时祖先序列，存在树状数组里；ask 该点被分配的 dfn 子树区间就能得到答案。
考虑询问，由于每次加入的都是编号最大的点，对于满足 1、满足 2 的贡献是显然的，而同时满足 12 的点就是在 min 树上的祖先，都是好做的。
实现的时候一定要把 min / max 树对应的性质思考清楚，不然会很麻烦
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<int> f1(n + 1), f2(n + 1);
std::iota(f1.begin() + 1, f1.end(), 1);
std::iota(f2.begin() + 1, f2.end(), 1);
std::function<int(int)> find1 = [&](int x) {
return x == f1[x] ? x : f1[x] = find1(f1[x]);
};
std::function<int(int)> find2 = [&](int x) {
return x == f2[x] ? x : f2[x] = find2(f2[x]);
};
std::vector<std::vector<int> > g1(n + 1), g2(n + 1), adj1(n + 1), adj2(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
if (x > y)
std::swap(x, y);
adj1[y].push_back(x);
adj2[x].push_back(y);
}
for (int i = 1; i <= n; ++i)
for (auto j : adj1[i]) {
int fi = find1(i), fj = find1(j);
g1[fi].push_back(fj), f1[fj] = fi;
}
for (int i = n; i; --i)
for (auto j : adj2[i]) {
int fi = find2(i), fj = find2(j);
g2[fi].push_back(fj), f2[fj] = fi;
}
std::vector<int> bit(n + 1), dfn(n + 1), rfn(n + 1);
auto lowbit = [](int x) {
return x & -x;
};
auto add = [&](int x, int v) {
for (; x <= n; x += lowbit(x))
bit[x] += v;
return;
};
auto ask = [&](int x) {
int res = 0;
for (; x; x -= lowbit(x))
res += bit[x];
return res;
};
int rt1 = 0, rt2 = 0;
for (int i = 1; i <= n; ++i) {
if (f1[i] == i)
rt1 = i;
if (f2[i] == i)
rt2 = i;
}
int q;
std::cin >> q;
std::vector<int> dep1(n + 1), dep2(n + q + 1);
long long res = 0ll;
std::function<void(int)> DFS = [&](int x) {
static int now = 0;
dfn[x] = ++now;
res += dep1[x];
for (auto i : g1[x]) {
dep1[i] = dep1[x] + 1;
DFS(i);
}
rfn[x] = now;
return;
};
DFS(rt1);
DFS = [&](int x) {
res += dep2[x];
res -= 2 * (ask(rfn[x]) - ask(dfn[x] - 1));
add(dfn[x], 1);
for (auto i : g2[x]) {
dep2[i] = dep2[x] + 1;
DFS(i);
}
add(dfn[x], -1);
return;
};
DFS(rt2);
std::cout << res << '\n';
for (int fa; q--; ) {
std::cin >> fa;
dep2[++n] = dep2[fa] + 1;
res += (n - 1) - dep2[n];
std::cout << res << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}D. 团队选拔
http://222.180.160.110:61235/contest/6534/problem/4
给定 \(a_{1\sim n}\)，从中任选一些互不相交的区间，满足每个区间内元素的 gcd 相同。
\(n\le 10^5,V\le 10^7\)。
注意到固定一个左端点后，移动右端点，gcd 每次至多减小到原来的一半；也就是说，其种类有 \(\log V\) 种。故全序列的 gcd 总数是 \(O(n\log V)\) 的。
很容易想到与此原理类似的全局答案求法：对于每个 \(i\)，向左处理出每一段 \([l,r]\)，满足 \(\gcd(a_{l\cdots i})=\gcd(a_r\cdots i)\)，并记录该 \(\gcd\)。这样求出来的 \((i,l,r)\) 共有 \(O(n\log V)\) 段。
对于每个 gcd 有 \(f_{i}=f_{i-1}+\sum\limits_{j=l_i}^{r_i} f_{j - 1}\)，可以做一个扫描线，得到全局答案；向前向后分别做到 \(i-1,i+1\)，相乘就能得到 \(i\) 未被选取时的答案
考虑怎么完成『相乘』这个动作：最后的 \(f\) 在每个右端点处发生变化，可以转化成若干段 \(f\)；反过来的 \(f'\) 亦可以这样转化。将 \(f\) 整体后移一位、\(f'\) 整体前移一位，就可以对齐。二者的端点总数是均摊单 log 的，区间总数也就是均摊单 log 的（归并就能快速寻找到区间），用差分做一个区间加即可。
用二分勉强单 log 解决了转移；还看到 @spdarkle 疑似在 \(1\sim n\) 上直接做的做法，和 @Rosmist 疑似直接在每个 \(i\) 上做的做法。官解是个看不懂的做法
呃，好像一不小心拿了最优解。而且优势很明显（怎么总用时比别人一个点还少？），这是为什么？
可能因为大家都看不懂官解，做法比较多样？除了我之外比较快的 lwz 和 @GoldSpade 都用归并完成最后一步；我较他们的额外优势大概是用二分换掉了树状数组？迷惑
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("selection.in", "r", stdin);
std::freopen("selection.out", "w", stdout);
#else
std::freopen("ex_selection2.in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1);
std::vector<std::vector<int> > st(20, std::vector<int> (n + 1));
for (int i = 1; i <= n; ++i)
std::cin >> a[i], st[0][i] = a[i];
for (int j = 1; (1 << j) <= n; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[j][i] = std::__gcd(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
auto askgcd = [&](int l, int r) {
int k = std::__lg(r - l + 1);
return std::__gcd(st[k][l], st[k][r - (1 << k) + 1]);
};
std::unordered_map<int, int> tab;
struct node {
int i, l, r;
bool operator< (const int q) const {
return i < q;
}
bool operator<= (const int q) const {
return i <= q;
}
};
std::vector<std::vector<node> > p1, p2;
for (int i = 1; i <= n; ++i) {
for (int to = i; to >= 1; ) {
int at = i, g = askgcd(to, i);
for (int l = 1, r = to, mid; l <= r; ) {
mid = (l + r) >> 1;
if (askgcd(mid, i) == g)
at = mid, r = mid - 1;
else
l = mid + 1;
}
if (!tab.count(g)) {
tab[g] = (int)p1.size();
p1.emplace_back(), p2.emplace_back();
}
p1[tab[g]].push_back({ i, at, to });
to = at - 1;
}
for (int to = i; to <= n; ) {
int at = i, g = askgcd(i, to);
for (int l = to, r = n, mid; l <= r; ) {
mid = (l + r) >> 1;
if (askgcd(i, mid) == g)
at = mid, l = mid + 1;
else
r = mid - 1;
}
if (!tab.count(g)) {
tab[g] = (int)p2.size();
p1.emplace_back(), p2.emplace_back();
}
p2[tab[g]].push_back({ i, to, at });
to = at + 1;
}
}
auto s(0ll);
std::vector<int> x1(n + 1), x2(n + 2), pos(2 * n + 3);
std::vector<long long> f1(n + 1), f2(n + 2), s1(n + 1), s2(n + 2), diff(n + 1);
for (auto [g, id] : tab) {
// printf("g = %d: \n", g);
int n1 = (int)p1[id].size();
x1[0] = 0, f1[0] = s1[0] = 1ll;
for (int i = 1; i <= n1; ++i) {
auto [x, L, R] = p1[id][i - 1];
--L, --R;
x1[i] = x, f1[i] = f1[i - 1];
int l = std::upper_bound(x1.begin() + 1, x1.begin() + i + 1, L) - x1.begin() - 1,
r = std::upper_bound(x1.begin() + 1, x1.begin() + i + 1, R) - x1.begin() - 1;
if (l == r)
(f1[i] += f1[l] * (R - L + 1)) %= mod;
else {
f1[i] += s1[r - 1] + mod - s1[l];
f1[i] += f1[r] * (R - x1[r] + 1);
f1[i] += f1[l] * (x1[l + 1] - L);
f1[i] %= mod;
}
// printf(" r = %d, l = [%d, %d]: %lld\n", x, L, R, f1[i]);
if (i != n1)
s1[i] = (s1[i - 1] + f1[i] * (p1[id][i].i - x)) % mod;
}
(s += f1[n1] - 1) %= mod;
int n2 = (int)p2[id].size();
x2[n2 + 1] = n + 1, f2[n2 + 1] = s2[n2 + 1] = 1ll;
for (int i = n2; i; --i) {
auto [x, L, R] = p2[id][i - 1];
++L, ++R;
x2[i] = x, f2[i] = f2[i + 1];
int l = std::lower_bound(x2.begin() + i, x2.begin() + n2 + 1, L) - x2.begin(),
r = std::lower_bound(x2.begin() + i, x2.begin() + n2 + 1, R) - x2.begin();
if (l == r)
(f2[i] += f2[l] * (R - L + 1)) %= mod;
else{
f2[i] += s2[l + 1] + mod - s2[r];
f2[i] += f2[r] * (R - x2[r - 1]);
f2[i] += f2[l] * (x2[l] - L + 1);
f2[i] %= mod;
}
// printf(" l = %d, r = [%d, %d]: %lld\n", x, L, R, f2[i]);
if (i != 1)
s2[i] = (s2[i + 1] + f2[i] * (x - p2[id][i - 2].i)) % mod;
}
for (int i = 0; i < n1; ++i)
x1[i] = x1[i + 1];
x1[n1] = n;
int t = (x2[1] == 1) + 1;
for (int i = 1; i <= n2 + 1; ++i)
--x2[i];
std::merge(x1.begin(), x1.begin() + n1 + 1, x2.begin() + t, x2.begin() + n2 + 2, pos.begin() + 1);
int m = std::unique(pos.begin() + 1, pos.begin() + n1 + n2 + 4 - t) - pos.begin() - 1;
for (int i = 1, p1 = 0, p2 = t, la = 0; i <= m; ++i) {
for (; p1 + 1 <= n1 && x1[p1] < pos[i]; ++p1);
for (; p2 + 1 <= n2 + 1 && x2[p2] < pos[i]; ++p2);
(diff[la + 1] += f1[p1] * f2[p2] + mod - 1) %= mod;
// printf(" [%d, %d]: %lld, %lld\n", la + 1, pos[i], f1[p1], f2[p2]);
if (pos[i] + 1 <= n)
(diff[pos[i] + 1] += mod - f1[p1] * f2[p2] + 1) %= mod;
la = pos[i];
}
}
// std::cout << s << '\n';
for (int i = 1; i <= n; ++i) {
(diff[i] += diff[i - 1]) %= mod;
std::cout << (s + mod - diff[i]) % mod << ' ';
}
std::cout << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}我一开始将 \(f\) 定义为单点答案而非前缀和，会导致需要线段树维护等差序列，还丢失了答案段数不多这个性质，非常麻烦。将 \(f\) 的意义替换为前缀和后，就可以很轻松地做了。
A. 宇宙
http://222.180.160.110:61235/contest/6535/problem/1
给定 \(a_{1\sim n}\)，对于 \(k=1,2,\cdots,n-1\)，回答：
- 令 \(i\) 从 \(1\) 开始自增，对于每个 \(i\)，都可以选取 \(k\) 个互不相同的下标，并使它们对应的元素增加 1。此时，若存在元素不大于 \(i\)，停止。输出停止时 \(i\) 可能的最大值。
\(n\le 10^6,V\le 10^9\)。
发现不大于这个 condition 有些反人类，先将 \(a\) 全部减 1，转化成小于来考虑
考虑能坚持到 \(i\) 的一个必要条件，即 \(\sum\limits_{a_j<i} i-a_j\le k\cdot i\)
容易发现该条件同时是充分的，同样从线段覆盖的角度出发，是一个 \(k\) 的扩展
对 \(a\) 排序，停止时参与运算的 \(a_j\) 是越来越多的，故记录最后一个参与运算的下标，逐步挪动（当发现解出来的 \(i\) 比下一个更大时就需要挪动），同时解不等式即可。
@Quack 云我在场上能想出官解对我来说是非常了不起的（其实场上写正解的人少得出奇），我也不得不承认我能做出来确实有一定运气成分，也能从中一窥我令人眼前一黑的数学素养！
#include <bits/stdc++.h>
int main() {
std::freopen("universe.in", "r", stdin);
std::freopen("universe.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int n;
std::cin >> n, std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i], --a[i];
std::sort(a.begin() + 1, a.end());
int id = 1;
long long s = a[1];
for (int i = 1; i < n; ++i) {
if (id < i + 1)
s += a[++id];
long long x = s / (id - i);
for (; id != n && x > a[id + 1]; s += a[++id], x = s / (id - i));
std::cout << x << ' ';
}
std::cout << '\n';
return 0;
}B. 跳跃
http://222.180.160.110:61235/contest/6535/problem/2
给定长度为 \(n\) 的 01 序列和跳跃上限 \(k\)。给定 \(q\) 个询问，回答：
- 从 \(a\) 跳到 \(b\)，保证 \(a,b\) 的颜色均为 1，每次不能跳超过 \(k\) 格或跳出去，在最小化踩到 0 数量的前提下，最小化跳跃次数，输出这两个值。
\(n,q\le5\times10^5\)。
容易发现只能往一个方向跳，那么不妨令 \(a<b\)。有一个贪心的想法是能往右就往右，手玩发现是对的（我场上手玩过后坚定地认为是错的；可能和没时间了兵荒马乱有关）。这样就很好想到第二问需要倍增；但把两个问结合起来考虑是有点困难的，赛时就意识到这两问的联系没有看起来那么大，甚至很可能是割裂的。
单独考虑第一问，发现对于一段长度为 \(len\) 的 0，需要踩到恰好 \(\left\lfloor\dfrac {len}k\right\rfloor\) 个 0。答案容易计算。
单独考虑第二问，考虑一个第一问答案固定为 0 的情况，也即每个 len 都比 \(k\) 小。则问题转化成在不踩 0 的情况下最小的步数。容易用倍增解决。
本题最令人印象深刻的点在于二者的结合，发现这 \(\left\lfloor\dfrac {len}k\right\rfloor\cdot k\) 个 0 是无论如何都会被经过的，所以可以在原始数组里删掉它们，转化成只考虑第二问的情况
？？？
我对于自己莫名其妙跑得比别人块一大截这件事情已经快要见怪不怪了，这次又是什么原理，我预处理写得比较漂亮吗？？
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("jump.in", "r", stdin);
std::freopen("jump.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, k, q, op;
std::cin >> n, std::cin >> n >> q >> k >> op;
std::vector<int> tmp(n + 1), a(1), s(1), to(n + 2);
for (int i = 1; i <= n; ++i) {
char t;
std::cin >> t;
tmp[i] = t - '0';
}
tmp.push_back(1), ++n;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (tmp[i] == 1) {
a.push_back(1), to[i] = (int)a.size() - 1;
s.push_back(s.back() + cnt), cnt = 0;
}
else {
++cnt;
if (i == n || tmp[i + 1] == 1) {
for (int j = 1; j <= cnt % k; ++j)
a.push_back(0), s.push_back(s.back());
cnt /= k;
}
}
}
n = (int)a.size() - 1;
std::vector<std::vector<int> > f(20, std::vector<int> (n + 1));
for (int i = 0; i < 20; ++i)
f[i][n] = n;
for (int i = n - 1; i; --i) {
f[0][i] = std::min({ n, i + k, f[0][i + 1] });
for (; !a[f[0][i]]; --f[0][i]);
if (a[i] == 1) {
for (int j = 1; j < 20; ++j)
f[j][i] = f[j - 1][f[j - 1][i]];
}
}
for (int a, b; q--; ) {
std::cin >> a >> b;
if (a > b)
std::swap(a, b);
a = to[a], b = to[b];
std::cout << s[b] - s[a];
if (op == 1) {
int res = s[b] - s[a];
for (int i = 19; ~i; --i)
if (f[i][a] < b)
a = f[i][a], res += (1 << i);
std::cout << ' ' << res + 1;
}
std::cout << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}D. Jongmah
https://codeforces.com/contest/1110/problem/D
容易发现当连续出现三次 \((i-1,i,i+1)\) 时，可以被三次相同代替；
容易发现需要使用 \(f_{i,a,b}\) 来代表 DP 到 \(i\) 时，用了 \(a\) 组 \((i-1,i,i+1)\) 和 \(b\) 组 \((i,i+1,i+2)\) 时的最大组数；
但是并没有想到要将二者结合起来！感觉应该是能比较快做出来的水平。能察觉到不太认真。悔过！
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> cnt(m + 1);
for (int i = 1, x; i <= n; ++i)
std::cin >> x, ++cnt[x];
std::vector<std::vector<std::vector<int> > > f(m + 1, std::vector<std::vector<int> > (3, std::vector<int> (3, -inf)));
f[0][0][0] = 0ll;
for (int i = 1; i <= m; ++i)
for (int a = 0; a <= 2; ++a) // i - 1, i, i + 1
for (int b = 0; b <= 2; ++b) // i, i + 1, i + 2
for (int c = 0; c <= 2; ++c) { // i - 2, i - 1, i
if (a + b + c > cnt[i]) continue;
f[i][a][b] = std::max(f[i][a][b], f[i - 1][c][a] + b + (cnt[i] - a - b - c) / 3);
}
std::cout << f[m][0][0] << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}E. Magic Stones
https://codeforces.com/contest/1110/problem/F
容易想到考察差分数组，发现这个操作就是交换了差分数组的相邻两个元素。故对于 \(c\) 和 \(t\) 的差分数组分别排序，然后 check 是否相等即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = 1; i <= n; ++i)
std::cin >> b[i];
if (a[1] != b[1] || a[n] != b[n]) {
std::cout << "No" << '\n';
return 0;
}
std::vector<int> da(n), db(n);
std::adjacent_difference(a.begin() + 1, a.end(), da.begin());
std::adjacent_difference(b.begin() + 1, b.end(), db.begin());
std::sort(da.begin(), da.end());
std::sort(db.begin(), db.end());
std::cout << (da == db ? "Yes" : "No") << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}