Farmer John Solves 3SUM

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
template<typename T>
void read(T& x)
{
    int f = 1;x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x *= f;
}
int a[5010];
ll dp[5010][5010];
int K = 1000000;
int Count[2000010];///Count[K + x]表示数字x出现次数
///dp[i][j]表示以a[i]+a[j]+a[k]的k的数量 k属于[i,j]
///sum[i][j] = dp[i][i] + dp[i][i + 1] + ... + dp[i][j]
///           +dp[i + 1][i] + dp[i + 1][i + 1] + ... + dp[i + 1][j]
///             ...             ...             ...
///           +dp[j][i] + dp[j][i + 1] + ... + dp[j][j]
///二维前缀和
///递推式:sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + dp[i][j]
///求解(x1, y1) -> (x2, y2)的和（x1<x2,y1<y2）
///sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
int main()
{
    int n, q;
    read(n);read(q);
    for(int i = 1; i <= n; i++)
        read(a[i]), a[i] += K;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            ///计算dp[i][j]时，Count中正好是i+1 - j-1的数字
            if(j > i + 1 && a[i] + a[j] <= 3 * K && a[i] + a[j] >= K)
                dp[i][j] = Count[3 * K - a[i] - a[j]];
            Count[a[j]]++;
        }
        for(int j = i + 1; j <= n; j++)
            Count[a[j]] = 0;
    }
    ///预处理二维前缀和
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    while(q--)
    {
        int l, r;
        read(l);read(r);
        printf("%lld\n", dp[r][r] - dp[l - 1][r] - dp[r][l - 1] + dp[l - 1][l - 1]);
    }
    return 0;
}