bzoj 2124 等差子序列 (线段树维护hash）

2023-01-08 09:00:49

2124: 等差子序列

Time Limit: 3 Sec Memory Limit: 259 MB
Submit: 1922 Solved: 714
[Submit][Status][Discuss]

Description

给一个1到N的排列{Ai}，询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3)，

使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

Input

输入的第一行包含一个整数T，表示组数。

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

N<=10000，T<=7

Output

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

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

N
Y

思路：

线段树神仙操作。。完全想不到怎么用线段树写，看了别人题解看了一天才看懂这操作。。

题目要求存在个数不小于3的等差序列就行了，那么我们只要找到三个数可以组成等差序列就可以了。

我们先从1-n逐步插入，用01表示插入的状态吗如果插入了就标为1，然后只要找出当前值左右两边是否存在

距离相等但状态不同的点，如果有的话那么就存在这么一种等差序列，因为状态不同只有一种情况：一个之前

就已经插入了，一个还没插入，但另一个迟早会插入，所以我们不用管，只要找到这个就可以确定他是等差序列了。

用线段树维护一下hash就行了。

线段树维护的操作比较麻烦，主要就是将这个由01组成的序列由二进制转成10进制来保存，每一步都取下模，如果这

两个数的十进制不同，那他们的二进制肯定也不同。这样就可以判断出答案了。

实现代码;

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define lson l,m,rt<<1

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

#define mid ll m = (l + r) >> 1

const ll M = 1e5+;

const ll md = 1e9+;

ll suml[M<<],sumr[M<<],a[M],pw[M];

void pushup(ll l,ll r,ll rt){

    ll len = r - l + ;

    ll m = len / ;

    suml[rt] = (suml[rt<<]*pw[m]+suml[rt<<|])%md;

    sumr[rt] = (sumr[rt<<|]*pw[len-m]+sumr[rt<<])%md;

    return ;

}

void update(ll p,ll l,ll r,ll rt){

    if(l == r){

        suml[rt] = sumr[rt] = ;

        return ;

    }

    mid;

    if(p <= m) update(p,lson);

    else update(p,rson);

    pushup(l,r,rt);

}

ll queryl(ll L,ll R,ll l,ll r,ll rt){

    if(L > R) return ;

    if(L == l&&R == r) return suml[rt];

    mid;

    if(L > m) return queryl(L,R,rson);

    else if(R <= m) return queryl(L,R,lson);

    else return (queryl(L,m,lson)*pw[R-m]+queryl(m+,R,rson))%md;

}

ll queryr(ll L,ll R,ll l,ll r,ll rt){

    if(L > R) return ;

    if(L == l&&R == r) return sumr[rt];

    mid;

    if(L > m) return queryr(L,R,rson);

    else if(R <= m) return queryr(L,R,lson);

    else  return (queryr(L,m,lson)+queryr(m+,R,rson)*pw[m-L+])%md;

}

int main()

{

    ll t,n;

    ios::sync_with_stdio();

    cin.tie(); cout.tie();

    cin>>t;

    pw[] = ;

    for(ll i = ;i <= ;i++)

        pw[i] = (pw[i-]*)%md;

    while(t--){

        cin>>n;

        memset(suml,,sizeof(suml));

        memset(sumr,,sizeof(sumr));

        memset(a,,sizeof(a));

        ll flag = ;

        for(ll i = ;i <= n;i ++) cin>>a[i];

        for(ll i = ;i <= n;i ++){

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

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

            ll t2 = queryr(a[i]+,a[i]+len,,n,);

            if(t1!=t2){

                flag = ;break;

            }

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

        }

        if(!flag) cout<<"Y"<<endl;

        else cout<<"N"<<endl;

    }

}

码农公寓