[线段树][字符串hash][假算法] bzoj2124 等差子序列

这个题在codeforces上有几乎一模一样的：http://codeforces.com/contest/452/problem/F

cf上的题说的是考虑长度为3的等差序列，bzoj这个说的是等差序列其实也是找长度为3的，因为显然能找到长度大于3的肯定也能找到等于3的。cf那个题有个假算法可以过掉所有数据，就是暴力枚举中点，然后往左右延伸的时候不超过5个就行。。之所以能这么做是因为这个题目要想构造出来NO的数据确实很难。。不过假算法依然是假算法。。

正解是每次出现过一个点之后把他在线段树上值变为1，然后求一个中点左右两边有没有相同的时候需要判断左右两边是不是完全一样，如果不是一定有解。这里判断的方法是hash。。。分别在两个线段树上维护正反两个方向的左右01字符串的hash值就可以了。
wa点：首先是对于这种多项式形式的线段树合并的时候要分三种情况，完全在左/完全在右/跨越中点；其次是跨越中间点的情况下一定要考虑清楚应该累加的数值是多少。。在这里是pw[mid-max(ql,l)]；最后是当ai==1和ai==n时候的特判，这时候不能query，但是必须update，我一开始写了单独处理1，然后i从2开始循环，后来忽然意识到a1并不一定等于1啊。。。傻了。。。

#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;
const int maxn=1e4+5;
const int mod=1e9+9;

int n;
LL pw[maxn],bas=3;
LL hash1[maxn<<2],hash2[maxn<<2];

void maintain1(int o,int l,int r)
{
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    hash1[o]=(hash1[o<<1]+pw[mid-l+1]*hash1[o<<1|1])%mod;
}

void maintain2(int o,int l,int r)
{
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    hash2[o]=(hash2[o<<1]+pw[mid-l+1]*hash2[o<<1|1])%mod;
}

int pos;
void update1(int o,int l,int r)
{
    if(l==r)
    {
        hash1[o]=1;
        return ;
    }
    else
    {
        int mid=(l+r)>>1;
        if(pos<=mid)
            update1(o<<1,l,mid);
        else
            update1(o<<1|1,mid+1,r);
    }
    maintain1(o,l,r);
}

void update2(int o,int l,int r)
{
    if(l==r)
    {
        hash2[o]=1;
        return ;
    }
    else if(l>1;
        if(pos<=mid)
            update2(o<<1,l,mid);
        else
            update2(o<<1|1,mid+1,r);
    }
    maintain2(o,l,r);
}

int ql,qr;
LL query1(int o,int l,int r)
{
    if(ql<=l&&r<=qr)
        return hash1[o]%mod;
    else
    {
        int mid=(l+r)>>1;
        LL ans=0;
        if(qr<=mid)
            ans=query1(o<<1,l,mid);//error0!
        else if(midmod)
            ans%=mod;
        return ans;
    }
}

LL query2(int o,int l,int r)
{
    if(ql<=l&&r<=qr)
        return hash2[o]%mod;
    else
    {
        int mid=(l+r)>>1;
        LL ans=0;
        if(qr<=mid)
            ans=query2(o<<1,l,mid);
        else if(midmod)
            ans%=mod;
        return ans;
    }
}
int ori[maxn];
int main()
{
    pw[0]=1;
    for (int i=1; i<=10000; i++)
        pw[i]=(pw[i-1]*bas)%mod;

    int T;
    scanf("%d",&T);
    int tmp,t1,t2;
    while(T--)
    {
        bool ok=0;
        memset(hash1,0,sizeof(hash1));
        memset(hash2,0,sizeof(hash2));
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&ori[i]);
        }
        if(n<3)
        {
            puts("N");
            continue;
        }
        //pos=1;update1(1,1,n);
        //if(pos<=0||pos>n)while(1);
        //pos=n;update2(1,1,n);//stupid error2!
        //if(pos<=0||pos>n)while(1);
        //cout<<"fuck?";
        for(int i=1; i<=n; i++)
        {
            tmp=ori[i];
            if(tmp!=n&&tmp!=1)//stupid error2!
            {
                ql=max(1,2*tmp-n),qr=tmp-1;
                t1=query1(1,1,n);
                ql=max(1,n-2*(tmp-1)),qr=n-tmp;
                t2=query2(1,1,n);
                if(t1!=t2)
                {
                    ok=1;
                    break;
                }
            }
            pos=tmp;
            update1(1,1,n);
            pos=n-tmp+1;
            update2(1,1,n);
        }
        if(ok)
            puts("Y");
        else
            puts("N");
    }
}