CodeForces 1320C World of Darkraft: Battle for Azathoth
(n)个武器(m)个盾牌，无论是武器还是盾牌都有相应的攻击值（防御值）和价格，同时还有(p)只怪物，每只怪物都有防御值、攻击值、和干掉它能有多少钱。你只能选择一件武器和一件盾牌去，问最终通过打怪获得最多的钱是多少（减去买武器和盾牌的花费后）？
题解
最朴素的想法是(O(nmp))，显然不行。那怎么入手呢？只考虑一维的话，对武器和怪物分别排序后，二分加算后缀就能解决。现在多了一维：盾牌和怪兽的攻击，有点难办了。对于每一件武器，假如它能杀死（仅仅只是武器的攻击值大于怪兽的防御值）的怪兽集合是(S)，那么怎么求集合(S)中能获得的最大收益呢？建一颗线段树，用来维护集合(S)的最大收益，每加入一个怪兽，假如它的攻击值为(x)，那么就更新大于(x)的那部分的最大值。举例来说：令(a[i] :=) 防御值为 (i) 的盾牌在集合S中能帮助您取得的最大收益，加入一个攻击值为(x)的怪兽，就更新：(a[x + 1] += coins, a[x + 2] += coins, ···)，然后取它们的最大值(max(a))就是集合(S)的最大收益。
当盾牌的防御值相同时，肯定选价格较低的那个盾牌，也就是在建树的函数中：
ma[root] = max(ma[root], -b.price)。
struct monster {
int x, y, z;
bool operator < (const monster o) const {
return x < o.x;
}
};
int n, m, p, cnt;
long long ma[1000005 * 4], laz[1000005 * 4];
void Build_Tree(int l, int r, int root, int pos, int x) {
if ((l == r) && (l == pos)) {
ma[root] = max(ma[root], (long long)-x); // 坑点1
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) Build_Tree(l, mid, root << 1, pos, x);
else Build_Tree(mid + 1, r, (root << 1) + 1, pos, x);
ma[root] = max(ma[root << 1], ma[(root << 1) + 1]);
}
void Push_down(int root) {
laz[root << 1] += laz[root];
laz[(root << 1) + 1] += laz[root];
ma[(root << 1)] += laz[root];
ma[(root << 1) + 1] += laz[root];
laz[root] = 0;
}
void Update_Tree(int L, int R, int l, int r, int root, int coins) {
if (L > R) return; // 坑点2
if (L <= l && r <= R) {
ma[root] += coins;
laz[root] += coins;
return;
}
if (laz[root]) Push_down(root);
int mid = (l + r) >> 1;
if (L <= mid) Update_Tree(L, R, l, mid, root << 1, coins);
if (R > mid) Update_Tree(L, R, mid + 1, r, (root << 1) + 1, coins);
ma[root] = max(ma[root << 1], ma[(root << 1) + 1]);
}
int main()
{
scanf("%d %d %d", &n, &m, &p);
vector<pair<int, int> > a(n), b(m);
vector<struct monster > c(p);
int length = 0;
myfor(i, 0, n) scanf("%d %d", &a[i].first, &a[i].second);
myfor(i, 0, m) scanf("%d %d", &b[i].first, &b[i].second), length = max(length, b[i].first);
myfor(i, 0, p) scanf("%d %d %d", &c[i].x, &c[i].y, &c[i].z), length = max(length, c[i].y);
sort(a.begin(), a.end());
sort(c.begin(), c.end());
myfor(i, 0, length * 4) ma[i] = -INF;
myfor(i, 0, m) Build_Tree(1, length, 1, b[i].first, b[i].second);
int index = 0;
long long ans = -INF;
myfor(i, 0, n) {
while(index < p && c[index].x < a[i].first) {
Update_Tree(c[index].y + 1, length, 1, length, 1, c[index].z); // length = max(c.y), 所以可能会出现：c[index].y + 1 > length
index++;
}
ans = max(ans, ma[1] - a[i].second);
}
cout << ans << endl;
return 0;
}
CodeForces 1320B Navigation System
给(n)个点，(m)条边, 组成一个有向图，然后再给一条路径: (p_1 ightarrow p_2 ightarrow p_3 ightarrow ··· ightarrow p_k)。有一个导航仪，当你走到(p_i)处，然后出发去下一个点(p_{i + 1})，如果(p_{i + 1}) 不是 (p_i)到终点(p_k)的最短路径上的点，则导航仪会重新规划一条从(p_{i + 1}) 到 (p_k) 的最短路径。如果是(p_i)到终点(p_k)的最短路径上的点且(p_i)到终点(p_k)的最短路径有多条，这时你选择去(p_{i + 1})，则导航仪可以重新规划也可以不重新规划。问最小规划次数和最大规划次数？
题目有点绕，建议看原文：https://vjudge.net/problem/CodeForces-1320B
题解
从终点BFS一遍，求出从终点出发到其它所有点的最短距离，然后判断(p_{i + 1})是不是从(p_i)到(p_k)的最短路径上的点：
- 是，并且从(p_i)到(p_k)的最短路径有多条，那么最大规划次数加一
- 不是，说明在(p_{i + 1})处必须重新规划到(p_k)的最短路径，那么最大和最小规划次数都加一
规划的最短路径可能会经过之前已经走到的点，举例来说：1-2，2-3，3-4，4-5，1-5，2-1，然后给出路径：1-2-3-4-5。当走到点2处，最短路径是2-1-5，而1已经走过。之所以会记录这个问题，是因为我标记了之前走过的点(被注释的两行代码)，然后wa了。
/* 998 ms, 算不来这样做的复杂度，忘大佬告知*/
void BFS(int st) {
myfor(i, 0, n) d[i] = INF;
queue<int> q;
q.push(st);
d[st] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for (int i = head_e[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (d[v] == INF) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
}
void Solve()
{
int ans_min = 0, ans_max = 0;
//vector<int> use(n + 1, 0);
myfor(i, 1, k - 1)
{
int u = p[i], t = 0;
//use[u] = 1;
for (int o = head_E[u]; o != -1; o = E[o].next) {
int v = E[o].to;
//if (use[v]) continue;
if (d[v] + 1 == d[u]) t++; // 判断有几条最短路径
}
if (d[p[i + 1]] + 1 == d[u]) {
if (t > 1) ans_max++;
}
else {
ans_min++, ans_max++;
}
}
cout << ans_min << " " << ans_max << endl;
}