Farmer John Solves 3SUM (USACO Gold 2020 January)

因为要回答 $Q=10^5$ 的查询，所以很可能结果是需要预先计算的，也就是把所有 $N^2$ 个 $N=5000$ 的子范围的解都求出来。这个就比较像range DP的问题了，我们往这个方向去想。

定义 $\text{dp}[i][j]$ 是 $[i,j]$ 范围内的3SUM答案，那么如果能求出这个就解完了。但这个一步的求解需要能在 $\mathcal{O}(1)$ 最多到 $\mathcal{O}(\log N)$ 的时间内求出来，需要找找规律。实际上，组合类的计数问题，容斥原理还是要经常想到，我们仔细画图之后可以找到如下转换方程：

\text{dp}[i][j] = \text{dp}[i][j-1] + \text{dp}[i+1][j] - \text{dp}[i+1][j-1] + \text{trp}(i,j)

其中 $\text{trp}(i,j)$ 是固定两个数是 $A_i, A_j$ ，再加区间中间一个数的和为0的方案数（也就是中间的数是 $-A_i-A_j$ 的数量）。公式意思是一共四种情况，头尾各少一个数，有两种情况，这两起来后重复计算了没有数在头尾的方案数，所以第三项减掉重复计算的方案数，最后第四项就是头尾固定在 $i,j$ 处的方案数。

到这里算法就清楚了，具体实现中有几个障碍：

$\text{trp}()$ 的实现比较容易TLE，比如容易想到用值域上的下标vector来求，在上面binary search，这个是不够快的，只能过一半测试点。用unordered_map来做，也是不够快的（一般而言map这样动态更新的数组结构都不会有binary search快）。
最后可行的方法是用数组计数，同时每一轮记数完成后不是用fill()清零，而是用for loop（见代码）。
内存也比较紧张， $\text{trp}()$ 结果要直接放到 $\text{dp}[]$ 里，否则MLE。

复杂度是 $\mathcal{O}(n^2)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, Q;
int a[5005];
ll dp[5005][5005];
int m[4000005];         // count of each value
const int OFF = 2e6;
 
int main() {
    scanf("%d %d", &n, &Q);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
 
    for (int i = 0; i < n; i++) {       // count 3SUM w/ a[i], a[j] and one in the middle
        for (int j = i+2; j < n; j++) {
            m[a[j-1]+OFF]++;
            dp[i][j] = m[-a[i]-a[j]+OFF];
        }
        for (int j = i+2; j < n; j++)   // restore 0. fill() will TLE
            m[a[j-1]+OFF]--;
    }
 
    for (int j = 2; j < n; j++)         // Range DP [i, i+j]
        for (int i = 0; i+j < n; i++)
            dp[i][i+j] += dp[i][i+j-1] + dp[i+1][i+j] - dp[i+1][i+j-1];
 
    for (int q = 0; q < Q; q++) {
        int l,r;
        scanf("%d %d", &l, &r);
        l--,r--;
        printf("%lld\n", dp[l][r]);
    }
    return 0;
}