C. Foe Pairs
time limit per test
memory limit per test
input
output
p of length n. Also you are given m foe 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
n and m (1 ≤ n, m ≤ 3·105) — the length of the permutation p
n distinct integers pi (1 ≤ pi ≤ n) — the elements of the permutation p.
m lines contains two integers (ai, bi) (1 ≤ ai, bi ≤ n, ai ≠ bi) — the i-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. In C++ you can use the long long integer type and in Java you can use long
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;
}