P2757 [国家集训队] 等差子序列 与 CF452F Permutation

题意：

给定一个长度为 \(n\) 的排列 \(a\)，判断其中是否有长度 \(\ge 3\) 的等差数列。

\(1 \le n \le 5 \times 10^5\)。

思路：

首先若存在长度 \(>3\) 的等差数列，则其中的一部分肯定由长度为 \(3\) 的等差数列组成；即我们现在只需要判断是否存在长度为 \(3\) 的等差数列即可。

考虑枚举中间的数 \(a_i\)，则问题转化为 \(a_i-k\) 与 \(a_i + k\) 是否同时出现在 \(i\) 的两侧。

注意到 \(a\) 是一个排列，则是没有重复数字的。

那么我们可以记作若 \(i\) 左边的 \(a_j\) 出现过，则将标记数组中第 \(a_j\) 个位置为 \(0\)。

若不可以构成等差数列的话，当 \(a_i-k\) 被标记了，则 \(a_i+k\) 也必须被标记（不然就会出现在 \(i\) 右侧，形成等差数列），那么标记数组就是以 \(i\) 为回文中心回文的。

现在我们需要支持单点赋值为 \(1\)，判断一个区间是否是回文的；可以直接线段树维护翻转后和未翻转时的哈希值，判断是否相等即为回文。

考虑提前预处理出 \(base\) 的次幂，则单组数据时间复杂度为 \(O(N \log N)\)。

完整代码：

P2757 [国家集训队] 等差子序列

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=5e5+10;
const ull base=127;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
mt19937_64 R(time(0));
int T,n,x,l,r;
bool ans;
ull h[2],f[N];
class St{
public:
    ull x,y;
    int len;
    inline void tidy(){
        x=y=len=0;
    }
    inline friend St operator+(const St a,const St b){
        St ans;
        ans.x=a.x*f[b.len]+b.x;
        ans.y=b.y*f[a.len]+a.y;
        ans.len=a.len+b.len;
        return ans;
    }
}F;
class Tree{
public:
    struct Node{
        int l,r;
        St sum;
    }X[N<<2];
    inline void pushup(int k){
        X[k].sum=X[k<<1].sum+X[k<<1|1].sum;
    }
    inline void build(int k,int l,int r){
        X[k].sum.tidy();
        X[k].l=l,X[k].r=r;
        X[k].sum.len=r-l+1;
        if(l==r){
            X[k].sum.x=X[k].sum.y=h[0];
            return ;
        }
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        pushup(k);
    }
    inline void add(int k,int i){
        if(X[k].l==i&&i==X[k].r){
            X[k].sum.x=X[k].sum.y=h[1];
            return ;
        }
        int mid=(X[k].l+X[k].r)>>1;
        if(i<=mid)
          add(k<<1,i);
        else
          add(k<<1|1,i);
        pushup(k);
    }
    inline St query(int k,int l,int r){
        if(X[k].l==l&&r==X[k].r)
          return X[k].sum;
        int mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          return query(k<<1,l,r);
        else if(l>mid)
          return query(k<<1|1,l,r);
        else
          return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
    }
}Tr;
inline void init(){
    h[0]=R(),h[1]=R();
    f[0]=1;
    For(i,1,N-1)
      f[i]=f[i-1]*base;
}
inline void solve(){
    ans=0;
    n=read();
    Tr.build(1,1,n);
    For(i,1,n){
        x=read();
        Tr.add(1,x);
        if(x<=n-x+1){
            l=1,r=(x<<1ll)-1;
            F=Tr.query(1,l,r);
        }
        else{
            l=(x<<1ll)-n,r=n;
            F=Tr.query(1,l,r);
        }
        if(F.x!=F.y)
          ans=1;
    }
    if(ans)
      puts("Y");
    else
      puts("N");
}
bool End;
int main(){
    init();
    T=read();
    while(T--)
      solve();
	//cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

CF452F Permutation

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=3e5+10;
const ull base=127;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
mt19937_64 R(time(0));
int T,n,x,l,r;
bool ans;
ull h[2],f[N];
class St{
public:
    ull x,y;
    int len;
    inline void tidy(){
        x=y=len=0;
    }
    inline friend St operator+(const St a,const St b){
        St ans;
        ans.x=a.x*f[b.len]+b.x;
        ans.y=b.y*f[a.len]+a.y;
        ans.len=a.len+b.len;
        return ans;
    }
}F;
class Tree{
public:
    struct Node{
        int l,r;
        St sum;
    }X[N<<2];
    inline void pushup(int k){
        X[k].sum=X[k<<1].sum+X[k<<1|1].sum;
    }
    inline void build(int k,int l,int r){
        X[k].sum.tidy();
        X[k].l=l,X[k].r=r;
        X[k].sum.len=r-l+1;
        if(l==r){
            X[k].sum.x=X[k].sum.y=h[0];
            return ;
        }
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        pushup(k);
    }
    inline void add(int k,int i){
        if(X[k].l==i&&i==X[k].r){
            X[k].sum.x=X[k].sum.y=h[1];
            return ;
        }
        int mid=(X[k].l+X[k].r)>>1;
        if(i<=mid)
          add(k<<1,i);
        else
          add(k<<1|1,i);
        pushup(k);
    }
    inline St query(int k,int l,int r){
        if(X[k].l==l&&r==X[k].r)
          return X[k].sum;
        int mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          return query(k<<1,l,r);
        else if(l>mid)
          return query(k<<1|1,l,r);
        else
          return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
    }
}Tr;
inline void init(){
    h[0]=R(),h[1]=R();
    f[0]=1;
    For(i,1,N-1)
      f[i]=f[i-1]*base;
}
inline void solve(){
    ans=0;
    n=read();
    Tr.build(1,1,n);
    For(i,1,n){
        x=read();
        Tr.add(1,x);
        if(x<=n-x+1){
            l=1,r=(x<<1ll)-1;
            F=Tr.query(1,l,r);
        }
        else{
            l=(x<<1ll)-n,r=n;
            F=Tr.query(1,l,r);
        }
        if(F.x!=F.y)
          ans=1;
    }
    if(ans)
      puts("YES");
    else
      puts("NO");
}
bool End;
int main(){
    init();
    T=1;
    while(T--)
      solve();
	//cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}