BZOJ 2124: 等差子序列线段树维护hash

2023-01-08 09:00:55

2124: 等差子序列

Description

给一个1到N的排列{Ai}，询问是否存在1<=p1=3），使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

Input

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

Output

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

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

N
Y

HINT

对于100%的数据，N<=10000，T<=7

题解：

　　题目说了是1到n的排列

　　我们将1到n逐渐插入线段树的中，且用01表示出现状态

　　假设当前x，我们只要找出与x相距距离相等的存在状态不同的就说明存在答案

　　这就是线段树维护hash

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 10010

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define p 3

#define mod 1000000007

using namespace std;

typedef long long ll;

ll hash[N<<],hash2[N<<];

ll pow[N];

int a[N];

int n,t;

void pushup(int rt,int m)

{

    ll tmp=m>>;

    hash[rt]=(hash[rt<<]*pow[tmp]+hash[rt<<|])%mod;

    hash2[rt]=(hash2[rt<<|]*pow[m-tmp]+hash2[rt<<])%mod;

}

void update(int pt,int l,int r,int rt)

{

    if(l==r)

    {

        hash[rt]=hash2[rt]=;

        return;

    }

    int mid=(l+r)>>;

    if(pt<=mid)update(pt,lson);

    else update(pt,rson);

    pushup(rt,r-l+);

}

ll query(int L,int R,int l,int r,int rt)

{

    if(L>R)return ;

    int ans=;

    if(L==l&&r==R)

    {

        return hash[rt];

    }

    int mid=(l+r)>>;

    if(R<=mid)return query(L,R,lson);

    else if(L>mid)return query(L,R,rson);

    else return (query(L,mid,lson)*pow[R-mid]+query(mid+,R,rson))%mod;

}

ll query2(int L,int R,int l,int r,int rt)

{

    if(L>R)return ;

    if(L==l&&r==R)

    {

        return hash2[rt];

    }

    int mid=(l+r)>>;

    if(R<=mid)return query2(L,R,lson);

    else if(L>mid)return query2(L,R,rson);

    else return (query2(L,mid,lson)+query2(mid+,R,rson)*pow[mid-L+])%mod;

}

int main()

{

    scanf("%d",&t);

    pow[]=p;

    for(int i=;i<=;i++)pow[i]=(pow[i-]*p)%mod;

    while(t--)

    {

        memset(hash,,sizeof(hash));

        memset(hash2,,sizeof(hash2));

        scanf("%d",&n);

        for(int i=;i<=n;i++)scanf("%d",&a[i]);

        int flag=;

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

        {

            ll len=min(a[i]-,n-a[i]);

            ll tmp1=query(a[i]-len,a[i]-,,n,);

            ll tmp2=query2(a[i]+,a[i]+len,,n,);

            if(tmp1!=tmp2)

            {

                flag=;break;

            }

            update(a[i],,n,);

        }

        if(flag)printf("Y\n");

        else printf("N\n");

    }

}

码农公寓