题目链接：CF452F
给你一个1到n的排列，你需要判断该排列内部是否存在一个3个元素的子序列(可以不连续)，使得这个子序列是等差序列。
nleq 3times 10^5。
Tutorial
不妨设 g[x] 为 x 的位置。题即求是否存在 g_{x-t} < g_x < g_{x t}g_{x-t} > g_x > g_{x t}
若从小到大枚举 i，其余 g 根据 g_{p_i} 大小关系赋为 0/1。则对于每个 x 判断是否存在 t 满足 g_{x-t} not = g_{x t}。
相当于从 x 出发两侧的 g 完全相等，哈希并用线段树维护即可。
时间复杂度：O(Nlog N)。
Solution
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=3e5 10,p1=19,p2=302627441;
int n,a[N];
struct node{unsigned LL x,y;}pw[N],bs={p1,p2};;
I node operator (Cn node& x,Cn node& y){return {x.x y.x,x.y y.y};}
I node operator * (Cn node& x,CI v){return {x.x*v,x.y*v};}
I node operator * (Cn node& x,Cn node& y){return {x.x*y.x,x.y*y.y};}
I bool operator == (Cn node& x,Cn node& y){return x.x==y.x&&x.y==y.y;}
I bool operator != (Cn node& x,Cn node& y){return !(x==y);}
class SegmentTree{
private:
node F[N<<2],G[N<<2];
#define mid (l r>>1)
#define PT CI x=1,CI l=1,CI r=n
#define LT x<<1,l,mid
#define RT x<<1|1,mid 1,r
#define PU(x) (F[x]=F[x<<1]*pw[r-mid] F[x<<1|1],G[x]=G[x<<1|1]*pw[mid-l 1] G[x<<1])
public:
I void U(CI p,unsigned LL v,PT){
if(l==r) return void(F[x]=G[x]={v,v});
p<=mid?U(p,v,LT):U(p,v,RT),PU(x);
}
I node QF(CI L,CI R,PT){
if(L<=l&&r<=R) return F[x];
if(R<=mid) return QF(L,R,LT);
if(L>mid) return QF(L,R,RT);
return QF(L,mid,LT)*pw[R-mid] QF(mid 1,R,RT);
}
I node QG(CI L,CI R,PT){
if(L<=l&&r<=R) return G[x];
if(R<=mid) return QG(L,R,LT);
if(L>mid) return QG(L,R,RT);
return QG(mid 1,R,RT)*pw[mid-L 1] QG(L,mid,LT);
}
}T;
int main(){
RI i,t;for(read(n),pw[0]={1,1},i=1;i<=n;i ) read(a[i]),pw[i]=pw[i-1]*bs;
for(i=1;i<=n;T.U(a[i],1),i ) if(t=min(a[i]-1,n-a[i]))
if(T.QF(a[i]-t,a[i]-1)!=T.QG(a[i] 1,a[i] t)) return puts("YES"),0;
return puts("NO"),0;
}
