常见优化技巧
-
P1102 A-B 数对
因为 \(a-b=c\)，所以 \(a+c=b\)，也就是对于每个数组内的 \(a\)，要找出所有等于 \(a+c\) 的元素个数。
因此可以对数组进行排序，再写两个二分方法，分别查询第一个合法元素和最后一个合法元素，通过两方法返回的索引之差计算元素个数，然后累加答案即可。
同样地，我们可以使用库内置的二分方法。
upper_bound(a+1,a+1+n,k)返回最后一个元素值等于k的下一位索引，lower_bound(a+1,a+1+n,k)返回第一个元素值等于k的索引。 -
P1638 逛画展
因为我们要看到所有画师的画，所以可以维护一个区间，用一个桶记录该区间内画师的画的数量。
可以先设置区间的左右端点（即左右指针）均为
1，并维护一个计数器，表示目前区间内画的种类数，接着重复执行以下步骤：- 每次r向右移动，将新画加入区间。如果这个画家是第一次出现，计数器自增；
- 在准备将左指针l向右移动时，如果当前画作
a[l]在区间中只有1幅，那么可以将计数器自减，维护计数器表示的意义永远是画的种数； - 尝试将左指针向右移动；
- 如果移动后仍然包含所有画家，继续移动；
- 如果移动后缺少某个画家，回退一步并退出循环；
- 如果计数器等于画的种类总数，则更新答案。
-
P2671 [NOIP 2015 普及组] 求和
推式子发现 \(x\) 和 \(z\) 同号，与 \(y\) 没有关系。
进而把每个颜色种类按照奇偶性再分类，最后把奇数产生的分数和偶数产生的分数加起来即可。
再推式子，发现一个前缀和，可以优化。
-
P2866 [USACO06NOV] Bad Hair Day S
开一个单调栈，从栈底到栈顶单调递减。
如果一个元素要入栈，并且栈顶的元素小于或等于该元素，那么弹栈，直到栈顶的元素大于该元素，并将该元素入栈。
将每个元素入栈时，都将栈的大小累积到答案里。
-
P2032 扫描
滑动窗口维护区间最值板子。
背下来吧。