bzoj2124: 等差子序列线段树+hash

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2124

思路

找大于3的等差数列其实就是找等于三的等差数列
三个等差数列的话，枚举中间点。
如果有对称点(a[i]-j,a[i]+j)在两侧，那么就能构成一个等差数列
我们可以转化为权值数组中a[i]能到达的最远对称串是否是回文串。
马拉车？？不不。hash是万能的。
这里hash可以用线段树维护

错误

我太菜了，代码写的特恶心

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define ull unsigned long long
using namespace std;
const int N=2e5+7;
const int mod=233;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,pos[N],a[N];
ull my_pow[N];
namespace BIT {
    int lowbit(int x) {return x&-x;}
    ull sum[2][N];
    void add(int id) {
        for(int i=id;i<=n;i+=lowbit(i))
            sum[0][i]+=my_pow[id];
        for(int i=n-id+1;i<=n;i+=lowbit(i))
            sum[1][i]+=my_pow[n-id+1];
    }
    ull QQ0(int x,int y) {
        ull ans=0;
        if(x-1) for(int i=x-1;i>=1;i-=lowbit(i)) ans-=sum[0][i];
        for(int i=y;i>=1;i-=lowbit(i)) ans+=sum[0][i];
        return ans;
    }
    ull QQ1(int x,int y) {
        ull ans=0;
        if(x-1) for(int i=x-1;i>=1;i-=lowbit(i)) ans-=sum[1][i];
        for(int i=y;i>=1;i-=lowbit(i)) ans+=sum[1][i];
        return ans; 
    }
}
// bool dsr[N];
int main() {
    // freopen("1.in","r",stdin);
    int T=read();
    my_pow[1]=1;
    for(int i=2;i<=10000;++i) my_pow[i]=my_pow[i-1]*233;
    while(T--) {
        memset(BIT::sum,0,sizeof(BIT::sum));
        n=read();
        for(int i=1;i<=n;++i) a[i]=read();
        bool flag=false;
        for(int i=1;i<=n;++i) {
            int len=min(a[i]-1,n-a[i]);
            // for(int k=1;k<=n;++k) cout<<dsr[k]<<" <";puts("");
            // cout<<a[i]-len<<" "<<a[i]<<" vs "<<a[i]<<" "<<a[i]+len<<"  <len\n";
            int x=a[i]-len,y=a[i];
            int y_=n-a[i]+1,x_=n-(a[i]+len)+1;
            int tmp0=1,tmp1=1;
            // cout<<x<<" "<<y<<" vs "<<x_<<" "<<y_<<"\n";
            if(x>x_) tmp1+=x-x_;
            else tmp0+=x_-x;
            // cout<<tmp0<<" "<<tmp1<<"\n";
            if(BIT::QQ0(x,y)*my_pow[tmp0]!=BIT::QQ1(x_,y_)*my_pow[tmp1]) {
                puts("Y");
                // cout<<i<<" "<<a[i]<<"\n";
                flag=true;
                break;
            }
            BIT::add(a[i]);
            // dsr[a[i]]=1;
        }
        if(!flag) puts("N");
    }
    return 0;
}