Code Forces 652C Foe Pairs

C. Foe Pai++rs

ti++me limit per test

memory limit per test

input

output

pof lengthn.
Also you are givenmfoe pairs(ai, bi)(1 ≤ ai, bi ≤ n, ai ≠ bi).

(x, y)(1 ≤ x ≤ y ≤ n)
that do not contain any foe pairs. So you shouldn't count intervals(x, y)

p = [1, 3, 2, 4]and foe pairs are{(3, 2), (4, 2)}.
The interval(1, 3)is incorrect because it contains a foe pair(3, 2).
The interval(1, 4)is also incorrect because it contains two foe pairs(3, 2)and(4, 2).
But the interval(1, 2)

Input

nandm(1 ≤ n, m ≤ 3105)
— the length of the permutationp

ndistinct integerspi(1 ≤ pi ≤ n)
— the elements of the permutationp.

mlines contains two integers(ai, bi)(1 ≤ ai, bi ≤ n, ai ≠ bi)
— thei-th foe pair. Note a foe pair can appear multiple times in the given list.

Output

c— the number of different intervals(x, y)

64-bit integer type to store it. InC++you
can use thelong longinteger type and inJavayou can uselong

Examples

input

4 2
1 3 2 4
3 2
2 4

output

5

input

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

output

20

Note

(1, 1),(1, 2),(2, 2),(3, 3)and(4, 4).

用一个数组表示每个数字可以向右延生的最大长度,也就是右边哪些点可以和这个数字形成一个区间。注意:

在给定完敌对点,更新数组之后,要从后往前再更新一次。相同左边端点的敌对点应该选择右端点较小的。

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
#define MAX 3*100000
int a[MAX+5];
int tag[MAX+5];
int dp[MAX+5];
int n,m;
int f[MAX+5];
int x,y;
int main()
{
scanf("%d%d",&n,&m);
memset(tag,0,sizeof(tag));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
tag[a[i]]=i;
f[i]=n;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
int l=min(tag[x],tag[y]);
int r=max(tag[x],tag[y]);
f[l]=min(f[l],r-1);
}

for(int i=n-1;i>=1;i--)
{
f[i]=min(f[i],f[i+1]);
}
__int64 num=0;
for(int i=1;i<=n;i++)
{
int right=f[i];
num+=right-i+1;
}
printf("%I64d\n",num);
return 0;

}