레이팅 미적용농부 존은 자신이 알고리즘 설계에서 중대한 돌파구를 마련했다고 믿고 있다. 그는 3SUM 문제에 대한 거의 선형 시간 알고리즘을 찾았다고 주장한다. 3SUM은 이차 시간보다 크게 나은 알려진 해법이 존재하지 않는 것으로 유명한 알고리즘 문제이다. 3SUM 문제의 한 가지 정식화는 다음과 같다. 정수 배열 \(s_1,\dots,s_m\)이 주어질 때, \(s_i + s_j + s_k = 0\)을 만족하는 서로 다른 인덱스들의 비순서 삼중쌍 \(i,j,k\)의 개수를 세는 것이다.
농부 존의 주장을 검증하기 위해, 베시는 \(N\)개의 정수로 이루어진 배열 \(A\)(\(1 \leq N \leq 5000\))를 제시했다. 베시는 또한 \(Q\)개의 쿼리(\(1 \leq Q \leq 10^5\))를 묻는데, 각 쿼리는 두 인덱스 \(1 \leq a_i \leq b_i \leq N\)으로 이루어진다. 각 쿼리에 대해, 농부 존은 부분 배열 \(A[a_i \dots b_i]\)에 대한 3SUM 문제를 풀어야 한다.
안타깝게도 농부 존은 방금 자신의 알고리즘에서 결함을 발견했다. 그는 알고리즘을 고칠 수 있다고 자신하지만, 그동안 베시의 시험을 통과할 수 있도록 당신이 도와주기를 부탁한다!
문제 제공: Dhruv Rohatgi
점수 배점
- 테스트 케이스 2-4는 \(N\le 500\)을 만족한다.
- 테스트 케이스 5-7은 \(N\le 2000\)을 만족한다.
- 테스트 케이스 8-15는 추가 제약이 없다.
문제 제공: Dhruv Rohatgi
첫째 줄에 공백으로 구분된 두 정수 \(N\)과 \(Q\)가 주어진다. 둘째 줄에 배열 \(A\)의 원소 \(A_1,\dots,A_N\)이 공백으로 구분되어 주어진다. 이어지는 \(Q\)개의 줄에는 각각 쿼리를 나타내는, 공백으로 구분된 두 정수 \(a_i\)와 \(b_i\)가 주어진다.
모든 배열 원소 \(A_i\)에 대해 \(-10^6 \leq A_i \leq 10^6\)이 보장된다.
출력은 \(Q\)개의 줄로 이루어져야 하며, 각 \(i\)번째 줄에는 \(i\)번째 쿼리의 답인 정수 하나를 출력한다. 오버플로를 피하기 위해 64비트 정수를 사용해야 함에 유의하라.
threesum.in · 출력을 쓸 파일 threesum.out7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 72
1
4For the first query, the possible triples are \((A_1,A_2,A_5)\) and
\((A_2,A_3,A_4).\)