等差子序列（sequence）

题目描述

给一个1到N的排列{Ai}，询问是否存在1<= p1 < p2 < p3 < p4 < p5 < … < pLen <=N（Len>=3），使得 Ap1, Ap2, Ap3, …ApLen是一个等差序列。

输入

输入的第一行包含一个整数T，表示组数。

下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。

输出

对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。

样例输入

样例输出

N

Y

提示

【数据说明】

对于5%的数据，N<=100

对于30%的数据，N<=1000

对于100%的数据，N<=10000，T<=7

solution

首先只要有3个数满足，那么就行了

我们枚举中间的数ai

我们可以记录每一个数值是否出现过：记为p

如果p是一个以a[i]为对称轴的回文串，那么就是不合法的。

也就是a[i-x],a[i+x]出现状况相同

这个可以用哈希实现

现在我们要维护哈希值，支持修改，区间查询

树状数组啦

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 10005

#define ll unsigned long long

#define p 1000000007

using namespace std;

int T,n,a[maxn];

ll ha[maxn],hb[maxn],po[maxn];

void cle(){

    for(int i=1;i<=n;i++)ha[i]=hb[i]=0;

}

void add_a(int i,ll v){

    for(;i<=n;i+=i&-i)ha[i]+=v;

}

void add_b(int i,ll v){

    for(;i<=n;i+=i&-i)hb[i]+=v;

}

ll ask_a(int i){

    ll sum=0;for(;i;i-=i&-i)sum+=ha[i];

    return sum;

}

ll ask_b(int i){

    ll sum=0;for(;i;i-=i&-i)sum+=hb[i];

    return sum;

}

int main()

{

    cin>>T;

    while(T--){

        cle();

        cin>>n;

        for(int i=1;i<=n;i++)scanf("%d",&a[i]);

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

        bool f=0;

        //for(int i=1;i<=n;i++)add_b(a[i],po[n-a[i]+1]);

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

            add_a(a[i],po[a[i]]);add_b(a[i],po[n-a[i]+1]);

            int M=min(a[i],n-a[i]+1);

            //cout<<"i "<<i<<' '<<a[i]<<' '<<M<<endl;

            ll t1=ask_a(a[i])-ask_a(a[i]-M);

            ll t2=ask_b(a[i]+M-1)-ask_b(a[i]-1);

            if(a[i]<n-a[i]+1)t1=t1*po[n-a[i]+1-a[i]];

            else t2=t2*po[a[i]-(n-a[i]+1)];

            //cout<<t1<<' '<<t2<<endl;

            if(t1!=t2){f=1;break;}

        }

        if(f)puts("Y");else puts("N");

    }

    return 0;

}