题目大意：
给定一个长度为(n)的排列，判断是否存在长度为(3)的等差数列。
数据范围：(3leq nleq 3 imes10^5)。
本题题解
考虑枚举“长度为(3)的等差数列”，中间的那个元素。朴素的想法是枚举原排列的每个位置(i)，看这个位置左边每个值，右边每个值，有没有刚好和(p_i)之差相等的。如果再枚举这个差值，时间复杂度(O(n^2))。不太好继续优化。
换个角度，考虑每个原排列里的每个值(v)，设它的出现位置为( ext{pos}[v])。现在要判断：( ext{pos})序列上(v)左边（即小于(v)的值里）每个元素和(v)右边每个对应的元素，是否一个大于( ext{pos}[v])，一个小于( ext{pos}[v])（这样就意味着，在原序列里，两个值分别在(v)的两侧）。这里“对应”，指的是和(v)的距离一样，例如(v-1)和(v+1)是一对，(v-2)和(v+2)是一对，......。只要有任意一个(v)，存在这样的“一对”，答案就是( ext{YES})了。
来看看把枚举位置换成枚举值有什么好处。(1) 原来是没有两边“位置”要“对应”这个要求的，现在有了，合法的位置对数一下子从(O(n^2))降到了(O(n))。(2) 原来两边的数要“与(p_i)的差相等”，现在两边的数只需要“一个大于( ext{pos}[v])，一个小于( ext{pos}[v])”。从要确定值相等，变成只需要判断01两种情况（大于和小于），这个限制变得宽泛了许多，因而也更容易求解了。
把大于看做(0)，小于看做(1)。我们的( ext{pos})序列，就变成了一个(01)序列。如果按原序列里的出现顺序枚举值(v)（也就按( ext{pos}[v])从小到大枚举），则相当于每次把序列里的一个(0)改成(1)：也就是做单点修改。然后我们要判断左右两边（从后往前和从前往后）对应位置的(01)值是否相等。只要存在一对不相等，答案就是( ext{YES})。这可以用( exttt{bitset})判断。时间复杂度(O(frac{n^2}{w}))。
把( exttt{bitset})改成哈希，用线段树维护哈希值，则时间复杂度(O(nlog n))。
参考代码：
//problem:ZR1325
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int MAXN=3e5;
const ull BASE=13131;
int n,a[MAXN+5],pos[MAXN+5];
ull pw[MAXN+5];
struct SegmentTree{
ull left_to_right[MAXN*4+5];
ull right_to_left[MAXN*4+5];
ull query_left_to_right(int p,int l,int r,int ql,int qr){
if(ql<=l && qr>=r){
return left_to_right[p];
}
int mid=(l+r)>>1;
if(ql<=mid && qr>mid){
return pw[min(r,qr)-mid]*query_left_to_right(p<<1,l,mid,ql,qr)
+query_left_to_right(p<<1|1,mid+1,r,ql,qr);
}
if(ql<=mid)return query_left_to_right(p<<1,l,mid,ql,qr);
if(qr>mid)return query_left_to_right(p<<1|1,mid+1,r,ql,qr);
//cout<<"error "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
assert(0);
}
ull query_right_to_left(int p,int l,int r,int ql,int qr){
if(ql<=l && qr>=r){
return right_to_left[p];
}
int mid=(l+r)>>1;
if(ql<=mid && qr>mid){
return pw[mid-max(l,ql)+1]*query_right_to_left(p<<1|1,mid+1,r,ql,qr)
+query_right_to_left(p<<1,l,mid,ql,qr);
}
if(ql<=mid)return query_right_to_left(p<<1,l,mid,ql,qr);
if(qr>mid)return query_right_to_left(p<<1|1,mid+1,r,ql,qr);
assert(0);
}
void modify(int p,int l,int r,int pos,ull v){
if(l==r){
left_to_right[p]=right_to_left[p]=v;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)modify(p<<1,l,mid,pos,v);
else modify(p<<1|1,mid+1,r,pos,v);
left_to_right[p]=pw[r-mid]*left_to_right[p<<1]+left_to_right[p<<1|1];
right_to_left[p]=pw[mid-l+1]*right_to_left[p<<1|1]+right_to_left[p<<1];
}
SegmentTree(){}
}T;
int main() {
cin>>n;
pw[0]=1;
for(int i=1;i<=n;++i)pw[i]=pw[i-1]*BASE;
for(int i=1;i<=n;++i)cin>>a[i],pos[a[i]]=i;
for(int i=1;i<=n;++i){
if(a[i]!=1 && a[i]!=n){
int len=min(a[i]-1,n-a[i]);
if(T.query_left_to_right(1,1,n,a[i]+1,a[i]+len)!=T.query_right_to_left(1,1,n,a[i]-len,a[i]-1)){
cout<<"YES"<<endl;
return 0;
}
}
T.modify(1,1,n,a[i],1);
}
cout<<"NO"<<endl;
return 0;
}