QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+5]

# 9615. 骨牌覆盖

Statistics

对于一个长度为 m 的非负整数序列 a1,,am,考虑 m 行的棋盘,其中第 i 行有 ai 列。若存在一种用 1×22×1 的多米诺骨牌覆盖整个棋盘的方式,则称序列 a 是好的。

给出一个长度为 n 的非负整数序列 b1,,bn,求有多少个 (l,r) 满足 1lrnbl,,br 可以被删空。

输入格式

第一行一个正整数 T,表示测试数据组数。

接下来对于每组数据,输入两行:

第一行一个正整数 n

第二行 n 个非负整数 b1,,bn

输出格式

对于每组数据,输出一行一个非负整数,表示答案。

样例

样例 1 输入

9
5
5 6 6 5 3
9
3 7 1 8 4 4 0 6 9
3
3 1 0
3
3 0 1
3
2 0 2
1
0
10
4 7 6 6 7 6 1 2 5 5
6
5 5 5 4 3 3
6
6 4 4 6 4 1

样例 1 输出

7
22
3
1
6
1
12
7
15

样例 1 说明

对于第一组数据,b=[5,6,6,5,3],合法的 (l,r) 有:(2,2)(3,3)(2,3)(4,5)(3,5)(1,4)(2,5)

样例 2

见下发文件。

数据范围

对于所有数据,满足 1T1001n5×105n1060bi109

  • subtask 1(5%):n10
  • subtask 2(20%):n100n5×103
  • subtask 3(20%):n5×103
  • subtask 4(20%):n105
  • subtask 5(35%):无特殊限制。