No.1788 Same Set
タグ : / 解いたユーザー数 30
作問者 : 👑
tute7627
/ テスター :
pazzle1230
Problem Statement
You are given sequences $A,B$ of length $N$. Find the number of pairs of integers $(l,r)$ satisfying the following conditions.
- $1 \le l \le r \le N$
- The set of all integers contained in $(A_l,A_{l+1}, \dots ,A_{r})$ is equal to the set of all integers contained in $(B_l,B_{l+1}, \dots ,B_{r})$.
Input
$N$ $A_1 \ A_2 \dots A_N$ $B_1 \ B_2 \dots B_N$
- All inputs are integers.
- $1 \le N \le 2 \times 10^5$
- $1 \le A_i ,B_i \le 4 \times 10^5$
Output
Output the number of pairs $(l,r)$ satisfying the conditions. Print a newline at the end.
Sample
Sample 1
Input
4 1 2 1 3 2 1 2 1
Output
3
The $3$ pairs $(l,r)$ satisfying the conditions are $(1,2),(1,3),(2,3)$.
For example, when $(l,r)=(1,3)$, the set of all integers contained in $(A_1,A_2,A_3)=(1,2,1)$ is $\{1,2\}$, and the set of all integers contained in $(B_1,B_2,B_3)=(2,1,2)$ is $\{1,2\}$, so the conditions are satisfied.
Sample 2
Input
5 10000 20000 30000 40000 50000 10000 20000 30000 40000 50000
Output
15
Sample 3
Input
7 1 3 2 1 2 2 3 1 2 3 3 2 1 2
Output
12
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。