← 返回题目列表

AtCoder · tupc2023_h

H. 计算伪回文数

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

配点 : 100 点

問題文

长度 小于或等于 M 序列 使用 B=(B_1,B_2,\dots,B_M) 是 在 回文 意味着 B_i=B_{M+1-i} 就是全部 对于 i=1,2,\dots,M 这是关于

另外,数列 B 是 在 擬回文 意味着 B 重新排列后可以成为回文的情况。


长度 小于或等于 2N 序列 使用 A=(A_1,A_2,\dots,A_{2N}) 。 对于 A 有 1,2,\dots,N 每个恰好包含 2 个。

各 i=1,2,\dots,2N 对于,请计算满足以下条件的正整数的组合数量 (l,r) \, (1 \le l \le r \le 2N) 个。

  • l \leq i \leq r
  • (A_l,A_{l+1},\dots,A_r) 属于 A_i 是 您也可以写 1 仅包含
  • (A_l,A_{l+1},\dots,A_r) 是伪回文

制約

  • 1 \le N \le 5 \times 10^5
  • 各 1,2,\dots,N 是 您也可以写 A 恰好在 2 包含
  • 所有输入均为整数

入力

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

N
A_1 A_2 \dots A_{2N}

出力

i 对应的答案是 X_i 。 X_1,X_2,\dots,X_{2N} ,用空格分隔。 当


入力例 1

2
1 1 2 2

出力例 1

1 2 2 1

各 i 对于,满足条件的正整数组合如下。

  • i=1: (1,1)
  • i=2: (2,2),(2,4)
  • i=3: (1,3),(3,3)
  • i=4: (4,4)

入力例 2

3
2 1 2 3 1 3

出力例 2

1 2 2 2 2 1

入力例 3

4
1 2 4 3 4 1 3 2

出力例 3

1 2 1 2 1 3 1 1

入力例 4

1
1 1

出力例 4

1 1