分析
求得是不能包含任意两个数字得子数组个数
那么排列问题当然要求数字对应得下标，把查询得两个数都转换为下标
得到m组下标对
然后按右端点排序
我们得思路是固定r，看看l最左到哪里
那么我们固定r，肯定对于右端点来说落在某两个中间
然后它左边得所有左端点都要满足l大于这个左端点
所以要维护左端点前缀最大值
然后就可以得到最左边得l了
Ac code
import sysfrom bisect import bisect_rightinput = sys.stdin.readlinen, m = list(map(int, input().split()))p = list(map(int, input().split()))pairs = []for _ in range(m):x, y = list(map(int, input().split()))pairs.append([x, y])idx = [0] * (n + 1)for i, v in enumerate(p):idx[v] = i + 1for i in range(m):pairs[i][0] = idx[pairs[i][0]]pairs[i][1] = idx[pairs[i][1]]if pairs[i][0] > pairs[i][1]:pairs[i][0], pairs[i][1] = pairs[i][1], pairs[i][0]pairs.sort(key = lambda x: x[1])maxleft = [0] * mfor i in range(m):if i == 0:maxleft[i] = pairs[i][0]else:maxleft[i] = max(maxleft[i - 1], pairs[i][0])rr = [r for _, r in pairs]ans = 0# fix r# most left lfor r in range(1, n + 1):idx = bisect_right(rr, r)if idx == 0:ans += relse:maxnl = maxleft[idx - 1]ans += r - maxnlprint(ans)
总结
子数组个数问题
固定一端，看看另一端最大取到哪里
