## 乘法减法按位或
#数学 #结论 #位运算
首先 $\mathcal O(n^2)$ 是非常好想的，但是发现优化很难。观察到值域较小，所以可以想到设 $dp_i$ 表示满足 $a_j|a_k=i$ 最大的 $j\times k$。然而根本不会转移，所以直接趋势。
不过，观察式子中 $i\times j$ 是一个二次项，增长幅度特别快，而 $-k(a_i|a_j)$ 是一次项，当 $i,j$ 过大的时候后面的那一项几乎可以忽略，所以可以猜测答案 $(i,j)$ 肯定在靠后的位置。
严格证明如下：
- [n] 假设 $(n-1,n)$ 是最终最大的，那么我们需要推翻这个结论的话一定会有一个更大的。设更大的为 $(i,n)$，最好情况下该二元组的值为 $in-0=in$，而 $(n-1,n)$ 最坏情况下值为 $n(n-1)-2kn$。所以有方程 $in\ge n(n-1)-2kn$，解得 $i\ge n-2k-1$（也可以不取等），所以我们只需要枚举 $i\in [n-2k-1,n]$ 即可。
时间复杂度 $\mathcal O(kn)$。
```cpp
#include <iostream>
using namespace std;
using LL = long long;
const LL kMaxN = 3e5 + 5;
LL a[kMaxN], t, n, k;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
LL ans = -1e18;
for (LL i = max(1LL, n - 2 * k - 1); i <= n; i++) {
for (LL j = 1; j <= n; j++) {
if (i != j) {
ans = max(ans, i * j - k * (a[i] | a[j]));
}
}
}
cout << ans << '\n';
}
return 0;
}
```
## 队列
#数学
首先，把 $n$ 个同学变成 $n$ 个点，$a$ 要站在 $b$ 前面可以看做 $a$ 往 $b$ 连一条边，那么最后会形成一个图，有多个连通块。如果一个连通块可以满足条件，那么这个连通块是一条链（因为不仅有前后关系还要相邻）。
如何判断每个连通块是否是链？每个点的入度、出度均不超过 $1$，且没有环。判环用拓扑排序即可。注意去重边。去掉重边之后若剩下 $m$ 条边那么连通块数量为 $n-m$，这些连通块彼此之间没有前后关系因此方案数 $(n-m)!$。
时间复杂度 $\mathcal O(n+m)$（去重边我带了个 $\log$）。
```cpp
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
using LL = long long;
const LL kMaxN = 2e5 + 5, kMod = 1e9 + 7;
LL id[kMaxN], od[kMaxN], n, m, cnt, sum, ans = 1;
vector<LL> e[kMaxN];
queue<LL> q;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (LL i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].push_back(v);
}
for (LL i = 1; i <= n; i++) {
sort(e[i].begin(), e[i].end());
e[i].erase(unique(e[i].begin(), e[i].end()), e[i].end());
od[i] = e[i].size();
for (int j : e[i]) {
id[j]++;
}
}
if (count_if(id + 1, id + n + 1, [](LL i) {
return i > 1;
}) || count_if(od + 1, od + n + 1, [](LL i) {
return i > 1;
})) {
cout << "0\n";
return 0;
}
for (LL i = 1; i <= n; i++) {
if (!id[i]) {
q.push(i);
}
}
for (; q.size(); q.pop()) {
LL t = q.front();
cnt++;
for (LL i : e[t]) {
if (!--id[i]) {
q.push(i);
}
}
}
if (cnt != n) {
cout << "0\n";
return 0;
}
for (LL i = 1; i <= n; i++) {
sum += e[i].size();
}
sum = n - sum;
for (LL i = 1; i <= sum; i++) {
ans = ans * i % kMod;
}
cout << ans << '\n';
return 0;
}
```
## 权值
#数学 #等比数列求和 #快速幂 #乘法逆元
贡献可以拆为
1. 所有满足条件序列的数量；
2. 每个数的出现次数之和。
首先是第一问，对于长度为 $i$ 且取值范围在 $[1,n]$ 的整数序列，一共有 $n^i$ 种。因此序列数量为 ${} f(n,m)=\sum\limits_{i=0}^m n^i {}$。这是一个等比数列，应用等比数列求和公式得到
$
f(n,m)=\sum\limits_{i=0}^m n^i=
\begin{cases}
m+1&\text{if}~n=1 \\
\cfrac{n^{m+1}-1}{n-1}&\text{else}
\end{cases}
$
至于每个数的出现次数之和，由于每个数的地位相等，因此每个数的出现次数之和也相等。对于 $1$，可以采用容斥，用总序列数量减去不使用 $1$ 的序列数量，即
$
\sum_{i=0}^m n^i-\sum_{i=0}^n (n-1)^i=f(n,m)-f(n-1,m)
$
再将这个数乘上 $n$ 即可得到所有数的出现次数之和，再加上一类贡献，得到最终答案
$
f(n,m)+n\times f(n,m)-n\times f(n-1,m)=(n+1)f(n,m)-n\times f(n-1,m)
$
用快速幂和乘法逆元即可。时间复杂度 $\mathcal O(t(\log_2 m+\log_2 n))$。
```cpp
#include <iostream>
using namespace std;
using LL = long long;
const LL kMod = 1e9 + 7;
LL t, n, m;
LL pow(LL a, LL b) {
LL res = 1;
for (; b; b /= 2) {
b % 2 && (res = res * a % kMod);
a = a * a % kMod;
}
return res;
}
LL solve(LL n, LL m) {
if (n == 1) {
return m + 1;
}
return (pow(n, m + 1) - 1 + kMod) % kMod * pow(n - 1, kMod - 2) % kMod;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n >> m;
cout << ((n + 1) * solve(n, m) % kMod - n * solve(n - 1, m) % kMod + kMod) % kMod << '\n';
}
return 0;
}
```
## 钓鱼
#贪心 #优先队列
### 20 分
瞎搜就行了。状态就是 $(i,j)$ 表示当前到达第 $i$ 个地点，当前深度为 $j$，然后它可以转移到 $(i+1,j\pm 1)$ 或者 $(i+1,j)$，累加以下贡献就行了。
### 50 分
可以发现上面的算法对于重复状态 $(i,j)$ 在不同时刻结果不一样，但是结果肯定是越大越好，因此采用动态规划，将贡献列为最优化属性。设 $dp_{i,j}$ 表示当前到达第 $i$ 个地点，深度为 $j$ 所可以获得的最大饱腹值，转移方程 $dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j\pm 1})+j\times(B_i-A_i)$。
### 80 分
想到了 100 分的思路，但是用的是双 $\log$ 实现，或者直接用费用流模拟贪心过程了导致的。
- [b] 赛时被 $\mathcal O(n^2)$ 暴力卡过去了，下次再搞大一点。
### 100 分
假设已经凿完了，我们可以将层数“抽丝剥茧”，把第一层抽下来，然后把第二层抽下来，不难发现第 $K$ 层会完全被包含在第 $K-1$ 层中，而且这两层左端点和右端点一定是不会重合的（因为如果重合了相邻深度差就会大于 $1$）。
因此这道题目可以简化为“区间覆盖”的形式，即进行若干次选择，每次选择 $[L,R]$ 对 $L\sim R$ 的每一个地点都凿深一个单位，并且每个地点都只能作为左端点和作为右端点最多一次。
由于涉及到区间求和，可以整一个前缀和 $P_i=\sum\limits_{j=1}^i(B_j-A_j)$，这样我们选择一个区间的操作就可以简化为选择一前一后两个 $P_i$ 相减。这时候就和买股票那题很像了。
我们枚举右端点 $R$，因为一个点只能最多作为右端点一次，因此我们需要在之前的左端点中找到 $P_{L-1}$ 最小的然后让 $P_R$ 减去 $P_{L-1}$ 进行一次区间覆盖（当然如果结果是负数那就不要做了）。同时由于一个点只能作为左端点一次，因此 $L$ 用完之后就需要把 $L$ 扔掉。
这样不一定是最后的，原因是因为以后可能会有更大的 $P_R$ 来减 $P_{L-1}$ 会更优。但是注意到 $P_k-P_i=(P_k-P_j)+(P_j-P_i)$，也就是说先让 $P_{R}$ 减去 $P_{L-1}$ 之后，遇到后面更大的让它直接减 $P_R$ 而不是 $P_{L-1}$，是和不选 $P_{R}$ 直接让后面的减 $P_{L}$ 是一样的，因此我们只需要把 $P_R$ 额外放进队列，静待后面的 $P$ 减去 $P_R$ “反悔”就行了。最后将 $P_R$ 放入队列，作为以后的左端点。
时间复杂度 $\mathcal O(n\log_2 n)$。
```cpp
#include <iostream>
#include <queue>
using namespace std;
using LL = long long;
const LL kMaxN = 1e6 + 5;
LL p[kMaxN], n, ans;
priority_queue<LL, vector<LL>, greater<>> q;
int main() {
// 输入并作前缀和
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1, a, b; i <= n; i++) {
cin >> a >> b;
p[i] = p[i - 1] + b - a;
}
// 反悔贪心
q.push(p[0]);
for (LL i = 1; i <= n; i++) {
if (p[i] - q.top() > 0) { // 进行区间覆盖
ans += p[i] - q.top();
q.pop();
q.push(p[i]); // 留下反悔机会
}
q.push(p[i]);
}
cout << ans << '\n';
return 0;
}
```
## 渴鹅村
#线段树 #二分 #离散化 #树链剖分
本题主要就是靠随机树来保证做法复杂度的
### 20 分
纯暴力，修改只改 `a[x] = y`，然后查询就爬取整个一条链，每个节点 $\mathcal O(n \log_2 n)$（使用 STL kth-element 可以到 $\mathcal O(n)$）计算 $v$ 值，链最长 $\mathcal O(n)$，所以总时间复杂度 $\mathcal O(m \times n^2 (\times \log n))$。
不过由于树是随机生成的，期望高度 $\log n$，时间复杂度可能跑不到上界，但是我的数据还是太超模了所以卡不过去。
### 50 分
预先计算所有的 $v$ 值，修改只需要修改所有的祖先。预处理 $v$ 值时间复杂度 ${} \mathcal O(n^2 (\log n)) {}$。由于树高期望 $\log n$，因此修改时间复杂度 $\mathcal O(n (\log n))$ 查询和路径长度有关系，随机数据的话也许时间复杂度为 $\mathcal O(\log n (\log n))$ 吧，不过实测会更慢。可以通过 $n,m\le 1000$ 的数据点
### 100 分
首先看到路径上查询，先写个树链剖分。值域太大了，但是只用到比大小因此可以离散化。首先快速查询第 $k$ 大，我们通常采用权值线段树处理。查询 $v$ 的值，这里有两种办法：对于每一个节点维护它的子树内所有 $a$ 的值的权值线段树，然后 dfs 做一个线段树合并，这样就能快速查子树第 $k$ 小；或者树套树，用树链剖分的普通线段树套上权值线段树，然后在多颗权值线段树上同时二分找第 $k$ 小。由于后面的方案不影响整体时间复杂度，而且可以复用维护 $v$ 的树套树，因此我选择用后面的方式实现。
现在我们获得了所有的 $v$ 值，那就用树套树维护它。对于查询路径 $v$ 值第 $k$ 小，我们先树剖把他剖成若干条链，然后在存着权值线段树的根的普通线段树上查询，得到若干个可以覆盖整个询问路径的权值线段树的根，然后在这些权值线段树上同时二分第 $k$ 小。时间复杂度 $\mathcal O(\log^3 n)$，原因是树剖一个 $\log$，外层线段树一个 $\log$，内层一个 $\log$。
至于查询，往上遍历祖先，对 $a$ 值和 $v$ 值的树套树进行修改。由于树高期望 ${} \log n$，因此时间复杂度也是 ${} \mathcal O(\log^3 n) {}$ 的。
因此总时间复杂度为 $\mathcal O(m \log^3 n)$。
不过我没有卡树上莫队，如果你实现得非常好是可以过的。要卡的就加个强制在线操作，不过这样子就无法离散化导致常数爆炸了。但是树上带修莫队本身复杂度也就不咋地，应该是过不了的。
```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
template <class T>
using Ref = const T &;
const int kMaxN = 1e5 + 5, kMaxM = 128 * kMaxN;
// 操作类
struct Operation {
int o, x, y, k;
};
int a[kMaxN], k[kMaxN], fa[kMaxN], dep[kMaxN], siz[kMaxN], son[kMaxN], top[kMaxN], dfn[kMaxN], rnk[kMaxN], v[kMaxN], n, m, cnt;
int val[kMaxN], q;
vector<int> e[kMaxN];
vector<Operation> opt;
// 权值线段树动态开点
struct Node {
int lc, rc, sum;
};
// 权值线段树
struct ValueSegmentTree {
Node tr[kMaxM];
int cnt;
// 合并儿子节点
void pushUp(int p) {
tr[p].sum = tr[tr[p].lc].sum + tr[tr[p].rc].sum;
}
// 修改 x 处值增加 d
void modify(int &p, int l, int r, int x, int d) {
if (!p) {
p = ++cnt;
}
if (l == r) {
tr[p].sum += d;
return;
}
int m = (l + r) / 2;
if (x <= m) {
modify(tr[p].lc, l, m, x, d);
} else {
modify(tr[p].rc, m + 1, r, x, d);
}
pushUp(p);
}
// 多个结点同时线段树二分查询第 k 小
int query(Ref<vector<int>> &v, int l, int r, int k) {
if (l == r) {
return l;
}
int sum = 0;
for (int p : v) {
sum += tr[tr[p].lc].sum;
}
int m = (l + r) / 2;
if (k <= sum) {
vector<int> nxt;
for (int p : v) {
nxt.push_back(tr[p].lc);
}
return query(nxt, l, m, k);
}
vector<int> nxt;
for (int p : v) {
nxt.push_back(tr[p].rc);
}
return query(nxt, m + 1, r, k - sum);
}
} w_tr, v_tr;
int w_rt[4 * kMaxN], v_rt[4 * kMaxN];
// 在树链线段树上修改 x 点。在 t 权值线段上修改，根为 rt
void modify(ValueSegmentTree &t, int *rt, int p, int l, int r, int x, int val, int d) {
t.modify(rt[p], 1, q, val, d);
if (l == r) {
return;
}
int m = (l + r) / 2;
if (x <= m) {
modify(t, rt, 2 * p, l, m, x, val, d);
} else {
modify(t, rt, 2 * p + 1, m + 1, r, x, val, d);
}
}
// 获取同一条树链上 s~t 的权值线段树的所有根
void getRoot(int *rt, int p, int l, int r, int s, int t, vector<int> &res) {
if (s <= l && r <= t) {
res.push_back(rt[p]);
return;
}
int m = (l + r) / 2;
if (s <= m) {
getRoot(rt, 2 * p, l, m, s, t, res);
}
if (m < t) {
getRoot(rt, 2 * p + 1, m + 1, r, s, t, res);
}
}
// 获取离散化之后的值
int getHash(int x) {
return lower_bound(val + 1, val + q + 1, x) - val;
}
// 处理出父亲、深度、子树大小和重儿子
void dfs1(int x, int f) {
fa[x] = f;
dep[x] = dep[f] + 1;
siz[x] = 1;
for (int i : e[x]) {
if (i == f) {
continue;
}
dfs1(i, x);
siz[x] += siz[i];
if (siz[i] > siz[son[x]]) {
son[x] = i;
}
}
}
// 获取链头、dfs 序
void dfs2(int x, int t) {
top[x] = t;
dfn[x] = ++cnt;
rnk[cnt] = x;
if (!son[x]) {
return;
}
dfs2(son[x], t);
for (int i : e[x]) {
if (i == fa[x] || i == son[x]) {
continue;
}
dfs2(i, i);
}
}
// 查询子树中 A 值的第 k 小
int querySubtree(int x, int k) {
vector<int> v;
getRoot(w_rt, 1, 1, n, dfn[x], dfn[x] + siz[x] - 1, v);
return w_tr.query(v, 1, q, k);
}
// 查询路径上 V 值的第 k 小
int queryPath(int x, int y, int k) {
vector<int> v;
for (; top[x] != top[y]; x = fa[top[x]]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
getRoot(v_rt, 1, 1, n, dfn[top[x]], dfn[x], v);
}
if (dep[x] > dep[y]) {
swap(x, y);
}
getRoot(v_rt, 1, 1, n, dfn[x], dfn[y], v);
return v_tr.query(v, 1, q, k);
}
int main() {
// 输入
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
val[++q] = a[i];
}
for (int i = 1; i <= n; i++) {
cin >> k[i];
}
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1, o, x, y, k; i <= m; i++) {
cin >> o >> x >> y;
if (o == 1) {
opt.push_back(Operation {o, x, y});
val[++q] = y;
} else {
cin >> k;
opt.push_back(Operation {o, x, y, k});
}
}
// 离散化
sort(val + 1, val + q + 1);
q = unique(val + 1, val + q + 1) - val - 1;
// 树链剖分
dfs1(1, 0);
dfs2(1, 1);
// 插入 A 值到线段树
for (int i = 1; i <= n; i++) {
modify(w_tr, w_rt, 1, 1, n, dfn[i], getHash(a[i]), 1);
}
// 插入 V 值到线段树
for (int i = 1; i <= n; i++) {
v[i] = querySubtree(i, k[i]);
modify(v_tr, v_rt, 1, 1, n, dfn[i], v[i], 1);
}
// 操作与询问
for (auto &i : opt) {
auto &&[o, x, y, k] = i;
if (o == 1) {
int old = getHash(a[x]), now = getHash(y);
a[x] = y;
modify(w_tr, w_rt, 1, 1, n, dfn[x], old, -1);
modify(w_tr, w_rt, 1, 1, n, dfn[x], now, 1);
for (int cur = x; cur; cur = fa[cur]) {
old = v[cur];
now = querySubtree(cur, ::k[cur]);
if (old != now) {
modify(v_tr, v_rt, 1, 1, n, dfn[cur], old, -1);
modify(v_tr, v_rt, 1, 1, n, dfn[cur], now, 1);
v[cur] = now;
}
}
} else {
cout << val[queryPath(x, y, k)] << '\n';
}
}
return 0;
}
```