题解 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)$求答案了。
## 代码
注意开桶的时候需要平移值域
```cpp
#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;
}
```