\(\text{Tricks}\)，也许叫【一些神奇的小知识】更贴切？

有时候可以成为解题的关键。

虽然有点晚了但还是写一点比较好🤔

\(\text{1.}\ 判定等差数列\)

觉得判定等差数列大概很容易考于是写写。

暴力的思想是把数全部扔到 multiset 里然后循环判断，或者说数组记录 sort 一遍后判断。这样做是 \(O(n \log n)\) 的。

但是太慢了。

考虑优化暴力，可以类似莫队一样在数列上移动，用 multiset 实时维护（但好像快不了多少。。）。但是还是不够快。

看 \(\text{APJifengc}\) 大佬的博客 （密码是多校IP地址以及端口号）

性质：给定一个数列 \(A\)，若排序后是一个等差数列，那么其公差即为 \(\gcd(|A_1 – A_2|, |A_2 – A_3|, …, A_{n-1} – A_n)\)

\(\text{APJ}\) 大佬说用扫描线一类的，但是我不会（

考虑一些简单的方法。注意到公差我们已经可以由上面的性质推出来了，此时我们要做的其实就是判断首项和末项是否合法。设公差为 \(d\)，则需判断 \(a_n = a_1 + (r-l) \times d\)。

此时还需要注意一个问题，判断序列中是否存在相同元素。这个可以转化为 \(\text{HH}\) 的项链，查区间不同元素个数是否等于区间长度。

目前此问题还没有解决，APJ说离线的话可以扫描线。

关于为何要判是否存在相同元素：1 3 5 9 3

关于为何是判相同元素而不是判一个区间加：4 2 4 10 12 10

\(\text{Hint}\)：参考了这位大佬的博客以及 \(\text{APJifengc}\) 大佬的博客

\(\text{2.}\ 判定排列\)

对于给定的一个序列 a，若询问区间 \([l, r]\) 内的数构成的集合是否构成了从 \(1\) 开始的一个排列，线段树求一个最小和最大值，然后套求和公式再线段树求一个区间 sum 判断。

显然是假的。考虑 1 2 3 4 和 1 1 4 4。

但是注意到 \(1 \times 2 \times 3 \times 4 \neq 1 \times 1 \times 4 \times 4\)，于是可以再套一个查询区间乘积来判断。可以卡掉但是并不好卡，因为区间乘积需要取模，模数是自己定的，实在不行可以套一个双模（

预处理阶乘即可用区间乘判断。

但是如果要卡的话构造比较小的数据（小于模数）应该就能卡？

还有一种 \(\text{sandom}\) 教的判定方式，就是对于每个数用 map 映射一个随机值，处理一下1~i的排列 map 映射后的 sum，预处理 \(sum_i\) 为 \(1 \sim i\) 映射后的和，怕溢出可以取模，然后到时候直接查区间 sum 看是不是就行了。有点像这道题。

以及 \(\text{joke}\) 的判定方式，每个数的二次方与三次方。

原文地址：http://www.cnblogs.com/charphi/p/16897573.html