Eysiking

上一章中介绍到使用可撤销并查集结合线段树分治可以维护图的连通性信息。由于在同一时间线段树的深度为 $O(\log q)$ ，因此可以利用直接复制的操作，如果数据结构大小为 $n$，则总的时间复杂度为 $O(nq\log q)$ CF601E 维护背包问题的 dp 数组： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, k; cin >> n >> k; std::vector<Z> fac(k); ...

线段树和离线算法的结合。假如你需要维护一些信息，这些信息会在某一个时间段内出现，要求在离线的前提下回答某一个时刻的信息并，则可以考虑使用线段树分治的技巧。 回顾线段树内容，假如需要维护一个时间轴上的操作，对这个时间轴建立线段树，把在某一时间段生效的操作挂在线段树节点上，在到达当前节点时，添加该节点上保存的操作；在离开该节点时，对于图的连通性问题通常使用可撤销并查集，对于其他特殊问题，如果需要维护的数据结构空间复杂度很小，也可以直接保存操作前的状态，离开该节点时再复制回原来的状态。询问操作一般存储在线段树叶节点上。 例题 loj121...

可持久化并查集可以查询任意版本的并查集，本质就是可持久化数组，将 $f$ 数组与 $siz$ 可持久化 为了减少每次合并操作的修改元素数量，只做按秩合并，不做路径压缩。假设要合并 $a$ 所在元素集合和 $b$ 所在元素集合，集合代表节点和集合大小分别为 $f_a,siz_a,f_b,siz_b(siz_a>siz_b)$，这样每次合并的操作就只有 $f[f_b]=f_a $ $siz[f_a]=siz_a+siz_b$ 只需进行两次操作，大大减小了操作量，并且由于启发式合并，每次查询操作也只会跳转 $O(\log n)$ 次。 可撤销并查集可以按照FIFO回滚所做操作，用一个栈来存储当前版本修改了哪些信息，以便回退到它上一个版本。 由于只维护了两个集合代表节点在合并时的相关信息，同样不能做路径压缩 模板 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758struct DSU...

简介SOS-DP，英文名 Sum over Subsets(SOS) dynamic programming，即子集和DP，用来求某一集合的所有子集对应状态之和。 给定一个含 $2^N$ 个元素的集合 $A$，下标用 $i$ 来表示，求一个 $F_{state}$，对应为：$$F_{state}=\sum_{i\subseteq state / i \text{&} state = state}A[i]$$ 解法： Bruteforce1234567for (int mask = 0; mask < (1 << N); mask++) { for (int i = 0; i < (1 << N); i++) { if ((mask & i) == i) { F[mask] += A[i]; } }} 对于每个 $mask$，暴力枚举哪些状态为它的子集，时间复杂度 $O(4^N)$ Suboptimal...

AtCoder Beginner Contest 408 - AtCoder f线段树优化 dp 每个点只能从 $[i-R,i+R]$ 的范围内传播 $dp[i]=dp[pos]+1$，其中 $pos$ 为 $[i-R,i+R]$ 内的满足 $h[pos]\le h[i]-D$ 的最大 $dp[pos]$ 所以如何设计 dp 呢 由于状态转移只能单调减，考虑将所有位置 $i$ 按照 $h[i]$ 排序，这样状态只能从前往后传递，这里考虑从小到大排序，如果要计算 $dp[i]$，需要先处理好所有 $h[pos]\le h[i]-D$ 的位置，并将 $dp[pos]$ 填入原位置，之后计算 $[i-R,i+R]$ 的所有 $dp$ 值的最大值 $dp[x]$，状态转移...

Dashboard - Codeforces Round 1026 (Div. 2) - Codeforces A将数组排序后，如果首尾相加为偶数，则直接输出0，否则枚举从前去掉的最少数字，和从后去掉的最少数字以达到首尾相加为偶数的最小值 123456789101112131415161718192021222324252627void solve() { int n; cin >> n; std::vector<int> a(n); for (int &x : a) { cin >> x; } std::sort(a.begin(), a.end()); if ((a[0] + a[n - 1]) % 2 == 0) { cout << 0 << "\n"; return; } int ans = n - 1; for (int i =...

AtCoder Beginner Contest 407 - AtCoder C 一定需要 $n$ 次1操作来将 $t$ 变为 $n$ 长度 $t$ 的下标小的位置得到的 2操作一定比下标大的位置更多 把一轮称为某位置执行10次1操作后重新从0开始累加。因此，如果有 $s[i]<s[i+1]$，则必然是 $s[i]$ 增加10之后的新一轮 统计最少需要经过多少轮即可 123456789101112131415int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); string s; cin >> s; int n = s.size(); i64 ans = 0; for (int i = n - 2; i >= 0; i--) { if (s[i] < s[i + 1]) { ans += 10; } } ...

Dashboard - Codeforces Round 1025 (Div. 2) - Codeforces A首先，$n-1$ 场比赛不可能出现 $n$ 个胜场，所以必然会有 0；另外，如果中间人次出现 0，那么他两侧数字必须为 1。 123456789101112131415161718192021void solve() { int n; cin >> n; std::vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } if (std::count(a.begin(), a.end(), 1) == n) { cout << "YES\n"; return; } for (int i = 0; i < n; i++) { if (a[i] == 0)...

比赛链接 D通过观察规则不难看出所有奇数位置数字和所有偶数位置数字是不互通的。尝试按照规则构造最小字典序序列，可以发现前 $n-3$ 个数字可以通过贪心构造出最小字典序，也就是奇数位置从小到大排列，偶数位置从小到大排列，这样构造之后得到的字典序一定最小，但是规则是一对奇偶位置一起交换，所以需要判断这样构造出来的序列是否合法，如果不合法，应该如何修改。 首先将奇偶位置分离开来分别构造一个数组，然后每次操作会发现，对于奇偶位置操作是相同的，也就是说逆序对相对数量不会发生变化，所以我们不妨直接按照下标进行排序，这样初始奇偶数列的下标的逆序对数量就是0，最后统计排序好的下标的逆序对数量差必须是偶数即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475i64 countInversions(std::vector<int> a) { ...

比赛链接 A题判断四个数是否相同即可： 12345678910void solve() { int a, b, c, d; cin >> a >> b >> c >> d; std::set<int> s{a, b, c, d}; if (s.size() == 1) { cout << "YES\n"; } else { cout << "NO\n"; }} B题对于边$x$，$y$，能构成三角形所能添加的最大边为$x+y-1$。累计加$n-1$次后，数列长度变为1，答案为$\sum_ia_i-n+1$。 123456789void solve() { int n; cin >> n; std::vector<int> a(n); for...