bzoj2124

题目大意 :
在一个很长(1e5)的串里面找一个长度为三的等比子序列

考虑枚举中间值，想办法在lg的复杂度下解决单次枚举，初次考虑为依次比较中间值+d和中间值-d是否出现在这个值的前面和后面这里可以通过映射On完成，但是复杂度仍然达不到要求，然后我们考虑到这是一个排列，也就是说那些数字出现且仅出现一次，那我们用一个01数列来维护某个值是否出现在枚举值的前面和后面，这里假设出现在前面为0，后面为1，那什么时候最终答案是yes呢，当且仅当关于某个中间值+d和这个中间值-d在01数列中恰好一个为0一个为1，也就是说不相同，这里还是很复杂，我们考虑把01数列当作一个大数，那答案是yes就意味着这个大数关于中间值没有局部回文，好！现在我们暂停深入分析，总结一下，首先我们在枚举中间值构建01数列，然后我们在01数列中寻找关于中心值的局部回文是否不存在。再进一步分析：枚举中间值的过程中，01数列在做单点修改查询局部回文是否不成立的过程可以直接用字符串hash解决，题目到此已经解决。解法：线段树维护01数列正反hash值，如何正反？构造一个反向01数列，用俩线段树就行了。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define ls (u<<1)
#define rs (u<<1|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
struct segment_tree{
    const static ll maxn=2.1e4;
    const static ll MOD=1e9+7;
    static ll pow_2[maxn];
    ll n;
    ll tree[maxn<<2];

    static void pow_ini(){
        pow_2[0]=1;
        for(int i=1;i<maxn;i++){
            pow_2[i]=pow_2[i-1]*2;
            if(pow_2[i]>MOD)pow_2[i]-=MOD;
        }
    }


    void pushup(ll l ,ll r,ll u){
        tree[u]=(tree[ls]*pow_2[r-((l+r)>>1)]+tree[rs])%MOD;
    }
    void build(ll nn){
        n=nn;
        build(1,n,1);
    }


    void build(ll l,ll r,ll u){
        if(l==r){
            tree[u]=0;
            return ;
        }

        build(l,ml,ls);
        build(mr,r,rs);
        pushup(l,r,u);
    }
    void update(ll q,ll d){
        update(q,d,1,1,n);
    }
    void update(ll q,ll d,ll u,ll l,ll r){
        if(q<=l&&r<=q){
            tree[u]=(tree[u]+d*pow_2[r-q])%MOD;
            return ;
        }
        if(q<=ml)update(q,d,ls,l,ml);
        if(q>=mr)update(q,d,rs,mr,r);
        pushup(l,r,u);
    }
    ll query(ll ql,ll qr){
        return query(ql,qr,1,1,n)%MOD;
    }
    ll query(ll ql,ll qr,ll u,ll l,ll r){
        if(ql<=l&&r<=qr)return tree[u]*pow_2[qr-r]%MOD;
        ll ret=0;
        if(ql<=ml)ret=ret+query(ql,qr,ls,l,ml);
        if(qr>=mr)ret=ret+query(ql,qr,rs,mr,r);
        return ret;
    }
}t1,t2;

ll segment_tree::pow_2[maxn];

const int maxn=segment_tree::maxn;
int per[maxn];


int main(){

    segment_tree::pow_ini();

    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%d",per+i);

        t1.build(n);
        t2.build(n);

        string ans="N";
        for(int mid=1;mid<n-1;mid++){
            t1.update(per[mid-1],1);
            t2.update(n+1-per[mid-1],1);

            int len=min(per[mid]-1,n-per[mid]);
            if(len==0)continue;

            if(t1.query(per[mid]-len,per[mid]-1)!=t2.query(      n+1-(per[mid]+len)   ,   n+1-(per[mid]+1) )){
                ans="Y";
                break;
            }
        }
        cout<<ans<<endl;
    }
}