## 博弈
#模拟 #博弈论
> [!note] 思路分析
>
> 根据题意，选择的两个元素若是一奇一偶那么最终值相对于它们的和将会减少 $1$，否则不变。所以对于第一个人，肯定是优先选择同奇同偶的。第二个人需要最小化答案，那么会优先选择一奇一偶的。
> [!question] 问题
>
> 但是第一个人在奇数和偶数都很多的情况下，会进行什么操作呢？它会优先选择两个奇数的消掉。这样就可以让第二个人没有奇数用；不消偶数的原因是不管任何情况合出来都会增加一个偶数。
> [!success] 正确思路
>
> 所以先进行若干次理想型操作，即第一个人反复拿两个奇数合成一个偶数，第二个人拿一个偶数一个奇数合成一个偶数。即每次消除三个奇数，然后答案减去一。可以 $\mathcal O(1)$ 计算完成。
>
> 对于最后剩下的元素，再进行不超过一轮以后，只会剩下偶数，此时和不变。可以直接模拟最后的操作。
- [n] 对于每个前缀都进行计算。时间复杂度 $\mathcal O(n)$。
```cpp
#include <fstream>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("makise.in");
ofstream cout("makise.out");
LL a[kMaxN], n, c0, c1, ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
c0 += a[i] % 2 == 0;
c1 += a[i] % 2 == 1;
LL x0 = c0, x1 = c1;
LL sub = x1 / 3;
x1 %= 3;
ans += a[i];
x0 += sub;
if (x1 >= 2) {
x1 -= 2;
x0++;
} else if (x0 >= 2) {
x0--;
} else if (x0 && x1) {
x0--, x1--;
sub++;
}
if (x0 && x1) {
sub++;
}
cout << ans - sub << ' ';
}
return 0;
}
```
## 购物
#贪心 #优先队列 #排序
> [!summary] 赛时思路
>
> 考虑较多次地选择 $b$ 最大（其次 $a$）的的元素，枚举其它元素的选择次数（最多不超过 $\min(2n, m)$），然后用优先队列每次选择其它元素当中可选的最大值。
> [!attention] 注意
>
> 赛时思路是错误的。考虑这个 $n=2,m=3$ 的样例
>
> $
> \left(\begin{matrix}
> 0&100\\
> 10&0\\
> 5&99
> \end{matrix}\right)
> $
>
> 我们把 $(0,100)$ 单独搞出去，枚举其它的选多少个。如果什么都不选就是 $100$。当选择其它的一个时，程序将贪心地选择 $10$。此时并不优。但是当选择其它的两个是，我们会选择 $5$，这直接导致了我们错过了最优解 $5+99$。
> [!question] 猜想
>
> 这似乎需要通过反悔贪心实现，不过我的实现仍然无法成功地通过大样例。
- [p] 好在只挂了 $15$ 分。
对于这道题目，一共有两种思路。他们都是正确的。
> [!success] 正确思路一
>
> 既然我们不一定会选择 $b_\max$ 较多次，于是我们就可以直接枚举选择哪个 $b_i$，那么就必定同样会选择 $a_i$。对于其它元素 $j\ne i$ 的 $b_j$ 我们都不会再次选择了，所以我们把所有大于 $b_i$ 的 $a_j$ 给选了。可以通过排序后二分或双指针实现。时间复杂度 $\mathcal O(m\textcolor{gray}{\log_2 m})$。
> [!success] 正确思路二
>
> 直接把一个物品拆成两个物品 $a_i,b_i$ 从大到小加入优先队列当中（$a$ 还是 $b$ 的信息仍要保留）。对于新的一个元素，如果是 $a$ 直接选上即可；如果是 $b$，如果以前已经选过了其对应的 $a$，直接选上即可；否则若剩余步数允许就把它的 $a$ 选上之后反复选 $b$，和答案求个 $\max$（注意这里不要 `break` 也不是实际选上了）。时间复杂度 $\mathcal O(m\log_2 m)$。
- [n] 我赛后改题实现的是正确思路二。
```cpp
#include <algorithm>
#include <fstream>
#include <queue>
#include <utility>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("shop.in");
ofstream cout("shop.out");
LL f[kMaxN], t, n, m;
pair<LL, LL> a[kMaxN];
struct Node {
LL id, val, tp;
Node(LL id, LL val, LL tp) : id(id), val(val), tp(tp) {}
friend bool operator<(const Node& a, const Node& b) {
return a.val != b.val ? a.val < b.val : a.tp < b.tp;
}
};
priority_queue<Node> q;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n >> m;
for (; q.size(); q.pop()) { }
fill(f + 1, f + m + 1, 0);
for (LL i = 1; i <= m; i++) {
cin >> a[i].first >> a[i].second;
q.emplace(i, a[i].first, 1);
q.emplace(i, a[i].second, 2);
}
LL ans = 0, sum = 0;
while (q.size()) {
auto [id, val, tp] = q.top();
q.pop();
if (!n) {
break;
}
if (tp == 1) {
sum += val;
ans = max(ans, sum);
f[id] = 1;
n--;
} else {
if (f[id]) {
sum += val * n;
ans = max(ans, sum);
break;
} else {
if (n == 1) {
continue;
}
ans = max(ans, sum + a[id].first + val * (n - 1));
}
}
}
cout << ans << '\n';
}
return 0;
}
```
## 划分
#线段树 #序列dp #ST表 #单调栈
> [!note] 思路
>
> 考虑 DP。由于和分段数量没有关系，所以设 $dp_i$ 表示若最后一段的最后一个元素为 $i$，所可以获得的最大价值。
>
> 转移如下：枚举最后一段实际的起点 $j$ $(1\le j\le i)$，那么前一段的终点就是 $j-1$，有 $dp_i=\max\limits_{j=1}^i(dp_{j-1}+f(j,i))$，其中 $f(j,i)$ 为 ${} b_k$ 其中 $b_k\ge a_{p}$ $(p\in[j,i])$。不难发现可以通过倒叙枚举 $j$ 维护最小值，时间复杂度优化为 $\mathcal O(n^2)$。
> [!important] 优化
>
> DP 状态设计已经足够简单了，如果优化转移复杂度呢？考虑维护全局最值，快速求出 $dp_{j-1}+f(j,i)$。
>
> 考虑线段树维护 $dp_{j-1}$ 和上面一大坨。首先我们思考，对于前面的所有状态每个的后方都加入一个 $a_i$，谁的最小值会改变谁不会？可以找到最后一个 ${} a_j\ge a_i$，$k\ge j$ 的就会改变，否则不会。
>
> > [!tip] 提示
> >
> > 可以用单调栈快速求，也可以用 ST 表维护 $a$ 的最小值然后二分。
>
> 现在对于 $k\in[j,i]$，$dp_k$ 后面的增量都会变成 $+b_i$。可以在线段树上直接做区间修改，拆成多段区间每段值都等于这一段 DP 最大值加上 $b_i$。
>
> 现在 $dp_i$ 就可以通过查询线段树全局最小值得到。由于是查询全局不需要写懒标记下放。
>
> 考虑 $dp_i$ 往后面的转移，作为 DP 值插入到线段树 $i$ 位置上即可。
找 $j$ 时间复杂度 $\mathcal O(n\textcolor{gray}{\log_2 n})$，计算 DP 时间复杂度 $\mathcal O(n\log_2 n)$。
```cpp
#include <fstream>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 10, kLog = 20;
ifstream cin("divide.in");
ofstream cout("divide.out");
struct Node {
LL dp, mx;
Node(): dp(-1e18), mx(-1e18) { }
} tr[4 * kMaxN];
LL a[kMaxN], b[kMaxN], f[kMaxN][kLog], lg[kMaxN], dp[kMaxN], n;
LL query(LL l, LL r) {
LL k = lg[r - l + 1];
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
Node merge(const Node &a, const Node &b) {
Node res{};
res.dp = max(a.dp, b.dp);
res.mx = max(a.mx, b.mx);
return res;
}
// 修改增量
void modifyAdd(LL p, LL l, LL r, LL s, LL t, LL val) {
if (s <= l && r <= t) {
tr[p].mx = tr[p].dp + val;
return;
}
LL m = (l + r) / 2;
if (s <= m) {
modifyAdd(2 * p, l, m, s, t, val);
}
if (m < t) {
modifyAdd(2 * p + 1, m + 1, r, s, t, val);
}
tr[p] = merge(tr[2 * p], tr[2 * p + 1]);
}
// 修改dp值
void modifyDp(LL p, LL l, LL r, LL x, LL val) {
tr[p].dp = max(tr[p].dp, val);
if (l == r) {
return;
}
LL m = (l + r) / 2;
if (x <= m) {
modifyDp(2 * p, l, m, x, val);
} else {
modifyDp(2 * p + 1, m + 1, r, x, val);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
f[i][0] = a[i];
}
for (LL i = 1; i <= n; i++) {
cin >> b[i];
}
for (LL j = 1; j < kLog; j++) {
for (LL i = 1; i + (1 << j) - 1 <= n; i++) {
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
for (LL i = 2; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
fill(begin(tr), end(tr), Node());
modifyDp(1, 0, n, 0, dp[0] = 0);
for (LL i = 1; i <= n; i++) {
LL p = i;
for (LL l = 1, r = i; l <= r; ) {
LL m = (l + r) / 2;
if (query(m, i) == a[i]) {
p = m;
r = m - 1;
} else {
l = m + 1;
}
}
modifyAdd(1, 0, n, p - 1, i - 1, b[i]);
dp[i] = tr[1].mx;
modifyDp(1, 0, n, i, dp[i]);
}
cout << dp[n] << '\n';
return 0;
}
```
## 树上计数
#树链剖分 #点分治 #树形dp #启发式合并
我写的暴力。
> [!note] 思路
>
> 首先可以枚举三元组的中间点，使得三个点到枚举的点距离相同。这个点肯定不会在边上。
>
> 枚举后以 $i$ 为根开始，跑出所有点的深度。那么我们求的以 $i$ 为中心的三元组肯定深度相同，且在 $i$ 的儿子的不同子树当中。这是一个组合数问题，可以线性解决。
>
> 时间复杂度 $\mathcal O(n^2)$。成功获得 $30$ 分。
正解是长链剖分+树形 DP $\mathcal O(n)$，当然淀粉质+树上启发式合并 $\mathcal O(n\log^2 n)$ 也过了。