题目：[[2024.10.24 题目]]
## 长方体
有 $n$ 个长方体，第 $i$ 个对角线的两个顶点为 $(x_0,y_0,z_0)$ 和 $(x_1,y_1,z_1)$。求至少被 $n-1$ 个长方体所覆盖的整点数量。
---
显然若答案求的是被正好 $n$ 个长方体覆盖的整点数量很好算，对于下标为 $0$ 的我们取最大值，对于下标为 $1$ 的我们取最小值，最后最小值前去最大值，三个维度乘起来即可。
想到这一步，转换到 $n-1$ 个长方体的求法就很简单了。我们可以枚举 $i$，假设 $i$ 不算入答案，那么对 $1\sim i-1$ 和 $i+1\sim n$ 的长方体我们就可以使用 $n$ 个长方形的求法，时间复杂度 $\mathcal O(n^2)$。不难想到答案只需要各个维度的最大值与最小值，因此可以做一下前缀最大值、前缀最小值、后缀最大值、后缀最小值，这样子时间复杂度就可以有效地降到 $\mathcal O(n)$。上面所述的方法有很大的问题，就是对于有些点，可能去掉多个不同的长方形仍然可以算在内，因此我们考虑反向容斥。
对于这种点，它们只可能是 $n$ 个长方形都共有的部分。因此我们提前将这一部分的体积算出来，假设有 $m$ 个长方形被去掉后 $n-1$ 个长方形仍然有共同的部分，那么答案就减去 $(m-1)\times V$，其中 $V$ 是这一部分的体积。问什么要减一呢？因为凡事都不能做得太绝对，毕竟「做人留一线，日后好相见。」
```cpp
#include <fstream>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("cube.in");
ofstream cout("cube.out");
struct Cube {
LL x0, y0, z0, x1, y1, z1;
} a[kMaxN];
LL premax[kMaxN][3], premin[kMaxN][3], sufmax[kMaxN][3], sufmin[kMaxN][3], n, ans;
int main() {
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i].x0 >> a[i].y0 >> a[i].z0 >> a[i].x1 >> a[i].y1 >> a[i].z1;
}
premax[0][0] = premax[0][1] = premax[0][2] = -1e18;
premin[0][0] = premin[0][1] = premin[0][2] = 1e18;
for (LL i = 1; i <= n; i++) {
premax[i][0] = max(premax[i - 1][0], a[i].x0);
premax[i][1] = max(premax[i - 1][1], a[i].y0);
premax[i][2] = max(premax[i - 1][2], a[i].z0);
premin[i][0] = min(premin[i - 1][0], a[i].x1);
premin[i][1] = min(premin[i - 1][1], a[i].y1);
premin[i][2] = min(premin[i - 1][2], a[i].z1);
}
sufmax[n + 1][0] = sufmax[n + 1][1] = sufmax[n + 1][2] = -1e18;
sufmin[n + 1][0] = sufmin[n + 1][1] = sufmin[n + 1][2] = 1e18;
for (LL i = n; i >= 1; i--) {
sufmax[i][0] = max(sufmax[i + 1][0], a[i].x0);
sufmax[i][1] = max(sufmax[i + 1][1], a[i].y0);
sufmax[i][2] = max(sufmax[i + 1][2], a[i].z0);
sufmin[i][0] = min(sufmin[i + 1][0], a[i].x1);
sufmin[i][1] = min(sufmin[i + 1][1], a[i].y1);
sufmin[i][2] = min(sufmin[i + 1][2], a[i].z1);
}
for (LL i = 1; i <= n; i++) {
LL a1 = max(premax[i - 1][0], sufmax[i + 1][0]), a2 = min(premin[i - 1][0], sufmin[i + 1][0]);
LL b1 = max(premax[i - 1][1], sufmax[i + 1][1]), b2 = min(premin[i - 1][1], sufmin[i + 1][1]);
LL c1 = max(premax[i - 1][2], sufmax[i + 1][2]), c2 = min(premin[i - 1][2], sufmin[i + 1][2]);
if (a2 == 1e18 || b2 == 1e18 || c2 == 1e18) {
continue;
}
if (a1 <= a2 && b1 <= b2 && c1 <= c2) {
ans += (a2 - a1 + 1) * (b2 - b1 + 1) * (c2 - c1 + 1);
ans -= max(0LL, premin[n][0] - premax[n][0] + 1) *
max(0LL, premin[n][1] - premax[n][1] + 1) *
max(0LL, premin[n][2] - premax[n][2] + 1);
}
}
cout << ans + max(0LL, premin[n][0] - premax[n][0] + 1) *
max(0LL, premin[n][1] - premax[n][1] + 1) *
max(0LL, premin[n][2] - premax[n][2] + 1) << '\n';
return 0;
}
```
## 三角形
给定长度为 $n$ 的序列 $a$，第 $i$ 个数为 $a_i$。进行 $q$ 次询问，每次询问的格式为 $[l,r]$，求区间内是否能够选出三个不同的下标 $(i,j,k)$ 使得三条 $(a_i,a_j,a_k)$ 的线段可以组成三角形。
---
不会写，采用暴力。首先我们可以对区间 $[l,r]$ 内的所有元素都进行一个 $\mathcal O(n^3)$ 的枚举，然后判断是否满足条件。这种枚举是最暴力最纯洁得了，总时间复杂度 $\mathcal O(mn^3)$。
不难想到优化，假设 $a_i$ 和 $a_j$ 是最小的那两个，并且 $a_i\le a_j$，只枚举 $i$ 和 $j$，$k$ 肯定是选择满足 $a_k>a_j$ 的，且 $k$ 尽量小，这样子对于一个区间我们只需要花费 $\mathcal O(n^2)$，总时间复杂度 $\mathcal O(mn^2)$。
考虑继续优化。此时忽然想起小学数学老师告诉过我们的，对于一个数列，想要选择三个数的长度的线段组成三角形，只需要选择大小相邻的就行了。因此我们可以对 $[l,r]$ 内的元素排序，然后三个三个判断，这样子的总时间复杂度就降到了 $\mathcal O(mn)$。可以获得 $60$ 分。
**正解**：考虑最坏的情况，无法组成三角形。由于 $a_i+a_j>a_k$，因此最坏的情况是构造类斐波那契数列的 $a_k=a_i+a_j$ 的序列。由于斐波那契数列在 $10^{18}$ 的范围之内只有不到 $100$ 个数，因此大于 $100$ 的情况就可以直接输出有解，否则采用暴力判断。
## 区间
给定长度为 $n$ 的序列 $a$，第 $i$ 个数为 $a_i$，并给定 $m$ 和 $q$ 次操作，每次操作给出 $(o,l)$。若 $o=1$，则翻转区间 $[l,l+m-1]$ 内的元素；如果 $o=2$，则获取 $a_l$。对于所有的操作 $2$，求出答案的异或和。
---
采用暴力。对于操作一，我们直接使用两个指针 $i,j$ 通过交换来实现区间翻转；对于第二个操作直接输出 $a_l$ 即可。该算法的时间复杂度为 $\mathcal O(mq)$，在对应的数据范围中理论上只能获得 $30$ 分，但是由于数据过水，此做法实际上可以获得 $60$ 分。
## 图
有 $n$ 个结点，第 $i$ 个结点的点权为 $a_i$。若 $a_i\operatorname{and}a_j=0$（$\operatorname{and}$ 是按位与），则 $i$ 与 $j$ 有一条边。初始时集合 ${} S=\emptyset$，进行 $n$ 次操作，每次加入一个结点到 $S$。加入结点 $v$ 有两种方式：
- 直接加入结点 $v$，代价为 $0$；
- 选择另一个结点 $u\in S$ 且 $u$ 与 $v$ 之间有一条边，代价为 $a_u$。
求能够获得的最大代价。
---
赛时一眼想到了最大生成树，但是由于大样例挂掉红温便没有继续调试，实际上我的代码改几行就可以通过。
我提交的代码是采用状态压缩动态规划的版本。令 $dp_i$ 表示为当前状态为二进制 $i$（第 $j$ 位为 $1$ 代表第 $j$ 个结点已经加入了集合，反之反之），那么我们可以枚举新加入哪一个结点，必须是 $i$ 里面没有的；再枚举和哪一个连边，找出最大值，然后转移即可。
时间复杂度为 $\mathcal O(2^nn^2)$，侥幸获得 ${} 40$ 分。
## 总结
- **排名**：$7$；
- **比赛分数**：$260/400$；
- **情况**：相比 [[2024.10.23 模拟赛]]，没区别；
- **问题**：调不出题目就红温。