## 好三角形
#数学 #树状数组 #排序
首先看到曼哈顿距离就知道不好处理，所以把整个坐标轴旋转 $45\degree$ 变成切比雪夫距离[^1]，更方便操作。题目要求存在 $T$ 满足 $d(P,T)=d(Q,T)=d(R,T)$，而在切比雪夫距离中，与 $T$ 点距离为 $d$ 的所有点会连成一个以 $T$ 为中心，边长为 $2d$ 的正方形。
因此，问题就变成了选择一个三元组，是否存在一个正方形使得三元组中每一个点都能在正方形的边上。但是这个问题非常的复杂，并且通过样例我们可以发现不能满足的三元组数量较少，因此可以选择容斥，求不满足条件的三元组的数量。
经过长达两个多小时的开庭，我找到了三元组不满足条件的充分条件，就是其中一个点在另外两个点以对角组成的长方形内部，这样子是肯定无法满足条件的，因为内部的那个点无法搞到正方形的边上，强制搞上另外两个点就不行了。
转换成坐标来表述就是如果三元组以 $x$ 递增/减排序的话，$y$ 坐标仍然也是递增/减的（二位偏序，严格），那么三元组不满足条件。所以我们能够简单地写出一个 $\mathcal O(n^3)$ 的暴力。
```cpp
#include <iostream>
#include <map>
using namespace std;
using LL = long long;
const LL kMaxN = 5e5 + 5;
struct Node {
LL x, y, u, v;
} a[kMaxN];
LL n, ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
a[i].u = a[i].x + a[i].y;
a[i].v = a[i].x - a[i].y;
}
// 如果 j 在 i 和 k 作为对角组成的长方形内部，则无法构成好三角形
for (LL i = 1; i <= n; i++) {
for (LL j = 1; j <= n; j++) {
if (i != j) {
for (LL k = 1; k <= n; k++) {
if (k != i && k != j) {
ans += a[i].u < a[j].u && a[j].u < a[k].u && a[i].v < a[j].v && a[j].v < a[k].v;
ans += a[i].u < a[j].u && a[j].u < a[k].u && a[i].v > a[j].v && a[j].v > a[k].v;
}
}
}
}
}
cout << n * (n - 1) * (n - 2) / 6 - ans << '\n';
return 0;
}
```
可以发现这份代码能过大样例，只是复杂度不对。这证明我们猜测的结论正好就是三元组不满足条件的充分必要条件，那么就可以尝试优化了。
首先按照 $x$ 递增排序，这样子后面的 $x$ 一定大于前面的 $x$。$y$ 的话就用树状数组维护，此时就可以很简单地写出求解二位偏序二元组的代码了。但是这里是三元的，所以我们可以先跑一遍二维的，然后在二维的答案的基础上再跑一遍得到二维偏序三元组的数量，即不满足条件的三元组数量，然后用总数减去它就行了。
注意是严格递增/减，所以 $x$ 排序之后仍然要用双指针维护。时间复杂度 $\mathcal O(n\log_2 n)$。
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const LL kMaxN = 1e6 + 5;
struct Node {
LL x, y;
} a[kMaxN];
LL val[kMaxN], tr[kMaxN], dp[kMaxN], n, m, ans;
void modify(LL x, LL y) {
for (; x <= m; x += x & -x) {
tr[x] += y;
}
}
LL query(LL x) {
LL res = 0;
for (; x; x -= x & -x) {
res += tr[x];
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1, x, y; i <= n; i++) {
cin >> x >> y;
a[i].x = x + y;
a[i].y = x - y;
val[++m] = a[i].y;
}
sort(val + 1, val + m + 1);
m = unique(val + 1, val + m + 1) - val - 1;
sort(a + 1, a + n + 1, [](const Node &a, const Node &b) {
return a.x < b.x;
});
// x 递增且 y 递增
for (LL i = 1, j = 1; i <= n; i++) {
a[i].y = lower_bound(val + 1, val + m + 1, a[i].y) - val;
for (; j < n && a[j].x < a[i].x; j++) {
modify(a[j].y, 1);
}
dp[i] = query(a[i].y - 1);
}
fill(tr + 1, tr + m + 1, 0);
for (LL i = 1, j = 1; i <= n; i++) {
for (; j < n && a[j].x < a[i].x; j++) {
modify(a[j].y, dp[j]);
}
ans += query(a[i].y - 1);
}
// x 递增且 y 递减
fill(tr + 1, tr + m + 1, 0);
for (LL i = 1, j = 1; i <= n; i++) {
for (; j < n && a[j].x < a[i].x; j++) {
modify(a[j].y, 1);
}
dp[i] = query(m) - query(a[i].y);
}
fill(tr + 1, tr + m + 1, 0);
for (LL i = 1, j = 1; i <= n; i++) {
for (; j < n && a[j].x < a[i].x; j++) {
modify(a[j].y, dp[j]);
}
ans += query(m) - query(a[i].y);
}
cout << n * (n - 1) * (n - 2) / 6 - ans << '\n';
return 0;
}
```
[^1]: $A(x_1,y_1)$ 和 $B(x_2,y_2)$ 之间的切比雪夫距离为 $\max(|x_1-x_2|,|y_1-y_2|)$，即斜着走需要的最小步数。
## 树上探测
#树形dp
首先预处理倍增 LCA，这样子就可以方便地计算树上距离。对于 $d_a+d_b=dis(a,b)$ 的数据，选择 $a$ 往上跳 $d_a$ 步或者选择 $b$ 往上跳 $d_b$ 步就行了，用那个不会跳到 LCA 以上的。其余数据全部写暴力。成功获得 $25$ 分。
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int kMaxN = 4e5 + 5, kLog = 21;
int dp[kMaxN][kLog], d[kMaxN], n, q;
vector<int> e[kMaxN];
void dfs(int x, int f) {
d[x] = d[f] + 1;
dp[x][0] = f;
for (int i = 1; i < kLog; i++) {
dp[x][i] = dp[dp[x][i - 1]][i - 1];
}
for (int i : e[x]) {
if (i != f) {
dfs(i, x);
}
}
}
int jump(int x, int k) {
for (int i = 0; i < kLog; i++) {
if (k & (1 << i)) {
x = dp[x][i];
}
}
return x;
}
int lca(int x, int y) {
if (d[x] < d[y]) {
swap(x, y);
}
x = jump(x, d[x] - d[y]);
if (x == y) {
return x;
}
for (int i = kLog - 1; i >= 0; i--) {
if (dp[x][i] != dp[y][i]) {
x = dp[x][i];
y = dp[y][i];
}
}
return dp[x][0];
}
int dis(int x, int y) {
return d[x] + d[y] - 2 * d[lca(x, y)];
}
int main() {
// freopen("main.in", "r", stdin);
// freopen("main.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
int x, dx, y, dy;
for (; q; q--) {
cin >> x >> dx >> y >> dy;
int l = lca(x, y);
if (d[x] + d[y] - 2 * d[l] == dx + dy) {
if (d[x] < d[y]) {
swap(x, y);
swap(dx, dy);
}
if (dx <= d[x] - d[l]) {
cout << jump(x, dx) << '\n';
} else {
cout << jump(y, dy) << '\n';
}
} else {
bool b = 0;
for (int i = 1; i <= n; i++) {
if (dis(i, x) == dx && dis(i, y) == dy) {
cout << i << '\n';
b = 1;
break;
}
}
if (!b) {
cout << "-1\n";
}
}
}
return 0;
}
```
## 按位覆盖
#二分 #前缀和
暴力都不会，$0$ 分。
## 最小权值
#树形dp #背包dp
采取的纯暴力，DFS 套 DFS，成功获得 $15$ 分。
## 总结
总分 $100+25+15=140$。
全场精力基本上全部都在想 T1，虽然最后想出来了但是另外几题啥都没过脑，代码源该降低难度了。不过感谢 PTY 老铁之前 ABC 教我们曼哈顿转切比雪夫，让我成功守住了 T1 的 AC。T2 应该也是我可以做的，等会想一想。后面两题太超标了。