题目链接：POJ - 2796
这是一个典型问题：需要你在短时间内求出所有的点左边/右边第一个比它大/小的位置。
应用：
以找到某个点左边/右边第一个比它小的位置为例（这里不包括那个比它小的点）：
初始化\(a_0 = a_{n+1} = -\infty\)，保证不会越界。
1 | #include <cstdio> |
维护一个单调栈，单调栈的顶部是左边/右边第一个比当前点小的点，如果需要不包含这个点，则左边+1右边-1即可。
1 | #include <cstdio> |
分层最短路，这题需要处理重边和自环，处理方法是自环不添加到图中，重边只算最短的。
相关题：BZOJ 2763，计蒜客 A1958 [TODO: add links]
1 | #include <bits/stdc++.h> |
题目链接：2019牛客多校第四场C
参考我的ICPC 2019 南昌邀请赛网络预赛，计蒜客38228 Max answer 题解。 [TODO: add links]
1 | #include <bits/stdc++.h> |
题目链接：2019牛客多校第三场J
使用链表来模拟题目中的 Array，这样插入删除都是 \(O(1)\) 的，记录每个元素在内存中的位置，即可以在短时间内查询到某个元素的迭代器，这里我使用 map 从 \(s\) 映射到在链表中对应的迭代器的位置。坑点：01 和 001 不一样，所有的 \(s\) 要在前面加 \(1\)。
1 | #include <bits/stdc++.h> |
题目链接：HDU 6601
首先可以确定为了在线性时间内判断和获取一个可以形成最大三角形的三元组，我们需要获得的是一个已经排序的序列。已经从大到小排序的序列，只有 \(d_i \leq d_{i+1} + d_{i + 2}\) 的时候不能构成三角形，我们考虑最极端的情况，即 \(d_i = d_{i+1} + d_{i+2}\)，根据斐波那契数列的性质，最多这个数列会在 45 项内收敛到 0。所以我们只要维护区间前 45 大的数，然后 \(O(45)\) 地判断最大三角形就可以了，这里可以用线段树实现，把 push-up 操作改成归并即可。
1 | #include <bits/stdc++.h> |
题目链接：HDU 6582
找到左右可能是最短路的边，利用这些边重新建图求最小割。寻找这些边的方法是，在跑完单源最短路后，\(d_u + c(u, v) = d_v\) 的边就是新图中的边。
1 | #include <bits/stdc++.h> |
题目链接：2019牛客多校第三场B
Substring：从第一个位置开始，为 0 就 -1，为 1 就 +1，两个值为 \(x\) 的位置中间的是合法串，统计所有的合法串中最长的即可。
Subsequence：记 0 的个数为 \(n_0\)，1的个数为 \(n_1\)，答案为 \(\min \{ n_0, n_1\}\)。
1 | #include <bits/stdc++.h> |
题目链接：2019 牛客多校第二场 F
把 \(2n\) 个人分成 \(n+n\) 两组，那么一共是 \({2n \choose n}\) 种情况，如果每一次都暴力计算竞争力总和，那么每一次的时间复杂度将是 \(O(n^2)\)，总时间复杂度是 \(O({\rm C}_{2n}^{n} \times n^2)\)，对于 \(n \leq 14\) 这个数据范围来说是过不去的。
考虑如何惰性计算这个竞争力总和，也就是说从状态 \(A\) 转移到状态 \(B\) 的时候根据状态的变化来计算贡献，这是一个常用的思路。
起初，我尝试讨论第 \(i\) 个元素是被分到哪一组，元素 \(x\) 加入 \(A\) 组对总和的贡献就是 \(\sum_{i \neq x} v_{ix}\)，加到一个变量里求和即可，渐进时间复杂度 \(O({\rm C}_{2n}^{n} \times n)\)，但是可能由于姿势不当 TLE 了。后来在题解中看到了一种思路类似的解法——算贡献的时候不用加，用减。假设当前没有分组的变量的竞争值就是 \(\sum_{i=1}^{n} \sum_{j = i+1}^{n} v_{ij}\)，每次将一个元素分到某一组后，这个元素和原来这个组里的所有元素的贡献需要减去，那么在 \(n+n\) 全分配完之后得到的这个变量的值就是还没有被“割断”的“边”。这样做有个好处就是有一个可以减枝的条件：如果当前还没有被“割断”的“边”的总和已经小于当前的最大值了，这条路就没有必要继续枚举了，所以在同是 \(O({\rm C}_{2n}^{n} \times n)\) 的复杂度的情况下，这个算法快了很多，1676/4000ms。
1 | #include <bits/stdc++.h> |
题目链接：2019 牛客多校第二场 H
动态维护第\(i\)行的每一个元素\(s_{i,j}\)，向上最大能到达的高度\(h_j\)，向左能到达的最远点\(l_j\)，向右能到达的最远点\(r_j\)，满足\(l_j\)和\(r_j\)的\(h\)值都是大于等于\(h_j\)的。那么我们知道最大值是
\[ \max_{i = 1}^{n} \max_{j = 1}^{m} h_j \times (r_j - l_j + 1) \]
那么我们只要在\(h_j \times (r_j - l_j + 1)\)的基础上减去一行或者一列，以及\(h_j \times (r_j - l_j + 1)\)本身都存起来，排序去重后取第二个就是全局第二大。渐进时间复杂度\(O(n^2 \log n)\)。
这道题去重会卡 set。
1 | #include <bits/stdc++.h> |
题目链接：[Codeforces 1195E]
典型二维RMQ，具体解法见我的上一篇博文BZOJ 1047 - 理想的正方形（题解）。[TODO: add links]
1 | #include <bits/stdc++.h> |