BZOJ2124 等差子序列（树状数组+哈希）

时间：2024-01-07 10:47:44

　　容易想到一种暴力的做法：枚举中间的位置，设该位置权值为x，如果其两边存在权值关于x对称即合法。

　　问题是如何快速寻找这个东西是否存在。考虑仅将该位置左边出现的权值标1。那么若在值域上若关于x对称的两权值标号不同，说明他们的位置分别在两侧，也就说明存在等差子序列。那么只需要判断整体是否相同，哈希即可。

　　哈希值需要动态维护，容易想到树状数组/线段树。从左到右依次处理并维护两个树状数组记录正反哈希值。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 10010

#define ul unsigned long long

int T,n,a[N];

ul tree[N],tree2[N],p[N];

void add(int k){ul x=p[k-];while (k<=n) tree[k]+=x,k+=k&-k;}

void add2(int k){ul x=p[n-k];while (k) tree2[k]+=x,k-=k&-k;}

ul query(int k){ul s=;while (k) s+=tree[k],k-=k&-k;return s;}

ul query2(int k){ul s=;while (k<=n) s+=tree2[k],k+=k&-k;return s;}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2124.in","r",stdin);

    freopen("bzoj2124.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();

    while (T--)

    {

        n=read();

        for (int i=;i<=n;i++) a[i]=read();

        p[]=;for (int i=;i<=n;i++) p[i]=p[i-]*;

        memset(tree,,sizeof(tree));

        memset(tree2,,sizeof(tree2));

        bool flag=;

        for (int i=;i<=n;i++)

        {

            if (a[i]-<n-a[i])

            {

                if (query(a[i]-)*p[n-(a[i]<<)+]!=query2(a[i]+)-query2(a[i]<<)) {flag=;break;}

            }

            else

            {

                if (query2(a[i]+)*p[a[i]-(n-a[i])-]!=query(a[i]-)-query(a[i]-(n-a[i])-)) {flag=;break;}

            }

            add(a[i]);add2(a[i]);

        }

        if (flag) printf("Y\n");else printf("N\n");

    }

    return ;

}

相关文章