思路:记录下来每一个数在序列里的位置,然后记录每一个位置向右最远能到达哪个位置
#include <stdio.h>#include <algorithm>using namespace std;typedef long long ll;const int maxn = 3 * 1e5 + 10;int a[maxn],pos[maxn],mx[maxn];int main(void){int n,m;scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);pos[a[i]] = i;mx[i] = n;}for(int i = 1; i <= m; i++){int x,y;scanf("%d%d",&x,&y);int l = min(pos[x],pos[y]);int r = max(pos[x],pos[y]);mx[l] = min(mx[l],r - 1);}for(int i = n - 1; i >= 1; i--){mx[i] = min(mx[i],mx[i + 1]);}//printf("asd\n");ll ans = 0;for(int i = 1; i <= n; i++){ans += mx[i] - i + 1;}printf("%I64d\n",ans);return 0;}