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

· · 题解

题目传送门。

善良的出题人已经在题面中告诉你了：

尚未发现运行速度比平方时间明显更优的解法。

而 O(qn^2) 过不了，所以题目显然是让你以 O(n^2) 进行预处理，再进行 O(1) 查询。

思考在暴力 O(n^3) 处理时，我们是以三元组 (i,j,k) 进行三重循环，逐个检查是否 s_i+s_j+s_k=0。不妨对这个式子进行变换，可得 s_k=-s_i-s_j。这时利用桶统计 [i,j] 中的 -s_i-s_j 数量即可。

在面对 q 次询问时，考虑 用 v_{i,j} 表示区间 [i,j] 中的结果。则有 v_{i+1,j} 为区间 (i,j] 中的结果， v_{i,j-1} 为区间 [i,j) 中的结果， v_{i+1,j-1} 为区间 (i,j) 中的结果。易得：

v_{i,j}=v_{i+1,j}+v_{i,j−1}−v_{i+1,j−1}+f_{i,j}

可惜的是这会导致你 MLE。应该把数组 v 去掉，因为 f 就可以了：

f_{i,j}=f_{i+1,j}+f_{i,j−1}−f_{i+1,j−1}

本题代码细节较恶心，故意跟数组过不去，应格外注意：

  1. 查找 -s_i-s_j 时要加上常数 M，因为数组不能访问负的，会数组越界。

  3. 桶应该开为 2\times M，如果较小可能会因为 +M 而数组越界。

View code：

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ri register int
#define il inline

const int N=5010,M=2e6+10;
int n,Q;
int s[N],b[M<<1];
ll f[N][N];

il ll read(){
    ll x=0,y=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            y=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*y;
}

il void work(){
    for(ri i=1;i<=n;i++){
        for(ri j=i+1;j<=n;j++){
            f[i][j]=b[M-s[i]-s[j]];
            b[s[j]+M]++;
        }
        for(ri j=i+1;j<=n;j++)
            b[s[j]+M]=0;
    }
    for(ri i=3;i<=n;i++){
        for(ri j=1;j<=n-i+1;j++){
            int k=i+j-1;
            f[j][k]+=f[j+1][k]+f[j][k-1]-f[j+1][k-1];
        }
    }
}

signed main(){
    n=read(),Q=read();
    for(ri i=1;i<=n;i++)
        s[i]=read();
    work();
    while(Q--){
        int a=read(),b=read();
        printf("%lld\n",f[a][b]);
    }
    return 0;
}