# P2757题解(P2757 problem solving)-其他

## P2757题解(P2757 problem solving)

``````#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 500001
#define mod 1000000007
#define bas 37
struct d{
ll v;int l;
}ta[N<<2],tb[N<<2];
int T,n;
ll p[N];
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
d mg(d x,d y){
d z;z.v=(x.v*p[y.l]%mod+y.v)%mod;
z.l=x.l+y.l;return z;
}
void pushup(int p){
ta[p]=mg(ta[lc],ta[rc]);
tb[p]=mg(tb[rc],tb[lc]);
}
void build(int p,int l,int r){
if(l==r){ta[p].l=tb[p].l=1;ta[p].v=tb[p].v=0;return;}
build(lc,l,mid);build(rc,mid+1,r);pushup(p);
}
void c(int p,int l,int r,int pos){
if(l==r){ta[p].v=tb[p].v=1;return;}
if(pos<=mid)c(lc,l,mid,pos);else c(rc,mid+1,r,pos);
pushup(p);
}
d q1(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return ta[p];
if(R<=mid)return q1(lc,l,mid,L,R);
if(L>mid)return q1(rc,mid+1,r,L,R);
return mg(q1(lc,l,mid,L,R),q1(rc,mid+1,r,L,R));
}
d q2(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return tb[p];
if(R<=mid)return q2(lc,l,mid,L,R);
if(L>mid)return q2(rc,mid+1,r,L,R);
return mg(q2(rc,mid+1,r,L,R),q2(lc,l,mid,L,R));
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
p[0]=1;for(int i=1;i<=n;++i)p[i]=p[i-1]*bas%mod;
bool ok=1;
build(1,1,n);
for(int i=1;i<=n;++i){
int x;scanf("%d",&x);c(1,1,n,x);
int l=min(x-1,n-x);
if(l<=0)continue;
if(ok&&q1(1,1,n,x-l,x-1).v!=q2(1,1,n,x+1,x+l).v){
ok=0;puts("Y");
}
}
if(ok)puts("N");
}
return 0;
}
``````
————————

Title portal
Description of the meaning of the question: an arrangement to find whether there is an arithmetic sequence with length \ (\ ge3 \).
If there is a sequence with length \ (& gt; 3 \), there must be a sequence with length \ (3 \). Set it to \ (p_1, p_2, p_3 \)
Obviously \ (p_2-p_1 = p_3-p_2 \), that is, \ (p_1, p_3 \) is symmetrical about \ (p_2 \), and they are on both sides of \ (p_2 \).
Sequence is an arrangement, which is a very important property.
That is, if it does not exist, for any \ (a_i \), \ (a_i + K, a_i-k \) is always on the same side of \ (p_i \).
When traversing to the \ (I \) number, add \ (a_i \) to a sequence.
If there is no sequence that meets the meaning of the question, the sequence is always symmetrical about the current \ (a_i \), that is \ (a_i + K, a_i-k \) either appears on the left or on the right at the same time.
Maintain interval hash value with segment tree.
finished.

``````#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 500001
#define mod 1000000007
#define bas 37
struct d{
ll v;int l;
}ta[N<<2],tb[N<<2];
int T,n;
ll p[N];
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
d mg(d x,d y){
d z;z.v=(x.v*p[y.l]%mod+y.v)%mod;
z.l=x.l+y.l;return z;
}
void pushup(int p){
ta[p]=mg(ta[lc],ta[rc]);
tb[p]=mg(tb[rc],tb[lc]);
}
void build(int p,int l,int r){
if(l==r){ta[p].l=tb[p].l=1;ta[p].v=tb[p].v=0;return;}
build(lc,l,mid);build(rc,mid+1,r);pushup(p);
}
void c(int p,int l,int r,int pos){
if(l==r){ta[p].v=tb[p].v=1;return;}
if(pos<=mid)c(lc,l,mid,pos);else c(rc,mid+1,r,pos);
pushup(p);
}
d q1(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return ta[p];
if(R<=mid)return q1(lc,l,mid,L,R);
if(L>mid)return q1(rc,mid+1,r,L,R);
return mg(q1(lc,l,mid,L,R),q1(rc,mid+1,r,L,R));
}
d q2(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return tb[p];
if(R<=mid)return q2(lc,l,mid,L,R);
if(L>mid)return q2(rc,mid+1,r,L,R);
return mg(q2(rc,mid+1,r,L,R),q2(lc,l,mid,L,R));
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
p[0]=1;for(int i=1;i<=n;++i)p[i]=p[i-1]*bas%mod;
bool ok=1;
build(1,1,n);
for(int i=1;i<=n;++i){
int x;scanf("%d",&x);c(1,1,n,x);
int l=min(x-1,n-x);
if(l<=0)continue;
if(ok&&q1(1,1,n,x-l,x-1).v!=q2(1,1,n,x+1,x+l).v){
ok=0;puts("Y");
}
}
if(ok)puts("N");
}
return 0;
}
``````