题目：[[2024.11.17 题目]]
## 覆盖
在 $[0,w]$ 的坐标轴上有 $n$ 个区间，第 $i$ 个区间为 $[l_i,r_i]$。现在你需要去掉一部分区间，使区间 $(x,x+c)$ 与任意一个原本的区间不重叠。第 $i$ 个区间删去代价为 $p_i$，求满足条件需要的最少代价。
---
首先，我们对区间以 $r$ 为关键字从小至大进行排序，然后枚举 $r_i$，尝试答案区间为 $(r_i,r_i+c)$ 需要的代价。由于 $l_i\le r_i$，因此只有 $j>i$ 的区间 $[l_j,r_j]$ 可能会与 $(r_i,r_i+c)$ 重叠。但是，我们发现这里重叠的标准是 $l$ 是否小于 $r_i+c$，不妨在 $l$ 上面下功夫。
新建另一个区间序列 $b$，将 $b_i$ 赋值为 $[l_i,r_i]$，对 $b$ 以 $l$ 为关键字从小至大排序，此时我们就可以极快地通过二分求出哪一段的 $l_i<r_i+c$ 了。此时我们发现当 $r_i<c$ 时即使 $l_i<r_i+c$ 也不会与我们的答案区间重叠，而原序列又是按照 $r_i$ 进行排序的，因此我们直接新建变量满足 $r_i<c$ 的区间 $p_i$ 记录下来，求答案时需要减去。
最后对于所有的答案区间进行求值即可。时间复杂度 $\mathcal O(n\log_2 n)$。注意 $(0,c)$ 也是一个可选的答案区间，不能忽略，否则会失分。
```cpp
#include <fstream>
#include <algorithm>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("cover.in");
ofstream cout("cover.out");
struct Interval {
LL l, r, p;
bool operator<(const Interval &that) {
return l < that.l;
}
} a[kMaxN], b[kMaxN];
LL p[kMaxN], n, w, c, sub, ans = 1e18;
LL calc(LL x) {
LL y = lower_bound(b + 1, b + n + 1, Interval{x, x, x}) - b - 1;
return p[y] - sub;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> w >> c;
for (LL i = 1; i <= n; i++) {
cin >> a[i].l >> a[i].r >> a[i].p;
b[i] = a[i];
}
sort(a + 1, a + n + 1, [](auto a, auto b) { return a.r < b.r; });
sort(b + 1, b + n + 1);
for (LL i = 1; i <= n; i++) {
p[i] = p[i - 1] + b[i].p;
}
ans = min(ans, calc(c));
for (LL i = 1; i <= n; i++) {
if (a[i].r + c <= w) {
sub += a[i].p;
ans = min(ans, calc(a[i].r + c));
}
}
cout << ans << '\n';
return 0;
}
```
## 分发传单
最开始有 $1$ 个 $1$ 代生物。有 $n$ 秒的时间可以让他们工作，第 $i$ 代生物可以进行如下工作：花费 $1$ 秒分发 $1$ 张传单或花费 $c\times i$ 秒繁殖一个第 $i+1$ 代的生物。多个生物可以同时工作，求 $n$ 秒内可以分发的传单的数量的最大值。
---
题目完全看懂了，但是对于小至 $1\le n_i,c_i\le 20$ 的数据仍然毫无头绪，代码都没输入，文件都没有创建，本题成功获得 $0$ 分。
**后记**：XBC 是机房内唯一一个使用 ${} \mathcal O(n^2)$ dp 的，获得 $50$ 分，本机房最高分。
![[the-end.png#pic_center]]
## 绘画
有 $n$ 个格子，进行 $k$ 次涂色，第 $i$ 将任意连续 $a_i$ 个格子染黑，若已经被染黑则颜色不变。求最后得到不同的结果的数量，答案为 $10^9+7$ 取模。
---
采用最垃圾的手段进行骗分。对于 $k=1$ 的特殊情况，也就是只会涂一次颜色，那么显然不会出现任何一个格子被重复填色的情况，因此答案即为 $n-a_1+1$。成功获得 $10$ 分。
**后记**：HHC 推公式 AC 掉了 $k\le 2$ 的所有测试点，太巨了。
## 三角覆盖
给出一个直角边长为 $n$ 的等腰直角三角形点集，共有 $n$ 行，第 $i$ 行的点为 $(i,1),(i,2),\cdots,(i,i)$。
有 $m$ 次覆盖操作，每次覆盖一个等腰直角三角形区域内的点，第 $i$ 次给出 $3$ 个数 $a_i,b_i,c_i$，表示对于 $1\le k\le j\le c_i$，点 $(a_i+j-1,b_i+k-1)$ 被覆盖了。
随后给出 $q$ 次询问操作，询问一个等腰直角三角形区域内未被覆盖的点数，第 $i$ 次给出 $3$ 个数 $d_i,e_i,f_i$，表示询问所有 $1\le k\le j\le f$，点 $(d_i+j-1,e_i+k-1)$ 有多少未被覆盖。
---
采用差分+前缀和的方式对于 $n\le 5000$ 的数据进行处理。
当 $n$ 较小的时候，我们可以对于每一次处理都枚举每一行，但是不能枚举修改的三角形当中的每一个点。因此不难想出对于每一行进行序列差分。
但是我们需要考虑的很重要一个点，就是我们的差分是对一个区间的每一个元素进行相加，而非将区间内的每一个元素标记为 $1$。这该怎么整呢？
实际上，我们还是正常地进行差分（区间都加 $1$），但是利用前缀和还原之后对于每一个不为 $0$ 的元素其实就是 $1$（原本的值代表它被标记了几次，而只要被标记了正整数次就是被覆盖），否则为 $0$。
然后再进行一次每行的前缀和。这样子我们的查询操作也能做到 $\mathcal O(nq)$。该算法的总时间复杂度为 $\mathcal O(n(m+q))$，成功获得 $30$ 分。