P2757 题解

· · 题解

线段树+哈希好题。qwaszx 学长讲字符串哈希的时候用了这个题，于是拿来练手。

先考虑一件事情，题目问存不存在一个长度不小于 3 的等差子序列，实际上我们只需要计算是否存在一个长度等于 3 的等差子序列即可，正确性显然。问题从而得到大大简化。

每次考虑三个数，那么中项就十分特殊了，因为和另外两项的差的绝对值相等。这时候还有一条重要性质：给出的序列是 1 到 n 的排列。所以对于位置 i，如果一个数（非 a_i）不在它左边，那么就一定在它的右边（废话）。这时候我们得到一个很好的做法，我们从左到右扫一遍序列，枚举中项，对于当前枚举到的中项下标 i，如果存在一个 k，使得 a_i-k 和 a_i+k 这两个数一个已经出现过，一个还没出现过（“出现过”指已经扫过，也就是说这个数在 i 左边），我们就能判定答案为存在。

接下来优化这一过程。我们假设建立了一个数组，初始全为 0，扫过一个数 a_i 后就把数组下标 a_i 的位置标为 1，如果我们以 a_i 为中心“对折”这个数组，若对于所有重合的位置，重合的两个数相等，则说明对于所有合法的 k，a_i-k 和 a_i+k 必然在 a_i 同侧（也就是对于当前的中心答案不存在）。其实是一个判断回文的过程。考虑用字符串哈希做这件事，把重合部分提取出来，如果中心位置左半边序列的哈希值等于右半边序列的反序列的哈希值，那么就回文，我们用线段树维护区间哈希和反序列哈希，这样对于一个 a_i 就能快速查询了，扫完 a_i 后也能快速修改。区间合并就是字符串哈希的基本操作了，不必多说。

upd：线段树上一个区间的“反序列哈希”指的是把原序列中这一段数取出，翻转后求得的哈希值。这里的哈希采用字符串哈希的维护方式。据某些同学的私信，这里似乎有点表意不清。

更多细节看代码吧，有不理解的地方或是有写错的地方欢迎私信。

#include<bits/stdc++.h>
using namespace std;
const int N=500010,mod=1e9+7,P=13331;
typedef long long ll;
int read(){
    int ss=0,ww=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            ww=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        ss=ss*10+ch-'0';
        ch=getchar();
    }
    return ss*ww;
}
int T,n;
ll p[N];
ll hash1[N*4],hash2[N*4];
int a[N];
int min(int x,int y){
    return x<y?x:y;
}
void upd(int root,int l,int r){
    int mid=(l+r)/2;
    hash1[root]=(hash1[root*2+1]+hash1[root*2]*p[r-mid]%mod)%mod;
    hash2[root]=(hash2[root*2]+hash2[root*2+1]*p[mid-l+1]%mod)%mod;
}
void add(int root,int l,int r,int x){
    if(l==r){
        hash1[root]=hash2[root]=1;
        return;
    }
    int mid=(l+r)/2;
    if(mid>=x)
        add(root*2,l,mid,x);
    else
        add(root*2+1,mid+1,r,x);
    upd(root,l,r);
}
ll res1,res2,nw;
void ask1(int root,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        res1=(res1+hash1[root]*p[nw]%mod)%mod;
        nw+=(r-l+1);
        return;
    }
    int mid=(l+r)/2;
    if(mid+1<=y)
        ask1(root*2+1,mid+1,r,x,y);
    if(mid>=x)
        ask1(root*2,l,mid,x,y); 
}
void ask2(int root,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        res2=(res2+hash2[root]*p[nw]%mod)%mod;
        nw+=(r-l+1);
        return;
    }
    int mid=(l+r)/2;
    if(mid>=x)
        ask2(root*2,l,mid,x,y);
    if(mid+1<=y)
        ask2(root*2+1,mid+1,r,x,y);
}
int main(){
    T=read();
    p[0]=1;
    for(int i=1;i<=5e5;i++)
        p[i]=p[i-1]*P%mod;
    while(T--){
        memset(hash1,0,sizeof(hash1));//多测记得清空
        memset(hash2,0,sizeof(hash2));
        n=read();
        for(int i=1;i<=n;i++)
            a[i]=read();
        bool flag=0;
        for(int i=1;i<=n;i++){
            add(1,1,n,a[i]);
            int len=min(a[i],n-a[i]+1);
            res1=res2=nw=0;
            ask1(1,1,n,a[i]-len+1,a[i]+len-1);
            nw=0;
            ask2(1,1,n,a[i]-len+1,a[i]+len-1);
            if(res1!=res2){
                flag=1;
                break;
            }
        }
        if(flag)
            cout<<"Y\n";
        else
            cout<<"N\n";
    }
    return 0;
}