Code Forces 652C Foe Pairs

C. Foe Pairs

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation p of length n. Also you are given m foe pairs (ai, bi)(1 ≤ ai, bi ≤ n, ai ≠ bi).

Your task is to count the number of different intervals (x, y) (1 ≤ x ≤ y ≤ n) that do not contain any foe pairs. So you shouldn't count intervals (x, y) that contain at least one foe pair in it (the positions and order of the values from the foe pair are not important).

Consider some example: 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) is correct because it doesn't contain any foe pair.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 3·105) — the length of the permutation p and the number of foe pairs.

The second line contains n distinct integers pi (1 ≤ pi ≤ n) — the elements of the permutation p.

Each of the next 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

Print the only integer c — the number of different intervals (x, y) that does not contain any foe pairs.

Note that the answer can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

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

In the first example the intervals from the answer are (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;

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

HDU 1403 Eight&POJ 1077(康拖,A* ,BFS,双广)

Eight Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Ja...

32070
来自专栏算法修养

PAT 甲级 1104 sum of Number Segments

1104. Sum of Number Segments (20) 时间限制 200 ms 内存限制 65536 kB 代码长度限制 16...

29150
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第7章 面向对象编程(OOP)(2)《Kotlin极简教程》正式上架:

在上面的代码中,我们通过向注解类添加元注解(meta-annotation)的方法来指定其他属性:

17420
来自专栏算法修养

CodeForces 666B World Tour(spfa+枚举)

B. World Tour time limit per test 5 seconds memory limit per test 512 mega...

34740
来自专栏ACM算法日常

String Problem(KMP+最小表示法)- HDU 3374

Give you a string with length N, you can generate N strings by left shifts. For ...

9320
来自专栏算法修养

ZOJ 3537 Cake(凸包判定+区间DP)

Cake Time Limit: 1 Second Memory Limit: 32768 KB You want to hold a par...

38290
来自专栏扎心了老铁

Elasticsearch JAVA api轻松搞定groupBy聚合

本文给出如何使用Elasticsearch的Java API做类似SQL的group by聚合。 为了简单起见,只给出一级groupby即group by fi...

82770
来自专栏我和未来有约会

(保存)C#基础概念二十五问

注:本文部份资料来自网络,如有侵权,请与我联系,我会在第一时间声明引用或将其删除!     当初学 C# 时是找个人大概问了一下数据类型和分支语句就开始做项目了...

21880
来自专栏算法修养

HDU 4605 Magic Ball Game(可持续化线段树,树状数组,离散化)

Magic Ball Game Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/...

36360
来自专栏Ryan Miao

jackson简单使用,对象转json,json转对象,json转list

添加jackson依赖: // https://mvnrepository.com/artifact/com.fasterxml.jackson.core/ja...

521110

扫码关注云+社区

领取腾讯云代金券