← 返回题目列表

AtCoder · utpc2024_q

Q. 二次块

中文机器翻译题面 查看原题

配点 : 100 点

問題文

长度 小于或等于 N 整数序列 给出 A = (A_1, A_2, \dots, A_N) 。 对于

1 \le L \le R \le N 的整数 选择 L, R 决定的连续子列 当 (A_L, A_{L + 1}, \dots, A_R) 满足以下条件时,该连续子列被定义为 2 次関数的。 考虑将

  • 一些实数 使用 a, b, c 存在并且 满足L \le i \le R 的任意整数 对于 i 是 在 A_i = a i^2 + b i + c 很满意。

整数列 A 分割成若干个 2 次函数的连续子列。请输出分割后连续子列数量可能的最小值。

T 测试用例,因此请逐一回答。

制約

  • 所有输入均为整数
  • 1 \le T \le 10^5
  • 1 \le N \le 2 \times 10^5
  • -10^{18} \le A_i \le 10^{18}
  • 1 对于一个输入中包含的测试用例,N 的总和是 2 \times 10^5 以下

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个案例均按以下格式给出。 打印

N
A_1 A_2 \ldots A_N

出力

T 行。i 在线 i 个测试用例的答案。


入力例 1

4
12
-16 -9 -4 -1 0 0 0 0 1 4 9 16
8
2 0 2 5 0 3 0 8
1
0
5
1000000000000000000 -500000000000000000 -1000000000000000000 -500000000000000000 1000000000000000000

出力例 1

3
3
1
1

1 关于第一个测试用例,给定的整数序列可以分割为 3 个 2 个函数式连续子序列 (-16, -9, -4, -1), \,(0, 0, 0),\, (0, 1, 4, 9, 16) 。实际上,对于每一个连续子序列,(a, b, c) = (-1, 10, -25), \, (0, 0, 0),\, (1, -16, 64) 满足条件。 2 个或更少的 2 个函数式连续子序列无法分割,因此答案是 3 。 对于

4 关于第一个测试用例,请注意输入值可能超出 32 位整数类型的范围。