题解 P6006 【[USACO20JAN]Farmer John Solves 3SUM G】

fighter · 2020-01-30 09:40:20 · 题解

发现n \leq 5000，那么我们自然想到O(n^2)预处理之后O(1)回答询问。

先考虑一个更简单的问题，如果f[i][j]表示在区间[l,r]中，满足k \in (l,r), a[k]+a[l]+a[r]=0的k的数量，那么我们是可以枚举左右端点，用一个桶做到O(n^2)预处理f的。

那么f与最后的答案是什么关系呢？最后要求的是：在一段区间内，左右端点不强制选的方案数。这隐隐约约的有点像是f数组的一个前缀和。

我们可以考虑先求出s[l][r]表示左端点在[1,l]内，右端点在[1,r]内的总方案数。这就真的是f的二位前缀和了。

可以这么理解，把f[l][r]对应到平面上的一个点，那么s[l][r]就是从(1,1)到(l,r)的这个矩形中所有点的和。这样我们也就可以在O(n^2)的时间内求出s。

同样的，最后的答案实际上是区间左右端点都在[l,r]内总答案。对应到平面上也就是左上角为(l,l)，右下角为(r,r)的矩形中所有点的和。这样就可以通过s来O(1)求答案了。

代码

注意开桶的时候需要平移值域

#include <bits/stdc++.h>
#define ll long long
#define MAX 5005
#define K 1000000
using namespace std;

int n, Q;
int a[MAX], cnt[2000005];
ll s[MAX][MAX];

int main()
{
    cin >> n >> Q;
    for(int i = 1; i <= n; ++i){
        scanf("%d", &a[i]), a[i] += K;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = i+1; j <= n; ++j){
            if(j > i+1){
                if(a[i]+a[j] <= K*3 && a[i]+a[j] >= K) s[i][j] = cnt[K*3-a[i]-a[j]];
            }
            cnt[a[j]]++;
        }
        for(int j = i+1; j <= n; ++j){
            cnt[a[j]]--;
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            s[i][j] += s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    int l, r;
    while(Q--){
        scanf("%d%d", &l, &r);
        printf("%lld\n", s[r][r]-s[l-1][r]-s[r][l-1]+s[l-1][l-1]);
    }

    return 0;
}