問題一覧 > 通常問題

No.1788 Same Set

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : tute7627tute7627 / テスター : pazzle1230pazzle1230
1 ProblemId : 7280 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-25 23:50:16

問題文

長さ $N$ の数列 $A,B$ が与えられます。 以下の条件を満たすような整数 $(l,r)$ の組の数を求めてください。

  • $1 \le l \le r \le N$
  • $(A_l,A_{l+1}, \dots ,A_{r})$ に含まれる整数全体からなる集合と $(B_l,B_{l+1}, \dots ,B_{r})$ に含まれる整数全体からなる集合が等しい。

入力

$N$
$A_1 \ A_2 \dots A_N$
$B_1 \ B_2 \dots B_N$

  • 入力は全て整数である。
  • $1 \le N \le 2 \times 10^5$
  • $1 \le A_i ,B_i \le 4 \times 10^5$

出力

条件を満たすような $(l,r)$ の組の数を求めてください。 最後に改行してください。

サンプル

サンプル1
入力
4
1 2 1 3
2 1 2 1
出力
3

条件を満たす $(l,r)$ は $(1,2),(1,3),(2,3)$ の $3$ 通りです。

例えば $(l,r)=(1,3)$ の場合、$(A_1,A_2,A_3)=(1,2,1)$ に含まれる整数全体からなる集合は $\{1,2\}$ となり、$(B_1,B_2,B_3)=(2,1,2)$ に含まれる整数全体からなる集合は $\{1,2\}$ となることから条件を満たします。

サンプル2
入力
5
10000 20000 30000 40000 50000
10000 20000 30000 40000 50000
出力
15

サンプル3
入力
7
1 3 2 1 2 2 3
1 2 3 3 2 1 2
出力
12

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。