[USACOJan20G]FarmerJohnSolves3SUM

NC222463. [USACOJan20G]FarmerJohnSolves3SUM

描述

Farmer John believes he has made a major breakthrough in algorithm design: he claims to have found a nearly linear time algorithm for the 3SUM problem, an algorithmic problem famous for the fact that no known solution exists running in substantially better than quadratic time. One formulation of the 3SUM problem is the following: given an array s₁,…,s_m of integers, count the number of unordered triples of distinct indices i,j,k such that s_i+s_j+s_k=0.
To test Farmer John's claim, Bessie has provided an array A of N integers (1≤N≤5000). Bessie also asks Q queries (1≤Q≤10⁵), each of which consists of two indices 1≤a_i≤b_i≤N. For each query, Farmer John must solve the 3SUM problem on the subarray A[a_i…b_i].

Unfortunately, Farmer John has just discovered a flaw in his algorithm. He is confident that he can fix the algorithm, but in the meantime, he asks that you help him pass Bessie's test!

输入描述

The first line contains two space-separated integers N and Q. The second line contains the space-separated elements A₁,…,A_N of array A. Each of the subsequent Q lines contains two space-separated integers a_i and b_i, representing a query.
It is guaranteed that −10⁶≤A_i≤10⁶ for every array element A_i.

输出描述

The output should consist of Q lines, with each line i containing a single integer---the answer to the i-th query. Note that you should use 64-bit integers to avoid overflow.

示例1

输入:

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

输出:

2
1
4

说明:

For the first query, the possible triples are (A₁,A₂,A₅) and (A₂,A₃,A₄).

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 727ms, 内存消耗: 124816K, 提交时间: 2023-06-10 17:24:53

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxN = 5e3 + 10, INF = 1e6; 
int n, Q, a[maxN], sum[INF + INF];
ll d[maxN][maxN];
int main(){
	cin >> n >> Q;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] += INF;
	}
	for(int i = 1; i <= n; i++){
		sum[a[i + 1]]++;
		for(int j = i + 2; j <= n; j++){
			if(a[i] + a[j] >= INF && a[i] + a[j] <= 3 * INF)
				d[i][j] = sum[3 * INF - a[i] - a[j]];
			sum[a[j]]++;
		}
		for(int j = i + 1; j <= n; j++) sum[a[j]]--;
	}
	
	for(int k = 4; k <= n; k++)
		for(int i = 1; i + k - 1 <= n; i++){
			int j = i + k - 1; 
			d[i][j] += d[i][j - 1] + d[i + 1][j] - d[i + 1][j - 1];
		}
	
	while(Q--){
		int x, y; cin >> x >> y;
		cout << d[x][y] << endl;
	}
	return 0;
}

上一题

下一题

详情