DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Four Integer

返回题目

题解

将所有 Ai+BjA_i+B_jAi​+Bj​ 存入数组 XXX,将所有 Ck+DℓC_k+D_\ellCk​+Dℓ​ 存入数组 YYY。两个数组的长度均为 n2n^2n2。即使不同下标对产生相同的和,也要分别存入。

将两个数组按升序排序。考察 XXX 中未处理的最小值 xxx 和 YYY 中未处理的最大值 yyy。若 x+y<0x+y<0x+y<0,则 与 中任何剩余值之和都为负,因此向前移动 一侧。若 ,则 与 中任何剩余值之和都为正,因此移动 一侧。

若 x+y=0x+y=0x+y=0,设两侧连续等于 xxx 和 yyy 的元素个数分别为 p,qp,qp,q。从两段中各选一个元素的 pqpq 种方案均满足条件。将这一数量计入答案并跳过两段。每个值只能与其相反数配对,因此不会重复计数。

时间复杂度为 O(n2log⁡n)O(n^2\log n)O(n2logn),空间复杂度为 O(n2)O(n^2)O(n2)。四个输入值之和可用 32 位有符号整数表示。出现次数的乘积及答案可能达到 4 0004=256 000 000 ,必须使用 64 位整数计算。

Solution written by GPT

xx
x
YYY
XXX
x+y>0x+y>0x+y>0
yyy
XXX
YYY
pq
000 0004\,000^4=256\,000\,000\,000\,000
40004=256000000000000