基本情况
场出三题，C卡了很久而且不是正解。
C. Swap Adjacent Elements
前缀和妙用
显然连续的 \(1\) 对应的序列是一定可以有序的。
有想到这点，但没想到合理的检查方式，所以直接用 \(\texttt{dsu}\) 模拟了。
myCode
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
std::string s;
for (auto& x : a) std::cin >> x, x--;
DSU dsu(n);
std::cin >> s;
for (int i = 0; i < sz(s); i++) {
if (s[i] == '1') {
dsu.merge(i, i + 1);
}
}
for (int i = 0; i < n; i++) {
if (not dsu.same(i, a[i])) {
NO; return ;
}
}
YES;
}
STD
实际上可以很直接的利用这个思路，一段连续的 \(1\) 完全可以用前缀和来检测。
当前位置的上一个和其目标位置的间隔必须全部为 \(1\)，即 \(a_i - i = pre_{a_i - 1} - pre_{i - 1}\)
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
std::string s;
for (auto& x : a) std::cin >> x, x--;
std::cin >> s;
std::vector<int> pre(n + 1);
for (int i = 0; i < n; i++) {
pre[i + 1] = pre[i] + (s[i] == '1');
}
for (int i = 0; i < n; i++) {
if (a[i] - i != pre[a[i]] - pre[i]) {NO; return ;}
}
YES;
}
E. Connected Components?
求连通块中 set 维护未遍历的点进行去重
给定一张无向图 \(G\), 求 \(G\)的补图的连通块的个数。
这里补图就是完全图 \(K\)去掉所有 \(G\) 中的连边，也就是断掉所有原本连着的两个点，连上所有原本没有连接的两个点。记 \(G\) 的补图为 \(T\) 。如果点 \(s\) 和点 \(t\) 处于同一个连通块中，那么一定有一条路径可以从 \(s\) 到 \(t\) ,所有满足上述条件的 \(s\) 和 \(t\) 点的集合称为一个连通块。
- 先看怎么处理补图。
- 用一个 set 维护不该连的边，然后搜索时跳过这些边，剩下的都是该连的边。
- 可以预见的是，暴力求这个补图的连通块时间复杂度极大： \(\operatorname{O}(n^2−m)\)。
- 再考虑优化
- 总共肯定只能访问到 \(n\) 个节点，瓶颈在于需要判断每一条边是否存在和是否给原来遍历过这个节点。于是考虑如何保证每一个节点和补边只会枚举到一次。
- 再维护一个 set，这个 set 仅仅有当前没有遍历到的东西。每一次深搜遍历到某一个节点删除对应元素。
然后，每一次到一个节点遍历一整个 set 来找还可以遍历到哪里。由于每一条补边都最多给统计两次，所有在 set 里节点均摊枚举到的次数是 \(\operatorname{O}(n +m)\)，时间复杂度 \(\operatorname{O}((n + m)\log n)\)，可以过。
std::set<std::pair<int, int>> unAdj;//维护补图
std::set<int> S;//维护未遍历到的点
std::set<int>::iterator dfs (int now, int& cnt) {
S.erase(now);
cnt++;
auto it(S.begin());
while (it != S.end()) {
if (unAdj.count({*it, now}) or unAdj.count({now, *it})) {
++it;
}
else {
it = dfs(*it, cnt);//dfs后遍历过的点都跳过了
}
}
return S.upper_bound(now);//返回当前遍历到的最后的点的迭代器
}
void solve() {
int n, m;
std::cin >> n >> m;
for (int i = 0, u, v; i < m; i++) {
std::cin >> u >> v;
--u, --v;
unAdj.insert({u, v});
unAdj.insert({v, u});
}
for (int i = 0; i < n; i++) {
S.insert(i);
}
std::vector<int> res;
while (not S.empty()) {
int cnt(0);
dfs(*S.begin(), cnt);
res.push_back(cnt);
}
std::sort(all(res));
std::cout << sz(res) << '\n';
for (auto& x : res) std::cout << x << ' ';
std::cout << '\n';
}
F. SUM and REPLACE
观察函数后进行分块
预处理
给定 \(n\) 个数的数组 \(a\)，\(m\) 次操作。操作有两种：
- 将 \(i\in[l,r]\) 中的所有 \(a_i\) 替换为 \(d(a_i)\)。\(d(x)\) 表示 \(x\) 的正约数的个数。
- 求 \(\displaystyle\sum_{i=l}^r a_i\)。
首先通过观察发现该函数是急速收敛的。
预处理出每个数对应的 \(d(x)\)。
void preprocessing() {//类似筛法原理，预处理出每个数的约数个数
for (int i = 1; i <= N; ++i) {
for (int j = i; j <= N; j += i) {
d[j]++;
}
}
}
对于 \(1, 2\) 这两个数而言，我们对它们修改是没有意义的，\(1\) 还是 \(1\)，\(2\) 还是 \(2\)。
因为函数急速收敛，对于 \(a_i\) 仅需几次操作之后就会变成 \(1, 2\)。
我们先预处理出 \(d_i\)，然后线段树维护两个值 \(\texttt{sum, max}\)，在修改操作的时候如果 \(\texttt{max}\) 为 \(1\) 或 \(2\)，那么跳过不修改；否则直接暴力修改即可。
const int N(1e6 + 10);
int d[N];
template<class Info>
struct SegmentTree {
int n;
std::vector<Info> info;
SegmentTree() : n(0) {}
SegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
SegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
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] = Info(init_[l], 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) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void rangeApply(int p, int l, int r, int x, int y) {
if (l >= y or r <= x) {
return;
}
if (info[p].max == 2 or info[p].max == 1) return ;//如果是2或者1就直接返回
if (l >= x and r <= y and r - l == 1) {//直接修改即可
info[p].apply();
return;
}
int m = (l + r) / 2;
rangeApply(2 * p, l, m, x, y);
rangeApply(2 * p + 1, m, r, x, y);
pull(p);
}
void rangeApply(int l, int r) {
return rangeApply(1, 0, n, l, r);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
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) {
return rangeQuery(1, 0, n, l, r);
}
};
struct Info {
i64 max = -1;
i64 sum = 0;
Info(){}
Info(int _max, int _sum): max(_max), sum(_sum) {}
void apply() {
max = d[max];
sum = d[sum];
}
};
Info operator+(Info a, Info b) {
Info c;
c.max = std::max(a.max, b.max);
c.sum = a.sum + b.sum;
return c;
}
void preprocessing() {//类似筛法原理，预处理出每个数的约数个数
for (int i = 1; i <= N; ++i) {
for (int j = i; j <= N; j += i) {
d[j]++;
}
}
}
void solve() {
preprocessing();
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (auto& x : a) std::cin >> x;
SegmentTree<Info> T(a);
for (int i = 0; i < m; i++) {
int o, l, r;
std::cin >> o >> l >> r;
--l;
if (o == 1) {
T.rangeApply(l, r);
}
else {
std::cout << T.rangeQuery(l, r).sum << '\n';
}
}
}