CF452F Permutation

(Updated: )
oi
,

题目链接：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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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;
}