BZOJ_2124_等差子序列_线段树+Hash

BZOJ_2124_等差子序列_线段树+Hash

Description

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

Input

输入的第一行包含一个整数T，表示组数。下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。N<=10000，T<=7

Output

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

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

N
Y

其实就是问是否存在一个长度为3的等差数列。

一种暴力：枚举中间数x，然后枚举差d，看x-d和x+d是不是有一个在桶里有一个不在桶里，如果是则x-d,x,x+d构成等差子序列。

然后优化这个暴力，如果把桶看成一个01的字符串，我要找的其实是x左边和右边延伸的一个字符串。

这个字符串如果不回文说明存在等差子序列。

可以用线段树动态维护正串和反串的hash值。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
#define N 10050
#define ls p<<1
#define rs p<<1|1
ll h[N<<2][2],mi[N],base=7233913;
int n,a[N];
void build(int l,int r,int p) {
    if(l==r)  {
        h[p][0]=h[p][1]='0';
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls); build(mid+1,r,rs);
    h[p][0]=h[ls][0]*mi[r-mid]+h[rs][0];
    h[p][1]=h[rs][1]*mi[mid-l+1]+h[ls][1];
}
void update(int l,int r,int x,int p) {
    if(l==r) {
        h[p][0]=h[p][1]='1';
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(l,mid,x,ls);
    else update(mid+1,r,x,rs);
    h[p][0]=h[ls][0]*mi[r-mid]+h[rs][0];
    h[p][1]=h[rs][1]*mi[mid-l+1]+h[ls][1];
}
ll query(int l,int r,int x,int y,int flg,int p) {
    if(x<=l&&y>=r) return h[p][flg];
    int mid=(l+r)>>1;
    if(y<=mid) return query(l,mid,x,y,flg,ls);
    else if(x>mid) return query(mid+1,r,x,y,flg,rs);
    else {
        ll lx=query(l,mid,x,mid,flg,ls),rx=query(mid+1,r,mid+1,y,flg,rs);
        if(!flg) {
            return lx*mi[y-mid]+rx;
        }else {
            return rx*mi[mid-x+1]+lx;
        }
    }
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        int i;
        for(mi[0]=1,i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            mi[i]=mi[i-1]*base;
        }
        memset(h,0,sizeof(h));
        build(1,n,1);
        int flg=0;
        for(i=1;i<=n;i++) {
            if(a[i]!=1&&a[i]!=n) {
                ll lans,rans;
                if(a[i]-1>=n-a[i]) {
                    lans=query(1,n,2*a[i]-n,a[i]-1,0,1);
                    rans=query(1,n,a[i]+1,n,1,1);
                }else {
                    lans=query(1,n,1,a[i]-1,0,1);
                    rans=query(1,n,a[i]+1,2*a[i]-1,1,1);
                }
                if(lans!=rans) {
                    flg=1; break;
                }
            }
            update(1,n,a[i],1);
        }
        puts(flg?"Y":"N");
    }
}