题意：
给定一个长度为 \(n\) 的排列 \(a\)，判定其中是否有长度 \(\ge 3\) 的等差数列。
\(1 \le n \le 5 \times 10^5\)。
思绪：
首先若存在长度 \(>3\) 的等差数列，则其中的一部门肯定由长度为 \(3\) 的等差数列构成；即我们如今只需要判定是否存在长度为 \(3\) 的等差数列即可。
考虑罗列中心的数 \(a_i\)，则题目转化为 \(a_i-k\) 与 \(a_i + k\) 是否同时出如今 \(i\) 的两侧。
留意到 \(a\) 是一个排列，则是没有重复数字的。
那么我们可以记作若 \(i\) 左边的 \(a_j\) 出现过，则将标记数组中第 \(a_j\) 个位置为 \(0\)。
若不可以构成等差数列的话，当 \(a_i-k\) 被标记了，则 \(a_i+k\) 也必须被标记（不然就会出如今 \(i\) 右侧，形成等差数列），那么标记数组就是以 \(i\) 为回文中心回文的。
如今我们需要支持单点赋值为 \(1\)，判定一个区间是否是回文的；可以直接线段树维护翻转后和未翻转时的哈希值，判定是否相等即为回文。
考虑提前预处理出 \(base\) 的次幂，则单组数据时间复杂度为 \(O(N \log N)\)。
完整代码：
P2757 [国家集训队] 等差子序列 [code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod) x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef long double lb;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=5e5+10;const ull base=127;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c |
