Disjoint Interval Union（并查区间）
这是一个码量特别小的，基于 std::set 的 STL 科技，能够维护不相交区间，同时还具有链表的性质。时间复杂度参考正常的 std::set。
注：该STL并非本人发明，发现该科技的人也没给它取名，DIU是我随便取的名字
如何声明
其代码量十分之小，仅有短短几行：
auto cmp = [](const auto& a, const auto& b) -> bool {
return a.second < b.first;
};
std::set<std::pair<int, int>, decltype(cmp)> s(cmp);
重点是这个 cmp，如果没有 decltype 可用，你也可以选择使用仿函数等方式传入 cmp：
class cmp {
public:
bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.second < b.first;
}
};
std::set<std::pair<int, int>, cmp> s;
或者干脆自己造个 struct 来维护：
struct Seg {
int l, r;
bool operator<(const Seg& a, const Seg& b) {
return a.r < b.l;
}
};
std::set<Seg> s;
std::pair<int, int> 不是必要的，只要你体现出这种右端点大于左端的非对称比较即可。
性质
这种 cmp 方式，配合 set 内部的排序机制，会让 set 以为两个相交的区间是同一个元素。
比方说，如果你往set中插入 $[1, 4]$ 后，再插入 $[3, 6]$，最后set中其实只有最开始的 $[1, 4]$，因为set认为你之后添加的 $[3, 6]$ 和 $[1, 4]$ 是相等的。
运用这种性质，我们可以使用 s.find({x, y}) 找到按左端点排序，从小到大，第一个与 $[x, y]$ 相交的元素的迭代器，没找到则返回 s.end()。
变式
我们将重载的 $<$ 换成 $\le$，那么这个 set 维护的不交区间将从闭区间变为开区间：
但是建议少用这种变式，因为可能会出现违背直觉的事情：
除非你真的知道自己在干什么，不然就尽量避免用这种变式，否则WA了后果自负。
原理
讲完了性质，现在来说说原理，为什么这样重载小于号之后，set就能够维护不相交区间呢？这涉及到了std::set底层的排序比较算法：
set 内部的元素比较使用的是“严格弱序”这一种关系。这种关系的推导用了一些离散数学的知识，这里仅仅只做简单的解释。
比如，< 就是一种严格弱序，而 <= 不是一种严格弱序。使用严格弱序这一关系的好处，就是仅仅只用重载 < 一个运算符，即可完成元素的比较，不需要重载 <=、==、> 等等。
所有的比较情况如下：
-
$a$ 小于 $b$ –> a < b
-
$b$ 小于 $a$ –> b < a
-
$a$ 等于 $b$ –> !(a < b) && !(b < a)
关键点就在于最后的等于这个判断。
第一种相交情况：相交，但不包含。
假设有两个结构体，分别表示两段区间 $a$ ：$[1,4]$、$b$：$[2,5]$。
按照上面的小于号重载方式手动验算，得到的结果正好就是 !(a < b) && !(b < a) 因此，这种情况下，set 就会认为这两个元素是相等的。
第二种相交情况：相交且包含。
假设有两个结构体，分别表示两段区间 $a$ ：$[1,5]$、$b$：$[2,4]$。
按照上面的小于号重载方式手动验算，得到的结果正好也是 !(a < b) && !(b < a)
第三种情况：不相交
简单想象一下便知，此时，一定有某一个区间的右端点小于另一个区间的左端点。无论如何，这两个不相交的区间是不会被认为是相等的。
综上所述，一旦两个区间产生了相交，set 就会认为它们相等，从而自动去重。而一旦两个区间不相交，它们也一定就不相等。
应用与例题
DIU 可以用来维护区间合并，也能用来处理区间分割。合理使用该性质，可以在有些题目中，想不出方法或者懒得写正解时偷鸡。
P2434 [SDOI2005] 区间
题意：
现给定 $n$ 个闭区间 $[a_i, b_i]$（$1 \le i \le n$）。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间 $[a, b]$ 和 $[c, d]$ 是按照升序排列的，那么我们有 $a \le b < c \le d$。
请写一个程序：
读入这些区间；
计算满足给定条件的不相交闭区间；
把这些区间按照升序输出。
DIU 做法：
纯纯的 DIU 板子，不说思路了，自己看代码理解：
void solve() {
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);
while (n--) {
int l, r;
std::cin >> l >> r;
auto it = s.find({l ,r});
while (it != s.end()) {
if (it->first > r) break;
l = std::min(l, it->first);
r = std::max(r, it->second);
it++;
s.erase(std::prev(it));
}
s.insert({l, r});
}
for (auto &[l, r] : s) {
std::cout << l << " " << r << "\n";
}
}
ABC001D - 感雨時刻の整理
题意：
给你 $N$ 个时间段，要你对每个时间段按5分钟进行取整后，合并相交的区间，最后输出剩下的时间段个数，并按时间顺序依次输出各个区间。
取整方式：左端点向下取整，右端点向上取整，例如：1323-1401 取整后变为：1320-1405
DIU 做法：
DIU 板子题，将时间格式化之后，用DIU维护区间合并即可。
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
void solve() {
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)> seg(cmp);
while (n--) {
std::string s;
std::cin >> s;
int l = std::stoi(s.substr(0, 4));
int r = std::stoi(s.substr(5, 4));
l = l / 5 * 5;//向下
r = (r + 4) / 5 * 5;//向上
if (r / 10 % 10 == 6) {
r = r / 100 + 1;
r *= 100;
}
auto it = seg.find({l, r});
while (it != seg.end()) {
auto [ll, rr] = *it;
seg.erase(it);
l = std::min(l, ll);
r = std::max(r, rr);
it = seg.find({l, r});
}
seg.insert({l, r});
}
auto norm = [](int x) {
auto s = std::to_string(x);
return std::string(4 - s.size(), '0') + s;
};
for (auto &[l, r] : seg) {
std::cout << norm(l) << "-" << norm(r) << "\n";
}
}
signed main() {
std::cin.tie(0) -> sync_with_stdio(false);
int t = 1;
//std::cin >> t;
while (t--) solve();
return 0;
}
CF1927D Find the Different Ones!
CF1927D Find the Different Ones!
题意：
给你一个由 $n$ 个整数组成的数组 $a$ 和 $q$ 个查询。
每个查询由两个整数 $l$ 和 $r$ ( $1 \le l \le r \le n$ ) 表示。您的任务是为每个查询找到两个索引 $i$ 和 $j$ （或者确定它们不存在），以便：
- $l \le i \le r$ ;
- $l \le j \le r$ ;
- $a_i \ne a_j$ .
换句话说，对于每个查询，您需要在 $a_l, a_{l+1}, \dots, a_r$ 中找到一对不同的元素，或者报告不存在这样一对元素。
DIU 做法：
一眼 DIU 板子题（确信），直接遍历数组，将每对相邻且不相等的元素记为一个区间，然后加入到 DIU 中维护即可。
考虑到这种情况： [3, 4] 为一个相邻互异元素对区间，我们查询 [4, 7] 的时候可能会不小心查到 [3, 4]，这是不合法的答案，因此 DIU 的 <= 的性质就派上用场了，只用 < 反而会出错。
void solve() {//在区间中找到一对不等数的下标
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
auto cmp = [](const auto& a, const auto& b) -> auto {
return a.second <= b.first;
};
std::set<std::pair<int, int>, decltype(cmp)> s(cmp);
for (int i = 1; i < n; i++) {//记录相邻互异区间
if (a[i] != a[i - 1]) {
s.insert({i - 1, i});
}
}
int q;
std::cin >> q;
while (q--) {
int l, r;
std::cin >> l >> r;
l--; r--;
auto it = s.find({l, r});//直接查
if (it == s.end()) {
std::cout << "-1 -1\n";
} else {
std::cout << it->first + 1 << " " << it->second + 1 << "\n";
}
}
std::cout << "\n";
}
abc380E 1D Bucket Tool
题意：
相信大家都玩过画板上的 “油漆桶” 功能吧，就如题目所言，本题要维护一个1维的油漆操作与查询。
你有一个 $1 \times n$ 的色带，一开始，第 $i$ 个格子的颜色为 $i$ 值。
你需要处理 $Q$ 个操作，有两种：
- 1 x c : 在位置 $x$ 使用油漆，这会将当前格子且与当前格子颜色相同且相邻的格子也涂成颜色 $c$，如果对于相邻的格子，也存在颜色相同且相邻的其他格子，那么继续将该涂色操作传递下去。
- 2 c : 查询颜色为 $c$ 的格子的数量。
DIU 做法：
正常写的话，是用并查集维护一个链表，搞合并。但是显然，我们也可以用 DIU 偷鸡。
我们用 DIU 维护区间的左右端点，颜色，以及区间大小。在涂色操作时，利用 DIU 找到与当前修改的区间的相邻区间，判断是否需要合并即可。
时间复杂度：$O(n\log n)$
void solve() {
int n, m;
std::cin >> n >> m;
auto cmp = [](const auto& a, const auto& b) -> auto {
return a[1] < b[0];
};
std::set<std::array<int, 4>, decltype(cmp)> s(cmp);
std::vector<int> cnt(n + 1, 1);
for (int i = 1; i <= n; i++) {
s.insert({i, i, i, 1});// l, r, c, siz
}
while (m--) {
int op;
std::cin >> op;
if (op == 1) {
int x, zc;
std::cin >> x >> zc;
auto it = s.find({x, x, -1, -1});
auto [l, r, c, siz] = *it;
s.erase(it);
cnt[c] -= siz;
c = zc;
cnt[c] += siz;
auto lit = s.find({l - 1, l - 1, -1, -1});
auto rit = s.find({r + 1, r + 1, -1, -1});
if (lit != s.end()) {
auto [ll, rr, cc, ssiz] = *lit;
if (cc == c) {//该合并了
l = ll;
siz += ssiz;
s.erase(lit);
}
}
if (rit != s.end()) {
auto [ll, rr, cc, ssiz] = *rit;
if (cc == c) {//该合并了
r = rr;
siz += ssiz;
s.erase(rit);
}
}
s.insert({l, r, c, siz});
} else {
int c;
std::cin >> c;
std::cout << cnt[c] << "\n";
}
}
}
CF550A Two Substrings
题意：
给定字符串 s 。您的任务是判断给定的字符串 s 是否包含两个不重叠的子串"AB" 和"BA" (子串的顺序不限)。
DIU 做法：
为什么 A 题上 DIU？其实是因为当时正解没想出来，罚时快罚爆了，最后迫不得已用 DIU 暴力偷鸡
我们直接暴力将所有含 “AB” 的区间添加到 DIU 中进行维护。然后暴力遍历字符串，每找到一个 “BA” 子串，就用这段区间抹掉 DIU 中的相交区间，然后判断 DIU 是否为空即可。
理论复杂度：$O(n^2\log n)$，实际跑起来特别快，$1e5$ 的数据只跑了 $78ms$。
void solve() {
std::string s;
std::cin >> s;
if (s.size() <= 3) {
std::cout << "NO";
return;
}
int n = s.size();
std::map<std::string, int> cnt;
for (int i = 0; i < n - 1; i++) {
cnt[s.substr(i, 2)]++;
}
auto cmp = [](const auto& a, const auto& b) -> auto {
return a.second < b.first;
};
std::set<std::pair<int, int>, decltype(cmp)> seg(cmp);
for (int i = 0; i < n - 1; i++) {
if (s.substr(i, 2) == "AB") seg.insert({i, i + 1});
}
for (int i = 0; i < n - 1; i++) {
if (s.substr(i, 2) == "BA") {
auto tmp = seg;
auto it = tmp.find({i, i + 1});
while ((it = tmp.find({i, i + 1})) != tmp.end()) {
tmp.erase(it);
}
if (tmp.size()) {
std::cout << "YES\n";
return;
}
}
}
std::cout << "NO\n";
}
CF1623B Game on Ranges
题意：
爱丽丝和鲍勃在玩下面这个游戏。爱丽丝有一个由互不相交的整数范围组成的集合 $S$ ，最初只包含一个范围 $[1, n]$ 。在一个回合中，爱丽丝从集合 $S$ 中选出一个范围 $[l, r]$ ，并要求鲍勃在这个范围中选出一个数字。鲍勃选择了一个数字 $d$ ( $l \le d \le r$ )。然后爱丽丝从 $S$ 中取出 $[l, r]$ 并将范围 $[l, d - 1]$ （如果是 $l \le d - 1$ ）和范围 $[d + 1, r]$ （如果是 $d + 1 \le r$ ）放入集合 $S$ 中。当集合 $S$ 为空时，游戏结束。我们可以证明每局棋的回合数正好是 $n$ 。
游戏结束后，爱丽丝记得她从集合 $S$ 中选出的所有范围 $[l, r]$ ，但鲍勃却不记得他选出的任何数字。但是鲍勃很聪明，他知道自己可以从爱丽丝的范围中找出自己的数字 $d$ ，所以他向你求助，希望你能用你的编程技巧帮助他。
给定爱丽丝挑选的范围列表 ( $[l, r]$ )，针对每个范围，帮助鲍勃找出鲍勃挑选的数字 $d$ 。
我们可以证明，对于爱丽丝挑选的有效范围列表，鲍勃总有一种唯一的方法来选择他的数字。
DIU 做法：
将区间按长度从大到小排序后遍历，用 DIU 模拟区间分割，给每个区间绑定一个序号，用于答案输出即可。时间复杂度 $O(n\log n)$
void solve() {
int n;
std::cin >> n;
std::vector<std::array<int, 4>> a(n);
for (auto &[len, l, r, i] : a) {
std::cin >> l >> r;
len = r - l + 1;
}
for (int i = 0; i < n; i++) {
a[i][3] = i;
}
std::sort(a.rbegin(), a.rend());
auto cmp = [](const auto& a, const auto& b) -> auto {
return a[1] < b[0];
};
std::set<std::array<int, 3>, decltype(cmp)> s(cmp);
std::vector<int> ans(n);
s.insert({1, n, a[0][3]});//
for (int i = 1; i < n; i++) {
auto it = s.find({a[i][1], a[i][2], 0});
auto [l, r, idx] = *it;
s.erase(it);
if (l == a[i][1] && r == a[i][2]) {//有别人干了
s.insert({a[i][1], a[i][2], a[i][3]});
continue;
}
if (l == a[i][1]) {//右端点分割
ans[idx] = a[i][2] + 1;
s.insert({a[i][1], a[i][2], a[i][3]});
if (a[i][2] + 1 < r) {
s.insert({a[i][2] + 2, r, a[i][3]});
}
} else {//左端点分割
ans[idx] = a[i][1] - 1;
s.insert({a[i][1], a[i][2], a[i][3]});
if (a[i][1] - 1 > l) {
s.insert({l, a[i][1] - 2, a[i][3]});
}
}
}
//ans[a[n - 1][3]] = a[n - 1][1];
std::sort(a.begin(), a.end(), [](const auto& a, const auto& b){//按下标排序
return a[3] < b[3];
});
for (int i = 0; i < n; i++) {
std::cout << a[i][1] << " " << a[i][2] << " " << (a[i][1] == a[i][2] ? a[i][1] : ans[i]) << "\n";
}
std::cout << "\n";
}
abc147F Sum Difference
题意：
我们有一个长度为 $N$ 的整数序列 $A$，其中 $A1=X,Ai+1=Ai+D(1≤i<N)$ 成立。
高桥将取走这个序列中的一些（可能是全部或者一个也不取），而青木将取走剩下的所有元素。
设 $S$ 和 $T$ 分别为高桥和青木取走的数字的总和。有多少个可能的 $S−T$ 的值？
DIU 做法：
Emmmm，我忘了当时的抽象思路了，找时间补一下做法，先放个实现
void solve() {//怎么都会数论啊
int n, x, d;
std::cin >> n >> x >> d;
if (d == 0) {//如果增量为 0
if (x == 0) {
std::cout << 1;
} else {
std::cout << n + 1;
}
return;
}
auto cmp = [](const std::pair<i64, i64> a, const std::pair<i64, i64> b) -> bool {
return a.first <= b.second;
};//为什么不让我decltype
std::map<int, std::set<std::pair<i64, i64>, decltype(cmp)>> cnt;
// std::map<int, std::set<std::pair<i64, i64>, cmp>> cnt;
if (d < 0) x = -x, d = -d;
for (i64 k = 0; k <= n; k++) {
i64 l = k * (k - 1) / 2, r = k * (2 * n - k - 1) / 2;
i64 t = k * x;
l += t / d, r += t / d;
if (!cnt.count(t % d)) {
cnt.insert({t % d, std::set<std::pair<i64, i64>, decltype(cmp)>(cmp)});
}
auto it = cnt[t % d].find({l, r});
if (it != cnt[t % d].end()) {
l = std::min(l, it -> first);
r = std::max(r, it -> second);
cnt[t % d].erase(it);
}
cnt[t % d].insert({l, r});
}
i64 sum = 0;
for (auto &[t, s] : cnt) {
for (auto &[l, r] : s) {
sum += r - l + 1;
}
}
std::cout << sum;
}
U503858 走地鸡分组
题意：
给定一个序列，要求对其分出尽可能多的组，使得每组中，每种元素数量为偶数。保证有解。
正解：
贪心，由于每只鸡都必须属于某个小组，考虑从前往后遍历，并将每次的分界处都尽量靠左，也就是一遇到可以分界的位置就直接分界。
可以使用 std::set 维护编号的出现次数：每遇到一个编号，如果它在 set 里，说明它已经出现过奇数次，那就把它删掉，否则把它插入 set 里。由于 set 里存的是所有当前出现次数是奇数的编号，那么当 set 的大小为 0 时，就说明当前组内不存在任何数量是奇数的编号，可以在此处分组。时间复杂度 $O(n\log n)$。
由于 $a \le 10^6$，也可以直接开 cnt 数组来记录出现次数，时间复杂度 $O(n)$。
DIU 做法：
考虑到必定有解，因此一定能从左到右，用相同元素组合出 $\frac{n}{2}$ 个区间，直接利用 DIU 从左到右贪心，合并存在相交的区间即可。时间复杂度 $O(n\log n)$
void solve() {
int n;
std::cin >> n;
std::vector<int> vis(1e6 + 1, -1);
std::vector<std::pair<int, int>> res;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
if (vis[x] != -1) {
res.push_back({vis[x], i});
vis[x] = -1;
} else {
vis[x] = i;
}
}
auto cmp = [](const auto& a, const auto& b) -> auto {
return a.second < b.first;
};
std::set<std::pair<int, int>, decltype(cmp)> s(cmp);
for (auto [l, r] : res) {
auto it = s.find({l, r});
while (it != s.end()) {
auto [ll, rr] = *it;
s.erase(it);
l = std::min(l, ll);
r = std::max(r, rr);
it = s.find({l, r});
}
s.insert({l, r});
}
std::cout << s.size();
}
U503856 走地鸡群
题意：
给定一个高度序列，$0$ 时刻时，雨水初始高度为 $0$，每分钟雨水上升一个单位长度，雨水上升过程中，低于雨水高度的部分会被淹没，从而将原始高度序列划分为若干独立的岛屿。你需要计算出，从 $0$ 时刻开始到刚好淹没整个岛屿的过程中，每时刻的岛屿数量。避免答案输出过大，你只需要输出所有时刻下岛屿数量的异或和即可。
正解：
方法一 首先对 $a$ 数组进行排序，然后从 $0$ 到 $d$ 遍历时间节点，在第 $i$ 时刻时，考虑高度为 $i$ 的地面被淹没所会造成的影响。 现在考虑下标为 $j$ 的地面被淹没造成的影响：
- 如果其左右两侧的地面已经被淹没，则该处地面被淹没后，答案减一。
- 如果其左右两侧地面都未被淹没，则该处地面被淹没后，答案加一。
- 其余情况，不会使答案发生改变。
在高度为 $i$ 的地面全部考虑完后，则所得答案即为时刻 $i$ 的答案。
最后统计异或和即可。
时间复杂度为 $O(n\log n)$。
方法二
观察到在固定时刻 $h$，合法二元组 $(x,y)$ 的数量，与 $a_i > h$ 且 $a_{i - 1} \le h$ 的下标 $i$ 的数量相等，因此可以考虑每处下标的地面在哪些时刻具有贡献。 对于 $a_{i - 1} \le a_i$ 的下标 $i$，显然其在任意时刻都没有贡献。 对于 $a_{i - 1} < a_i$ 的下标 ，在 $h \in [a_{i - 1}, a_i - 1]$ 时， 其具有 $1$ 的贡献。 使用差分进行区间修改，最后统计答案即可。 时间复杂度为 $O(n)$。
DIU 做法：
哪那么多废话，枚举雨水高度，直接无脑用 DIU 模拟区间分割即可。时间复杂度 $O(n\log n)$
void solve() {
int n;
std::cin >> n;
std::map<int, std::vector<int>> pos;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
pos[x].push_back(i);
}
int h = pos.rbegin()->first;
auto cmp = [](const auto& a, const auto& b) -> auto {
return a.second < b.first;
};
std::set<std::pair<int, int>, decltype(cmp)> s(cmp);
s.insert({0, n - 1});
auto add = [&](int l, int r) -> void {
if (l > r) return;
s.insert({l, r});
};
int ans = 0;
for (int i = 0; i < h; i++) {
for (auto &j : pos[i]) {
auto it = s.find({j, j});
auto [l, r] = *it;
s.erase(it);
add(l, j - 1);
add(j + 1, r);
}
ans ^= (int)s.size();
}
std::cout << ans;
}
CF2020D Connect the Dots
题意：
在一个晴朗的夜晚，爱丽丝坐下来玩经典游戏 “连连看”，但游戏规则有了变化。
游戏开始时，爱丽丝画了一条直线，并在直线上标出了 $n$ 个点，索引从 $1$ 到 $n$ 。最初，这些点之间没有弧线，所以它们都是不相交的。之后，爱丽丝执行了 $m$ 次以下类型的操作：
- 她选取三个整数 $a_i$ 、 $d_i$ ( $1 \le d_i \le 10$ ) 和 $k_i$ 。
- 她选取点 $a_i, a_i+d_i, a_i+2d_i, a_i+3d_i, \ldots, a_i+k_i\cdot d_i$ 并用弧连接每一对点。
在完成所有 $m$ 操作后，她想知道这些点所构成的连通部分的个数 $^\dagger$ 。请帮她求出这个数。
$^\dagger$ 如果两点之间有一条路径经过几条（可能为零）弧和其他点，则这两点被称为在一个相连的分量中。
DIU 做法：
DIU 配合 DSU，考虑到 $d$ 特别小，最大为 $10$，我们直接开 $10 * 10 = 100$ 个 DIU，然后每次操作时，在对应 $d$ 的 $a % d$ 的 DIU 中进行区间合并即可。
全部操作处理完毕后，暴力遍历所有的 DIU，用 DSU 合并处理即可。
时间复杂度：$O(100n\log^2n)$
const int N=200005;
int F[N];
int find(int x){//查询，自带路径压缩
return x==F[x]?x:F[x]=find(F[x]);
}
void join(int x,int y){//合并集合
F[find(x)]=find(y);
}
void solve() {
int n, m;
std::cin >> n >> m;
for (int i = 1; i <= n; i++) F[i] = i;
auto cmp = [](const auto& a, const auto& b) -> bool {
return a.second < b.first;
};
std::vector<std::vector<std::set<std::pair<int, int>, decltype(cmp)>>> seg(11);
for (int i = 1; i <= 10; i++) {
seg[i] = std::vector<std::set<std::pair<int, int>, decltype(cmp)>>(i, std::set<std::pair<int, int>, decltype(cmp)>(cmp));
}
while (m--) {
int a, d, k;
std::cin >> a >> d >> k;
if (k == 0) continue;
auto it = seg[d][a % d].find({a, a + k * d});
if (it == seg[d][a % d].end()) {
seg[d][a % d].insert({a, a + k * d});
} else {
int L = a;
int R = a + k * d;
while ((it = seg[d][a % d].find({a, a + k * d})) != seg[d][a % d].end()) {
L = std::min(L, it -> first);
R = std::max(R, it -> second);
seg[d][a % d].erase(it);
}
seg[d][a % d].insert({L, R});
}
}
for (int i = 1; i <= 10; i++) {
for (int j = 0; j < i; j++) {
for (auto &[l, r] : seg[i][j]) {
for (int k = l; k <= r; k += i) {
join(l, k);
}
}
}
}
std::set<int> cnt;
for (int i = 1; i <= n; i++) {
cnt.insert(find(i));
}
std::cout << cnt.size() << "\n";
}
GYM104095 J. 二进制与、平方和
2020 CCPC Henan Provincial Collegiate Programming Contest J 二进制与、平方和
题意：
请你维护一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$，支持以下两种操作：
第一种操作会将序列 $a_l, a_{l + 1}, \dots, a_r$ 中的每个元素，修改为各自和 $x$ 的"二进制与"（Bitwise binary AND）的值，其中 $l, r, x$ 在每次操作时会给定； 第二种操作会询问序列 $a_l, a_{l + 1}, \dots, a_r$ 中所有元素的平方和模 $998244353$ 的值，即 $ \sum_{i = l}^ra_i^2 \mod 998244353$，其中 $l, r$ 在每次操作时会给定。 总共有 $q$ 次操作，请你在维护序列的过程中，输出第二种操作所询问的答案。注意需要取模。
DIU 做法：
考虑操作一有次数限制，对与 $n$ 个数的每个位，操作一最多能进行 $1$ 次操作，暴力修改，最多次数是 $nlogv$ 次。
我们可以对每个位开 DIU，维护一堆连续的 $1$ 区间，然后每次操作一的时候暴力对每位的 DIU 进行修改即可。
至于平方和，直接用树状数组 BIT 解决。
时间复杂度 $O(nlogvlogn)$
constexpr int M = 998244353;
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]) %= M;
x -= (x &- x);
}
return s;
}
void modify(int x, T val) {//单点增加x处的值 O(logn)
while (x <= n) {
(a[x] += val) %= M;
x += (x &- x);
}
}
};
void solve() {
int n;
std::cin >> n;
std::vector<i64> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
auto cmp = [](const auto& a, const auto& b) -> auto {
return a.second < b.first;
};
std::vector<std::set<std::pair<int, int>, decltype(cmp)>> seg(24);
for (int i = 0; i < 24; i++) {
seg[i] = std::set<std::pair<int, int>, decltype(cmp)>(cmp);
}
for (auto &s : seg) {
s.insert({1, n});
}
auto add = [&](int l, int r, std::set<std::pair<int, int>, decltype(cmp)>& s) {
if (l <= r) s.insert({l, r});
};
for (int i = 1; i <= n; i++) {
for (int w = 0; w < 24; w++) {
if (!(a[i] >> w & 1)) {
auto it = seg[w].find({i, i});
auto [l, r] = *it;
seg[w].erase(it);
add(l, i - 1, seg[w]);
add(i + 1, r, seg[w]);
}
}
}
BIT<i64> bit(n);
for (int i = 1; i <= n; i++) {
bit.modify(i, (a[i] % M) * (a[i] % M) % M);
}
int q;
std::cin >> q;
while (q--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r;
i64 x;
std::cin >> l >> r >> x;
for (int w = 0; w < 24; w++) {
if ((x >> w & 1)) continue;
auto it = seg[w].find({l, r});
while (it != seg[w].end() && it->first <= r) {
auto [sl, sr] = *it;
it++;
seg[w].erase(std::prev(it));
for (int i = std::max(l, sl); i <= std::min(sr, r); i++) {
bit.modify(i, (M - (a[i] % M) * (a[i] % M) % M) % M);
a[i] = a[i] ^ (1ll << w);
bit.modify(i, (a[i] % M) * (a[i] % M) % M);
}
add(sl, l - 1, seg[w]);
add(r + 1, sr, seg[w]);
}
}
} else {
int l, r;
std::cin >> l >> r;
std::cout << (M + bit.getsum(r) - bit.getsum(l - 1)) % M << "\n";
}
}
}
练习用例题
仅作为 DIU 练手用，有些题目用 DIU 可能反而麻烦了：
CF1927D Find the Different Ones!
2020 CCPC Henan Provincial Collegiate Programming Contest J 二进制与、平方和
CF915E Physical Education Lessons
嵌套 STL 报错问题
我也不知道为什么会报错，在使用其他 STL 套 DIU 前，记得先给 STL 内部的 DIU 赋个值初始化一下，不然没法正常使用。
auto cmp = [](const auto& a, const auto& b) -> auto {
return a.second < b.first;
};
std::vector<std::set<std::pair<int, int>, decltype(cmp)>> seg(24);
for (int i = 0; i < 24; i++) {
seg[i] = std::set<std::pair<int, int>, decltype(cmp)>(cmp);
}
或者：
auto cmp = [](const auto& a, const auto& b) -> auto {
return a.second < b.first;
};
std::vector<std::set<std::pair<int, int>, decltype(cmp)>>
seg(24, std::set<std::pair<int, int>, decltype(cmp)>(cmp));
也就动手复制粘贴的事情，花不了多少时间，就当是为了使用它那美丽性质的代价吧。
后记
多次实践中发现，这其实就是散装珂朵莉树吧。很多珂朵莉树能过的题，它都能过。