BZOJ 2124: 等差子序列

时间：2023-03-08 16:42:31

Sol

线段树+Hash.

首先暴力 等差子序列至少3项就可以了,就枚举中项,枚举公差就可以了,只需要一个数在中项前出现,另一个数在中项前没出现过就可以了.复杂度 \(O(n^2)\)

然后我想了一个虽然复杂度没变(因为我不会设计这个数据结构...) 但是好像有点用的算法,就是枚举中项,考虑从一个中项转移到另一个中项,那就是 \(\pm \Delta\) 就可以了...如果能够用数据结构维护这个操作,那就灰常好了.变换中项也就是变换折叠的位置吧.

标算呢...就是用线段树维护Hash,一个数字出现过,那就为1,没出现过就为0,维护一个正反序的01序列,如果一个数的 小于它正序01序列 和 大于它的反序01序列 异或值不为0那么就存在满足条件的等差序列.

01串太长了就可以用Hash来维护了...

PS:100000007不是质数...没开Long Long 直接见祖宗.

PS:我常数好大啊QAQ

Code

/**************************************************************

    Problem: 2124

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:2348 ms

    Memory:8720 kb

****************************************************************/

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 100005;

const LL p = 100000007;

#define debug(a) cout<<#a<<"="<<a<<" "

#define mid ((l+r)>>1)

#define lc (o<<1)

#define rc (o<<1|1)

int T,n;

int a[N];

LL h1[N<<2],h2[N<<2],pow[N];

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }

inline void Update(int x,int o,int l,int r){

    if(l==r){ h1[o]=h2[o]=1;return; }

    if(x<=mid) Update(x,lc,l,mid);

    else Update(x,rc,mid+1,r);

    h1[o]=(h1[lc]+h1[rc]*pow[mid-l+1])%p;

    h2[o]=(h2[lc]*pow[r-mid]+h2[rc])%p;

}

inline LL Query1(int L,int R,int o,int l,int r){

    if(L>R) return -1;

//  debug(L),debug(R),debug(l),debug(r)<<endl;

    if(L==l&&r==R) return h1[o];

    if(L<=mid&&R>mid) return (Query1(L,mid,lc,l,mid)+Query1(mid+1,R,rc,mid+1,r)*pow[mid-L+1])%p;

    if(L<=mid) return Query1(L,R,lc,l,mid)%p;

    else return Query1(L,R,rc,mid+1,r)%p;

//  debug(res)<<endl;

//  return res;

}

inline LL Query2(int L,int R,int o,int l,int r){

    if(L>R) return -1;

    if(L==l&&r==R) return h2[o];

    if(L<=mid&&R>mid) return (Query2(L,mid,lc,l,mid)*pow[R-mid]+Query2(mid+1,R,rc,mid+1,r))%p;

    if(L<=mid) return Query2(L,R,lc,l,mid)%p;

    else return Query2(L,R,rc,mid+1,r)%p;

//  return res;

}

int main(){

    pow[0]=1;for(int i=1;i<N;i++) pow[i]=(pow[i-1]<<1)%p;

    for(T=in();T--;){

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

        int f=0;

        memset(h1,0,sizeof(h1)),memset(h2,0,sizeof(h2));

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

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

            int u=Query2(a[i]-l,a[i]-1,1,1,n);

            int v=Query1(a[i]+1,a[i]+l,1,1,n);

//          cout<<"*********"<<endl;

//          debug(i)<<endl;

//          debug(l),debug(a[i])<<endl;

//          debug(a[i]-l),debug(a[i]-1)<<endl;

//          debug(a[i]+1),debug(a[i]+l)<<endl;

//          cout<<u<<" "<<v<<endl;

            if(u!=v){ f=1;break; }

            Update(a[i],1,1,n);

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

    }

    return 0;

}

　　

相关文章