nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

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;
    }
}