社区首页 >专栏 >CF452F Permutation

CF452F Permutation

yzxoi

发布于 2022-09-19 06:09:25

57600

代码可运行

文章被收录于专栏：OIOI

运行总次数：0

代码可运行

题目链接：CF452F

给你一个1到n的排列，你需要判断该排列内部是否存在一个3个元素的子序列(可以不连续)，使得这个子序列是等差序列。

n\leq 3\times 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(N\log N)。

Solution

#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%10+'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;
}