参照Piggy424008写的代码

对了subtask 0, 1

subtask 2 错了前面4个 subtask 3 错了前面6个

#include <bits/stdc++.h>

using namespace std;

const int N = 500010;

typedef long long LL;

inline int read()
{
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + (c ^ 48);
	return s * w;
}

int n, m;
int a[N];
LL res;

int main()
{
	int T;
	scanf("%d", &T);
	while (T -- )
	{
		n = read(), m = read();
		for (int i = 1; i <= n; i ++ ) a[i] = -1;
		if (m == 0) //特判
		{
			printf("%lld\n", (LL)(n - 1) * (n - 1));
			continue ;
		}
		
		bool flag = 1;
		for (int i = 1; i <= m; i ++ )
		{
			int x, y;
			x = read(), y = read();
			a[x] = y;
			
			if (x != y) flag = 0; 
		}
		
		if (flag && m) //xi = yi
		{
			int cur = 0;
			for (int i = 1; i <= n; i ++ )
				if (a[i] == -1) cur ++ ;
				else if (cur)
				{
					res += (LL)(cur - 1) * (cur - 1);
					cur = 0;
				}
			if (cur) res += (LL)(cur - 1) * (cur - 1);
			printf("%lld\n", res);
			continue ;
		}
		
		int p = -1;
		bool success = true;
		for (int i = 1; i <= n; i ++ ) // |xi-yi|>=2
			if (a[i] != -1)
				if (abs(i - a[i]) >= 2)
				{
					if (~p)
					{
						success = false;
						break ;
					}
					else p = i;
				}
		
		if (!success)
		{
			puts("0");
			continue ;
		}
		
		if (~p)
		{
			success = true;
			if (a[p] > p)
			{
				for (int i = 1; i <= n; i ++ )
					if (a[i] != -1)
					{
						if ((i < p || i > a[p]) && a[i] != i) success = false;
						if ((i > p && i <= a[p]) && a[i] != i - 1) success = false;
					}
			}
			else
			{
				for (int i = 1; i <= n; i ++ )
					if (a[i] != -1)
					{
						if ((i < a[p] && i > p) && a[i] != i) success = false;
						if ((i >= a[p] && i < p) && a[i] != i + 1) success = false;
					}
			}
			if (success)
			{
				puts("1");
				continue ;
			}
			else
			{
				puts("0");
				continue ;
			}
		}
		
		int cnt = 0; //xi=xi+1 xi+1=xi
		for (int i = 1; i <= n; i ++ )
			if (a[i] == -1 || a[i] == i) continue ;
			else if (a[i] == i + 1 && a[i + 1] == i) i ++ , cnt ++ ;
			else
			{
				cnt = -1;
				break ;
			}
		if (~cnt)
		{
			puts("0");
			continue ;
		}
		
		int f = 0, l, r;
		p = 0;
		success = true;
		
		for (int i = 1; i <= n; i ++ ) //|xi-yi|<=1
		{
			if (a[i] == -1) continue ;
			if (a[i] == i)
			{
				if (f == 1) f = 2;	
			}	
			else
			{
				r = i;
				if (f == 0)
				{
					p = a[i] - i;
					l = i, f = 1;
				}
				else if (f == 1)
				{
					if (a[i] - i != p)
					{
						success = false;
						break ;
					}
					
				}
				else
				{
					success = false;
					break ;		
				}
			}
		}
		if (!success)
		{
			puts("0");
			continue ;
		}
		int lcnt = 0, rcnt = 0;
		for (int i = l - 1; i && a[i] == -1; i -- ) lcnt ++ ;
		for (int i = r + 1; i <= n && a[i] == -1; i ++ ) rcnt ++ ;
		res = (LL)lcnt * rcnt;
		res += (~p ? rcnt : lcnt);
		printf("%lld\n", res);
	}
	return 0;
}